Innuo

The NIPS paper Random Fourier Features for Large-scale Kernel Machines , by Rahimi and Recht presents a method for randomized feature mapping where dot products in the transformed feature space approximate (a certain class of) positive definite (p.d.) kernels in the original space. We know that for any p.d. kernel there exists a deterministic map that has the aforementioned property but it may be infinite dimensional. The paper presents results indicating that with the randomized map we  can get away with only a "small" number of features (at least for a classification setting). Before applying the method to density estimation let us review the relevant section of the paper briefly. Bochner's Theorem and Random Fourier Features Assume that we have data in $R^d$ and a continuous p.d. kernel $K(x,y)$ defined for every pair of points $x,y \in R^d$. Assume further that the kernel is shift-invariant, i.e., $K(x,y) = K(x-y) \triangleq K(\delta)$ and that the kernel is...

First I would like to mention that, since my last post , I came across the paper from 2005 on Robust Supervised Learning by J. Andrew Bagnell that proposed almost exactly the same regularized minimax algorithm as the one I derived. He motivates the problem slightly differently and weights each example separately and not based on types, but the details are essentially identical. Experiments on Synthetic Data I tried the algorithm on some synthetic data and a linear logistic regression model. The results are shown in the figures below. In both examples, there are examples from two classes (red and blue). Each class is a drawn from a  mixture of two normal distributions (i.e., there are two types per class). The types are shown as red squares and red circles, and blue diamonds and blue triangles. Class-conditionally the types have a skewed distribution. There are 9 times as many red squares as red circles, and 9 times as many blue diamonds as triangles. We would expect a plain logistic ...

This post is about using minimax estimation for robust learning when the test data distribution is expected to be different from the training data distribution, i.e learning that is robust to data drift. Cost Sensitive Loss Functions Given a training data set $latex D = \{x_i, y_i\}_{i=1,\ldots,N}$, most learning algorithms learn a classifier $latex \phi$ that is parametrized by a vector $latex w$ by minimizing a loss function where $latex l(x_i, y_i, w)$ is the loss on example $latex i$ and $latex f(w)$ is some function that penalizes complexity. For example for logistic regression the loss function looks like for some $latex \lambda > 0$. If, in addition, the examples came with costs $latex c_i$ (that somehow specify the importance of minimizing the loss on that particular example), we can perform cost sensitive learning by over/under-sampling the training data or minimize a cost-weighted loss function (see this paper by Zadrozny et. al. ) We further constrain $latex \sum_i^N c_i...

In a previous post , I talked about an idea for sparsifying kernel logistic regression by using random prototypes. I also showed how the prototypes themselves (as well as the kernel parameters) can be updated. (Update Apr 2010. Slides for a tutorial on this stuff.) (As a brief aside, I note that an essentially identical approach was used to sparsify Gaussian Process Regression by Snelson and Gharahmani . For GPR they use gradient ascent on the log-likelihood to learn the prototypes and labels, which is akin to learning the prototypes and betas for logistic regression. The set of prototypes and labels generated by their algorithm can be thought of as a pseudo training set.) I recently (with the help of my super-competent Java developer colleague Hiroko Bretz) implemented the sparse kernel logistic regression algorithm. The learning is done in an online fashion (i.e., using stochastic gradient descent). It seems to perform reasonably well on large datasets. Below I'll show its behav...

As opposed to the traditional supervised learning setting where the labeled training data is generated (we hope) independently and identically, in active learning the learner is allowed to select points for which labels are requested. Because it is often impossible to construct the equivalent real-world object from its feature values, almost universally, active learning is pool-based . That is we start with a large pool of unlabeled data and the learner (usually sequentially) picks the objects from the pool for which the labels are requested. One unavoidable effect of active learning is that we end up with a biased training data set. If the true data distribution is $latex P(x,y)$, we have data drawn from some distribution $latex \hat{P}(x,y)$ (as always $latex x$ is the feature vector and $latex y$ is the class label). We would like to correct for this bias so it does not lead to learning an incorrect classifier. And furthermore we want to use this biased data set to accurately evalu...

I will present a sparse kernelization of logistic regression where the prototypes are not necessarily from the training data. Traditional sparse kernel logistic regression Consider an $latex M$ class logistic regression model given by $latex P(y|x)\propto\mbox{exp}(\beta_{y0} + \sum_{j}^{d}\beta_{yj}x_j)$ for $latex y =0,1,\ldots,M$ where $latex j$ indexes the $latex d$ features. Fitting the model to a data set $latex D = \{x_i, y_i\}_{i=1,\ldots,N}$ involves estimating the betas to maximize the likelihood of $latex D$. The above logistic regression model is quite simple (because the classifier is a linear function of the features of the example), and in some circumstances we might want a classifier that can produce a more complex decision boundary. One way to achieve this is by kernelization . We write $latex P(y|x) \propto \mbox{exp}(\beta_{y0} + \sum_{i=1}^N \beta_{yi} k(x,x_i))$ for $latex y=0,1,\ldots,M$. where $latex k(.,.)$ is a kernel function. In order to be able to use this c...

Here's an estimation problem that I ran into not long ago while working on a problem in entity co-reference resolution in natural language documents. Let $latex X$ be a random variable taking on values in $latex \{0,1,2,\ldots\}$.  We are given data $latex D=\{(N_1,S_1), (N_2,S_2),\ldots,(N_k,S_k)\}$, where $latex S_i$ is the sum of $latex N_i$ independent draws of $latex X$ for $latex i = 1, 2,\ldots, k$. We are required to estimate the distribution of $latex X$ from $latex D$. For some distributions of $latex X$ we can use the method-of-moments. For example if $latex X \sim \mbox{Poisson}(\lambda)$, we know that the mean of $latex X$ is $latex \lambda$. We can therefore estimate $latex \lambda$ as the sample mean, i.e., $latex \hat{\lambda}=\frac{S_1+S_2+\ldots+S_k}{N_1+N_2+\ldots+N_k}$. Because of the nice additive property of the parameters for sums of i.i.d. poisson random variables, the maximum likelihood estimate also turns out be the same as $latex \hat{\lambda}$. The probl...

Perhaps it has always been obvious to exalted statistical minds that density estimation can be viewed as classification and (perhaps) done using a classifier. Assume that we have samples $latex \{x_i\}_{i=1,\ldots,N}$ of a random vector $latex X$ whose distribution has bounded support. In fact, without loss of generality, let the support be the unit hypercube $latex [0,1]^d$. We are required to estimate $latex P_X(x)$ the density of $latex X$. Now assume that we generate a bunch of samples $latex \{z_i\}_{i=1,\ldots,M}$ uniformly distributed in $latex [0,1]^d$. We assign a label $latex y = 1$ to all the samples $latex x_i$ and a label $latex y = 0$ to all $latex z_i$ and a build a classifier $latex \psi$ between the two sample sets. In other words we construct an estimate $latex P_\psi(y=1|x)$ of the posterior class probability $latex P(y=1|x)$ $latex \forall x \in [0,1]^d$. Now, we know that where $latex U(x) = 1$, the uniform distribution over the unit hypercube. The above equation c...