

![0_image_0.png](0_image_0.png)

User clustering One hypothesis for the strong results in Figure 2 might originate from the non-uniform distribution of user votes - it is possible that using personalization and feature hashing we benefit a small number of users who have labeled many emails, degrading the performance of most users (who have labeled few or no emails) in the process. In fact, in real life, a large fraction of email users do not contribute at all to the training corpus and only interact with the classifier during test time. The personalized version of the test email Φu(xu) is then hashed into buckets of other tokens and only adds interference noise ǫito the classification. In order to show that we improve the performance of most users, it is therefore important that we not only report averaged results over all emails, but explicitly examine the effects of the personalized classifier for users depending on their contribution to the training set. To this end, we place users into exponentially growing buckets based on their number of training emails and compute the relative reduction of uncaught spam for each bucket individually. Figure 3 shows the results on a per-bucket basis. We do not compare against a *purely* local approach, with no global component, since for a large fraction of users—those without training data—this approach cannot outperform random guessing.

It might appear rather surprising that users in the bucket with none or very little training emails (the line of bucket
[0] is identical to bucket [1]) also benefit from personalization. After all, their personalized classifier was never trained and can only add noise at test-time. The classifier improvement of this bucket can be explained by the subjective definition of *spam* and *not-spam*. In the personalized setting the individual component of user labeling is absorbed by the local classifiers and the global classifier represents the *common* definition of spam and not-spam.

In other words, the global part of the personalized classifier obtains better generalization properties, benefiting all users.

## 6. Related Work

A number of researchers have tackled related, albeit different problems.

(Rahimi & Recht, 2008) use Bochner's theorem and sampling to obtain approximate inner products for Radial Basis Function kernels. (Rahimi & Recht, 2009) extend this to sparse approximation of weighted combinations of basis functions. This is computationally efficient for many function spaces. Note that the representation is *dense*.

(Li et al., 2007) take a complementary approach: for sparse feature vectors, φ(x), they devise a scheme of reducing the number of nonzero terms even further. While this is in principle desirable, it does not resolve the problem of φ(x) being high dimensional. More succinctly, it is necessary to express the function in the dual representation rather than expressing f as a linear function, where w is unlikely to be compactly represented: f(x) = hφ(x), wi.

(Achlioptas, 2003) provides computationally efficient randomization schemes for dimensionality reduction. Instead of performing a dense d·m dimensional matrix vector multiplication to reduce the dimensionality for a vector of dimensionality d to one of dimensionality m, as is required by the algorithm of (Gionis et al., 1999), he only requires 13 of that computation by designing a matrix consisting only of entries {−1, 0, 1}. Pioneered by (Ailon & Chazelle, 2006), there has been a line of work (Ailon & Liberty, 2008; Matousek, 2008) on improving the complexity of random projection by using various code-matrices in order to preprocess the input vectors. Some of our theoretical bounds are derivable from that of **(Liberty et al., 2008)**.

A related construction is the CountMin sketch of **(Cormode & Muthukrishnan, 2004)** which stores counts in a number of replicates of a hash table. This leads to good concentration inequalities for range and point queries.

(Shi et al., 2009) propose a hash kernel to deal with the issue of computational efficiency by a very simple algorithm:
high-dimensional vectors are compressed by adding up all coordinates which have the same hash value - one only needs to perform as many calculations as there are nonzero terms in the vector. This is a significant computational saving over locality sensitive hashing (Achlioptas, 2003; Gionis et al., 1999).

Several additional works provide motivation for the investigation of hashing representations. For example, **(Ganchev**
& Dredze, 2008) provide empirical evidence that the hash-