Monthly Archives: September 2024

You are browsing the site archives by month.

Fitting any dataset with a function that only has 1 parameter

September 12, 2024 11:27 ,

Laurent Bou´e, Real numbers, data science and chaos: How to fit any dataset with a single parameter, arXiv:1904.12320v1 [cs.LG] 28 Apr 2019.

We show how any dataset of any modality (time-series, images, sound…) can be approximated by a well-
behaved (continuous, differentiable…) scalar function with a single real-valued parameter. Building upon
elementary concepts from chaos theory, we adopt a pedagogical approach demonstrating how to adjust this
parameter in order to achieve arbitrary precision fit to all samples of the data. Targeting an audience of
data scientists with a taste for the curious and unusual, the results presented here expand on previous similar
observations [1] regarding expressiveness power and generalization of machine learning models.

Posted in: Mathematics , Tagged:

Equivalence between Transformers and SVMs

September 12, 2024 11:16 ,

Davoud Ataee Tarzanagh, Yingcong Li, Christos Thrampoulidis, Samet Oymak, Transformers as Support Vector Machines, arXiv:2308.16898 [cs.LG], https://arxiv.org/abs/2308.16898.

Since its inception in “Attention Is All You Need”, transformer architecture has led to revolutionary advancements in NLP. The attention layer within the transformer admits a sequence of input tokens X and makes them interact through pairwise similarities computed as softmax(XQK⊤X⊤), where (K,Q) are the trainable key-query parameters. In this work, we establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem that separates optimal input tokens from non-optimal tokens using linear constraints on the outer-products of token pairs. This formalism allows us to characterize the implicit bias of 1-layer transformers optimized with gradient descent: (1) Optimizing the attention layer with vanishing regularization, parameterized by (K,Q), converges in direction to an SVM solution minimizing the nuclear norm of the combined parameter W=KQ⊤. Instead, directly parameterizing by W minimizes a Frobenius norm objective. We characterize this convergence, highlighting that it can occur toward locally-optimal directions rather than global ones. (2) Complementing this, we prove the local/global directional convergence of gradient descent under suitable geometric conditions. Importantly, we show that over-parameterization catalyzes global convergence by ensuring the feasibility of the SVM problem and by guaranteeing a benign optimization landscape devoid of stationary points. (3) While our theory applies primarily to linear prediction heads, we propose a more general SVM equivalence that predicts the implicit bias with nonlinear heads. Our findings are applicable to arbitrary datasets and their validity is verified via experiments. We also introduce several open problems and research directions. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.

Posted in: Artificial Intelligence , Tagged: , , ,

Interesting survey of floating-point arithmetic in computers

September 12, 2024 11:05 ,

David Goldberg, What Every Computer Scientist Should Know About Floating-Point Arithmetic, March, 1991 issue of Computing Surveys of the ACM, https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html.

Floating-point arithmetic is considered an esoteric subject by many people. This is rather surprising because floating-point is ubiquitous in computer systems. Almost every language has a floating-point datatype; computers from PCs to supercomputers have floating-point accelerators; most compilers will be called upon to compile floating-point algorithms from time to time; and virtually every operating system must respond to floating-point exceptions such as overflow. This paper presents a tutorial on those aspects of floating-point that have a direct impact on designers of computer systems. It begins with background on floating-point representation and rounding error, continues with a discussion of the IEEE floating-point standard, and concludes with numerous examples of how computer builders can better support floating-point.

Posted in: Computer science , Tagged:

Procrustes analysis as a method for finding the best consensus between two sets of signals

September 12, 2024 10:58 ,

B.G.M. Vandeginste, J. Smeyers-Verbeke, Procrustes Analysis, 1998, https://www.sciencedirect.com/topics/computer-science/procrustes-analysis.

Procrustes analysis is a method in computer science that relates two sets of multivariate observations by finding the transformation that best matches the configuration of points in one set to the corresponding points in the other set, while preserving the internal structure of the objects. It involves operations such as mean centering, reflection, rotation, and finding the best match by minimizing the sum of squared distances between the transformed objects and the target configuration.

Posted in: Probability and statistics , Tagged:

Interesting review of denoising methods (applied to vision and ML, but general enough for other applications)

September 12, 2024 10:51 ,

Peyman Milanfar, Mauricio Delbracio, Denoising: A Powerful Building-Block for Imaging, Inverse Problems, and Machine Learning, arXiv:2409.06219 [cs.LG], DOI: 10.48550/arXiv.2409.06219.

Denoising, the process of reducing random fluctuations in a signal to emphasize essential patterns, has been a fundamental problem of interest since the dawn of modern scientific inquiry. Recent denoising techniques, particularly in imaging, have achieved remarkable success, nearing theoretical limits by some measures. Yet, despite tens of thousands of research papers, the wide-ranging applications of denoising beyond noise removal have not been fully recognized. This is partly due to the vast and diverse literature, making a clear overview challenging. This paper aims to address this gap. We present a comprehensive perspective on denoisers, their structure, and desired properties. We emphasize the increasing importance of denoising and showcase its evolution into an essential building block for complex tasks in imaging, inverse problems, and machine learning. Despite its long history, the community continues to uncover unexpected and groundbreaking uses for denoising, further solidifying its place as a cornerstone of scientific and engineering practice.

See also: https://en.wikipedia.org/wiki/Total_variation_denoising

Posted in: Probability and statistics , Tagged:

A novel way of addressing the maximization bias in RL

September 12, 2024 08:34 ,

Martin Waltz, Ostap Okhrin, Addressing maximization bias in reinforcement learning with two-sample testing, Artificial Intelligence, Volume 336, 2024, DOI: 10.1016/j.artint.2024.104204.

Value-based reinforcement-learning algorithms have shown strong results in games, robotics, and other real-world applications. Overestimation bias is a known threat to those algorithms and can sometimes lead to dramatic performance decreases or even complete algorithmic failure. We frame the bias problem statistically and consider it an instance of estimating the maximum expected value (MEV) of a set of random variables. We propose the T-Estimator (TE) based on two-sample testing for the mean, that flexibly interpolates between over- and underestimation by adjusting the significance level of the underlying hypothesis tests. We also introduce a generalization, termed K-Estimator (KE), that obeys the same bias and variance bounds as the TE and relies on a nearly arbitrary kernel function. We introduce modifications of Q-Learning and the Bootstrapped Deep Q-Network (BDQN) using the TE and the KE, and prove convergence in the tabular setting. Furthermore, we propose an adaptive variant of the TE-based BDQN that dynamically adjusts the significance level to minimize the absolute estimation bias. All proposed estimators and algorithms are thoroughly tested and validated on diverse tasks and environments, illustrating the bias control and performance potential of the TE and KE.

Posted in: Reinforcement learning in AI , Tagged:

Safety in RL through “predictive safety filters”

September 12, 2024 08:31 ,

Aksel Vaaler, Svein Jostein Husa, Daniel Menges, Thomas Nakken Larsen, Adil Rasheed, Modular control architecture for safe marine navigation: Reinforcement learning with predictive safety filters, Artificial Intelligence, Volume 336, 2024, DOI: 10.1016/j.artint.2024.104201.

Many autonomous systems are safety-critical, making it essential to have a closed-loop control system that satisfies constraints arising from underlying physical limitations and safety aspects in a robust manner. However, this is often challenging to achieve for real-world systems. For example, autonomous ships at sea have nonlinear and uncertain dynamics and are subject to numerous time-varying environmental disturbances such as waves, currents, and wind. There is increasing interest in using machine learning-based approaches to adapt these systems to more complex scenarios, but there are few standard frameworks that guarantee the safety and stability of such systems. Recently, predictive safety filters (PSF) have emerged as a promising method to ensure constraint satisfaction in learning-based control, bypassing the need for explicit constraint handling in the learning algorithms themselves. The safety filter approach leads to a modular separation of the problem, allowing the use of arbitrary control policies in a task-agnostic way. The filter takes in a potentially unsafe control action from the main controller and solves an optimization problem to compute a minimal perturbation of the proposed action that adheres to both physical and safety constraints. In this work, we combine reinforcement learning (RL) with predictive safety filtering in the context of marine navigation and control. The RL agent is trained on path-following and safety adherence across a wide range of randomly generated environments, while the predictive safety filter continuously monitors the agents’ proposed control actions and modifies them if necessary. The combined PSF/RL scheme is implemented on a simulated model of Cybership II, a miniature replica of a typical supply ship. Safety performance and learning rate are evaluated and compared with those of a standard, non-PSF, RL agent. It is demonstrated that the predictive safety filter is able to keep the vessel safe, while not prohibiting the learning rate and performance of the RL agent.

See also: https://doi.org/10.1016/j.artint.2024.104195

Posted in: Applications of reinforcement learning to robots , Tagged:

It seems that vectors can help in the path toward symbols for ANNs

September 6, 2024 09:30 ,

Steven T. Piantadosi, Dyana C.Y. Muller, Joshua S. Rule, Karthikeya Kaushik, Mark Gorenstein, Elena R. Leib, Emily Sanford, Why concepts are (probably) vectors, Trends in Cognitive Sciences, Volume 28, Issue 9, 2024, Pages 844-856 DOI: 10.1016/j.tics.2024.06.011.

For decades, cognitive scientists have debated what kind of representation might characterize human concepts. Whatever the format of the representation, it must allow for the computation of varied properties, including similarities, features, categories, definitions, and relations. It must also support the development of theories, ad hoc categories, and knowledge of procedures. Here, we discuss why vector-based representations provide a compelling account that can meet all these needs while being plausibly encoded into neural architectures. This view has become especially promising with recent advances in both large language models and vector symbolic architectures. These innovations show how vectors can handle many properties traditionally thought to be out of reach for neural models, including compositionality, definitions, structures, and symbolic computational processes.

Posted in: Psycho-physiological bases of engineering , Tagged: ,

Using physical models to guide Deep RL in robotics

September 6, 2024 09:05 ,

X. Li, W. Shang and S. Cong, Offline Reinforcement Learning of Robotic Control Using Deep Kinematics and Dynamics, IEEE/ASME Transactions on Mechatronics, vol. 29, no. 4, pp. 2428-2439, Aug. 2024 DOI: 10.1109/TMECH.2023.3336316.

With the rapid development of deep learning, model-free reinforcement learning algorithms have achieved remarkable results in many fields. However, their high sample complexity and the potential for causing damage to environments and robots pose severe challenges for their application in real-world environments. Model-based reinforcement learning algorithms are often used to reduce the sample complexity. One limitation of these algorithms is the inevitable modeling errors. While the black-box model can fit complex state transition models, it ignores the existing knowledge of physics and robotics, especially studies of kinematic and dynamic models of the robotic manipulator. Compared with the black-box model, the physics-inspired deep models do not require specific knowledge of each system to obtain interpretable kinematic and dynamic models. In model-based reinforcement learning, these models can simulate the motion and be combined with classical controllers. This is due to their sharing the same form as traditional models, leading to higher precision tracking results. In this work, we utilize physics-inspired deep models to learn the kinematics and dynamics of a robotic manipulator. We propose a model-based offline reinforcement learning algorithm for controller parameter learning, combined with the traditional computed-torque controller. Experiments on trajectory tracking control of the Baxter manipulator, both in joint and operational space, are conducted in simulation and real environments. Experimental results demonstrate that our algorithm can significantly improve tracking accuracy and exhibits strong generalization and robustness.

Posted in: Applications of reinforcement learning to robots , Tagged:

Cognitive evidences of the need of abstraction (==”modularity”) in achieving AI

September 6, 2024 08:52 ,

Schilling, M., Hammer, B., Ohl, F.W. et al. Modularity in Nervous Systems—a Key to Efficient Adaptivity for Deep Reinforcement Learning, Cogn Comput 16, 2358–2373 (2024) DOI: 10.1007/s12559-022-10080-w.

Modularity as observed in biological systems has proven valuable for guiding classical motor theories towards good answers about action selection and execution. New challenges arise when we turn to learning: Trying to scale current computational models, such as deep reinforcement learning (DRL), to action spaces, input dimensions, and time horizons seen in biological systems still faces severe obstacles unless vast amounts of training data are available. This leads to the question: does biological modularity also hold an important key for better answers to obtain efficient adaptivity for deep reinforcement learning? We review biological experimental work on modularity in biological motor control and link this with current examples of (deep) RL approaches. Analyzing outcomes of simulation studies, we show that these approaches benefit from forms of modularization as found in biological systems. We identify three different strands of modularity exhibited in biological control systems. Two of them—modularity in state (i) and in action (ii) spaces—appear as a consequence of local interconnectivity (as in reflexes) and are often modulated by higher levels in a control hierarchy. A third strand arises from chunking of action elements along a (iii) temporal dimension. Usually interacting in an overarching spatio-temporal hierarchy of the overall system, the three strands offer major “factors” decomposing the entire modularity structure. We conclude that modularity with its above strands can provide an effective prior for DRL approaches to speed up learning considerably and making learned controllers more robust and adaptive.

Posted in: Psycho-physiological bases of engineering , Tagged: