Jump to Content
Kedar Dhamdhere

Kedar Dhamdhere

Kedar Dhamdhere is a research scientist at Google. His research interests include model understanding and Q&A systems. In the past, he has worked on search at Google and Facebook. Prior to joining Google he finished his PhD in Computer Science from CMU.
Authored Publications
Google Publications
Other Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    Preview abstract We study interactions among players in cooperative games. We propose a new interaction index called Shapley-Taylor Interaction index. It decomposes the value of the game into terms that model the interactions betweensubsets of players in a manner analogous to how the Taylor series represents a function in terms of its derivativesWe axiomatize the method using the axioms that axiomatize the Shapley value—linearity,dummyandefficiency—and also an additional axiom that we call theinteraction distributionaxiom. This axiom explicitlycharacterizes how interactions are distributed for a class of games called interaction games.We contrast Shapley-Taylor values against the previously proposed Shapley Interaction Value(cf. [1]) thatinstead relies on a recursive construction rather than the efficiency and interaction distribution axioms. View details
    Preview abstract The problem of attributing a deep network’s prediction to its input/base features is well-studied (cf. Simonyan et al. (2013)). We introduce the notion of conductance to extend the notion of attribution to understanding the importance of hidden units. Informally, the conductance of a hidden unit of a deep network is the flow of attribution via this hidden unit. We can use conductance to understand the importance of a hidden unit to the prediction for a specific input, or over a set of inputs. We justify conductance in multiple ways via a qualitative comparison with other methods, via some axiomatic results, and via an empirical evaluation based on a feature selection task. The empirical evaluations are done using the Inception network over ImageNet data, and a convolutinal network over text data. In both cases, we demonstrate the effectiveness of conductance in identifying interesting insights about the internal workings of these networks. View details
    Preview abstract We analyze state-of-the-art deep learning models for three tasks: question answering on (1) images, (2) tables, and (3) passages of text. Using the notion of attribution (word importance), we find that these deep networks often ignore important question terms. Leveraging such behavior, we perturb questions to craft a variety of adversarial examples. Our strongest attacks drop the accuracy of a visual question answering model from 61.1% to 19%, and that of a tabular question answering model from 33.5% to 3.3%. Additionally, we show how attributions can strengthen attacks proposed by Jia and Liang (2017) on paragraph comprehension models. Our results demonstrate that attributions can augment standard measures of accuracy and empower investigation of model performance. When a model is accurate but for the wrong reasons, attributions can surface erroneous logic in the model that indicates inadequacies in the test data. View details
    Analyza: Exploring Data with Conversation
    Kevin McCurley
    Ralfi Nahmias
    Intelligent User Interfaces 2017, ACM, Limassol, Cyprus (to appear)
    Preview abstract We describe Analyza, a system that helps lay users explore data. Analyza has been used within two large real world systems. The first is a question-and-answer feature in a spreadsheet product. The second provides convenient access to a revenue/inventory database for a large sales force. Both user bases consist of users who do not necessarily have coding skills, demonstrating Analyza's ability to democratize access to data. We discuss the key design decisions in implementing this system. For instance, how to mix structured and natural language modalities, how to use conversation to disambiguate and simplify querying, how to rely on the ``semantics'' of the data to compensate for the lack of syntactic structure, and how to efficiently curate the data. View details
    Metric Embeddings with Relaxed Guarantees
    T H Hubert Chan
    Anupam Gupta
    Jon m Kleinberg
    Aleksandrs Slivkins
    SIAM Journal on Computing, vol. 38 (2009), pp. 2303-2329
    Preview abstract We consider the problem of embedding finite metrics with slack: We seek to produce embeddings with small dimension and distortion while allowing a (small) constant fraction of all distances to be arbitrarily distorted. This definition is motivated by recent research in the networking community, which achieved striking empirical success at embedding Internet latencies with low distortion into low-dimensional Euclidean space, provided that some small slack is allowed. Answering an open question of Kleinberg, Slivkins, and Wexler [in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, 2004], we show that provable guarantees of this type can in fact be achieved in general: Any finite metric space can be embedded, with constant slack and constant distortion, into constant-dimensional Euclidean space. We then show that there exist stronger embeddings into $\ell_1$ which exhibit gracefully degrading distortion: There is a single embedding into $\ell_1$ that achieves distortion at most $O(\log\frac{1}{\epsilon})$ on all but at most-1.5pt an $\epsilon$ fraction of distances simultaneously for all $\epsilon>0$. We extend this with distortion1pt $O(\log\frac{1}{\epsilon})^{1/p}$ to maps into general $\ell_p$, $p\geq1$, for several classes of metrics, including those with bounded doubling dimension and those arising from the shortest-path metric of a graph with an excluded minor. Finally, we show that many of our constructions are tight and give a general technique to obtain lower bounds for $\epsilon$-slack embeddings from lower bounds for low-distortion embeddings. View details
    Minimizing Weighted Flow Time
    Nikhil Bansal
    ACM Transactions on Algorithms, vol. 3, no. 4 (2007), pp. 1-14
    Preview
    Algorithms for Efficient Near-Perfect Phylogenetic Tree Reconstruction in Theory and Practice
    Srinath Sridhar
    Guy E. Blelloch
    Eran Halperin
    R. Ravi
    Russell Schwartz
    IEEE/ACM Trans. Comput. Biology Bioinform., vol. 4 (2007), pp. 561-571
    Preview
    Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees
    Srinath Sridhar
    Guy E. Blelloch
    Eran Halperin
    R. Ravi
    Russell Schwartz
    International Conference on Computational Science (2) (2006), pp. 799-806
    Preview
    Relaxing Haplotype Block Models for Association Testing
    Natalie Castellana
    Srinath Sridhar
    Russell Schwartz
    Pacific Symposium on Biocomputing (2006), pp. 454-466
    Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction
    Guy E. Blelloch
    Eran Halperin
    R. Ravi
    Russell Schwartz
    Srinath Sridhar
    ICALP (1) (2006), pp. 667-678
    Improved embeddings of graph metrics into random trees
    Anupam Gupta
    Harald R"cke
    SODA (2006), pp. 61-69
    Approximation Algorithms for Minimizing Average Distortion
    Anupam Gupta
    R. Ravi
    Theory Comput. Syst., vol. 39 (2006), pp. 93-111
    Metric Embeddings with Relaxed Guarantees
    Ittai Abraham
    Yair Bartal
    Hubert T.-H. Chan
    Anupam Gupta
    Jon M. Kleinberg
    Ofer Neiman
    Aleksandrs Slivkins
    FOCS (2005), pp. 83-100
    Approximation algorithms for low-distortion embeddings into low-dimensional spaces
    Mihai Badoiu
    Anupam Gupta
    Yuri Rabinovich
    Harald R"cke
    R. Ravi
    Anastasios Sidiropoulos
    SODA (2005), pp. 119-128
    On Two-Stage Stochastic Minimum Spanning Trees
    R. Ravi
    Mohit Singh
    IPCO (2005), pp. 321-334
    How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems
    Vineet Goyal
    R. Ravi
    Mohit Singh
    FOCS (2005), pp. 367-378
    Finding (Recently) Frequent Items in Distributed Data Streams
    Amit Manjhi
    Vladislav Shkapenyuk
    Christopher Olston
    ICDE (2005), pp. 767-778
    Approximation Algorithms for Minimizing Average Distortion
    Anupam Gupta
    R. Ravi
    STACS (2004), pp. 234-245
    Non-Clairvoyant Scheduling for Minimizing Mean Slowdown
    Nikhil Bansal
    Jochen Koenemann
    Amitabh Sinha
    Algorithmica, vol. 40 (2004), pp. 305-318
    WIC: A General-Purpose Algorithm for Monitoring Web Information Sources
    Sandeep Pandey
    Christopher Olston
    VLDB (2004), pp. 360-371
    Approximating Additive Distortion of Embeddings into Line Metrics
    APPROX-RANDOM (2004), pp. 96-104
    Scheduling for Flow-Time with Admission Control
    Nikhil Bansal
    Avrim Blum
    Shuchi Chawla
    ESA (2003), pp. 43-54
    Non-clairvoyant Scheduling for Minimizing Mean Slowdown
    Nikhil Bansal
    Jochen Koenemann
    Amitabh Sinha
    STACS (2003), pp. 260-270
    Minimizing weighted flow time
    Nikhil Bansal
    SODA (2003), pp. 508-516