Abstract
dc:description.abstract<p>Machine Learning (ML) implementations are fundamentally brittle: nondeterministic, inconsistent, and prone to overfitting; however, constraint solving can be used to systematically expose, quantify, and address this brittleness.</p><p>This dissertation first establishes that widely-used implementations of popular ML algorithms are nondeterministic (producing different outputs on the same input, across different runs) and inconsistent (different implementations of the same algorithm producing different outputs on the same input). This is more prevalent in Unsupervised Learning (UL) implementations where, due to the lack of a ground truth, subtle execution errors can go unnoticed and are difficult to verify. Nondeterminism and inconsistency also introduce security vulnerabilities when output instability can be actively exploited by an adversary. To address these issues, this research introduces OCELOT, a framework that reduces nondeterminism and inconsistency checking to SMT solving. Given an UL implementation, OCELOT automatically isolates the nondeterministic kernel (variables and code), which forms the basis for a Z3 specification. This specification is then checked for satisfiability, i.e., nondeterminism or inconsistency in the implementation, using Z3. OCELOT has exposed sources of nondeterminism and inconsistency in well-known implementations of Clustering and Anomaly Detection algorithms.</p><p>Next, this dissertation introduces a constraint-solving approach to tackle overfitting in neural networks (NN) based on mixed-integer linear programming (MILP). The framework improves NN generalization post-training through controlled sample reclassification by minimally perturbing the final layer weights and biases, using MILP. Unlike SMT solvers, MILP solvers optimize for a specific objective, e.g., minimizing the weight perturbation.</p><p>While OCELOT exposes where and why implementations fail, this dissertation also introduces a complementary feedback-directed approach (and tool, named DEANOMALYZER), that given a dataset, automatically searches for a parameter setting that maximizes determinism and consistency.</p><p>Finally, this dissertation introduces an approach (and tool, named ACE) that enables clustering algorithm implementations to tackle large datasets on commodity hardware, via an algorithm-independent parallelization method. Specifically, ACE partitions the dataset, runs the clustering implementation on the partitions in parallel, and aggregates the intermediate results.</p>
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy in Computing Sciences - (Ph.D.)
- Discipline thesis:degree_discipline
- Computer Science
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Ahmed, Muyeed
- 0000-0002-4478-5044
- Contributors dc:contributor
-
- Iulian Neamtiu
- Martin Kellogg
- Cong Shi
Subjects
dc:subject × 7Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.njit.edu/dissertations/1894