Friday, 22nd September - 10am Dan Vilenchik : Seminar

Title: Towards Reverse Algorithmic Engineering of Neural Networks

Abstract:

As machine learning models get more complex, they can outperform traditional algorithms and tackle a wider range of problems, including challenging combinatorial optimization tasks. However, this increased complexity can make understanding how the model makes its decisions difficult. Explainable models can increase trust in the model’s decisions and may even lead to improvements in the algorithm itself. Algorithms like GradCAM or SHAP provide good explanation in terms of feature importance, typically for classification tasks, but they provide little insight when the ML pipeline is designed to work, for example, as an algorithm for solving optimization problems.

In this talk we present a framework for explaining a model’s decision-making process from an algorithmic point of view while taking into account domain knowledge of the problem at hand. Using the NeuroSAT algorithm for SAT solving as a case study, we demonstrate how our framework explains the underlying algorithmic concepts that drive the operation of an NN-based model. For example, we discover that for sparse random SAT instances, NeuroSAT mimics the Pure Literal heuristic, while for denser formulas, it relies on the concept of support to decide which variables to flip, similar to the WalkSAT algorithm.

Join work with Elad Shoham (Phd student, BGU), Kahalil Wattad (MsC student BGU), Hadar Cohen (MsC student BGU), Havana Rica (Tel-Aviv-Yafo Academic College) and Claire Chen (MIT, undergraduate student).

Short bio:

Dan Vilenchik holds a PhD in computer science from Tel Aviv University. He did a postdoc at UC Berkeley and UCLA. He is currently a tenured member of the school of Electrical Engineering at Ben-Gurion University. His research includes both theoretical (challenges of high-dimensional data) and applicative (NLP and multidisciplinary projects) aspects of machine learning.

https://www.bgu.ac.il/~vilench