BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Postgraduate Seminars in the School of Computer Sc
ience
SUMMARY:Random triangles and the curse of dimensionality -
Bob Durrant\, School of Computer Science
DTSTART:20110302T120000Z
DTEND:20110302T133000Z
UID:TALK575AT
URL:/talk/index/575
DESCRIPTION:Prerequisites: Passing familiarity with basic prob
ability and the ideas of an integral\, a limit\, a
nd 3D geometry.\n\nOutline: Given three vectors ch
osen randomly from a standard normal distribution
in R^2\, what is the probability that the triangle
they form is acute or obtuse? It turns out that t
he probability of an obtuse triangle is exactly 3/
4\, and this can be shown using either a slightly
scary integral or via a simple "proof by pictures"
argument.\n\nNow what about if we choose three ve
ctors randomly from a standard normal distribution
in some outrageously high dimensional space R^d?
Say R^1000 or R^10000? What is the probability tha
t our random triangle is still obtuse? We can no l
onger draw the picture\, so we revert to our scary
integral and find that the probability of an obtu
se random triangle drops sharply as d increases. I
n fact in the limit when d -> infinity the probabi
lity is zero.\n\nWhy should this be? It turns out
to be the result of a very general phenomenon in h
igh dimensional space that the random vectors are
very likely to have nearly the same length and be
nearly orthogonal to each other. This means that i
n the limit our random triangle is equilateral wit
h probability 1.\n\nFinally\, these last facts are
aspects of the "curse of dimensionality" and have
practical implications for a range of popular dat
a-mining techniques\, where the typical domain is
indeed often something like R^1000.
LOCATION:Room 124\, School of Computer Science
CONTACT:Mohamed Menaa
END:VEVENT
END:VCALENDAR