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
Sort By
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, 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
Algorithms for Efficient Near-Perfect Phylogenetic Tree Reconstruction in Theory and Practice
Preview
Srinath Sridhar
Guy E. Blelloch
Eran Halperin
R. Ravi
Russell Schwartz
IEEE/ACM Trans. Comput. Biology Bioinform., 4 (2007), pp. 561-571
Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees
Preview
Srinath Sridhar
Guy E. Blelloch
Eran Halperin
R. Ravi
Russell Schwartz
International Conference on Computational Science (2) (2006), pp. 799-806
