2013年8月27日,星期二

角色扮演

如果您喜欢原始线性方法,那么您可能已经花了很多时间考虑要素工程。如果您使用过内核学习,那么您可能已经花了很多时间来考虑适合您问题的内核,这是思考功能工程的另一种方式。事实证明,在解决原始凸优化问题时,有一种方法可以利用内核社区的工作:随机特征图。这个想法已经存在了一段时间: Rahimi和Recht撰写的论文 真正开始的事情是从2007年开始 关于它的博客完善技术,而Veeramachaneni有一个 不错的博客文章 以图形方式探索该技术。一种通用策略是找到内核的积分表示,然后通过蒙特卡洛近似积分表示。最终,这看起来像一个随机特征图$ \ phi $,其原始点积$ \ phi(x)^ \ top \ phi(y)$收敛到内核函数$ k的值(x,y)$。当使用傅立叶基础进行内核的整数表示时,随机特征图由余弦组成,因此我们在CISL中将其称为``cosplay''。

该技术应该比它更广为人知,因为它提供了良好的学习性能(当相关的内核是解决该问题的不错选择时),它易于实现并且非常快。我希望我可以通过在众所周知的数据集上提供简单的实现来提高知名度,并且本着这种精神,这里是一个Matlab脚本,它将该技术应用于mnist。在运行此程序之前,您需要下载 mnist在matlab格式,然后下载 maxent和lbfgs for matlab.

rand('seed',867);
randn('seed',5309);

tic
fprintf('loading mnist');

% get mnist from http://cs.nyu.edu/~roweis/data/mnist_all.mat
load('mnist_all.mat');

trainx=single([train0; train1; train2; train3; train4; train5; train6; train7; train8; train9])/255.0;
testx=single([test0; test1; test2; test3; test4; test5; test6; test7; test8; test9])/255.0;
st=[size(train0,1); size(train1,1); size(train2,1); size(train3,1); size(train4,1); size(train5,1); size(train6,1); size(train7,1); size(train8,1); size(train9,1)];
ss=[size(test0,1); size(test1,1); size(test2,1); size(test3,1); size(test4,1); size(test5,1); size(test6,1); size(test7,1); size(test8,1); size(test9,1)];
paren = @(x, varargin) x(varargin{:});
yt=[]; for i=1:10; yt=[yt; repmat(paren(eye(10),i,:),st(i),1)]; end
ys=[]; for i=1:10; ys=[ys; repmat(paren(eye(10),i,:),ss(i),1)]; end

clear i st ss
clear train0 train1 train2 train3 train4 train5 train6 train7 train8 train9
clear test0 test1 test2 test3 test4 test5 test6 test7 test8 test9

fprintf(' finished: ');
toc

tic
fprintf('computing random feature map');

% (uncentered) pca to 50 ... makes subsequent operations faster,
% but also makes the random projection more efficient by focusing on
% where the data is

opts.isreal = true; 
[v,~]=eigs(double(trainx'*trainx),50,'LM',opts);
trainx=trainx*v;
testx=testx*v; 
clear v opts;

% estimate kernel bandwidth using the "median trick"
% this is a standard Gaussian kernel technique

[n,k]=size(yt);
[m,p]=size(testx);
sz=3000;
perm=randperm(n);
sample=trainx(perm(1:sz),:);
norms=sum(sample.^2,2);
dist=norms*ones(1,sz)+ones(sz,1)*norms'-2*sample*sample';
scale=1/sqrt(median(dist(:)));

clear sz perm sample norms dist;

% here is the actual feature map:
% Gaussian random matrix, uniform phase, 和 cosine

d=4000;
r=randn(p,d);
b=2.0*pi*rand(1,d);
trainx=cos(bsxfun(@plus,scale*trainx*r,b));
testx=cos(bsxfun(@plus,scale*testx*r,b));

fprintf(' finished: ');
toc

tic
fprintf('starting logistic regression (this takes a while)\n');

% get @maxent 和 lbfgs.m from http://www.cs.grinnell.edu/~weinman/code/
% if you get an error about randint being undefined, change it to randi

addpath recognition;
addpath opt;
addpath local;

C0=maxent(k,d);
[~,trainy]=max(yt');
options.MaxIter=300; 
options.Display='off';
C1=train(C0,trainy,trainx,'gauss',4.2813,[],[],[],options);
% regularizer was chosen by cross-validation as follows
%perm=randperm(n);
%it=logical(zeros(1,n));
%it(perm(1:int32(0.8*n)))=1;
%[C1,V]=cvtrain(C0,trainy(perm),trainx(perm,:),'gauss',10.^linspace(-4,4,20), ...
%               [],0,[],it,[],@accuracy);
        
fprintf('finished: ');
toc
fprintf('train accuracy is %g\n',accuracy(C1,trainy,trainx));
[~,testy]=max(ys');
fprintf('test accuracy is %g\n',accuracy(C1,testy,testx));

这是在笔记本电脑上运行脚本的结果:
>> clear all; cosplay
loading mnist finished: Elapsed time is 2.227499 seconds.
computing random feature map finished: Elapsed time is 6.994094 seconds.
starting logistic regression (this takes a while)
finished: Elapsed time is 219.007670 seconds.
train accuracy is 0.99905
test accuracy is 0.9822
这接近高斯内核SVM的性能,但具有简单性和速度。通过尝试不同 随机特征图,您可以改善此结果。

如果您喜欢这种东西,请务必检查一下 机器学习的随机方法 NIPS 2013研讨会。

1条评论:

  1. 感谢您发布此代码。这里'是Kaggle的Digit Recognizer竞赛的稍作修改的版本:

    //github.com/zygmuntz/kaggle-digits

    得分〜0.977。

    回复删除