More Like this

1. Spectrahedral Regression

   https://doi.org/10.1137/21M1455899  

   O’Reilly, Eliza; Chandrasekaran, Venkat (June 2023, SIAM Journal on Optimization)

   Convex regression is the problem of fitting a convex function to a data set consisting of input-output pairs. We present a new approach to this problem called spectrahedral regression, in which we fit a spectrahedral function to the data, i.e., a function that is the maximum eigenvalue of an affine matrix expression of the input. This method represents a significant generalization of polyhedral (also called max-affine) regression, in which a polyhedral function (a maximum of a fixed number of affine functions) is fit to the data. We prove bounds on how well spectrahedral functions can approximate arbitrary convex functions via statistical risk analysis. We also analyze an alternating minimization algorithm for the nonconvex optimization problem of fitting the best spectrahedral function to a given data set. We show that this algorithm converges geometrically with high probability to a small ball around the optimal parameter given a good initialization. Finally, we demonstrate the utility of our approach with experiments on synthetic data sets as well as real data arising in applications such as economics and engineering design. 

   more » « less
2. Data driven verification of positive invariant sets for discrete, nonlinear systems

   Strong, Amy K; Bridgeman, Leila J (July 2024, PMLR)

   Invariant sets are essential for understanding the stability and safety of nonlinear systems. However, certifying the existence of a positive invariant set for a nonlinear model is difficult and often requires knowledge of the system’s dynamic model. This paper presents a data driven method to certify a positive invariant set for an unknown, discrete, nonlinear system. A triangulation of a subset of the state space is used to query data points. Then, linear programming is used to create a continuous piecewise affine function that fulfills the criteria of the Extended Invariant Set Principle by leveraging an inequality error bound that uses the Lipschitz constant of the unknown system. Numerical results demonstrate the program’s ability to certify positive invariant sets from sampled data. 

   more » « less
3. BigSift: automated debugging of big data analytics in data-intensive scalable computing

   https://doi.org/10.1145/3236024.3264586  

   Gulzar, Muhammad Ali; Wang, Siman; Kim, Miryung (November 2018, Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering)

   Developing Big Data Analytics often involves trial and error debugging, due to the unclean nature of datasets or wrong assumptions made about data. When errors (e.g. program crash, outlier results, etc.) arise, developers are often interested in pinpointing the root cause of errors. To address this problem, BigSift takes an Apache Spark program, a user-defined test oracle function, and a dataset as input and outputs a minimum set of input records that reproduces the same test failure by combining the insights from delta debugging with data provenance. The technical contribution of BigSift is the design of systems optimizations that bring automated debugging closer to a reality for data intensive scalable computing. BigSift exposes an interactive web interface where a user can monitor a big data analytics job running remotely on the cloud, write a user-defined test oracle function, and then trigger the automated debugging process. BigSift also provides a set of predefined test oracle functions, which can be used for explaining common types of anomalies in big data analytics--for example, finding the origin of the output value that is more than k standard deviations away from the median. The demonstration video is available at https://youtu.be/jdBsCd61a1Q. 

   more » « less
4. White-box Induction From SVM Models: Explainable AI with Logic Programming

   https://doi.org/10.1017/S1471068420000356  

   Shakerin, Farhad; Gupta, Gopal (December 2020, Theory and practice of logic programming)

   Ricca, Francesco; Russo, Alessandra (Ed.)

   We focus on the problem of inducing logic programs that explain models learned by the support vector machine (SVM) algorithm. The top-down sequential covering inductive logic programming (ILP) algorithms (e.g., FOIL) apply hill-climbing search using heuristics from information theory. A major issue with this class of algorithms is getting stuck in local optima. In our new approach, however, the data-dependent hill-climbing search is replaced with a model-dependent search where a globally optimal SVM model is trained first, then the algorithm looks into support vectors as the most influential data points in the model, and induces a clause that would cover the support vector and points that are most similar to that support vector. Instead of defining a fixed hypothesis search space, our algorithm makes use of SHAP, an example-specific interpreter in explainable AI, to determine a relevant set of features. This approach yields an algorithm that captures the SVM model’s underlying logic and outperforms other ILP algorithms in terms of the number of induced clauses and classification evaluation metrics. 

   more » « less
5. Sparse Approximation via Generating Point Sets

   https://doi.org/10.1137/1.9781611974331.ch40  

   Blum, Avrim; Har-Peled, Sariel; Raichel, Benjamin (December 2015, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2016))

   For a set P of n points in the unit ball b ⊆ R d , consider the problem of finding a small subset T ⊆ P such that its convex-hull ε-approximates the convex-hull of the original set. Specifically, the Hausdorff distance between the convex hull of T and the convex hull of P should be at most ε. We present an efficient algorithm to compute such an ε ′ -approximation of size kalg, where ε ′ is a function of ε, and kalg is a function of the minimum size kopt of such an ε-approximation. Surprisingly, there is no dependence on the dimension d in either of the bounds. Furthermore, every point of P can be ε- approximated by a convex-combination of points of T that is O(1/ε2 )-sparse. Our result can be viewed as a method for sparse, convex autoencoding: approximately representing the data in a compact way using sparse combinations of a small subset T of the original data. The new algorithm can be kernelized, and it preserves sparsity in the original input. 

   more » « less