Computer Science Colloquium

Beyond Two: Discovering Complex Relationships in Real-world Problems

Susan L. Epstein, Hunter College

November 01, 2013 11:30AM
Warren Weaver Hall, 1302
251 Mercer Street
New York, NY 10012

Fall 2013 Colloquia Calendar


Ernest Davis


Real-world problems and human perceptions about them are considerably richer
and more challenging than pairwise relationships suggest. This talk explores
the shortcomings of a traditional focus on pairwise similarity metrics, and
shows how sets of similar objects better support incisive reasoning and
intelligent behavior. In three diverse domains, a new algorithm detects
subgraphs of size greater than two that support particular goals. The first
domain is constraint satisfaction problems, where binary graphs represent
the degree to which variables mutually restrict one another. Here, the
algorithm discovers particularly difficult subproblems, directs initial
resources to them, demonstrably accelerates search, and clarifies the nature
of the problem for human users. The second domain is protein-protein
interaction (PPI) networks, where binary graphs represent known interactions
between proteins. Here, the algorithm discovers sets of genes that interact
heavily with one another and suggests avenues of investigation for human
researchers. The third domain is item recommendation, where sets of binary
graphs represent multiple similarities among movies. Here, the algorithm
discovers subsets that support recommendations for a prospective viewer. In
each case, facets of similarity are explored and controlled to support
reasoning and develop expertise.

top | contact webmaster