IntroductionSuppose you see two drunks (i.e., two random walks) wandering around. The drunks don’t know each other (they’re independent), so there’s no meaningful relationship between their paths.But suppose instead you have a drunk walking with her dog. This time thereisa connection. What’s the nature of this connection? Notice that although each path individually is still an unpredictable random walk, given the location of one of the drunk or dog, we have a pretty good idea of where the other is; that is, the distance between the two is fairly predictable. (For exampl ...继续阅读 (16)

Given a set of datapoints, we often want to know how many clusters the datapoints form. Thegap statisticand theprediction strengthare two practical algorithms for choosing the number of clusters.Gap StatisticThegap statistic algorithmworks as follows:For each i from 1 up to some maximum number of clusters,Run a k-means algorithm on the original dataset to find i clusters, and sum the distance of all points from their cluster mean. Call this sum thedispersion.Generate a set ofreferencedatasets (of the same size as the original). One simple way of generating a reference dataset is to sample unif ...继续阅读 (17)

I was playing around with theHacker News databaseRonnie Rollermade (thanks!), so I thought I’d post some of the things I looked at.Activity on the SiteMy first question was how activity on the site has increased over time. I looked at number of posts, points on posts, comments on posts, and number of users.PostsThis looks like a strong linear fit, with an increase of 292 posts every month.CommentsFor comments, I fit a quadratic regression:PointsA quadratic regression was also a better fit for points by month:UsersAnd again for the number of distinct users with a submission:Points and Com ...继续阅读 (15)

Measure theory studies ways of generalizing the notions of length/area/volume. Even in 2 dimensions, it might not be clear how to measure the area of the following fairly tame shape:much less the “area” of even weirder shapes in higher dimensions or different spaces entirely.For example, suppose you want to measure the length of a book (so that you can get a good sense of how long it takes to read). What’s a good measure? One possibility is to measure a book’s length inpages. Since books provide page counts, this is a fairly easy measure to get. However, different versi ...继续阅读 (13)

Suppose you’re very indecisive, so whenever you want to watch a movie, you ask your friend Willow if she thinks you’ll like it. In order to answer, Willow first needs to figure out what movies you like, so you give her a bunch of movies and tell her whether you liked each one or not (i.e., you give her a labeled training set). Then, when you ask her if she thinks you’ll like movie X or not, she plays a 20 questions-like game with IMDB, asking questions like “Is X a romantic movie?”, “Does Johnny Depp star in X?”, and so on. She asks more informative qu ...继续阅读 (17)

(Way back when, I went through all the Netflix prize papers. I’m now (very slowly) trying to clean up my notes and put them online. Eventually, I hope to have a more integrated tutorial, but here’s a rough draft for now.)This is a summary of Koren’s 2008Factorization Meets the Neighborhood: a Multifaceted Collaborative Filtering Model.There are two approaches to collaborative filtering: neighborhood methods and latent factor models.Neighborhood models are most effective at detecting very localized relationships (e.g., that people who like X-Men also like Spiderman), but poor ...继续阅读 (15)

(Way back when, I went through all the Netflix prize papers. I’m now (very slowly) trying to clean up my notes and put them online. Eventually, I hope to have a more integrated tutorial, but here’s a rough draft for now.)This is a summary of Bell and Koren’s 2007Scalable Collaborative Filtering with Jointly Derived Neighborhood Interpolation Weightspaper.tl;drThis paper’s main innovation is deriving neighborhood weights by solving a least squares problem, instead of using a standard similarity function to compute weights.This paper improves upon the standard neighborhoo ...继续阅读 (23)

Lots of people know that theRiemann Hypothesishassomethingto do with prime numbers, but most introductions fail to say what or why. I’ll try to give one angle of explanation.Layman’s TermsSuppose you have a bunch of friends, each with an instrument that plays at a frequency equal to the imaginary part of a zero of the Riemann zeta function. If the Riemann Hypothesis holds, you can create a song that sounds exactly at the prime-powered beats, by simply telling all your friends to play at the same volume.Mathematical TermsLet $ \pi(x) $ denote the number of primes less than or eq ...继续阅读 (26)

The Kahn, Saks, and Sturtevant approach to the Evasiveness Conjecture (see the original paperhere) is an epic application of pure mathematics to computer science. I’ll give an overview of the approach here, and probably try to add some more information on the problem in other posts.tl;drThe KSS approach provides an algebraic-topological attack to a combinatorial hypothesis, and reduces a graph complexity problem to a problem of contractibility and (not) finding fixed points.First, the Evasiveness Conjecture states that any (non-trivial) monotone graph property is evasive. In other words, ...继续阅读 (18)

IntroductionIn making its product recommendations, Amazon makes heavy use of an item-to-item collaborative filtering approach. This essentially means that for each item X, Amazon builds a neighborhood of related items S(X); whenever you buy/look at an item, Amazon then recommends you items from that item’s neighborhood. That’s why when you sign in to Amazon and look at the front page, your recommendations are mostly of the form “You viewed… Customers who viewed this also viewed…”.Other approaches.The item-to-item approach can be contrasted to:A user-to-user ...继续阅读 (17)