Braverman readings in machine learning : key ideas from inception to current state : International Conference Commemorating the 40th Anniversary of Emmanuil Braverman's Decease, Boston, MA, USA, April 28-30, 2017, invited talks

This state-of-the-art survey is dedicated to the memory of Emmanuil Markovich Braverman (1931-1977), a pioneer in developing machine learning theory. The 12 revised full papers and 4 short papers included in this volume were presented at the conference "Braverman Readings in Machine Learning: Key Ideas from Inception to Current State" held in Boston, MA, USA, in April 2017, commemorating the 40th anniversary of Emmanuil Braverman's decease. The papers present an overview of some of Braverman's ideas and approaches. The collection is divided in three parts. The first part bridges the past and the present and covers the concept of kernel function and its application to signal and image analysis as well as clustering. The second part presents a set of extensions of Braverman's work to issues of current interest both in theory and applications of machine learning. The third part includes short essays by a friend, a student, and a colleague. Preface......Page 6 Reference......Page 7 Organization......Page 8 Acknowledgments......Page 9 Contents......Page 10 Bridging Past and Future......Page 12 1 Introduction......Page 13 2.1 Potential Functions and Their Properties......Page 15 2.3 Similarity or Dissimilarity-Based Potential Functions......Page 16 2.4 Alignment-Based Potential Functions (Convolution Kernels)......Page 18 2.5 Potential Functions on Elements of Biological Sequences......Page 22 2.6 The Generalized Probabilistic Approach to Constructing Potential Functions for Sequences......Page 23 3 Kernel-Based SVM for Two-Class Pattern Recognition......Page 29 4.1 Short Review of Multi-kernel Learning......Page 30 4.2 Supervised Selective Support Kernel SVM (SSKSVM)......Page 31 5.1 Multi-Kernel Membrane Protein Prediction......Page 33 Acknowledgements......Page 37 References......Page 38 1.1 Braverman's Algorithm Spectrum......Page 42 1.2 Diagonalization of Similarity Matrices......Page 44 2.1 K-Means Algorithm and Criterion......Page 45 2.2 Data Recovery Equation: Encoder and Decoder......Page 46 2.3 Principal Component Analysis Extended to Clustering......Page 48 2.4 Data Scatter Clustering Decomposition......Page 50 2.5 One-By-One Strategy for Extracting Clusters......Page 51 2.6 Reformulation of the Complementary Criterion in Terms of Object-To-Object Similarity......Page 52 2.7 Returning to Matrix Diagonalization......Page 53 2.8 Returning to Spectrum......Page 54 2.9 Illustrative Example......Page 55 References......Page 60 1.1 The Generalized Machine Learning (Dependence Estimation) Problem......Page 62 1.3 Potential Function......Page 63 1.5 The Aim and the Structure of This Paper......Page 65 2.1 The Notion of the Distance Space......Page 67 2.2 Distance-Induced Similarity Function......Page 68 3.1 Embedding in the General Case of a Distance Space......Page 69 3.2 The Particular Case of a Proto-Euclidean Metric Space......Page 71 4.1 The Embedding Linear Space......Page 73 4.2 Indefinite Inner Product in the Embedding Linear Space......Page 76 4.3 Isodistant Image of a Distance Space in Its Pseudo-Euclidean Embedding Space......Page 78 4.4 An Important Particular Case: Embedding of a Proto-Euclidean Metric Space into the Euclidean Linear Space......Page 79 5.1.1 The First Heuristic of the Observer – Distance Function......Page 80 5.1.3 Empirical Risk Minimization......Page 81 5.1.4 The Third Heuristic of the Observer – Regularization Function......Page 82 5.1.6 Some Link Functions......Page 83 5.2.1 A Finite Basis in the Hypothetical Linear Embedding Space......Page 85 5.2.2 The Parametric Family of Generalized Linear Features and Parametric Representation of the Regularized Empirical Risk......Page 86 5.2.3 Some Parametric Regularization Functions......Page 88 5.3.1 Distance Transformation via Exponential Potential Function......Page 95 5.3.2 Fusion of Several Distance Functions......Page 97 5.3.3 Some Link and Regularization Functions for Distance Fusion......Page 98 5.3.4 Decision Rules of Growing Complexity......Page 99 6 Conclusions......Page 102 Appendix. The Proofs of Theorems......Page 104 References......Page 110 1 Introduction......Page 113 2 The Problem......Page 114 3 Bayesian Solution......Page 115 4 Fiducial Predictive Distributions......Page 116 5 Conformal Predictive Distributions......Page 117 6 Kernel Ridge Regression Prediction Machine......Page 119 7 Limitation of the KRRPM......Page 123 8 Experimental Results......Page 124 9 Conclusion......Page 127 A Properties of the Hat Matrix......Page 128 References......Page 130 On the Concept of Compositional Complexity......Page 132 1 A Metric Space with a Measure; the Linear Space of L2 Functions, Defined in the Metric Space, and the Theory of Representation of the Group of Isometric Transformations......Page 133 3 Functionals of Complexity in Symmetric Spaces......Page 134 4 Compositional Complexity of Functions and Its Decomposition into a Series. Non-complicating Operators......Page 136 1 Symmetric Space......Page 138 2 Quadratic Quality Functionals on Symmetric Spaces......Page 139 3 The Assignment of Classes for Functions of Equal Quality......Page 142 4 The Power Series Expansion of a Function of Distance......Page 146 5 The Potential Function in a Symmetric Space......Page 149 6 On the Choice of a Potential Function in the Space of Vertices of an m-dimensional Cube......Page 153 1 Introduction......Page 158 2 Lessons from the Ideal Causal Models......Page 161 3.1 General Ideas and Definitions......Page 168 3.2 Some Problems and Drawbacks of the DAG Theory......Page 172 3.3 DAG and PO (Potential Outcomes) Theories – Similarities and Differences......Page 175 4.1 What the Actual Causes Are?......Page 179 4.2 Statistical Estimations of the Generated Outcomes......Page 182 4.3 Additive Models: Detection of the Generative Variables......Page 185 5 Conclusion......Page 192 References......Page 193 Novel Developments......Page 197 1 Introduction......Page 198 2 Related Work......Page 199 3 Algorithm......Page 200 3.1 Linear Separability and Maximum by Probability......Page 201 3.3 Algorithms of Semi-supervised Transductive Learning for One-Class Classification......Page 203 4 Experiments......Page 206 5 Conclusion......Page 207 References......Page 208 1 Introduction......Page 210 2 Data Sources of Cell Lines and Patients to Design, Test and Validate Our Method......Page 212 3 Data Transfer Method: From the Cell Lines to Patients......Page 213 4 Validation of the Data Transfer Procedure......Page 215 5 Discussion......Page 218 Appendices: Materials and Methods......Page 219 References......Page 220 1 Preface......Page 222 2 Introduction......Page 223 3 The Problem......Page 226 4 Who Needs Such Robots and What It Takes to Realize Them?......Page 229 5 Topology Provides an Alternative......Page 230 6 How Does It Work?......Page 231 7 The Arm Manipulator Case......Page 232 8 Moving the Approach to Real-Life Applications......Page 234 9 Sensing System Hardware......Page 235 References......Page 237 1 Introduction......Page 238 2.1 Setup......Page 240 2.2 Implicit Modeling......Page 241 2.3 Adversarial Training......Page 242 2.4 Integral Probability Metrics......Page 244 2.5 f-Divergences......Page 245 2.6 Wasserstein Distance......Page 246 2.7 Energy Distance and Maximum Mean Discrepancy......Page 248 3 Energy Distance vs. 1-Wasserstein Distance......Page 252 3.1 Three Quantitative Properties......Page 253 3.2 WD and ED/MMD in Practice......Page 255 4 Length Spaces......Page 257 5 Minimal Geodesics in Probability Space......Page 259 5.1 Mixture Geodesics......Page 260 5.2 Displacement Geodesics......Page 261 6.1 Convexity à-la-carte......Page 266 6.2 The Convexity of Implicit Model Families......Page 268 6.3 The Convexity of Distances......Page 269 6.4 Almost-Convexity......Page 271 References......Page 274 1.1 Deep Learning in the Natural Sciences......Page 278 1.2 Deep Learning in Physics......Page 279 2 Antimatter Physics......Page 280 2.1 ASACUSA......Page 281 3 High Energy Physics......Page 286 3.1 Exotic Particle Searches......Page 287 3.2 Jet Substructure Classification......Page 289 3.3 Decorrelated Jet Substructure Tagging with Adversarial Neural Networks......Page 292 4 Neutrino Physics......Page 294 5 Dark Matter Physics......Page 299 6 Conclusion......Page 301 References......Page 302 1.1 Brief History......Page 307 1.3 General Idea Behind Reinforcement Learning......Page 309 1.4 Definitions......Page 310 1.5 Markov Decision Processes (MDPs)......Page 311 2 Main Algorithmic Approaches......Page 312 2.2 Dynamic Programming......Page 313 2.3 Monte-Carlo Methods......Page 315 2.4 Temporal Difference Methods......Page 317 2.5 Planning......Page 320 2.7 Policy Gradient Algorithms......Page 322 3.2 Limitations of Markov Decision Processes (MDPs)......Page 323 3.3 The POMDP Model......Page 325 3.4 Multi-agent Paradigm......Page 326 4.2 Hierarchical Reinforcement Learning......Page 327 4.4 Relational Reinforcement Learning......Page 328 5.1 Value-Based Deep Reinforcement Learning......Page 329 5.2 Policy-Based Deep Reinforcement Learning......Page 330 References......Page 331 Personal and Beyond......Page 338 A Man of Unlimited Capabilities (in Memory of E. M. Braverman)......Page 339 Braverman and His Theory of Disequilibrium Economics......Page 341 1 The Disequilibrium Theory of Economic Systems - a Conceptual Description of Emmanuel Braverman’s New Approach......Page 345 References......Page 348 Misha Braverman: My Mentor and My Model......Page 349 List of Braverman's Papers Published in the ``Avtomatika i telemekhanika'' Journal, Moscow, Russia, and Translated to English as ``Automation and Remote Control'' Journal......Page 357 Correction to: Chapter “Braverman and His Theory of Disequilibrium Economics” in: L. Rozonoer et al. (Eds.): Braverman Readings in Machine Learning, LNAI 11100, https://doi.org/10.1007/978-3-319-99492-5_15......Page 360 Author Index......Page 361 This state-of-the-art survey is dedicated to the memory of Emmanuil Markovich Braverman (1931-1977), a pioneer in developing the machine learning theory. The 12 revised full papers and 4 short papers included in this volume were presented at the conference "Braverman Readings in Machine Learning: Key Ideas from Inception to Current State" held in Boston, MA, USA, in April 2017, commemorating the 40th anniversary of Emmanuil Braverman's decease. The papers present an overview of some of Braverman's ideas and approaches. The collection is divided in three parts. The first part bridges the past and the present. Its main contents relate to the concept of kernel function and its application to signal and image analysis as well as clustering. The second part presents a set of extensions of Braverman's work to issues of current interest both in theory and applications of machine learning. The third part includes short essays by a friend, a student, and a colleague