

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

and W in memory quickly becomes infeasible. Instead, we may choose to compress the matrices U and W using hashing. For **U, W** ∈ R
n×d denote by **u, w** ∈ R
m vectors with

$u_{i}=\sum_{j,k:h(j,k)=i}\xi(j,k)U_{jk}$ and $w_{i}=\sum_{j,k:h^{\prime}(j,k)=i}\xi^{\prime}(j,k)W_{jk}$.  
where (**h, ξ**) and (h′, ξ′) are independently chosen hash functions. This allows us to approximate matrix elements Mij = [U⊤W]ij via

$$M_{i j}^{\phi}:=\sum_{k}\xi(k,i)\xi^{\prime}(k,j)u_{h(k,i)}w_{h^{\prime}(k,j)}.$$

This gives a compressed vector representation of M that can be efficiently stored.

## 5. Results

We evaluated our algorithm in the setting of personalization. As data set, we used a proprietary email spamclassification task of n = 3.2 million emails, properly anonymized, collected from |U| **= 433167** users. Each email is labeled as spam or *not-spam* by one user in U. After tokenization, the data set consists of 40 million unique words.

For all experiments in this paper, we used the Vowpal Wabbit implementation1 of stochastic gradient descent on a square-loss. In the mail-spam literature the misclassification of *not-spam* is considered to be much more harmful than misclassification of *spam*. We therefore follow the convention to set the classification threshold during test time such that exactly 1% of the not − **spam** test data is classified as **spam** Our implementation of the personalized hash functions is illustrated in Figure 1. To obtain a personalized hash function φu for user u, we concatenate a unique user-id to each word in the email and then hash the newly generated tokens with the same global hash function.

1http://hunch.net/∼vw/
The data set was collected over a span of 14 days. We used the first 10 days for training and the remaining 4 days for testing. As *baseline*, we chose the purely global classifier trained over all users and hashed into 2 26 dimensional space. As 2 26 far exceeds the total number of unique words we can regard the baseline to be representative for the classification without hashing. All results are reported as the amount of spam that passed the filter undetected, relative to this baseline (eg. a value of 0.80 indicates a 20% reduction in spam for the user)2.

Figure 2 displays the average amount of spam in users' inboxes as a function of the number of hash keys m, relative to the baseline above. In addition to the baseline, we evaluate two different settings.

The *global-hashed* curve represents the relative spam catch-rate of the global classifier after hashing hφ0(w0), φ0(x)i. At m = 226 this is identical to the baseline. Early convergence at m = 222 suggests that at this point hash collisions have no impact on the classification error and the *baseline* is indeed equivalent to that obtainable without hashing.

In the *personalized* setting each user u ∈ U gets her own classifier φu(wu) as well as the global classifier φ0(w0).

Without hashing the feature space explodes, as the cross product of u **= 400**K users and n **= 40**M tokens results in 16 trillion possible unique personalized features. Figure 2 shows that despite aggressive hashing, personalization results in a 30% spam reduction once the hash table is indexed by 22 bits.

2As part of our data sharing agreement, we agreed not to include absolute classification error-rates.