Latent search engines and question-answering (QA) engines fundamentally depend on our intuitive notion of semantics and semantic distance. However, such a semantic distance is likely undefinable, certainly un-computable, and often blindly approximated. Can we develop a theoretical framework for this area?
I will describe a theory, using the well-defined information distance, to approximate the elusive semantic distance such that it is mathematically proven that our approximation is "better than" any computable approximation of the intuitive concept of semantic distance. Although information distance itself is obviously also not computable, it does allow a natural approximation by compression. We will then describe a natural language encoding system to implement our theory followed by experiments on a QA system.
Ming Li is a Canada Research Chair in Bioinformatics and a University Professor at the University of Waterloo. He is a fellow of the Royal Society of Canada, ACM, and IEEE. He is a recipient of E.W.R. Steacie Fellowship Award in 1996, the 2001 Killam Fellowship, and the 2010 Killam Prize. Together with Paul Vitanyi they have co-authored the book "An Introduction to Kolmogorov Complexity and Its Applications".
Prof. Chrisos H. Papadimitrious (University of California - Berkeley, USA)
Computational Insights and the Theory of Evolution
Covertly computational ideas have influenced the Theory of Evolution from the
very start. This talk is about recent work on Evolution that was inspired and
informed by computational insights. Considerations about the performance of
genetic algorithms led to a novel theory of the role of sex in Evolution based
on the concept of mixability, while the equations describing the evolution of
a species can be reinterpreted as a repeated game between genes played through
the multiplicative updates algorithm. Finally, a theorem on Boolean functions
helps us understand better Waddington's genetic assimilation as well as
mechanisms for the emergence of novelty in Life.
Christos H. Papadimitriou is the C. Lester Hogan Professor of Computer Science
at UC Berkeley. Before joining Berkeley in 1996 he taught at Harvard, MIT,
Athens Polytechnic, Stanford, and UCSD. He has written five textbooks and many
articles on algorithms and complexity, and their applications to optimization,
databases, AI, the Internet, economics, and evolution. He is a member of the
Academy of Sciences of the U.S., the American Academy of Arts and Sciences, and
the National Academy of Engineering, and a recipient of the Knuth prize, the
Goedel prize, and eight honorary doctorates. He has also published three