-
A Geometric Framework for Adversarial Vulnerability in Machine Learning
Authors:
Brian Bell
Abstract:
This work starts with the intention of using mathematics to understand the intriguing vulnerability observed by ~\citet{szegedy2013} within artificial neural networks. Along the way, we will develop some novel tools with applications far outside of just the adversarial domain. We will do this while developing a rigorous mathematical framework to examine this problem. Our goal is to build out theor…
▽ More
This work starts with the intention of using mathematics to understand the intriguing vulnerability observed by ~\citet{szegedy2013} within artificial neural networks. Along the way, we will develop some novel tools with applications far outside of just the adversarial domain. We will do this while developing a rigorous mathematical framework to examine this problem. Our goal is to build out theory which can support increasingly sophisticated conjecture about adversarial attacks with a particular focus on the so called ``Dimpled Manifold Hypothesis'' by ~\citet{shamir2021dimpled}. Chapter one will cover the history and architecture of neural network architectures. Chapter two is focused on the background of adversarial vulnerability. Starting from the seminal paper by ~\citet{szegedy2013} we will develop the theory of adversarial perturbation and attack.
Chapter three will build a theory of persistence that is related to Ricci Curvature, which can be used to measure properties of decision boundaries. We will use this foundation to make a conjecture relating adversarial attacks. Chapters four and five represent a sudden and wonderful digression that examines an intriguing related body of theory for spatial analysis of neural networks as approximations of kernel machines and becomes a novel theory for representing neural networks with bilinear maps. These heavily mathematical chapters will set up a framework and begin exploring applications of what may become a very important theoretical foundation for analyzing neural network learning with spatial and geometric information. We will conclude by setting up our new methods to address the conjecture from chapter 3 in continuing research.
△ Less
Submitted 3 July, 2024;
originally announced July 2024.
-
Wooly Graphs : A Mathematical Framework For Knitting
Authors:
Kathryn Gray,
Brian Bell,
Diana Sieper,
Stephen Kobourov,
Falk Schreiber,
Karsten Klein,
Seokhee Hong
Abstract:
This paper aims to develop a mathematical foundation to model knitting with graphs. We provide a precise definition for knit objects with a knot theoretic component and propose a simple undirected graph, a simple directed graph, and a directed multigraph model for any arbitrary knit object. Using these models, we propose natural categories related to the complexity of knitting structures. We use t…
▽ More
This paper aims to develop a mathematical foundation to model knitting with graphs. We provide a precise definition for knit objects with a knot theoretic component and propose a simple undirected graph, a simple directed graph, and a directed multigraph model for any arbitrary knit object. Using these models, we propose natural categories related to the complexity of knitting structures. We use these categories to explore the hardness of determining whether a knit object of each class exists for a given graph. We show that while this problem is NP-hard in general, under specific cases, there are linear and polynomial time algorithms which take advantage of unique properties of common knitting techniques. This work aims to bridge the gap between textile arts and graph theory, offering a useful and rigorous framework for analyzing knitting objects using their corresponding graphs and for generating knitting objects from graphs.
△ Less
Submitted 3 July, 2024; v1 submitted 29 June, 2024;
originally announced July 2024.
-
A Graph Model and a Layout Algorithm for Knitting Patterns
Authors:
Kathryn Gray,
Brian Bell,
Stephen Kobourov
Abstract:
Knitting, an ancient fiber art, creates a structured fabric consisting of loops or stitches. Publishing hand knitting patterns involves lengthy testing periods and numerous knitters. Modeling knitting patterns with graphs can help expedite error detection and pattern validation. In this paper, we describe how to model simple knitting patterns as planar graphs. We then design, implement, and evalua…
▽ More
Knitting, an ancient fiber art, creates a structured fabric consisting of loops or stitches. Publishing hand knitting patterns involves lengthy testing periods and numerous knitters. Modeling knitting patterns with graphs can help expedite error detection and pattern validation. In this paper, we describe how to model simple knitting patterns as planar graphs. We then design, implement, and evaluate a layout algorithm to visualize knitting patterns. Knitting patterns correspond to graphs with pre-specified edge lengths (e.g., uniform lengths, two lengths, etc.). This yields a natural graph layout optimization problem: realize a planar graph with pre-specified edge lengths, while ensuring there are no edge crossings. We quantitatively evaluate our algorithm using real knitting patterns of various sizes against three others; one created for knitting patterns, one that maintains planarity and optimizes edge lengths, and a popular force-directed algorithm.
△ Less
Submitted 19 June, 2024;
originally announced June 2024.
-
Persistent Classification: A New Approach to Stability of Data and Adversarial Examples
Authors:
Brian Bell,
Michael Geyer,
David Glickenstein,
Keaton Hamm,
Carlos Scheidegger,
Amanda Fernandez,
Juston Moore
Abstract:
There are a number of hypotheses underlying the existence of adversarial examples for classification problems. These include the high-dimensionality of the data, high codimension in the ambient space of the data manifolds of interest, and that the structure of machine learning models may encourage classifiers to develop decision boundaries close to data points. This article proposes a new framewor…
▽ More
There are a number of hypotheses underlying the existence of adversarial examples for classification problems. These include the high-dimensionality of the data, high codimension in the ambient space of the data manifolds of interest, and that the structure of machine learning models may encourage classifiers to develop decision boundaries close to data points. This article proposes a new framework for studying adversarial examples that does not depend directly on the distance to the decision boundary. Similarly to the smoothed classifier literature, we define a (natural or adversarial) data point to be $(γ,σ)$-stable if the probability of the same classification is at least $γ$ for points sampled in a Gaussian neighborhood of the point with a given standard deviation $σ$. We focus on studying the differences between persistence metrics along interpolants of natural and adversarial points. We show that adversarial examples have significantly lower persistence than natural examples for large neural networks in the context of the MNIST and ImageNet datasets. We connect this lack of persistence with decision boundary geometry by measuring angles of interpolants with respect to decision boundaries. Finally, we connect this approach with robustness by developing a manifold alignment gradient metric and demonstrating the increase in robustness that can be achieved when training with the addition of this metric.
△ Less
Submitted 11 April, 2024;
originally announced April 2024.
-
An Exact Kernel Equivalence for Finite Classification Models
Authors:
Brian Bell,
Michael Geyer,
David Glickenstein,
Amanda Fernandez,
Juston Moore
Abstract:
We explore the equivalence between neural networks and kernel methods by deriving the first exact representation of any finite-size parametric classification model trained with gradient descent as a kernel machine. We compare our exact representation to the well-known Neural Tangent Kernel (NTK) and discuss approximation error relative to the NTK and other non-exact path kernel formulations. We ex…
▽ More
We explore the equivalence between neural networks and kernel methods by deriving the first exact representation of any finite-size parametric classification model trained with gradient descent as a kernel machine. We compare our exact representation to the well-known Neural Tangent Kernel (NTK) and discuss approximation error relative to the NTK and other non-exact path kernel formulations. We experimentally demonstrate that the kernel can be computed for realistic networks up to machine precision. We use this exact kernel to show that our theoretical contribution can provide useful insights into the predictions made by neural networks, particularly the way in which they generalize.
△ Less
Submitted 9 August, 2023; v1 submitted 1 August, 2023;
originally announced August 2023.
-
Computing Sparse Jacobians and Hessians Using Algorithmic Differentiation
Authors:
Bradley M. Bell,
Kasper Kristensen
Abstract:
Stochastic scientific models and machine learning optimization estimators have a large number of variables; hence computing large sparse Jacobians and Hessians is important. Algorithmic differentiation (AD) greatly reduces the programming effort required to obtain the sparsity patterns and values for these matrices. We present forward, reverse, and subgraph methods for computing sparse Jacobians a…
▽ More
Stochastic scientific models and machine learning optimization estimators have a large number of variables; hence computing large sparse Jacobians and Hessians is important. Algorithmic differentiation (AD) greatly reduces the programming effort required to obtain the sparsity patterns and values for these matrices. We present forward, reverse, and subgraph methods for computing sparse Jacobians and Hessians. Special attention is given the the subgraph method because it is new. The coloring and compression steps are not necessary when computing sparse Jacobians and Hessians using subgraphs. Complexity analysis shows that for some problems the subgraph method is expected to be much faster. We compare C++ operator overloading implementations of the methods in the ADOL-C and CppAD software packages using some of the MINPACK-2 test problems. The experiments are set up in a way that makes them easy to run on different hardware, different systems, different compilers, other test problem and other AD packages. The setup time is the time to record the graph, compute sparsity, coloring, compression, and optimization of the graph. If the setup is necessary for each evaluation, the subgraph implementation has similar run times for sparse Jacobians and faster run times for sparse Hessians.
△ Less
Submitted 9 November, 2021;
originally announced November 2021.
-
MFED: A System for Monitoring Family Eating Dynamics
Authors:
Md Abu Sayeed Mondol,
Brooke Bell,
Meiyi Ma,
Ridwan Alam,
Ifat Emi,
Sarah Masud Preum,
Kayla de la Haye,
Donna Spruijt-Metz,
John C. Lach,
John A. Stankovic
Abstract:
Obesity is a risk factor for many health issues, including heart disease, diabetes, osteoarthritis, and certain cancers. One of the primary behavioral causes, dietary intake, has proven particularly challenging to measure and track. Current behavioral science suggests that family eating dynamics (FED) have high potential to impact child and parent dietary intake, and ultimately the risk of obesity…
▽ More
Obesity is a risk factor for many health issues, including heart disease, diabetes, osteoarthritis, and certain cancers. One of the primary behavioral causes, dietary intake, has proven particularly challenging to measure and track. Current behavioral science suggests that family eating dynamics (FED) have high potential to impact child and parent dietary intake, and ultimately the risk of obesity. Monitoring FED requires information about when and where eating events are occurring, the presence or absence of family members during eating events, and some person-level states such as stress, mood, and hunger. To date, there exists no system for real-time monitoring of FED. This paper presents MFED, the first of its kind of system for monitoring FED in the wild in real-time. Smart wearables and Bluetooth beacons are used to monitor and detect eating activities and the location of the users at home. A smartphone is used for the Ecological Momentary Assessment (EMA) of a number of behaviors, states, and situations. While the system itself is novel, we also present a novel and efficient algorithm for detecting eating events from wrist-worn accelerometer data. The algorithm improves eating gesture detection F1-score by 19% with less than 20% computation compared to the state-of-the-art methods. To date, the MFED system has been deployed in 20 homes with a total of 74 participants, and responses from 4750 EMA surveys have been collected. This paper describes the system components, reports on the eating detection results from the deployments, proposes two techniques for improving ground truth collection after the system is deployed, and provides an overview of the FED data, generated from the multi-component system, that can be used to model and more comprehensively understand insights into the monitoring of family eating dynamics.
△ Less
Submitted 11 July, 2020;
originally announced July 2020.
-
Iterative Construction of Gaussian Process Surrogate Models for Bayesian Inference
Authors:
Leen Alawieh,
Jonathan Goodman,
John B. Bell
Abstract:
A new algorithm is developed to tackle the issue of sampling non-Gaussian model parameter posterior probability distributions that arise from solutions to Bayesian inverse problems. The algorithm aims to mitigate some of the hurdles faced by traditional Markov Chain Monte Carlo (MCMC) samplers, through constructing proposal probability densities that are both, easy to sample and that provide a bet…
▽ More
A new algorithm is developed to tackle the issue of sampling non-Gaussian model parameter posterior probability distributions that arise from solutions to Bayesian inverse problems. The algorithm aims to mitigate some of the hurdles faced by traditional Markov Chain Monte Carlo (MCMC) samplers, through constructing proposal probability densities that are both, easy to sample and that provide a better approximation to the target density than a simple Gaussian proposal distribution would. To achieve that, a Gaussian proposal distribution is augmented with a Gaussian Process (GP) surface that helps capture non-linearities in the log-likelihood function. In order to train the GP surface, an iterative approach is adopted for the optimal selection of points in parameter space. Optimality is sought by maximizing the information gain of the GP surface using a minimum number of forward model simulation runs. The accuracy of the GP-augmented surface approximation is assessed in two ways. The first consists of comparing predictions obtained from the approximate surface with those obtained through running the actual simulation model at hold-out points in parameter space. The second consists of a measure based on the relative variance of sample weights obtained from sampling the approximate posterior probability distribution of the model parameters. The efficacy of this new algorithm is tested on inferring reaction rate parameters in a 3-node and 6-node network toy problems, which imitate idealized reaction networks in combustion applications.
△ Less
Submitted 17 November, 2019;
originally announced November 2019.
-
Achieving algorithmic resilience for temporal integration through spectral deferred corrections
Authors:
R. W. Grout,
H. Kolla,
M. L. Minion,
J. B. Bell
Abstract:
Spectral deferred corrections (SDC) is an iterative approach for constructing higher- order accurate numerical approximations of ordinary differential equations. SDC starts with an initial approximation of the solution defined at a set of Gaussian or spectral collocation nodes over a time interval and uses an iterative application of lower-order time discretizations applied to a correction equatio…
▽ More
Spectral deferred corrections (SDC) is an iterative approach for constructing higher- order accurate numerical approximations of ordinary differential equations. SDC starts with an initial approximation of the solution defined at a set of Gaussian or spectral collocation nodes over a time interval and uses an iterative application of lower-order time discretizations applied to a correction equation to improve the solution at these nodes. Each deferred correction sweep increases the formal order of accuracy of the method up to the limit inherent in the accuracy defined by the collocation points. In this paper, we demonstrate that SDC is well suited to recovering from soft (transient) hardware faults in the data. A strategy where extra correction iterations are used to recover from soft errors and provide algorithmic resilience is proposed. Specifically, in this approach the iteration is continued until the residual (a measure of the error in the approximation) is small relative to the residual on the first correction iteration and changes slowly between successive iterations. We demonstrate the effectiveness of this strategy for both canonical test problems and a comprehen- sive situation involving a mature scientific application code that solves the reacting Navier-Stokes equations for combustion research.
△ Less
Submitted 6 April, 2015;
originally announced April 2015.
-
The connection between Bayesian estimation of a Gaussian random field and RKHS
Authors:
Aleksandr Y. Aravkin,
Bradley M. Bell,
James V. Burke,
Gianluigi Pillonetto
Abstract:
Reconstruction of a function from noisy data is often formulated as a regularized optimization problem over an infinite-dimensional reproducing kernel Hilbert space (RKHS). The solution describes the observed data and has a small RKHS norm. When the data fit is measured using a quadratic loss, this estimator has a known statistical interpretation. Given the noisy measurements, the RKHS estimate re…
▽ More
Reconstruction of a function from noisy data is often formulated as a regularized optimization problem over an infinite-dimensional reproducing kernel Hilbert space (RKHS). The solution describes the observed data and has a small RKHS norm. When the data fit is measured using a quadratic loss, this estimator has a known statistical interpretation. Given the noisy measurements, the RKHS estimate represents the posterior mean (minimum variance estimate) of a Gaussian random field with covariance proportional to the kernel associated with the RKHS. In this paper, we provide a statistical interpretation when more general losses are used, such as absolute value, Vapnik or Huber. Specifically, for any finite set of sampling locations (including where the data were collected), the MAP estimate for the signal samples is given by the RKHS estimate evaluated at these locations.
△ Less
Submitted 17 July, 2013; v1 submitted 22 January, 2013;
originally announced January 2013.
