%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%% ICML 2009 EXAMPLE LATEX SUBMISSION FILE %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Use the following line _only_ if you're still using LaTeX 2.09.
%\documentstyle[icml2009,epsf,mlapa]{article}
% If you rely on Latex2e packages, like most moden people use this:
\documentclass{article}

% Employ the following version of the ``usepackage'' statement for
% submitting the draft version of the paper for review.  This will set
% the note in the first column to ``Under review.  Do not distribute.''
%\usepackage{icml2009}
% Employ this version of the ``usepackage'' statement after the paper has
% been accepted, when creating the final version.  This will set the
% note in the first column to ``Appearing in''
\usepackage[accepted]{icml2009}

% For figures
\usepackage{graphicx} % more modern
%\usepackage{epsfig} % less modern
\usepackage{subfigure}
\usepackage{alex}
\usepackage{mlapa}
\usepackage{mdwlist}
%\usepackage[small,it]{caption}
%\usepackage{fullpage}
\def\N{m}
\usepackage{times}

% Let's keep this title for now ....
%\icmltitlerunning{Concentration Inequalities for Hash Kernels}

% People won't know hash kernels
\icmltitlerunning{Feature Hashing for Large Scale Multitask Learning}

\begin{document}

\twocolumn[
\icmltitle{Feature Hashing for Large Scale Multitask Learning}

%\icmlauthor{}{}
% LEAVE BLANK FOR ORIGINAL SUBMISSION
%
% The author names and address list should only appear in the accepted version.
\icmlauthor{Kilian Weinberger}{kilian@yahoo-inc.com}
\icmlauthor{Anirban Dasgupta}{anirban@yahoo-inc.com}
\icmlauthor{John Langford}{jl@hunch.net}
\icmlauthor{Alex Smola}{alex@smola.org}
\icmlauthor{Josh Attenberg}{josh@cis.poly.edu}
\icmladdress{Yahoo! Research, 2821 Mission College Blvd., Santa Clara, CA 95051 USA}

\icmladdress{{\bf Keywords}: kernels, concentration inequalities, document classification, classifier personalization, multitask learning}
\vskip 0.3in
]

\begin{abstract}
Empirical evidence suggests that hashing is an effective strategy for dimensionality reduction and practical nonparametric estimation. In this paper we provide exponential tail bounds for feature hashing and show that the interaction between random subspaces is negligible with high probability. We demonstrate the feasibility of this approach with experimental results for a new use case --- multitask learning with hundreds of thousands of tasks.
\end{abstract}

\section{Introduction}
\label{sec:intro}


Kernel methods use inner products as the basic tool for comparisons between objects. That is, given objects $x_1,\dots, x_n \in \Xcal$ for some domain $\Xcal$, they rely on
\begin{align}
  \label{eq:kernel}
  k(x_i,x_j) := \inner{\phi(x_i)}{\phi(x_j)}
\end{align}
to compare the features $\phi(x_i)$ of $x_i$ and $\phi(x_j)$ of $x_j$ respectively. %Moreover, in the case of structure estimation, data $x$ and labels $y \in \Ycal$ are \emph{jointly} mapped via $\phi(x,y)$ into a high-dimensional feature space.




Eq.~(\ref{eq:kernel}) is often famously referred to as the \emph{kernel-trick}. It allows the use of inner products between very high
dimensional feature vectors $\phi(x_i)$ and $\phi(x_j)$ \emph{implicitly} through the definition of a positive semi-definite kernel matrix $k$
without ever having to compute a vector $\phi(x_i)$ directly. This can be particularly powerful in classification settings where the original
input representation has a non-linear decision boundary. Often, linear separability can be achieved in a  high dimensional feature space $\phi(x_i)$.
%The kernel-trick matrix $k$ scales linearly with the training set size, and avoids the cumbersome computation on $\phi(x_i)$.

%However, for example in the context of text classification, researchers have often encountered the opposite problem. The training set size can be very large, but separability of the input vectors $x$ is not particularly concerning (often because of the existence of handcrafted non-linear features). In this case there is no need to map the input vectors into a higher dimensional feature space. Instead, storing a kernel matrix is infeasible.

In practice, for example in text classification, researchers frequently encounter the opposite problem:  the original input space is almost linearly separable (often because of the existence of handcrafted non-linear features), yet, the training set may be prohibitively large in size and very high dimensional. In such a case, there is no need to map the input vectors into a higher dimensional feature space. Instead, limited memory makes storing a kernel matrix infeasible.

For this common scenario several authors have recently proposed an alternative, but highly complimentary variation of the kernel-trick, which  we refer to as the \emph{hashing-trick}: one \emph{hashes} the high dimensional input vectors $x$ into a \emph{lower} dimensional feature space $\RR^m$ with \mbox{$\phi:\Xcal\rightarrow\RR^m$}~\cite{LaLiSt07,Shietal09}. The parameter vector of a classifier can therefore live in $\RR^m$ instead of in the original input space$\RR^d$ (or in $\RR^n$ in the case of kernel matrices), where $m\ll n$ and $m\ll d$. Different from random projections, the hashing-trick preserves sparsity and introduces no additional overhead to store projection matrices.


%For this common scenario several authors have recently proposed an alternate, highly complimentary variation of the kernel-trick, which  we refer to as the \emph{hashing-trick}: One \emph{hashes} the high dimensional input vectors $x$ into a \emph{lower} dimensional feature space $\RR^m$ with \mbox{$\phi:\Xcal\rightarrow\RR^m$}~\cite{LaLiSt07,Shietal09}. The parameter vector of a classifier can therefore live in $\RR^m$ instead of in $\RR^n$ with kernel matrices or $\RR^d$ in the original input space, where $m\ll n$ and $m\ll d$. Unlike random projections, the hashing-trick strictly preserves sparsity and introduces no additional  overhead to store random vectors.


%In practice, researchers frequently encounter the opposite problem: separability of the input vectors $x$ is not particularly difficult (often because of the existence of handcrafted non-linear features), however, the size of the training set may be prohibitively large. In such a case, there is no need to map the input vectors into a higher dimensional feature space. Instead, limited memory makes storing a kernel matrix infeasible. Text classification is an example of a domain frequently limited by this problem.

To our knowledge, we are the first to provide exponential tail bounds on the canonical distortion of these hashed inner products. We also show that the hashing-trick can be particularly powerful in multi-task learning scenarios where the original feature spaces are the cross-product of the data, $\Xcal$, and the set of tasks, $U$. We show that one can use different hash functions for each task $\phi_1,\dots,\phi_{|U|}$, to map the data into one joint space with little interference. Sharing amongst the different tasks is achieved with an additional hash function $\phi_0$ that also maps into the same joint space. The hash function $\phi_0$ is shared amongst all $|U|$ tasks and allows to learn their common components. 

%Each data vector of a task $u$ is duplicated and mapped into the task-specific hash-space of $\phi_u$ and also into the joint hash-space of $\phi_0$.

%%%%%%%For this common scenario several authors have recently proposed an alternative, but highly complimentary variation of the kernel-trick, which  we refer to as the \emph{hashing-trick}: One \emph{hashes} the high dimensional input vectors $x$ into a \emph{lower} dimensional feature space $\RR^m$ with \mbox{$\phi:\Xcal\rightarrow\RR^m$}~\cite{LaLiSt07,Shietal09}. The parameter vector of a classifier can therefore live in $\RR^m$ instead of in $\RR^n$ with kernel matrices or $\RR^d$ in the original input space, where $m\ll n$ and $m\ll d$. Different from random projections, the hashing-trick strictly preserves sparsity and introduces no additional  overhead to store random vectors.
%%%%%%%
%%%%%%%
%%%%%%%To our knowledge, we are the first to provide exponential tail bounds on the canonical distortion of these hashed inner products. We also show that the hashing-trick can be particularly powerful in multi-task learning scenarios where the original feature spaces are the cross-product of the data $\Xcal$ and the set of tasks $U$. We show that one can use different hash functions for each task $\phi_1,\dots,\phi_{|U|}$ to map the data into one joint space with little interference.

%Scalability is an increasing concern within many areas of machine learning. Recent years have witnessed an explosion of data set sizes, often in multi-class or multi-user settings~\cite{netflix}. A common problem with large data sets are the millions of features and parameters that should ideally be stored in the RAM of a single computer. In this paper we investigate the approach of feature- and parameter-hashing~\cite{LaLiSt07,GanchevDredze08,Shietal09} to reduce the memory footprint and improve efficiency for collaborative and multitask learning.

While many potential applications exist for the hashing-trick, as a particular case study we focus on collaborative email spam filtering. In this scenario, hundreds of thousands of users collectively label emails as \emph{spam} or \emph{not-spam}, and each user expects a personalized classifier that reflects their particular preferences. Here, the set of tasks, $U$, is the number of email users (this can be very large for open systems such as \emph{Yahoo Mail}\texttrademark or \emph{Gmail}\texttrademark), and the feature space spans the union of vocabularies in multitudes of languages.

%While many potential applications exist for the hash-based dimensionality reduction presented here, as a particular case study we focus on collaborative email spam filtering. In this scenario, hundreds of thousands of users collectively label emails as \emph{spam} or \emph{not-spam}, and each user expects a personalized classifier that reflects their particular preferences. Here, the set of tasks, $U$, is the number of email users (this can be very large for open systems such as \emph{Yahoo Mail}\texttrademark or \emph{Gmail}\texttrademark), and the feature space spans the union of vocabularies in multitudes of languages.

%Large webmail providers (such as \emph{Yahoo Mail}\texttrademark or \emph{Gmail}\texttrademark) need to deliver Billions of emails per day and therefore can only allocate very little cpu time per incoming email. Ideally, an incoming email is classified within a few milliseconds.

%In this scenario, hashing can help in several ways: 1. A hash-function that maps arbitrary strings to indices renders a dictionary unnecessary and frees up a large chunk of memory to store more classifier parameters.  2. In large-scale text classification problems it is usually necessary, in order to save memory, to ignore infrequent words. In the mail-spam scenario this can be fatal, as spammers utilize this trick by maliciously misspelling words and therefore creating highly infrequent but spam-typical tokens that ``fall under the radar'' of conventional classifiers. If all words are hashed into a finite-sized feature vector, infrequent but class-indicative tokens get a chance to contribute to the classification outcome. 3. Personalization for hundreds of thousands of users is costly and impractical because the parameters for every single user cannot be stored in memory and therefore must be loaded from disk during test time. We propose a hashing approach where all user-specific classifier parameters are hashed into a single weight vector kept in memory.

%Although there are many potential applications, as a particular case study we will focus on  collaborative email spam filtering, where hundred thousands of users collectively label emails as \emph{spam} or \emph{not-spam} and each expects a personalized classifier that reflects their particular preferences.
%This problem arises naturally on large webmail providers (such as \emph{Yahoo Mail}\texttrademark or \emph{Gmail}\texttrademark). These providers have to deliver Billions of emails per day and therefore can only allocate very little cpu time per incoming email. Ideally, an incoming email must be classified within the order of a few milliseconds, which requires all user-specific parameters to be already stored in the server's memory.
%In this scenario, hashing can help in several ways: 1. A hash-function that maps arbitrary strings to indices renders a dictionary unnecessary and frees up a large chunk of memory to store more classifier parameters.  2. In large-scale text classification problems it is usually necessary, in order to save memory, to ignore infrequent words. In the mail-spam scenario this can be fatal, as spammers utilize this trick by maliciously misspelling words and therefore creating highly infrequent tokens that ``fall under the radar'' of conventional classifiers. If all words are hashed into a finite-sized feature vector, infrequent but class-indicative tokens get a fair chance to contribute to the classification outcome. 3. Personalization for hundred thousands of users is costly and impractical because the parameters for every single user cannot be stored in memory and therefore must be loaded from disk during test time. We propose a hashing scenario where we hash all user-specific classifier into a single weight vector that is constantly kept in memory. We show that by using different hash functions for different users we can keep the interference between different users very small with high probability and obtain convincing empirical results.


%We show that by using different hash functions for different users we can keep the interference between different users very small with high probability and obtain convincing empirical results.

%This paper makes four main contributions: 1.~In section~\ref{sec:hashkernels} we introduce specialized hash functions with unbiased inner-products that are directly applicable to a large variety of kernel-methods. 2.~In section~\ref{sec:analysis} we provide exponential tail bounds that help explain why hashed feature vectors have frequently resulted in surprisingly strong empirical results. 3.~Additionally in section~\ref{sec:analysis} we go on to show that the interference between independently hashed subspaces is negligible with high probability, a property permitting large-scale multi-task learning in a very compressed space. 4.~In section~\ref{sec:results}  we introduce collaborative email-spam filtering as a novel application for hash representations and provide experimental results on large-scale real-world spam data sets.

This paper makes four main contributions: 1.~In section~\ref{sec:hashkernels} we introduce specialized hash functions with unbiased inner-products that are directly applicable to a large variety of kernel-methods. 2.~In section~\ref{sec:analysis} we provide exponential tail bounds that help explain why hashed feature vectors have repeatedly lead to, at times surprisingly, strong empirical results. 3.~In the same chapter we show that the interference between independently hashed subspaces is negligible with high probability, which allows large-scale multi-task learning in a very compressed space. 4.~In section~\ref{sec:results}  we introduce collaborative email-spam filtering as a novel application for hash representations and provide experimental results on large-scale real-world spam data sets.


%For convenience, we adapt the naming convention of~\cite{Shietal09} and define the hash functions from a \emph{hash-kernel} perspective. Although in this paper we often take the viewpoint of the primal-space, and therefore make no explicit use of kernels, all equations are expressable in terms of kernels.


\section{Hash Functions}
\label{sec:hashkernels}



We introduce a variant on the hash kernel proposed by
\cite{Shietal09}. This scheme is modified through the introduction of a \emph{signed}
sum of hashed features whereas the original hash kernels use an
\emph{unsigned} sum. This modification leads to an unbiased estimate, which we demonstrate and further utilize in the following section.

\begin{definition}
Denote by $h$ a hash function $h:\NN\rightarrow \cbr{1,\dots,\N}$. Moreover, denote by $\xi$ a hash function $\xi:\NN\rightarrow\cbr{\pm 1}$. Then for vectors ${x},{x}'\in \ell_2$ we define the hashed feature map $\phi$ and the corresponding inner product as
  \begin{align}
    \phi^{(h,\xi)}_i(x) & = \hspace{-2mm} \sum_{j: h(j) = i} \hspace{-2mm}
    \xi(j) x_j \\
    \text{ and }
    \inner{x}{x'}_\phi & := \inner{\phi^{(h,\xi)}(x)}{\phi^{(h,\xi)}(x')}.
  \end{align}\label{def:hash}
\end{definition}
\vspace{-3mm}
%%%%%%%%KQW
%%%%%%%%\begin{definition}
%%%%%%%%Denote by $h$ a hash function on $\NN$ with a keyspace of $\N$ values. Moreover, denote by $\xi$ a $\cbr{\pm 1}$ valued hash function on $\NN$. Then for vectors $\bf{x},\bf{x}'\in \ell_2$ we define the hashed feature map $\phi$ and the corresponding inner product as
%%%%%%%%  \begin{align}
%%%%%%%%    \phi^{(h,\xi)}_i(x) & = \hspace{-2mm} \sum_{j: h(j) = i} \hspace{-2mm}
%%%%%%%%    \xi(i) x_i \\
%%%%%%%%    \text{ and }
%%%%%%%%    \inner{x}{x'}_\phi & := \inner{\phi^{(h,\xi)}(x)}{\phi^{(h,\xi)}(x')}.
%%%%%%%%  \end{align}
%%%%%%%%\end{definition}
%
Although the hash functions in definition~\ref{def:hash} are defined over the natural numbers $\NN$, in practice we often consider hash functions over arbitrary strings. These are equivalent, since each finite-length string can be represented by a unique natural number.

Usually, we abbreviate the notation $\phi^{(h,\xi)}(\cdot)$ by just
$\phi(\cdot)$. Two hash functions $\phi$ and $\phi'$ are different
when $\phi = \phi^{(h,\xi)}$ and $\phi'= \phi^{(h',\xi')}$ such that
either $h'\neq h$ or $\xi \neq \xi'$.  The purpose of the binary hash
$\xi$ is to remove the bias inherent in the hash kernel of
\cite{Shietal09}.

In a multi-task setting, we obtain instances in combination with tasks, $(x,u)\in \Xcal\times U$.
We can naturally extend our definition~\ref{def:hash} to hash pairs, and will write $\phi_u(x)=\phi((x,u))$.



\section{Analysis}
\label{sec:analysis}
The following section is dedicated to theoretical analysis of hash
kernels and their applications. In this sense, the present paper continues
 where~\cite{Shietal09} falls short: we prove exponential tail
bounds. These bounds hold for general hash kernels, which we later
apply to show how hashing enables us to do large-scale multitask learning efficiently. We start with a simple lemma about the bias and variance of the hash kernel. The proof of this lemma appears in
appendix~\ref{proof:mean}.

\begin{lemma}
  \label{th:meanvar}
The hash kernel is unbiased, that is $\Eb_\phi[\inner{x}{x'}_\phi] =
\inner{x}{x'}$. Moreover, the variance is
$\sigma^2_{x,x'} = \frac{1}{\N}\left(\sum_{i\neq j} x_i^2 {x_j'}^2 + x_i {x}_i' x_j {x}_j'  \right)$,
and thus, for $\|x\|_2 = \|x'\|_2 = 1$, $\sigma_{x,x'}^2 = O\left(\frac{1}{\N}\right)$.
\end{lemma}
%
%%%KQW
%%%%This suggests that typical values of the hash kernel should be concentrated within $O(\sigma)$ of the typical value. Clearly, Chebyshev's inequality implies that at least half of all observations are within a range of $\sqrt{2} \sigma$. We will use this fact in the construction of an exponential tail bound using Talagrand's convex distance inequality.

This suggests that typical values of the hash kernel should be concentrated within $O(\frac{1}{\sqrt{\N}})$ of the target value. We use Chebyshev's inequality to show that half of all observations are within a range of $\sqrt{2}\sigma$. This, together with Talagrand's convex distance inequality, enables us to construct exponential tail bounds.

%This suggests that typical values of the hash kernel should be concentrated within $O(\sigma)$ of the typical value. %In section~\ref{sec:analysis}
%In the following we will use Chebyshev's inequality to show that half of all observations are within a range of $\sqrt{2}\sigma$. This, together with Talagrand's convex distance inequality, will enable us the construction of an exponential tail bound.

%Chebyshev's inequality implies that at least half of all observations are within a range of $\sqrt{2} \sigma$.


\subsection{Concentration of Measure Bounds}
In this subsection we show that under a hashed feature-map the length
of each vector is preserved with high probability.
Talagrand's inequality~\cite{Ledoux01} is a key tool for the proof of
the following theorem (detailed in the appendix~\ref{sec:proofs}).
\begin{theorem}
  \label{th:key}
  Let $\epsilon <1$ be a fixed constant and $x$  be a given instance. Let $\eta = \frac{\|x\|_\infty}{\|x\|_2}$. Under the assumptions above, the hash kernel satisfies the following inequality
  \begin{align}
    \nonumber
    \Pr\cbr{\frac{|\nbr{x}^2_\phi - \nbr{x}_2^2|}{\nbr{x}_2^2} \geq \sqrt{2} \sigma_{x,x} + \epsilon} \leq \exp\rbr{\textstyle - \frac{\sqrt{\epsilon}}{4\eta}}.
  \end{align}
\end{theorem}
Note that an analogous result would also hold for the original hash kernel of \cite{Shietal09}, the only modification being the associated bias terms. The above result can also be utilized to show a concentration
bound on the inner product between two general vectors $x$ and $x'$.

\begin{corollary}
\label{cor:inner}
For two vectors $x$ and $x'$, let us define
\begin{align*}
\sigma&:=\max(\sigma_{x,x}, \sigma_{x',x'}, \sigma_{x-x',x-x'})\\
\eta&:= \min\left(\frac{\|x\|_\infty}{\|x\|_2},\frac{\|x'\|_\infty}{\|x'\|_2},\frac{\|x-x'\|_\infty}{\|x-x'\|_2} \right).
\end{align*}
 Also let $\Delta = \nbr{x}^2 + \nbr{x'}^2 + \nbr{x - x'}^2$. Under the assumptions above, we have that
\begin{align*}
&\Pr\sbr{|\inner{x}{x'}_{\phi}\!-\! \inner{x}{x'}|\! >\! (\sqrt{2}\sigma\! +\! \epsilon) \Delta/2}\!\nonumber \!<\! 3e^{- \frac{\sqrt{\epsilon}}{4\eta}}.
\end{align*}
\end{corollary}
% Note that we have a weaker (additive error) bound for the inner product $\inner{x}{x'}$ than for $\inner{x}{x}$.
%The bound shows that the canonical distortion of the hash embedding (i.e. the ratio between $\nbr{x}^2_2$ and $\nbr{x}_\phi^2$) is bounded by $\sqrt{2} \sigma + \epsilon$.
The proof for this corollary can be found in appendix~\ref{sec:innerproof}. We can also extend the bound in Theorem~\ref{th:key} for the maximal canonical distortion over large sets of distances between
vectors as follows:
\begin{corollary}
  \label{cor:union}
  Denote by $X = \cbr{x_1, \ldots, x_n}$ a set of vectors which
  satisfy $\nbr{x_i - x_j}_\infty \leq \eta \nbr{x_i - x_j}_2$ for all
  pairs $i, j$. In this case with probability $1 - \delta$ we have for
  all $i,j$
  \begin{align*}
    \frac{|\nbr{x_i-x_j}_\phi^2 - \nbr{x_i-x_j}_2^2|}{\nbr{x_i-x_j}_2^2}\leq \sqrt{\frac{2}{\N}} + 64 \eta^2 \log^2 \textstyle \frac{n}{2\delta}.
  \end{align*}
\end{corollary}
This means that the number of observations $n$ (or correspondingly the size of the un-hashed kernel matrix) only enters \emph{logarithmically} in the
analysis.
%
\begin{proof}
  We apply the bound of Theorem~\ref{th:key} to each distance
  individually. Note the bound $\sigma^2 \leq \frac{1}{\N}$ for all
  normalized vectors.  Also, since we have $\frac{n(n-1)}{2}$ pairs of
  distances the union bound yields a corresponding factor. Solving
  \mbox{$\delta \geq {\textstyle \frac{n (n-1)}{2}}
  e^{-\frac{\sqrt{\epsilon}}{4 \eta}}$} for $\epsilon$ and easy
  inequalities proves the claim.
\end{proof}
\vspace{-3mm}
%

\subsection{Multiple Hashing}
Note that the tightness of the union bound in Corollary~\ref{cor:union} depends crucially on the
magnitude of $\eta$. In other words, for large values of $\eta$, that
is, whenever some terms in $x$ are very large, even a single collision
can already lead to significant distortions of the embedding. This
issue can be amended by trading off sparsity with variance. A vector of unit
length may be written as $(1, 0, 0, 0, \ldots)$, or as $\left(\frac{1}{\sqrt{2}},
\frac{1}{\sqrt{2}}, 0, \ldots\right)$, or more generally as a vector with $c$
nonzero terms of magnitude $c^{-\frac{1}{2}}$. This is relevant, for
instance whenever the magnitudes of $x$ follow a known pattern,
e.g.\ when representing documents as bags of words since we may simply
hash frequent words several times. The following corollary gives an
intuition as to how the confidence bounds scale in terms of the
replications:
%
\begin{lemma}
   \label{lem:rep}
  If we let  $x' = \frac{1}{\sqrt{c}}(x, \ldots, x)$ then:
\begin{enumerate}
  \item It is norm preserving: $\nbr{x}_2 = \nbr{x'}_2.$
  \item It reduces component magnitude by $\frac{1}{\sqrt{c}} = \frac{\nbr{x'}_\infty}{\nbr{x}_\infty}.$
  \item Variance increases to $\sigma^2_{x', x'}\! =\! \frac{1}{c}\sigma^2_{x,x}\!+\! \frac{c-1}{c}2\nbr{x}_2^4.$
\end{enumerate}
\end{lemma}
Applying Lemma~\ref{lem:rep} to Theorem~\ref{th:key}, a large magnitude can be decreased at
the cost of an increased variance.

\subsection{Approximate Orthogonality}

For multitask learning, we must learn a different parameter vector for
each related task. When mapped into the same hash-feature space
we want to ensure that there is little interaction between the
different parameter vectors. Let $U$ be a set of different tasks,
$u\in U$ being a specific one.  Let $w$ be a combination of the
parameter vectors of tasks in $U\setminus \{u\}$. We show that for any
observation $x$ for task $u$, the interaction of $w$ with $x$ in the
hashed feature space is minimal.  For each $x$, let the image of $x$
under the hash feature-map for task $u$ be denoted as $\phi_u(x)=\phi^{(\xi, h)}((x,u))$.
%
%In some situations it is desirable to obtain bounds on the
%interference between different parameter vectors. %For instance, in the parameter compression scenario we want to ensure that by storing several parameter vectors $w_i$ in the compressed version, optimizing over one $w_i$ does not degrade the other $w_j$ by too much.
% KQW: I think it is better to go with the personalization variant.
%In the personalization setting,
%We analyze this situation as follows. For a given vector $w$ for which
%$\inner{w}{\phi^h(x,i)}$ generates desirable estimates, we bound the
%value of $\inner{w}{\phi^h(x,j)}$ for $j \neq i$.

\begin{theorem}
  \label{th:ortho}
  Let $w \in \RR^\N$ be a parameter vector for tasks in $U\setminus \{u\}$. In this case the value of the inner product
  $\inner{w}{\phi_u(x)}$ is
  bounded by
  \begin{align}
    \nonumber
    \Pr\cbr{\abr{\inner{w}{\phi_u(x)}} > \epsilon}
     \leq 2 e^{
      -\frac{\epsilon^2/2}{\N^{-1} \nbr{w}_2^2 \nbr{x}_2^2 + \epsilon
        \nbr{w}_\infty \nbr{x}_\infty/3}}
  \end{align}
\end{theorem}
\begin{proof}
  We use Bernstein's inequality~\cite{Bernstein46}, which states that for independent random variables $X_j$, with $\Eb\sbr{X_j} = 0$, if $C>0$ is such that $|X_j|\leq C$, then
\begin{equation}
	\Pr\sbr{\sum_{j=1}^n\! X_j\!>\!t}\!\leq\! \exp{\!\left(\!-\frac{t^2/2}{\sum_{j=1}^n\mathbf{E}\sbr{X_j^2}+Ct/3}\!\right)}.	\label{def:Bernstein}
\end{equation}

%Choosing a random value of $i$ is
%  equivalent to picking a random hash function pair $h, \sigma$ and
%  computing $\sum_i x_i \xi(i) w_{h(i)}$.

We have to compute the concentration property of \\$\inner{w}{\phi_u(x)}=\sum_j x_j \xi(j) w_{h(j)}$.  Let $X_j = x_j \xi(j)w_{h(j)}$. By the definition of $h$ and $\xi$, $X_j$ are independent. Also, for each $j$, since $w$ depends only on the hash-functions for $U\setminus\{u\}$, $w_h(j)$ is independent of $\xi(j)$. Thus, $\Eb[X_j] = \Eb_{(\xi, h)}\sbr{x_j \xi(j) w_{h(j)}} = 0$. For each $j$, we also have $|X_j| < \nbr{x}_\infty
  \nbr{w}_\infty=:C$. Finally, $\sum_j \Eb[X_j^2]$ is given by
  \begin{align*}
    \Eb\sbr{\sum_j (x_j \xi(j) w_{h(j)})^2} = {\textstyle \frac{1}{\N}}
    \sum_{j,\ell} x_j^2 w_\ell^2 = {\textstyle \frac{1}{\N}} \nbr{x}_2^2 \nbr{w}_2^2
  \end{align*}
  The claim follows by plugging both terms and $C$ into the Bernstein inequality~(\ref{def:Bernstein}).
\end{proof}
%

Theorem~\ref{th:ortho} bounds the influence of unrelated tasks with any particular instance.
In section~\ref{sec:results} we demonstrate the real-world applicability with empirical results on a large-scale multi-task learning problem.



%% {\bf KQW: We could cut the section here, as Theorem 6 is now over x and \emph{all other} weight vectors Cor 7 is now slightly redundant.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Theorem~\ref{th:ortho} allows us to bound the interference between
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%different weight vectors. However, what we need is a combined bound
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%when storing all vectors jointly.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Denote by $\bar{w} = \sum_{i=1}^l w_i$ such a joint vector, where $w_i$ is the weight vector for task $i$. If
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%$\nbr{w_i}_2 \leq 1$ for all $i$ it follows that $\nbr{\bar{w}}_2 \leq
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\sqrt{l}$. For all inequalities to hold simultaneously we bound each
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%interaction individually and sum over all cases. This yields $l(l-1)$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%terms. Moreover, the overall error can be bounded by tightening the
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%bound for individual terms to
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%$\epsilon/l$. Solving the bound of Theorem~\ref{th:ortho} for a given
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%failure probability we have the following corollary.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\begin{corollary}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  The interference from storing $l$ weight vectors jointly is
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  bounded with probability $1-\delta$ by
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  \begin{align*}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    l^2 \nbr{w}_\infty \nbr{x}_\infty \log l m /\delta
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    \sbr{1 + \sqrt{1 + \frac{2 l}{\N} \frac{\nbr{w}_2^2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%          \nbr{x}_2^2}{\log l m/\delta}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  \end{align*}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\end{corollary}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%This bound is very conservative since it assumes that the $\ell_2$ and
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%the $\ell_\infty$ norm both grow $O(l)$. A tighter bound could be
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%obtained by obtaining an inner-product analog of
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Corollary~\ref{cor:union}.%\alex{I think we can do that at a later  stage. After all, we're  starting to run out of space. Yes, the $l$-dependency is UGLY and we  could reduce it to $\log l$ by hashing down the parameter vector  $w$.}

%\section{Application to text documents}
%\label{sec:zipf}

\section{Applications}

The advantage of feature hashing is that it allows for significant
storage compression for parameter vectors: storing
$w$ in the raw feature space na\"ively requires $O(d)$ numbers, when $w \in
\RR^d$. By hashing, we are able to reduce this to $O(\N)$ numbers while
avoiding costly matrix-vector multiplications common in
Locality Sensitive Hashing. In addition, the sparsity of the resulting vector is preserved.%: the number of non-zero entries never increases.

The benefits of the hashing-trick leads to applications in almost all areas of machine learning and beyond. In particular, feature hashing is extremely useful whenever large numbers of parameters with redundancies need to be stored within bounded memory capacity.
%In this scenario, hashing can help in several ways:   2. In large-scale text classification problems it is usually necessary,
%in order to save memory, to ignore infrequent words. In the mail-spam scenario this can be fatal, as spammers utilize this trick by
%maliciously misspelling words and therefore creating highly infrequent but spam-typical tokens that   3. Personalization for hundreds of thousands
%of users is costly and impractical because the parameters for every single user cannot be stored in memory and therefore must be loaded from disk
%during test time. We prop


\paragraph{Personalization}
\label{par:personalization}
%A natural application for feature hashing is found in multitask learning. 
\cite{Daume07} introduced a very simple but strikingly effective method for multitask learning. Each task updates its very specific own (local) weights  and a set of common (global) weights that are shared amongst all tasks. Theorem~\ref{th:ortho} allows us to hash all these multiple classifiers into one feature space with little interaction.   
%To illustrate, we adopt the terminology of classifier personalization: input refer to tasks as
%we adopt the terminology of classifier personalization within the context of email-spam filtering.
%
To illustrate, we explore this setting in the context of spam-classifier personalization.

Suppose we have thousands of users $U$ and want to perform related but not identical classification tasks for each of the them. %A typical example is the construction of email spam filters on large-scale webmail servers. Here,
Users provide labeled data by marking emails as
\emph{spam} or \emph{not-spam}. Ideally, for each user $u\in U$, we
want to learn a predictor $w_u$ based on the data of that user
solely. However, webmail users are notoriously lazy in labeling emails
and even those that do not contribute to the training data
expect a working spam filter. Therefore, we also need to learn an
additional global predictor $w_0$ to allow data sharing amongst all
users.

Storing all predictors $w_i$ requires $O(d\times (|U|+1))$ memory. In a task like collaborative spam-filtering, $|U|$, the number of users can be in the hundreds of thousands and the size of the vocabulary is usually in the order of millions. The na\"ive way of dealing with this is to eliminate all infrequent tokens. However, spammers target this memory-vulnerability by maliciously misspelling words and thereby creating highly infrequent but spam-typical tokens that ``fall under the radar'' of conventional classifiers. Instead, if all words are hashed into a finite-sized feature vector, infrequent but class-indicative tokens get a chance to contribute to the classification outcome. Further, large scale spam-filters (e.g. \emph{Yahoo Mail}\texttrademark or \emph{GMail}\texttrademark) typically have severe memory and time constraints, since they have to handle billions of emails per day. To guarantee a finite-size memory footprint we hash all weight vectors $w_0,\dots,w_{|U|}$ into a joint, significantly smaller, feature space $\RR^m$ with different hash functions $\phi_0,\dots,\phi_{|U|}$. The resulting hashed-weight vector $w_h\in\RR^m$ can then be written as:
\begin{equation}
	w_h = \phi_0 (w_0) + \sum_{u\in U} \phi_u(w_u).\label{eq:hybriddef}
\end{equation}
Note that in practice the weight vector $w_h$ can be learned directly in the hashed space. All un-hashed weight vectors never need to be computed. Given a new document/email $x$ of user $u\in U$, the prediction task now consists of calculating $\inner{\phi_0(x) + \phi_u(x)}{w_h}$. Due to hashing we have two sources of error -- distortion $\epsilon_d$ of the hashed inner products and the interference with other hashed weight vectors $\epsilon_i$. More precisely:
\begin{equation}
\inner{\phi_0(x)+\phi_u(x)}{w_h}=\inner{x}{w_0+w_u}+\epsilon_d+\epsilon_i.
\end{equation}

%\begin{align}
%\inner{\phi_u(x)}{w_h} &=&  \inner{\phi_u(x)}{\phi_0(w_0)+ \phi_u(w_u)} \\
%  &+& \hspace{-2ex}\sum_{v\in U, v\neq u}\hspace{-2ex}\inner{\phi_u(x)}{\phi_v(w_v)}
%\end{align}

%For this to work in practice we have to show that
%\begin{equation}
%	\inner{\phi_u(x)}{w_h}\approx  x^\top (w_0+w_u).
%\end{equation}
%Intuitively, the first term captures the real prediction for $x$ that is obtained by the combination of the global and personalized predictor, and the second term
%corresponds to the interference that occurs due to putting all predictors in the hash-space. We will apply our bounds on hash-kernels in this setting to show that
% the above method of personalization has reasonable guarantees.
%%%%For brevity, denote, $\tilde{w} = w_0 + w_u$. We know that
%%%%\begin{align*}
%%%%2\inner{\phi_u(x)}{\phi_u(\tilde{w})} =   \|\phi_u(x)\|_2^2 +\| \phi_u(\tilde{w})\|_2^2 - \|\phi_u(x - \tilde{w})\|_2^2,
%%%%\end{align*}
%%%%
%%%%Using the results of Theorem~\ref{th:key} for each of the terms,
%%%%we have that with probability $1 - 3\exp(-\sqrt{\epsilon}/4\eta)$,
%%%%\begin{align*}
%%%%& | 2\inner{\phi_u(x)}{\phi_u(\tilde{w})} - 2\inner{x}{\tilde{w}} |  \leq | \nbr{\phi_u(x)}^2 - \nbr{x}^2 | \\
%%%%& + | \nbr{\phi_u(\tilde{w})}^2 - \nbr{\tilde{w}}^2| + | \nbr{\phi(x - \tilde{w})}^2 - \nbr{x - \tilde{w}}^2 | \\
%%%%& \leq  (\sqrt{2}\sigma +  \epsilon) ( \nbr{x}^2 + \nbr{\tilde{w}}^2 + \nbr{x - \tilde{w}}^2 )
%%%%\end{align*}
%%%%where $\sigma = \max(\sigma_{x,x}, \sigma_{\tilde{w},\tilde{w}}, \sigma_{x-\tilde{w},x-\tilde{w}}) = O\left(\frac{1}{\N}\right)$.

The interference error consists of all collisions between $\phi_0(x)$ or $\phi_u(x)$ with hash functions of other users,
\begin{equation}
\epsilon_i\!=\hspace{-2ex}\sum_{v\in U, v\neq 0}\hspace{-2ex}\inner{\phi_0(x)}{\phi_v(w_v)}+\hspace{-2ex}\sum_{v\in U, v\neq u}\hspace{-2ex}\inner{\phi_u(x)}{\phi_v(w_v)}.\label{def:epsiloni}
\end{equation}
To show that $\epsilon_i$ is small with high probability we can apply Theorem~\ref{th:ortho} twice, once for each term of (\ref{def:epsiloni}). We consider each user's classification to be a separate task, and since $\sum_{v\in U, v\neq 0}w_v$ is independent of the hash-function $\phi_0$, the conditions of Theorem~\ref{th:ortho} apply with $w = \sum_{v\neq 0} w_v$  and we can employ it to bound the second term, $\sum_{v\in U, v\neq 0}\inner{\phi_u(x)}{\phi_u(w_v)}$. The second application is identical except that all  subscripts  ``0'' are substituted with ``u''. For lack of space we do not derive the exact bounds.

The distortion error occurs because each hash function that is utilized by user $u$ can self-collide:
\begin{equation}
 \epsilon_d=\!\sum_{v\in\{u,0\}}\! |\inner{\phi_v(x)}{\phi_v(w_v)}-\inner{x}{w_v}|.
\end{equation}
To show that $\epsilon_d$ is small with high probability, we apply Corollary~\ref{cor:inner} once for each possible values of $v$.


In section~\ref{sec:results} we show experimental results for this
setting.  The empirical results are stronger than the theoretical
bounds derived in this subsection---our technique outperforms a single
global classifier on hundreds thousands of users.  In the same section we provide 
an intuitive explanation for these strong results. 


\paragraph{Massively Multiclass Estimation}
We can also regard massively multi-class classification as a multitask problem, and apply feature hashing in a way similar to the personalization setting. Instead of using a different hash function for each user, we use a different hash function for each class.  %Similarly, we can also use the trick in~(\ref{eq:jointhashing}) and hash the weight- or data vectors jointly with their class-labels.

\cite{Shietal09} apply feature hashing to problems with a high number
of categories. They show empirically that \emph{joint} hashing of the
feature vector $\phi(x,y)$ can be efficiently achieved for problems
with millions of features and thousands of classes.
%
%%%%%The basic idea is as follows: for sparse vectors $\phi(x_i)$ define
%%%%%$\phi(x,y) = e_y \times \phi(x_i)$. That is, we take the outer product between
%%%%%the unit vector $e_y$ and the feature map $\phi(x_i)$. For $c$ classes,
%%%%%this increases the storage requirements by $c$. This is reduced via
%%%%%the construction
%%%%%\begin{align}
%%%%%  \phi_i^h(x,y) = \sum_{j:h(j,y) = i} \xi(i) x_i.
%%%%%\end{align}
%%%%%In other words, all we do is jointly hash the coordinate $j$ and the
%%%%%label \emph{value} $y$ when computing $\phi^h(x,y)$. This allows one
%%%%%to approximate a $10^6 \cdot 10^3$ matrix in 2GB.

\paragraph{Collaborative Filtering}

Assume that we are given a very large sparse matrix $M$ where the entry $M_{ij}$ indicates what action user $i$ took on instance $j$. A common example for actions and instances is
user-ratings of movies~\cite{netflix}. A successful method for finding common factors amongst users and instances for predicting unobserved actions is to factorize
$M$ into $M=U^\top W$. If we have millions of users performing millions of actions, storing $U$ and $W$ in memory quickly becomes infeasible.
%100 dimensions for 100 million users would require over 40GB of storage which is infeasible with current computers.
Instead, we may choose to compress the matrices $U$ and $W$ using hashing. For $U, W \in \RR^{n \times d}$ denote by $u, w \in \RR^\N$ vectors with
\begin{align}
  \nonumber
  u_{i} = \hspace{-2ex} \sum_{j,k : h(j,k) = i} \hspace{-2ex} \xi(j,k) U_{jk}
  \text{ and }
  w_{i} = \hspace{-2ex} \sum_{j,k : h'(j,k) = i} \hspace{-2ex} \xi'(j,k) W_{jk}.
\end{align}
where $(h,\xi)$ and $(h',\xi')$ are independently chosen hash
functions.  This allows us to approximate matrix elements $M_{ij} =
[U^\top W]_{ij}$ via
\begin{align*}
  M^\phi_{ij} := \sum_k \xi(k,i) \xi'(k,j) u_{h(k,i)} w_{h'(k,j)}.
\end{align*}
This gives a compressed vector representation of $M$ that can be efficiently stored.
%The rationale behind is that we may write $M_{ij} =
%\inner{\phi(i)}{\psi(j)}$ where $\phi(i) = e_i \times (U_{1i}, \ldots,
%U_{di})$ and correspondingly $\psi(j) = e_j \times (W_{1i}, \ldots,
%W_{dj})$. Given this representation we may apply hashing to obtain a
%compressed vector representation.

\section{Results}
\label{sec:results}

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

\begin{figure}[t!]
  \centering
  \includegraphics[width=0.5\textwidth]{figures/schema}
  \caption{The hashed personalization summarized in a schematic
    layout. Each token is duplicated and one copy is individualized (e.g. by concatenating each word with a unique user identifier). Then, the global hash function maps all tokens  into a low dimensional feature space where the document is classified.}
  \label{fig:schema}
\vspace{-2ex}
\end{figure}
%

For all experiments in this paper, we used the Vowpal Wabbit implementation\footnote{{http://hunch.net/$\sim$vw/}} of stochastic gradient descent on a square-loss.
In the mail-spam literature the misclassification of \emph{not-spam} is considered to be much more harmful than misclassification of \emph{spam}. %In other words, spam catch-rates are only meaningful if the classifier hardly ever misclassify \emph{not-spam} as \emph{spam}.
%To ensure a comparison in the relevant spectrum of the ROC curve, we
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$
%
%%%
%Note that in practice these many hash functions do not require any additional over-head, as all of them can easily be implemented as permutations of a single function $\phi$.
Our implementation of the  personalized hash functions is illustrated in Figure~\ref{fig:schema}. To obtain a personalized hash function $\phi_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.
%%%
%

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 \emph{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)\footnote{As part of our data sharing agreement, we agreed not to include absolute classification error-rates.}.
%
%%% KQW: I think we have said this before
%The setting of email-spam filtering is particularly interesting for a variety of reasons: 1. The majority of users label much fewer emails than are necessary to train a purely local (per user) classifier. 2. The definition of spam and not-spam is subjective and differs largely between users. A purely global (one for all) classifier is therefore non-optimal. 3. Time and space constraints during test-time make it imperative that all learned parameters are compact enough to be stored in memory.
%As a global classifier for all users is not sufficient, but local classifiers require too much memory and training data, we introduce a hybrid architecture that is based on feature hashing.
%Each tokenized input email ${\bf x}$ is duplicated as ${\bf x}_l$, where each token is personalized through concatenation with a unique user-id string.

Figure~\ref{fig:global_results} 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.

\begin{figure}[t]
  \centering
  \includegraphics[width=\columnwidth]{figures/global_results}
  \caption{The decrease of uncaught spam over the baseline classifier averaged over all users. The classification threshold was chosen to keep the not-spam misclassification fixed at $1\%$. The hashed global classifier (\emph{global-hashed}) converges relatively soon, showing that the distortion error $\epsilon_d$ vanishes. The personalized classifier results in an average improvement of up to $30\%$. }
  \label{fig:global_results}
\vspace{-2ex}
\end{figure}
%
The \emph{global-hashed} curve represents the relative spam catch-rate of the global classifier after hashing $\inner{\phi_0(w_0)}{\phi_0(x)}$. At $m=2^{26}$ this is identical to the baseline. Early convergence at $m=2^{22}$ suggests that at this point hash collisions have no impact on the classification error and the {\em baseline} is indeed equivalent to that obtainable without hashing.

In the \emph{personalized} setting each user $u\in U$ gets her own
classifier $\phi_u(w_u)$ as well as the global classifier
$\phi_0(w_0)$.  Without hashing the feature space explodes, as the
cross product of $u=400K$ users and $n=40M$ tokens results in $16$
trillion possible unique personalized features. Figure~\ref{fig:global_results}
shows that despite aggressive hashing, personalization results in a
$30\%$ spam reduction once the hash table is indexed by $22$ bits.

\paragraph{User clustering}
One hypothesis for the strong results in Figure~\ref{fig:global_results} might originate from the non-uniform distribution of user votes --- it is possible that by 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 $\phi_u(x_u)$ is then hashed into buckets of other tokens and only
adds interference noise $\epsilon_i$ to the classification.

\begin{figure}[t!]
  \centering
  \includegraphics[width=\columnwidth]{figures/results}
  \caption{Results for users clustered by training emails. For
    example, the bucket $[8,15]$ consists of all users with eight to
    fifteen training emails. Although users in buckets with large
    amounts of training data do benefit more from the personalized
    classifier (up-to $65\%$ reduction in spam), even users that did
    not contribute to the training corpus at all obtain almost $20\%$
    spam-reduction.}
  \label{fig:figures_results}
\vspace{-2ex}
\end{figure}
%
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~\ref{fig:figures_results} shows the results on a
per-bucket basis.  We do not compare against a \emph{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 \emph{spam} and \emph{not-spam}. In
the personalized setting the individual component of user labeling is
absorbed by the local classifiers and the global classifier represents
the \emph{common} definition of spam and not-spam. In other words, the
global part of the personalized classifier obtains better
generalization properties, benefiting all users.

\section{Related Work}

A number of researchers have tackled related, albeit different
problems.
%To our knowledge, only hash kernels offer both computational
%and storage efficiency for a given dimensionality of the problem.

{\bfseries \cite{RahRec08}} use Bochner's theorem and
sampling to obtain approximate inner products for Radial Basis
Function kernels. \cite{RahRec09} extend this to sparse
approximation of weighted combinations of basis
functions. This is computationally efficient for many function
spaces. Note that the representation is
\emph{dense}.

{\bfseries \cite{LiChuHas07}} take a complementary approach: for
sparse feature vectors, $\phi(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 $\phi(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) = \inner{\phi(x)}{w}$.
%

{\bfseries \cite{Achlioptas03}} provides computationally efficient
randomization schemes for dimensionality reduction. Instead of
performing a dense $d \cdot \N$ dimensional matrix vector
multiplication to reduce the dimensionality for a vector of
dimensionality $d$ to one of dimensionality $\N$, as is required by the
algorithm of \cite{GioIndMot99}, he only requires $\frac{1}{3}$ of
that computation by designing a matrix consisting only of entries
$\cbr{-1, 0, 1}$.

%% TODO KQW: Is this really that similar?
%The work most closely related ot that presented here is the CountMin sketch of {\bfseries \cite{CorMut04}} which stores counts in a number of replicates of a hash table. This leads to good concentration inequalities for range and point queries.

{\bfseries \cite{Shietal09}} 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
\cite{Achlioptas03,GioIndMot99}.

Several additional works provide motivation for the investigation of
hashing representations.  For example, {\bfseries
  \cite{GanchevDredze08}} provide empirical evidence that the hashing-trick can be used to effectively reduce the memory footprint on
many sparse learning problems by an order of magnitude via removal of
the dictionary.  Our experimental results validate this, and show that
much more radical compression levels are achievable.  In addition,
{\bfseries \cite{LaLiSt07}} released the Vowpal Wabbit fast online
learning software which uses a hash representation similar to that
discussed here.

%Several additional works provide motivation for the investigation of hashing representations.  For example, {\bfseries  \cite{GanchevDredze08}} provide empirical evidence that the hashing approach can be used to effectively reduce the memory footprint on many sparse learning problems by an order of magnitude via removal of the dictionary.  Our experimental results validate this, and show that much more radical compression levels are achievable.  In addition, {\bfseries \cite{LaLiSt07}} released the Vowpal Wabbit fast online learning software which uses a hash representation similar to that discussed here.  Our tail inequality results provide a strong theoretical justification for this approach and suggests improvements in the way hashing should be done.
%% KQW: Sounds very nice, moved some of this into the conclusion.


\section{Conclusion}
\label{sec:conclusion}
In this paper we analyze the hashing-trick for dimensionality
reduction  theoretically and  empirically. As part of our theoretical analysis we introduce unbiased hash functions and  provide exponential tail bounds for hash kernels. These give further insight into hash-spaces and explain previously made empirical observations. We also derive that random subspaces of the hashed space are likely to not interact, which makes multitask learning with many tasks possible.

Our empirical results validate this on a real-world application within
the context of spam filtering. Here we demonstrate that
even with a very large number of tasks and features, all mapped into
a joint lower dimensional hash-space, one can obtain impressive classification results with finite memory guarantee.

%{\small
\bibliography{haschisch}
\bibliographystyle{mlapa}
%}
\begin{appendix}

\section{Mean and Variance}

\label{proof:mean}
\begin{proof} [Lemma~\ref{th:meanvar}]
  To compute the expectation we expand
\begin{equation}
    \inner{x}{x'}_\phi = \sum_{i,j} \xi(i) \xi(j) x_i x_j' \delta_{h(i), h(j)}.	
\end{equation}
Since $\Eb_\phi[\inner{x}{x'}_\phi] = \Eb_h[ \Eb_\xi[\inner{x}{x'}_\phi ]]$, taking expectations over $\xi$ we see that only the terms $i = j$ have
  nonzero value, which shows the first claim. For the variance we compute $\Eb_\phi[\inner{x}{x'}_\phi^2]$.  Expanding this, we get:
\begin{equation*}
	    \inner{x}{x'}^2_\phi = \sum_{i,j,k,l} \xi(i) \xi(j) \xi(k) \xi(l) x_i {x}_j' x_k {x}_l' \delta_{h(i), h(j)}	\delta_{h(k), h(l)}.
\end{equation*}
This expression can be simplified by noting that:
  \begin{align*}
    \Eb_\xi \sbr{\xi(i) \xi(j) \xi(k) \xi(l) } =
    \delta_{ij} \delta_{kl} + [1 - \delta_{ijkl}] ( \delta_{ik} \delta_{jl} + \delta_{il}\delta_{jk}).
  \end{align*}
Passing the expectation over $\xi$ through the sum, this allows us to
break down the expansion of the variance into two terms.
  \begin{align*}
    & \Eb_{\phi}[\inner{x}{x'}_\phi^2] = \sum_{i,k} x_i x_i' x_k x_k'
    + \sum_{i \neq j} x_i^2 {x_j'}^2 \Eb_h\sbr{\delta_{h(i),h(j)}} \\& + \sum_{i \neq j} x_i x_i' x_j x_j' \Eb_h\sbr{\delta_{h(i),h(j)}}\\
    & = \inner{x}{x'}^2 + \frac{1}{\N}\left( \sum_{i \neq j} x_i^2 {x_j'}^2 + \sum_{i \neq j} x_i x_i' x_j x_j'\right)
  \end{align*}
  by noting that $\Eb_h\sbr{\delta_{h(i),h(j)}} = \frac{1}{\N}$ for $i\neq j$. Using the fact that $\sigma^2 = \Eb_\phi[\inner{x}{x'}_\phi^2] -
  \Eb_\phi[\inner{x}{x'}_\phi]^2$ proves the claim.
\end{proof}


\section{Concentration of Measure}
\label{sec:proofs}
Our proof uses Talagrand's convex distance inequality.  We first define a weighted Hamming distance function between two hash-function $\phi$ and $\phi'$ as follows.
\begin{align*}
  d(\phi,\phi')
  = & \sup_{\nbr{\alpha}_2 \leq 1}\sum_i \alpha_i I(h(i) \neq
    h'(i) \text{ or } \xi(i) \neq \xi'(i)) \\
  = & \sqrt{|\cbr{i : h(i) \neq h'(i) \text{ or } \xi(i) \neq \xi'(i)}|}
\end{align*}
Next denote by $d(\phi,A)$ the distance between a hash function and a
set $A$ of hash functions, that is $d(\phi,A) = \inf_{\phi' \in A} d(\phi,\phi').$
In this case Talagrand's convex distance inequality \cite{Ledoux01}
holds. If $\Pr(A)$ denotes the total probability mass of the set
${A}$, then
\begin{align}
  \Pr\cbr{d(\phi,A) \geq s} \leq \sbr{\Pr(A)}^{-1} e^{-s^2/4}.\label{eq:talagrand}
\end{align}

%%% KQW Painful, but might have to go
%\begin{figure}[t!]
%  \centering
%  \includegraphics[width=0.8\columnwidth]{figures/talagrand}
%  \caption{Talagrand's inequality bounds the probability of the set of all hash functions $\bar A_s$ that are at least a distance $s$ from $A$.}
%  \label{fig:figures_talagrand}
%\end{figure}


\begin{proof}[Theorem~\ref{th:key}]
  Without loss of generality assume that $\nbr{x}_2 = 1$. We can then easily generalize to the general $x$ case. From
  Lemma~\ref{th:meanvar} it follows that the variance of
  $\nbr{x}_\phi^2$ is given by $\sigma^2_{x,x}=\frac{2}{N}[1 - \nbr{x}_4^4]$ and $E(\nbr{x}_\phi^2)=1$.

Chebyshev's inequality states that $P(|X-E(X)|\leq\sqrt{2}\sigma)\geq \frac{1}{2}$.
We can therefore denote $$A := \cbr{\phi \text{ where } \left|\nbr{x}_\phi^2 - 1\right| \leq \sqrt{2}\sigma_{x,x}}.$$
and obtain $\Pr(A)\geq \frac{1}{2}.$
%Let $\bar A_s=\cbr{\phi\ :\  d(\phi,A)\geq s}$.
From Talagrand's inequality~(\ref{eq:talagrand}) we know that $\Pr(\cbr{\phi: d(\phi,A)\geq s})\leq  2e^{-s^2/4}$.
Now assume that we have a pair of hash functions $\phi$ and $\phi'$, with $\phi' \in A$.
Let us define the difference of their hashed inner-products as $\delta := {\nbr{x}_\phi^2 - \inner{x}{x}_{\phi'}}$.
By the triangle inequality and because $\phi'\in A$, we can state that
\begin{align}
  \nonumber
  \abr{\nbr{x}_\phi^2 - 1} & \leq   \abr{\nbr{x}_\phi^2 - \inner{x}{x}_{\phi'}} +   \abr{\inner{x}{x}_{\phi'} - 1} \\
& \leq  |\delta| + \sqrt{2}\sigma.\label{eq:triangular}
\end{align}

Let us now denote the coordinate-wise difference between the hashed features as
$v_i := \phi'_i(x) - \phi_i(x).$ With this definition, we can express $\delta$ in terms of $v$:
  $ \delta  = \sum_i \phi_i(x)^2 - {\phi_i'(x)}^2=-2\inner{\phi'(x)}{v} +\|v\|_2^2.$
%\\   & ={-2 \sum_i \phi_i(x) v_i -    \sum_i v_i^2}
 % \end{align*}
By applying the Cauchy-Schwartz inequality to the inner product $\inner{\phi'(x)}{v}$, we obtain
%\begin{equation}
$|\delta| \leq 2\|\phi'(x)\|_2\|{v}\|_2+\|v\|_2^2.$
%\end{equation}
Plugging this into  (\ref{eq:triangular}) leads us to
\begin{equation}
 \abr{\nbr{x}_\phi^2 - 1} \leq 2\|\phi'(x)\|_2\|{v}\|_2+\|v\|_2^2+\sqrt{2} \sigma_{x,x}.\label{eq:combined}
\end{equation}

Next, we bound $\|v\|_2$ in terms of $d(\phi, \phi')$. To do this, expand
%\begin{equation}
$v_i = \sum_j x_j (\xi'_j \delta_{h'(j)i} - \xi_j\delta_{h(j)i}).$
%\end{equation}
As $\xi_j\in\cbr{+1,-1}$, we know that $|\xi_j-\xi_j'|\leq 2$. Further, $x_j\leq \|x\|_\infty$ and we can  write
\begin{equation}
	|v_i| \leq  2\nbr{x}_\infty\sum_j \delta_{h(j)i} + \delta_{h'(j)i}.
\end{equation}
We can now make two observations:
First note that $\sum_i \sum_j \delta_{h(j)i} + \delta_{h'(j)i}$ is at most $2t$ where $t = |\{j : h(j) \neq h'(j)\}|$. Second, from the definition of the distance function,
we get that $d(\phi, \phi') \geq \sqrt{t}$. Putting these together,
\begin{align*} \sum_i |v_i| &\leq 4\nbr{x}_\infty t \leq 4\nbr{x}_\infty d^2(\phi, \phi')\\
\|v_i\|_2^2 &=\sum_i |v_i|^2 \leq 16 \nbr{x}_\infty^2 d^4(\phi,\phi').
\end{align*}
(The last inequality holds because in the worst case all mass is concentrated in a single entry of $v_i$.)
As a next step we will express $\|\phi'(x)\|_2$ in terms of $\sigma_{x,x}$. Because $\phi'\in A$, we obtain that
\begin{equation*}
\|\phi'(x)\|_2  = \sqrt{\inner{x}{x}_{\phi'}} \leq (1 + \sqrt{2}\sigma_{x,x})^{1/2}\leq 1 + \sigma_{x,x}/\sqrt{2}.
\end{equation*}
To simplify our notation, let us define $\beta = 1 +  \sigma_{x,x}/\sqrt{2}$.
Plugging our upper bounds for $\|v\|_2$ and $\|\phi'(x)\|_2$ into~(\ref{eq:combined}) leads to
  \begin{align*}
    \abr{\nbr{x}_\phi^2\!-\! 1}\!\leq\!  8 \nbr{x}_\infty\! \beta d^2(\phi,\phi') (\beta \!+\! 2\nbr{x}_\infty\! d^2(\phi,\phi'))\! +\! \sqrt{2}\sigma.
  \end{align*}
As we have not specified our particular choice of $\phi'$, we can now
choose it to be the closest vector to $\phi$ within $A$, ie such that
$d(\phi,\phi')=d(\phi,A)$.  By Talagrand's inequality, we know that
with probability at least $1 - 2e^{-s^2/4}$ we obtain $d(\phi,A)\leq
s$ and therefore with high probability:
\begin{equation*}
    \abr{\nbr{x}_\phi^2 - 1} \leq  8\nbr{x}_\infty \beta s^2 + 16
      \nbr{x}_\infty^2 s^4  + \sqrt{2} \sigma.
\end{equation*}
A change of variables $s^2 = \frac{\sqrt{\beta^2 + \epsilon} - \beta}{4\nbr{x}_\infty}$
%  \begin{align}
%  s^2 = \frac{\sqrt{\beta^2 + \epsilon} - \beta}{4\nbr{x}_\infty}
%  \end{align}
 gives us that
%\begin{align}
$\abr{\nbr{x}_\phi^2 - 1} \leq \sqrt{2} \sigma + \epsilon$ w.p. $1 - 2e^{-s^2/4}.$
%\end{align}
 Noting that $s^2 = (\sqrt{\beta^2 + \epsilon} - \beta)/4 \nbr{x}_\infty \geq \sqrt{\epsilon}/4 \nbr{x}_\infty$, lets us obtain our final result
 \begin{align*}
 \abr{\nbr{x}_\phi^2 - 1} \leq \sqrt{2} \sigma + \epsilon \mbox{  w.p. } 1 - 2e^{-\sqrt{\epsilon}/4\nbr{x}_\infty}.
 \end{align*}
Finally, for a general $x$, we can derive the above result for $y  = \frac{x}{\|x\|_2}$. Replacing $ \|y\|_\infty = \frac{\|x\|_\infty}{\|x\|_2}$ we get the following version for a general $x$,
\begin{align*}
\Pr\cbr{\frac{|\nbr{x}_\phi^2 - \nbr{x}_2^2|}{\nbr{x}_2^2} \geq \sqrt{2} \sigma_{x,x} + \epsilon} \leq \exp\rbr{\textstyle - \frac{\sqrt{\epsilon}\|x\|_2}{4\nbr{x}_\infty}}
\end{align*}
\end{proof}

\vspace{-1cm}
\section{Inner Product}
\label{sec:innerproof}
\begin{proof}[Corollary~\ref{cor:inner}] We have that $2\inner{x}{x'}_\phi = \nbr{x}_\phi^2 +  \nbr{x'}_\phi^2 -  \nbr{x - x'}_\phi^2$.
%\end{align*}
Taking expectations, we have the standard inner product inequality. Thus,
\begin{align*}
& | 2\inner{\phi_u(x)}{\phi_u(x)} - 2\inner{x}{x} |  \leq | \nbr{\phi_u(x)}^2 - \nbr{x}^2 | \\
& + | \nbr{\phi_u(x')}^2 - \nbr{x'}^2| + | \nbr{\phi(x - x')}^2 - \nbr{x - x'}^2 |
\end{align*}
Using union bound, with probability $ 1 - 3\exp\left( - \frac{\sqrt{\epsilon}}{4\eta}\right)$, each of the terms above is bounded using Theorem~\ref{th:key}. Thus, putting the bounds together, we have that, with probability $ 1 - 3\exp\left( - \frac{\sqrt{\epsilon}}{4\eta}\right)$,
\begin{align*}
& | 2\inner{\phi_u(x)}{\phi_u(x)} - 2\inner{x}{x} |  \leq \\
& \leq  (\sqrt{2}\sigma +  \epsilon) ( \nbr{x}^2 + \nbr{x'}^2 + \nbr{x - x'}^2 )
\end{align*}
\end{proof}
\end{appendix}

\end{document}


% This document was modified from the file originally made available by
% Pat Langley and Andrea Danyluk for ICML-2K. This 2009 version was
% created by Kiri Wagstaff, slightly modified from Sam Roweis's 2008
% version, which is slightly modified from Prasad Tadepalli's 2007
% version which is a lightly changed version of the previous year's
% version by Andrew Moore, which was in turn edited from those of
% Kristian Kersting and Codrina Lauth. Alex Smola contributed to the
% algorithmic style files.


