Norman Sadeh

AAAI Conference 2022 Conference Paper

Explain, Edit, and Understand: Rethinking User Study Design for Evaluating Model Explanations

• Siddhant Arora
• Danish Pruthi
• Norman Sadeh
• William W. Cohen
• Zachary C. Lipton
• Graham Neubig

In attempts to “explain” predictions of machine learning models, researchers have proposed hundreds of techniques for attributing predictions to features that are deemed important. While these attributions are often claimed to hold the potential to improve human “understanding” of the models, surprisingly little work explicitly evaluates progress towards this aspiration. In this paper, we conduct a crowdsourcing study, where participants interact with deception detection models that have been trained to distinguish between genuine and fake hotel reviews. They are challenged both to simulate the model on fresh reviews, and to edit reviews with the goal of lowering the probability of the originally predicted class. Successful manipulations would lead to an adversarial example. During the training (but not the test) phase, input spans are highlighted to communicate salience. Through our evaluation, we observe that for a linear bag-of-words model, participants with access to the feature coefficients during training are able to cause a larger reduction in model confidence in the testing phase when compared to the no-explanation control. For the BERT-based classifier, popular local explanations do not improve their ability to reduce the model confidence over the no-explanation case. Remarkably, when the explanation for the BERT model is given by the (global) attributions of a linear model trained to imitate the BERT model, people can effectively manipulate the model.

AAAI Conference 2011 Conference Paper

User-Controllable Learning of Location Privacy Policies With Gaussian Mixture Models

• Justin Cranshaw
• Jonathan Mugan
• Norman Sadeh

With smart-phones becoming increasingly commonplace, there has been a subsequent surge in applications that continuously track the location of users. However, serious privacy concerns arise as people start to widely adopt these applications. Users will need to maintain policies to determine under which circumstances to share their location. Specifying these policies however, is a cumbersome task, suggesting that machine learning might be helpful. In this paper, we present a user-controllable method for learning location sharing policies. We use a classifier based on multivariate Gaussian mixtures that is suitably modified so as to restrict the evolution of the underlying policy to favor incremental and therefore human-understandable changes as new data arrives. We evaluate the model on real location-sharing policies collected from a live location-sharing social network, and we show that our method can learn policies in a user-controllable setting that are just as accurate as policies that do not evolve incrementally. Additionally, we highlight the strength of the generative modeling approach we take, by showing how our model easily extends to the semi-supervised setting.

IJCAI Conference 2009 Conference Paper

• Michael Benisch
• Norman Sadeh
• Tuomas Sandholm

Mechanisms (especially on the Internet) have begun allowing people or organizations to express richer preferences in order to provide for greater levels of overall satisfaction. In this paper, we develop an operational methodology for quantifying the expected gains in economic efficiency associated with different forms of expressiveness. We begin by proving that the sponsored search mechanism (GSP) used by Google, Yahoo! , MSN, etc. can be arbitrarily inefficient. We then experimentally compare its efficiency to a slightly more expressive variant (PGSP), which solicits an extra bid for a premium class of positions. We generate random preference distributions based on published industry knowledge. We determine ideal strategies for the agents using a custom tree search technique, and we also benchmark using straightforward heuristic bidding strategies. The GSP’s efficiency loss is greatest in the practical case where some advertisers (“brand advertisers”) prefer top positions while others (“value advertisers”) prefer middle positions, and that loss can be dramatic. It is also worst when agents have small profit margins. While the PGSP is only slightly more expressive (and thus not much more cumbersome), it removes almost all of the efficiency loss in all of the settings we study.

AAMAS Conference 2006 Conference Paper

Examining DCSP Coordination Tradeoffs

• Michael Benisch
• Norman Sadeh

AIJ Journal 1996 Journal Article

Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem

• Norman Sadeh
• Mark S. Fox

Practical constraint satisfaction problems (CSPs) such as design of integrated circuits or scheduling generally entail large search spaces with hundreds or even thousands of variables, each with hundreds or thousands of possible values. Often, only a very tiny fraction of all these possible assignments participates in a satisfactory solution. This article discusses techniques that aim at reducing the effective size of the search space to be explored in order to find a satisfactory solution by judiciously selecting the order in which variables are instantiated and the sequence in which possible values are tried for each variable. In the CSP literature, these techniques are commonly referred to as variable and value ordering heuristics. Our investigation is conducted in the job shop scheduling domain. We show that, in contrast with problems studied earlier in the CSP literature, generic variable and value heuristics do not perform well in this domain. This is attributed to the difficulty of these heuristics to properly account for the tightness of constraints and/or the connectivity of the constraint graphs induced by job shop scheduling CSPs. A new probabilistic framework is introduced that better captures these key aspects of the job shop scheduling search space. Empirical results show that variable and value ordering heuristics derived within this probabilistic framework often yield significant improvements in search efficiency and significant reductions in the search time required to obtain a satisfactory solution. The research reported in this article was the first one, along with the work of Keng and Yun (1989), to use the CSP problem solving paradigm to solve job shop scheduling problems. The suite of benchmark problems it introduced has been used since then by a number of other researchers to evaluate alternative techniques for the job shop scheduling CSP. The article briefly reviews some of these more recent efforts and shows that our variable and value ordering heuristics remain quite competitive

AIJ Journal 1995 Journal Article

Backtracking techniques for the job shop scheduling constraint satisfaction problem

• Norman Sadeh
• Katia Sycara
• Yalin Xiong

This paper studies a version of the job shop scheduling problem in which some operations have to be scheduled within non-relaxable time windows (i. e. earliest/latest possible start time windows). This problem is a well-known NP-complete Constraint Satisfaction Problem (CSP). A popular method for solving this type of problems involves using depth-first backtrack search. In our earlier work, we focused on the development of consistency enforcing techniques and variable/value ordering heuristics that improve the efficiency of this search procedure. In this paper, we combine these techniques with new look-back schemes that help the search procedure recover from so-called deadend search states (i. e. partial solutions that cannot be completed without violating some constraints). More specifically, we successively describe three “intelligent” backtracking schemes: (1) Dynamic Consistency Enforcement dynamically identifies critical subproblems and determines how far to backtrack by selectively enforcing higher levels of consistency among variables participating in these critical subproblems, (2) Learning Ordering From Failure dynamically modifies the order in which variables are instantiated based on earlier conflicts, and (3) Incomplete Backjumping Heuristic abandons areas of the search space that appear to require excessive computational efforts. These schemes are shown to (1) further reduce the average complexity of the backtrack search procedure, (2) enable our system to efficiently solve problems that could not be solved otherwise due to excessive computation cost, and (3) be more effective at solving job shop scheduling problems than other look-back schemes advocated in the literature.

IJCAI Conference 1989 Conference Paper

Constrained Heuristic Search

• Mark S. Fox
• Norman Sadeh
• Can Baykan