显示带有标签的帖子 实用技巧. 显示所有帖子
显示带有标签的帖子 实用技巧. 显示所有帖子

2020年7月17日,星期五

凹凸凹面游戏

如果您现在需要解决凸优化问题,那么您的情况就很好。任何形式为$$的问题
\ begin {alignat} {2}
&\!\ inf_z&\ qquad&f(z)\\
&\ text {取决于}&&h(z)= 0 \\
&&&g(z)\ preceq 0
\ end {alignat}
$$,其中$ f $和$ g $是凸的,而$ h $是仿射的,可以用几个优秀的免费提供的软件包来攻击:我目前最喜欢的是 cvxpy ,使用起来很愉快。如果您有很多变量而不是很多约束,则可以解决一个双重问题。最终看起来像$$
\ begin {alignat} {2}
&\!\ sup_ {x}和\ qquad&L(x)\\
&\ text {取决于}&&\ tilde {h} _x(x)= 0 \\
&&&\\ tilde {g} _x(x)\ preceq 0
\ end {alignat}
$$,其中$ L $是凹面的,假设您很幸运,并且可以分析地消除所有原始变量$ z $,从而仅保留对偶变量$ x $。但是,如果您不能消除所有原始变量,而只能消除其中的大多数,那该怎么办?您可能会遇到类似$$的问题
\ begin {alignat} {2}
&\!\ sup_ {x} \ inf_y&\ qquad&L(x,y)\\
&\ text {取决于}&&\ tilde {h} _x(x)= 0 \\
&&&\\ tilde {g} _x(x)\ preceq 0 \\
&&&\\ tilde {h} _y(y)= 0 \\
&&&\\ tilde {g} _y(y)\ preceq 0
\ end {alignat}
$$ where $\tilde{g}_x$ 和 $\tilde{g}_y$ are convex, 和 $\tilde{h}_x$ 和 $\tilde{h}_y$ are affine, $L(x, \cdot)$ is convex in $y$ given fixed $x$, 和 $L(\cdot, y)$ is concave in $x$ given fixed $y$. It 感觉s like this problem should be easier to solve than the original problem if many primal variables have been analytically eliminated. Unfortunately, 我最喜欢的凸优化工具包都不会接受这种形式的问题。 尽管 内点方法解决此类问题的可行性。笨蛋

我尝试的一件事是使用标准工具包求解内部极小值,通过灵敏度图计算带有外部参数的解的梯度,然后对外部极值使用一阶方法。这对我不起作用:它适用于玩具问题,但在实际问题上,外部上层的收敛非常缓慢,这表明身体不适。

我需要的是内点方法通过二阶信息处理疾病的能力。我可以通过顺序二次极大极小编程来实现此目标:首先,在当前点周围用二次方局部逼近目标$ L(\ lambda,\ mu,y)$并将约束线性化。 $$
\ begin {alignat} {2}
&\!\ sup _ {\ delta x} \ inf _ {\ delta y}&\ qquad&\ frac {1} {2} \ left(\ begin {array} {c} \ delta x \\ \ delta y \ end {array} \ right)^ \ top \ left(\ begin {array} {cc} P_ {xx}和P_ {yx} ^ \ top \\ P_ {yx}&P_ {yy} \ end {array} \ right )\ left(\ begin {array} {c} \ delta x \\ \ delta y \ end {array} \ right)+ \ left(\ begin {array} {c} q_x \\ q_y \ end {array} \ right)^ \ top \ left(\ begin {array} {c} \ delta x \\ \ delta y \ end {array} \ right)\\
&\ text {根据}&&\ left(\ begin {array} {cc} A_x&0 \\ 0&A_y \ end {array} \ right)\ left(\ begin {array} {c} \ delta x \\ \ delta y \ end {array} \ right)= \ left(\ begin {array} {c} b_x \\ b_y \ end {array} \ right)\\
&&&\ left(\ begin {array} {cc} G_x&0 \\ 0&G_y \ end {array} \ right)\ left(\ begin {array} {c} \ delta x \\ \ delta y \ end {array} \ right)\ preceq \ left(\ begin {array} {c} h_x \\ h_y \ end {array} \ right)\\
\ end {alignat}
$$ 沃尔夫双重 将此问题转换为标准的QP:$$
\ begin {alignat} {2}
&\!\ sup _ {\ delta x,\ delta y,\ lambda,\ mu}&\ qquad&\ frac {1} {2} \ left(\ begin {array} {c} \ delta x \\ \ delta y \\ \ lambda \\ \ mu \ end {array} \ right)^ \ top \ left(\ begin {array} {cccc} P_ {xx}&0&0&0 \\ 0&-P_ {yy} &0&0 \\ 0&0&0&0 \\ 0&0&0&0 \ end {array} \ right)\ left(\ begin {array} {c} \ delta x \\ \ delta y \ \ \ lambda \\ \ mu \ end {array} \ right)+ \ left(\ begin {array} {c} q_x \\ 0 \\ -b_y \\ -h_y \ end {array} \ right)^ \ top \ left(\ begin {array} {c} \ delta x \\ \ delta y \\ \ lambda \\ \ mu \ end {array} \ right)\\
&\ text {取决于}&&\ left(\ begin {array} {cc} A_x&0&0&0 \\ P_ {yx}&P_ {yy}&A_y ^ \ top&G_y ^ \ top \ end {array} \ right)\ left(\ begin {array} {c} \ delta x \\ \ delta y \\ \ lambda \\ \ mu \ end {array} \ right)= \ left(\ begin {array} {c} b_x \\ -q _y \ end {array} \ right)\\
&&&\ left(\ begin {array} {cc} G_x&0&0&0 \\ 0&0&0&-I \ end {array} \ right)\ left(\ begin {array} {c} \ delta x \\ \ delta y \\ \ lambda \\ \ mu \ end {array} \ right)\ preceq \ left(\ begin {array} {c} h_x \\ 0 \ end {array} \ right)\ \
\ end {alignat}
$$如果为$(\ delta x,\ delta y)$解决此问题,您将获得牛顿步骤以解决原始问题。这里的步验收标准很棘手:如果迭代可行,则您希望利用鞍点条件(请参见方程式(11) Essid等。等)。如果迭代不可行,则需要更复杂的方法,但是幸运的是,我的约束实际上是线性的,因此,进行初始的精确内部求解可使我在保持可行的同时进行迭代。 (注意:如果您在每个步骤上都解决了更一般的凸问题,则无需线性化$ x $约束。)

YMMV!

2017年2月15日星期三

软件工程与机器学习概念

并非软件工程的所有核心概念都可以转化为机器学习领域。这是我注意到的一些差异。

分而治之 软件工程中的一项关键技术是将一个问题分解为更简单的子问题,解决这些子问题,然后将它们组合为原始问题的解决方案。可以说,这是递归应用的整个工作,直到可以使用任何编程语言在一行中表示解决方案为止。规范的教学示例是 河内塔.

不幸的是,在机器学习中我们永远无法完全解决问题。充其量,我们大约可以解决一个问题。这是该技术需要修改的地方:在软件工程中,子问题解决方案是 精确 ,但在机器学习错误中,复合和综合结果可能完全是垃圾。另外,如果组件是“improved”孤立,但聚合系统性能会降低“improvement”部署(例如,由于 模式 现在,下游组件无法预料到错误的发生,即使它们的出现频率较低)。

这是否意味着我们注定要进行整体思考(这听起来似乎无法解决大问题)?不,但这意味着您必须对子问题分解保持防御。可行时,最佳策略是对系统进行端到端培训,即一起(而不是孤立地)优化所有组件(和组合策略)。通常这是不可行的,因此(受贝叶斯思想启发)另一种选择是让每个组件随输出报告某种类型的置信度或方差,以便于下游处理和集成。

实际上,当系统达到特定范围时,需要分解以将工作分配给许多人。正如Leon Bottou在他的著作中优雅地描述的那样,这现在在机器学习中不起作用是一个问题。 ICML 2015邀请演讲.

谈到莱昂讨论$ \ ldots $的另一个概念

正确性 在软件工程中,就给定关于输入的特定假设而言,当算法终止时,某些属性将为真,在某种意义上,可以证明算法是正确的。在(监督的)机器学习中,我们真正拥有的唯一保证是,如果训练集是来自特定分布的iid样本,则来自同一分布的另一个iid样本的性能将接近训练集,而并非远非最佳。

因此,任何以机器学习为生的人都有实验的心态。通常,我被问到选项A还是选项B更好,大多数时候我的答案是“我不知道,让我们同时尝试一下,看看会发生什么。”机器学习领域的人们可能知道的最重要的事情是如何以可预测泛化的方式评估模型。即使那样“feel”事情:识别并防止训练和验证集之间的泄漏(例如,通过分层抽样和时间抽样)是您花了几次力气才能学到的东西;反事实循环的同上。 卡格勒 非常适合学习前者,但是后者似乎需要在闭环系统上犯错才能真正欣赏。

实验性“correctness”它比其他软件的保证要弱得多,并且有很多方法可以使事情恶化。例如,根据我的经验,它总是临时的:模型过时,似乎总是在发生。如此,您需要计划不断(因此自动)重新训练模型。

重用 This one is interesting. 重用 is the key to leverage in 传统软件 engineering: it's not just more productive to reuse other code, but every line of code you write yourself is an opportunity to inject defects. Thus, reuse not only allows you to move faster but also make less mistakes: in return, you must pay the price of learning how to operate a piece of software written by others (when done well, this price has been lowered through good organization, documentation, 和 community support).

机器学习的某些方面表现出完全相同的权衡。例如,如果您正在编写自己的深度学习工具包,请认识到您很有趣。乐趣并没有错,可以说教学活动比整天玩视频游戏要好。但是,如果您想完成某件事,则绝对应该尝试重用尽可能多的技术,这意味着您应该使用标准工具箱。一旦学习了如何使用标准工具箱,您将可以更快地行动并减少错误。

机器学习工具包是“traditional software”但是,并且被设计为可以重用。模型重用呢?那也可能很好,但是上面关于分解的警告仍然适用。因此,也许您使用的模型会根据用户个人资料生成特征,作为模型的输入。很好,但是您应该对所依赖的模型进行版本控制,并且不要在未经评估或重新培训的情况下盲目升级。重用另一个模型的内部结构尤其危险,因为大多数机器学习模型无法识别,即具有各种内部对称性,而这些对称性不是由训练过程确定的。例如,将一个嵌入与一棵树耦合,当嵌入的下一个版本是上一个的旋转时,您可以看到性能立即下降。

基本上,模型重用会创建 强大 组件之间的耦合,如果更改一个组件,可能会出现问题。

测验 我发现软件测试在机器学习中的作用是所有问题中最棘手的问题。毫无疑问,测试是必要的,但是使用基于属性的测试之类的挑战在于,机器学习组件捕获的概念很难用属性来表征(否则,您将使用非ml软件技术来编写它。 )。在一定程度上,ml组件应该显示某些属性,您可以测试一下这些属性,但是除非将这些属性合并到学习过程本身中(例如,通过参数绑定或数据扩充),否则您可能会违反该属性不一定表示缺陷。

有一个“extra-test”具有最低可接受质量的数据集是一个好主意:这可能是简单的示例,“any reasonable model”应该正确。还有自洽性:在Yahoo,他们曾经使用带有一组输入-输出对的模型来运送模型,这些输入-输出对是在模型放在一起时计算的,并且如果加载的模型没有重现该对,则模型加载会被取消。 (那是永远不会发生的,对吗?惊喜!也许您正在使用具有不同版本或类似内容的库来使输入具有特色。)

监视已部署模型的度量标准(代理和真实)也有助于发现问题。如果代理指标(即您实际在其上训练模型并估计通用性能的事物)向南移动,则模型的输入正在以某种方式发生变化(例如,非平稳环境,特征提取管道的变化);但是如果代理指标稳定,而真正指标向南移动,则问题可能出在如何利用模型的输出。

Unfortunately what I find is many software systems with machine learning components are tested in a way that would make 传统软件 engineers cringe: we look 在 the output to see if it is reasonable. Crazy! As machine learning becomes a more pervasive part of software engineering, this state of affairs must change.

2015年11月30日,星期一

样本方差惩罚

在大多数情况下,有监督的机器学习是通过优化训练集上的平均损失(即经验风险最小化)来完成的,也许添加了(通常不依赖数据)正则化术语。但是,有一篇不错的论文毛雷尔(Maurer)和庞蒂尔(Pontil)几年前的介绍 样本方差惩罚。基本思想是在训练集上优化损失的第一刻和第二刻的组合:这是由经验伯恩斯坦界限,霍夫丁界限的精炼(这是经验风险最小化的正式基础)很好地激发的。除其他外,界限表示,在给定两个具有相同平均经验损失的假设的情况下,您应该偏向于具有较低经验损失方差的假设。一般而言,优化边界会导致目标函数\ [
f(w)= \ mathbb {E} [l(y,h(x; w))] + \ kappa \ sqrt {\ mathbb {E} \ left [\ left(l(y,h(x; w) )-\ mathbb {E} [l(y,h(x; w))] \ right)^ 2 \ right]} \ doteq \ mu(l; w)+ \ kapp \ \ sigma(l; w),
\] 期望值超出训练集,即只是写出经验平均值的一种简洁方法; $ h(x; w)$是由向量$ w $参数化的某些假设类别,$ l $是损失,$ y $是标签,$ \ kapp $是(还有!)超参数。

据我所知,这并没有真正起飞(尽管 事实风险最小化 使用它,这非常酷)。目标是非凸面的,这在当时可能是负面特征。该目标还涉及批次数量,也许这是负数。如今,无论如何,我们都在进行非凸目标的小批量训练,因此SVP值得一提。如果您打开曲柄,则会得到\ [
\ nabla_w f(w)= \ mathbb {E} \ left [\ left(1 + \ kappa \ frac {l(y,h(x; w))-\ mu(l; w)} {\ sigma(l ; w)} \ right)\ nabla_w l(y,h(x; w))\ right],
\] 看起来像是SGD,其学习速度可变:比平均损失差的示例获得更高的学习率,而比平均损失更好的示例获得更低(可能为负!)的学习率。度量单位定义“worse” 和 “better”是损失方差。在实践中,我发现负面的学习率令人反感,因此我将下界定为零,但是对于$ \ kappa $有用的值(0.25是一个很好的初始猜测),通常并不重要。

批次数量$ \ mu(l; w)$和$ \ sigma(l; w)$看起来很痛苦,但以我的经验,您可以用小批量估计替换它们,这仍然很有帮助。使用此技术,我在解决一些问题时变得谦虚但始终如一, 极限学习 (神经)语言建模等问题。当然,您应该只考虑在怀疑所需模型类将过拟合并且正则化很重要的问题上应用此技术:极端学习问题具有这种结构,因为许多尾类都具有接近单例的支持。 YMMV。

2014年9月24日,星期三

子线调试

I have a post on 亚线性调试 on 微软的机器学习博客.
在线学习算法是一类机器学习(ML)技术,它们将输入作为流使用,并在它们使用输入时进行调整。它们通常用于计算方面的需求,例如速度,使用大数据集的能力以及处理非凸目标的能力。但是,它们还有另一个有用的好处,即“sub-linear debugging”.
如果您有兴趣点击 多赫蒂阈值 在机器学习中,阅读 整件事!

2014年4月25日,星期五

判别表征学习技术

我和Nikos开发了一种使用数值线性代数技术学习判别特征的技术 效果很好 对于一些问题。基本思想如下。假设您遇到一个多类问题,即训练数据的形式为$ S = \ {(x,y)| x \ in \ mathbb {R} ^ d,y \ in \ {1,\ ldots,k \} \} $。 $ x $是原始表示形式(功能),您想学习有助于分类器的新功能。在深度学习中,此问题通过定义$ x $的多级参数非线性和优化参数来解决。深度学习很棒,但是由此产生的优化问题却极具挑战性,尤其是在分布式环境中,因此我们一直在寻找更适合计算的东西。

首先考虑两类情况。想象一下寻找形式为$ \ phi(w ^ \ top x)$的特征,其中$ w \ in \ mathbb {R} ^ d $是一个“weight vector”$ \ phi $是某种非线性。定义良好功能的简单标准是什么?一个想法是该功能在一个类上具有较小的平均值,而在另一类上具有较大的平均值。假设$ \ phi $为非负数,则建议最大化比率\ [
w ^ * = \ arg \ max_w \ frac {\ mathbb {E} [\ phi(w ^ \ top x)| y = 1]} {\ mathbb {E} [\ phi(w ^ \ top x)| y = 0]}。
\] 对于$ \ phi(z)= z ^ 2 $的特定选择,这是易处理的,因为它会导致 瑞利商 在两个有条件的第二时刻之间,\ [
w ^ * = \ arg \ max_w \ frac {w ^ \ top \ mathbb {E} [x x ^ \ top | y = 1] w} {w ^ \ top \ mathbb {E} [x x ^ \ top | y = 0] w},
\] 可以通过广义特征值分解来解决。广义特征值问题已经在机器学习和其他领域进行了广泛的研究,并且上述想法与许多其他建议(例如, 费希尔LDA),但它是不同的,而且在经验上更有效。我将引导您参考该论文进行更深入的讨论,但是我会提到在论文被接受之后,有人指出了与 CSP ,这是时间序列分析中的一种技术(参见 传道书1:4-11 )。

此过程产生的功能通过了气味测试。例如,从上的原始像素表示开始 mnist , the 权重向量s can be visualized as images; the first 权重向量 for discriminating 3 vs. 2 looks like
看起来像笔触,参见图1D 兰萨托等等

我们在本文中还提出了其他一些意见。首先是,如果相关的广义特征值较大,则瑞利商的多个孤立极小值将很有用,即可以从瑞利商中提取多个特征。第二个是,对于适度的$ k $,我们可以独立提取每个类对的特征,并使用所有得到的特征获得良好的结果。第三是所得方向具有附加结构,该附加结构不能被平方非线性完全捕获,这会激发(单变量)基函数展开。第四,一旦原始表示增加了其他功能,就可以重复该过程,有时还会产生其他改进。最后,我们可以将其与随机特征图组合起来,以近似RKHS中的相应操作,有时还会产生其他改进。在本文中,我们还提出了一个抛弃式的评论,即在映射简化样式的分布式框架中轻松完成计算类条件第二矩矩阵的操作,但这实际上是我们朝这个方向进行探索的主要动机,但事实并非如此。不太适合本文的论述,因此我们不再强调它。

将上述想法与Nikos的多类别预处理梯度学习结合起来, 以前的帖子,导致出现以下Matlab脚本,该脚本在(排列不变)mnist上获得91个测试错误。注意:您需要下载 mnist _all.mat 从Sam Roweis的网站运行。
function calgevsquared

more off;
clear all;
close all;

start=tic;
load('mnist_all.mat');
xxt=[train0; train1; train2; train3; train4; train5; ...
     train6; train7; train8; train9];
xxs=[test0; test1; test2; test3; test4; test5; test6; test7; test8; test9];
kt=single(xxt)/255;
ks=single(xxs)/255;
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=zeros(60000,10);
ys=zeros(10000,10);
I10=eye(10);
lst=1;
for i=1:10; yt(lst:lst+st(i)-1,:)=repmat(I10(i,:),st(i),1); lst=lst+st(i); end
lst=1;
for i=1:10; ys(lst:lst+ss(i)-1,:)=repmat(I10(i,:),ss(i),1); lst=lst+ss(i); end

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

[n,k]=size(yt);
[m,d]=size(ks);

gamma=0.1;
top=20;
for i=1:k
    ind=find(yt(:,i)==1);
    kind=kt(ind,:);
    ni=length(ind);
    covs(:,:,i)=double(kind'*kind)/ni;
    clear ind kind;
end
filters=zeros(d,top*k*(k-1),'single');
last=0;
threshold=0;
for j=1:k
    covj=squeeze(covs(:,:,j)); l=chol(covj+gamma*eye(d))';
    for i=1:k
        if j~=i
            covi=squeeze(covs(:,:,i));
            C=l\covi/l'; CS=0.5*(C+C'); [v,L]=eigs(CS,top); V=l'\v;
            take=find(diag(L)>=threshold);
            batch=length(take);
            fprintf('%u,%u,%u ', i, j, batch);
            filters(:,last+1:last+batch)=V(:,take);
            last=last+batch;
        end
    end
    fprintf('\n');
end

clear covi covj covs C CS V v L

% NB: augmenting kt/ks with .^2 terms is very slow  和  doesn't help

filters=filters(:,1:last);
ft=kt*filters;
clear kt;
kt=[ones(n,1,'single') sqrt(1+max(ft,0))-1 sqrt(1+max(-ft,0))-1];
clear ft;
fs=ks*filters;
clear ks filters;
ks=[ones(m,1,'single') sqrt(1+max(fs,0))-1 sqrt(1+max(-fs,0))-1];
clear fs;

[n,k]=size(yt);
[m,d]=size(ks);

for i=1:k
    ind=find(yt(:,i)==1);
    kind=kt(ind,:);
    ni=length(ind);
    covs(:,:,i)=double(kind'*kind)/ni;
    clear ind kind;
end

filters=zeros(d,top*k*(k-1),'single');
last=0;
threshold=7.5;
for j=1:k
    covj=squeeze(covs(:,:,j)); l=chol(covj+gamma*eye(d))';
    for i=1:k
        if j~=i
            covi=squeeze(covs(:,:,i));
            C=l\covi/l'; CS=0.5*(C+C'); [v,L]=eigs(CS,top); V=l'\v;
            take=find(diag(L)>=threshold);
            batch=length(take);
            fprintf('%u,%u,%u ', i, j, batch);
            filters(:,last+1:last+batch)=V(:,take);
            last=last+batch;
        end
    end
    fprintf('\n');
end
fprintf('gamma=%g,top=%u,threshold=%g\n',gamma,top,threshold);
fprintf('last=%u filtered=%u\n', last, size(filters,2) - last);

clear covi covj covs C CS V v L

filters=filters(:,1:last);
ft=kt*filters;
clear kt;
kt=[sqrt(1+max(ft,0))-1 sqrt(1+max(-ft,0))-1];
clear ft;
fs=ks*filters;
clear ks filters;
ks=[sqrt(1+max(fs,0))-1 sqrt(1+max(-fs,0))-1];
clear fs;

trainx=[ones(n,1,'single') kt kt.^2];
clear kt;
testx=[ones(m,1,'single') ks ks.^2];
clear ks;

C=chol(0.5*(trainx'*trainx)+sqrt(n)*eye(size(trainx,2)),'lower');
w=C'\(C\(trainx'*yt));
pt=trainx*w;
ps=testx*w;

[~,trainy]=max(yt,[],2);
[~,testy]=max(ys,[],2);

for i=1:5
        xn=[pt pt.^2/2 pt.^3/6 pt.^4/24];
        xm=[ps ps.^2/2 ps.^3/6 ps.^4/24];
        c=chol(xn'*xn+sqrt(n)*eye(size(xn,2)),'lower');
        ww=c'\(c\(xn'*yt));
        ppt=SimplexProj(xn*ww);
        pps=SimplexProj(xm*ww);
        w=C'\(C\(trainx'*(yt-ppt)));
        pt=ppt+trainx*w;
        ps=pps+testx*w;

        [~,yhatt]=max(pt,[],2);
        [~,yhats]=max(ps,[],2);
        errort=sum(yhatt~=trainy)/n;
        errors=sum(yhats~=testy)/m;
        fprintf('%u,%g,%g\n',i,errort,errors)
end
fprintf('%4s\t', 'pred');
for true=1:k
        fprintf('%5u', true-1);
end
fprintf('%5s\n%4s\n', '!=', 'true');
for true=1:k
        fprintf('%4u\t', true-1);
        trueidx=find(testy==true);
        for predicted=1:k
                predidx=find(yhats(trueidx)==predicted);
                fprintf('%5u', sum(predidx>0));
        end
        predidx=find(yhats(trueidx)~=true);
        fprintf('%5u\n', sum(predidx>0));
end

toc(start)

end

% http://arxiv.org/pdf/1309.1541v1.pdf
function X = SimplexProj(Y)
  [N,D] = size(Y);
  X = sort(Y,2,'descend');
  Xtmp = bsxfun(@times,cumsum(X,2)-1,(1./(1:D)));
  X = max(bsxfun(@minus,Y,Xtmp(sub2ind([N,D],(1:N)',sum(X>Xtmp,2)))),0);
end
当我在台式机上运行它时
>> calgevsquared
2,1,20 3,1,20 4,1,20 5,1,20 6,1,20 7,1,20 8,1,20 9,1,20 10,1,20 
1,2,20 3,2,20 4,2,20 5,2,20 6,2,20 7,2,20 8,2,20 9,2,20 10,2,20 
1,3,20 2,3,20 4,3,20 5,3,20 6,3,20 7,3,20 8,3,20 9,3,20 10,3,20 
1,4,20 2,4,20 3,4,20 5,4,20 6,4,20 7,4,20 8,4,20 9,4,20 10,4,20 
1,5,20 2,5,20 3,5,20 4,5,20 6,5,20 7,5,20 8,5,20 9,5,20 10,5,20 
1,6,20 2,6,20 3,6,20 4,6,20 5,6,20 7,6,20 8,6,20 9,6,20 10,6,20 
1,7,20 2,7,20 3,7,20 4,7,20 5,7,20 6,7,20 8,7,20 9,7,20 10,7,20 
1,8,20 2,8,20 3,8,20 4,8,20 5,8,20 6,8,20 7,8,20 9,8,20 10,8,20 
1,9,20 2,9,20 3,9,20 4,9,20 5,9,20 6,9,20 7,9,20 8,9,20 10,9,20 
1,10,20 2,10,20 3,10,20 4,10,20 5,10,20 6,10,20 7,10,20 8,10,20 9,10,20 
2,1,15 3,1,20 4,1,20 5,1,20 6,1,20 7,1,20 8,1,20 9,1,20 10,1,20 
1,2,20 3,2,20 4,2,20 5,2,20 6,2,20 7,2,20 8,2,20 9,2,20 10,2,20 
1,3,20 2,3,11 4,3,17 5,3,20 6,3,20 7,3,19 8,3,18 9,3,18 10,3,19 
1,4,20 2,4,12 3,4,20 5,4,20 6,4,12 7,4,20 8,4,19 9,4,15 10,4,20 
1,5,20 2,5,12 3,5,20 4,5,20 6,5,20 7,5,20 8,5,16 9,5,20 10,5,9 
1,6,18 2,6,13 3,6,20 4,6,12 5,6,20 7,6,18 8,6,20 9,6,13 10,6,18 
1,7,20 2,7,14 3,7,20 4,7,20 5,7,20 6,7,20 8,7,20 9,7,20 10,7,20 
1,8,20 2,8,14 3,8,20 4,8,20 5,8,20 6,8,20 7,8,20 9,8,20 10,8,12 
1,9,20 2,9,9 3,9,20 4,9,15 5,9,18 6,9,11 7,9,20 8,9,17 10,9,16 
1,10,20 2,10,14 3,10,20 4,10,20 5,10,14 6,10,20 7,10,20 8,10,12 9,10,20 
gamma=0.1,top=20,threshold=7.5
last=1630 filtered=170
1,0.0035,0.0097
2,0.00263333,0.0096
3,0.00191667,0.0092
4,0.00156667,0.0093
5,0.00141667,0.0091
pred        0    1    2    3    4    5    6    7    8    9   !=
true
   0      977    0    1    0    0    1    0    1    0    0    3
   1        0 1129    2    1    0    0    1    1    1    0    6
   2        1    1 1020    0    1    0    0    6    3    0   12
   3        0    0    1 1004    0    1    0    2    1    1    6
   4        0    0    0    0  972    0    4    0    2    4   10
   5        1    0    0    5    0  883    2    1    0    0    9
   6        4    2    0    0    2    2  947    0    1    0   11
   7        0    2    5    0    0    0    0 1018    1    2   10
   8        1    0    1    1    1    1    0    1  966    2    8
   9        1    1    0    2    5    2    0    4    1  993   16
Elapsed time is 186.147659 seconds.
That's a pretty good confusion matrix, comparable to state-of-the-art deep learning results on (permutation invariant) mnist . In the paper we report a slightly 更差 number (96 test errors) because for a paper we have to choose hyperparameters via cross-validation on the training set rather than cherry-pick them as for a blog post.

此处所述的技术实际上仅对超薄设计矩阵有用(即,有很多示例,但没有太多特征):如果原始特征维数太大(例如,$>10 ^ 4 $)比单纯使用标准广义特征求解器变得缓慢或不可行,并且还需要其他技巧。此外,如果类数太大而不是解决$ O(k ^ 2)$广义特征值问题,那也是不合理的。我们正在努力解决这些问题,我们也很高兴将此策略扩展到结构化预测。希望我们在接下来的几届会议上能有更多的话要说。

2014年3月9日星期日

快速失败

我在圣诞节休息期间研究了一些与矩阵分解相关的想法。我想知道的两件事是:第一,辍学对于判别低阶二次方是否是一个很好的正则化器;其次,如何做类似 GeV表示学习 用于区分性低阶二次方。对于后者,我有一个确定可以工作的想法,但我无法使其工作。俗话说:“你的宝宝不像你想象的那样美丽”。尽管有我们先前的信念,但大多数想法都不是好主意,因此,尽快消除想法很重要。

新兴企业已经普及了 快速失败,因为大多数商业想法也不是好主意。的想法 最低可行产品 已成为创业社区的中心教条。类似地,在测试机器学习思想时,最好从“最小可行算法”。此类算法使用尽可能多的现有语言和包(例如,Matlab,NumPy)以尽可能高级的语言编写(例如, CVX ),并且不采取任何计算捷径来提高效率。

我开始在Matlab中研究用于矩阵分解的辍学正则化,当我看到它正在起作用时 电影镜头,然后我花了一些时间来实现以减少大众使用量。我的事实 知道了 它应该可以使我克服实施时引入的多个缺陷。短话甚至更短,结果在主分支中,您可以 查看演示.

我尝试的下一个想法是将学习低阶二次特征摆在一个交替的线性分数优化问题上。交替最小二乘的类比是如此强大,以至于从理论上讲,我确信它是赢家。对于二进制二进位示例上的多类预测任务(例如,没有附带信息的电影镜头),请执行以下操作:$ S = \ {\ {(l,r),y \} | l \ in \ {0,1 \} ^ m,r \ in \ {0,1 \} ^ n,y \ in \ {0,1,\ ldots,k \} \} $,一个预测变量潜在的MF风格功能看起来像\ [
f((l,r); w,p,q)= w ^ \ top(l,r)+(l ^ \ top p)(r ^ \ top q),
\] 为了简单起见,忽略了常量功能。这里$ p \ in \ mathbb {R} _ + ^ m $和$ q \ in \ mathbb {R} _ + ^ n $是单个潜在特征。在没有附带信息的电影镜头上,$ l $和$ r $分别是用户ID和电影ID的指示变量,因此$ p $和$ q $由这些标识符索引,并分别生成一个标量,并将其乘积添加到预测变量中。

想法是选择潜在特征在$ i $类上高度活跃,而在另一个$ j $类上高度活跃,\ [
\ max_ {p \ in \ mathbb {R} _ + ^ m,q \ in \ mathbb {R} _ + ^ n} \ frac {p ^ \ top \ mathbb {E} [l r ^ \ top | y = i] q} {\ alpha + p ^ \ top \ mathbb {E} [l r ^ \ top | y = j] q}。
\] 受$ p \ preceq 1 $和$ q \ preceq 1 $约束(否则它可以分开)。 $ \ alpha>0 $是一个正则化分母的超参数。当然,在实践中,期望值将转换为训练集的平均值。

对于固定的$ p $,这是$ q $的线性分数程序,反之亦然,因此从随机点开始,我能够快速切换到视觉上看起来不错的功能(在高收视率的用户电影对上产生高产品能量,低收视率的用户电影对产品能量较低)。但是,与没有交互作用的线性模型相比,这些功能对测试集的预测提升几乎不存在。然后,我尝试了增强型变体,其中首先拟合没有交互作用的线性模型,然后尝试区分正残差示例和负残差示例。这更有趣:除少数数据外,这些功能最终几乎都为零,这表明尽管原始功能在视觉上看起来不错,但它们大多为线性模型提供了冗余信息。

使用Matlab和CVX,我能够在短短几天之内解决这些负面结果(这有助于在假日期间不召开会议)。我可能会搞砸了,但实际上这个主意是个好主意吗?是的,但是在如此高的水平上进行工作消除了对优化器的担忧,这使它更有可能实际上是错误的策略。无论如何,我都有很多想法,我需要花时间在那些最有可能产生有趣结果的想法上。尽管不是确定的,但是这些快速的实验表明我应该将时间花在其他地方。

认为是 贝叶斯搜索理论 在思想空间上。







2014年2月17日,星期一

机器学习狗屋

这是关于 角色扮演 发布。当我发表这篇文章时,我不得不使用次优的优化策略,因为 尼科斯 仍在完善 优越策略. Now he has agreed to do a guest post detailing much 更好 techniques.

机器学习狗屋

大约一年前 深卡卡德 在雷德蒙访问我们。他来谈谈他在使用矩量法而不是最大似然法估算模型(例如高斯模型和潜在狄利克雷分配的混合模型)方面的出色工作。 Sham喜欢简单而强大的算法。矩量法就是这样的一个例子:您不必担心局部最小值,初始化等等。今天,我要谈谈我与Sham(和 阿列克 格雷格 )。

当Sham拜访时,我刚从研究生院毕业,并且主要处理了将示例表示为高维稀疏向量的问题。当时,我不完全欣赏他坚持他所说的话“处理数据中的相关性”。您知道,Sham已开始探索一系列非常不同的问题。来自图像,音频和视频的数据是密集的,而不是高维的。即使数据名义上是高维的,数据矩阵的特征值也会迅速衰减,我们可以减小维数(例如使用随机SVD / PCA),而不会影响性能。对于文本问题根本不是这样。

这对学习算法有什么影响?首先,理论表明,对于这些病态问题(在线),一阶优化器将缓慢收敛。在实践中,情况甚至更糟。这些方法不仅需要多次通过,而且根本无法达到二阶优化方法所能达到的测试精度。在尝试之前,我一直不相信。但是二阶优化可能会很慢,因此在本文中,我将描述两种快速,健壮且没有(与优化相关的)调整参数的算法。我还将探讨一种解决高维问题的方法。两种算法每次更新都花费$ O(d ^ 2k)$,它们的收敛不依赖于条件数$ \ kappa $。这比标准二阶算法每次更新所需的时间$ O(d ^ 3k ^ 3)$便宜得多。另一方面,一阶算法每次更新需要$ O(dk)$,但它们的收敛性取决于$ \ kappa $,因此,在条件数较大时,以下方法更可取。

我们将关注mutliclass(和multilabel)分类,因为这类问题具有我们将要利用的特殊结构。首先,假设我们要拟合一个\ [
\ mathbb {E} [y | x] = g(x ^ \ top W ^ *),
\]
其中$ y $是$ k $类之一的指标向量,$ x \ in \ mathbb {R} ^ d $是我们的输入向量,$ W ^ * $是$ d \ timesk $参数矩阵要估计,并且$ g:\ mathbb {R} ^ k \到\ Delta ^ k $是softmax链接函数,将实数向量映射到概率单纯形:\ [
g(v)= \ left [\ begin {array} {c}
\ frac {\ exp(v_1)} {\ sum_ {j = 1} ^ k \ exp(v_j)} \\
\ vdots \\
\ frac {\ exp(v_k)} {\ sum_ {j = 1} ^ k \ exp(v_j)} \\
\ end {array} \ right]。
\] 第一种算法的基本思想是为多项式逻辑损失的Hessian提出一个很好的代理。这个坏男孩是$ dk \ times dk $,并取决于当前参数。相反,我们将使用不依赖于参数且易于计算的矩阵。底线是多项逻辑回归,我们可以得到一个对角线代理,在对角线上有$ k $个相同的块,每个块的大小为$ d \ times d $。将块选择为$ \ frac {1} {2} X ^ \ top X $可确保我们的更新永远不会发散,同时避免行搜索和弄乱步长。使用此矩阵作为前提条件,我们可以继续进行前提条件(批量)的梯度下降操作。剧本 毫升 通过两个(有原则的)修改来做到这一点,从而大大加快了工作速度。首先,我们在足够大的子样本上计算预处理器。该脚本在注释中包括完整预处理器的代码。第二个修改是我们使用 加速梯度下降 而不是梯度下降。

将此优化器插入 角色扮演 几个月前的脚本在我的计算机上以9.7秒的时间提供了0.9844的测试精度,这比LBFGS快约20倍,并且精度更高。

第二种算法甚至更快,并且适用于多类以及多标签问题。还有一个缺点是,您不会在尾巴中获得非常准确的概率估计:这种方法不能优化交叉熵。基本思想是我们将学习链接功能,有时也称为校准。

对于二进制分类, PAV算法 可以学习使所有单调函数中的平方误差最小的链接函数。有趣的是, 等温纸 证明在PAV和线性分类器的参数的最小二乘学习之间进行迭代会导致此非凸问题的全局最小值。

剧本 cls.m 从我们在拟合目标和校准之间交替的意义上讲,将这些思想扩展到多类分类。在实现中使用的校准概念有些薄弱,等同于假设未知链接函数的逆可以表示为原始预测的低次多项式。为了简单起见,我们开了两个角:首先,我们不强迫链接为单调的(尽管单调性是 为高尺寸精心定义)。其次,我们假设在训练时(也称为转导设置)可以访问未标记的测试数据。在没有任何其他见解的情况下,不假定这样做的实现将更加复杂。

将优化器插入上述角色扮演脚本中,我在机器上的9.4秒内获得了0.9844的测试精度。同样,我们比LBFGS快20倍以上,并且更加准确。有趣的是,将该算法扩展为在多标签设置中工作非常简单:我们将其投影到单元超立方体上,而不是投影到单纯形上。

高维数据呢?这就是为什么二阶方法出现在机器学习社区的狗屋中的主要原因。一个简单而实用的解决方案是从加速和协调下降方法中调适思想。我们采用了一系列功能,并根据上述任一方法对它们进行了优化。然后,我们采用另一批特征并拟合残差。通常,根据问题,批量大小可以在300到2000之间。较小的尺寸提供最大的速度潜力,较大的尺寸提供最大的准确性潜力。提供最佳运行时间/精度权衡的批次大小取决于问题。脚本 mlsinner.m deals with the inner loop of this procedure. It takes two additional parameters that will be provided by the outer loop. It only performs a few iterations trying to find how to extend our initial predictions using a new batch of features so that we approximate the labels 更好. We also pass in a vector of weights which tell us on which examples should the preconditioner focus on. The outer loop stagewisemls.m 只需生成新的功能批次,跟踪预测并更新预处理器的重要性权重即可。

将此优化器插入cosplay脚本中,可以在67秒内得到0.986的测试精度。

最后, 角色扮演 driver.m 在mnist数据集上运行上述所有算法。这是八度复制的方法。 (我上面报告的时间是在MATLAB中进行的。)
git clone //github.com/fest/secondorderdemos.git
cd secondorderdemos
octave  -q   角色扮演 driver.m

2013年11月9日,星期六

我们可以哈希一下

该实验室位于西北太平洋,因此很自然地会问什么机器学习原语和 酸洗 。目前有两名主要候选人: 随机特征图和the 哈希技巧。事实证明,后者可以有益地用于随机PCA。

正如我所见,随机PCA算法 最近讨论, 是真棒。根据经验,要获得非常好的结果,似乎需要两个(或更多个)通过算法。理想情况下,可以只使用一种(结构化的)随机性将数据向下传递到某个计算上合适的维度,然后使用精确的技术将其完成。在实践中,这并不是很好,尽管有时计算上的好处(单次传递数据和低内存使用)是合理的。两遍算法使用第一遍构造正交基础,然后将该基础用于第二遍。除了额外的数据传递外,还需要存储两个传递算法作为基础,以及正交化步骤。如果原始特征维数为$ p $,所需分量数为$ k $,则存储需求为$ O(p k)$,并且正交化步骤的时间复杂度为$ O(p k)$。如果$ O(p k)$可以放入主存储器中,这不是问题,但否则就很麻烦,因为本质上需要分布式QR分解。

哈希技巧(更一般而言,结构化随机性)可以在两个极端之间建立桥梁。想法是使用结构化随机性将特征维数从$ p $减少到$ d $,以使$ O(d k)$适合主存,然后使用两次通过随机算法。这可以看作是利用结构化随机性的一遍算法与传统的两遍算法之间的插值。实际上,我们只是在尝试使用可用的空间资源来获得良好的答案。我们发现散列是稀疏域(例如文本或图形数据)的良好结构化随机性,而其他结构化随机性(例如,子采样 哈特利变换) are 更好 for dense data. When using hashing, other conveniences of the 哈希技巧, such as not needing to know the feature cardinality of the input data apriori, are inherited by the approach.

这些随机方法不应令人生畏:一旦您理解它们,它们将非常简单。这是一些Matlab使用散列进行随机PCA:
function H=makehash(d,p)
  i = linspace(1,d,d);
  j = zeros(1,d);
  s = 2*randi(2,1,d)-3;

  perm = randperm(d);
  j=1+mod(perm(1:d),p);
  H = sparse(i,j,s);
end
function [V,L]=hashpca(X,k,H)
  [~,p] = size(H);
  Omega = randn(p,k+5);
  [n,~] = size(X);
  Z = (X*H)'*((X*H)*Omega)/n;
  Q = orth(Z);
  Z = (X*H)'*((X*H)*Q)/n;
  [V,Lm,~] = svd(Z,'econ');
  V = V(:,1:k);
  L = diag(Lm(1:k,1:k));
end
你可以用类似的东西来调用
>> H=makehash(1000000,100000); [V,L]=hashpca(sprandn(4000000,1000000,1e-5),5,H); L'

ans =

   1.0e-03 *

    0.1083    0.1082    0.1081    0.1080    0.1079
因此,与往常一样,好处之一就是让您在商用笔记本电脑上进行一些计算,而这又使其他实现难以为继。这是PCA产生的图片 公开可用的Twitter社会图 在我的笔记本电脑上使用大约800 MB的内存。散列节省的空间仅约20倍,因此,如果您有一台具有16 GB内存的计算机,则可以使用 红碟 毫无困难,但是当然有了更大的数据集,最终内存会变得昂贵。
该图像可能很难看懂,但是如果单击它会变大,然后如果在新选项卡中打开较大的版本并放大,则可以获得更多细节。

如果您喜欢这种东西,可以查看 ,或者您可以访问 NIPS机器学习随机方法 尼科斯 将讨论的研讨会。 阿伦·库玛(Arun Kumar)于今年夏天在CISL实习,他在 Biglearn 关于实施于 .

2013年7月19日,星期五

使用更少的数据

在一个 以前的帖子 我指出,在进行数据科学时,对较小的数据集进行操作是确保生产率和快速实验的最佳方法之一。在ICML 2013上,我和Nikos提出了 一般策略 使用较少的数据来解决各种各样的问题。

这个想法的灵感来自 类不平衡二次采样启发式。这是计算广告从业者中的一个众所周知的技巧,这种技术的奇特效果一直吸引着我。诀窍在于:当二元分类数据集主要由一个类别的示例组成时,可以对更频繁的类别进行二次采样而不会影响最终分类器的质量。事实证明,我们能够将这一技巧概括如下。

假设您打算通过最小化损失函数$ \ mathcal {L} $(即经验风险最小化(ERM))来从集合$ \ mathcal {H} $中选择假设$ h ^ * $。还要假设有人给您一个假设$ \ tilde h \ in \ mathcal {H} $。您可以在执行ERM之前使用$ \ tilde h $对数据集进行子采样,并且引入的超额风险是适度的(有关确切的超额风险界限,请参见本文)。可以丢弃的数据量取决于$ \ tilde h $的经验损失。如果$ \ tilde h $的经验损失较低,那么您可以主动进行子采样。该策略很简单:以与$ x $上$ \ tilde h $的损失成比例的比率对每个示例$ x $进行采样。您必须对最终子样本进行重要性加权以保持无偏,并在最后一步中将重要性加权的经验损失降至​​最低,但是许多机器学习算法可以直接合并重要性加权(如果没有,则可以使用 将重要性加权损失减少为均匀加权损失 通过拒绝采样)。

在这种解释中,类不平衡子采样启发法对应于使用$ \ tilde h $,它是一个常量预测变量,例如,$ \ forall x,\ tilde h(x)= 0 $对于在正数广告中是一个很好的选择。例子(例如点击)相对较少。但是,此技术的概括适用范围更广。首先,我们有一个非常广泛的损失概念,不仅包括分类,回归,排名和结构化预测。但是还有一些无监督的设置,这些设置可以优化逐点丢失,例如重构错误或困惑。其次,我们允许使用假设集$ \ mathcal {H} $中的任何$ \ tilde h $。通常,对于\\ tilde h $的一个很好的选择是可以容易地按比例估计但损失很小的任何假设。对于类不平衡的问题,最好的常数预测器是很好的,并且很容易按比例估计(只需对标签计数!),但是即使对于那些不平衡的问题,自由选择$ \ tilde h $的能力也具有很大的灵活性。

作为自由选择$ \ tilde h $启用的功能的示例,考虑一下我以前工作过的eHarmony。 eHarmony的一个问题是估计两个人(如果匹配)彼此交流的可能性。 eHarmony已派发约10次6 多年来每天都进行匹配,因此它们拥有庞大的数据集。尽管eHarmony使用数百种功能来预测通信,但仍有一些功能非常有用,而许多功能则非常有用。如果您在会议期间获得了Vaclav Petricek的精彩演讲 UAI 2013推荐研讨会,您知道身高差,年龄差和身体距离是三个具有较高预测价值的功能。仅基于这三个预测变量的预测变量可以轻松地仅使用Hive进行大规模组装,而并非最优的它将损失相对较低。因此,这是$ \ tilde h $的不错的选择。我没有在eHarmony的数据上尝试过此操作,因为在那儿工作时我并不了解这些事情,但是我与Vaclav进行了交谈,他愿意尝试一下。

此技术的一个重要特殊情况是对\\ tilde h $使用线性预测器,对最终ERM使用神经网络或决策树。这很有用,因为线性预测变量可以 估计规模。请注意,要满足定理的条件,您必须确保线性预测变量在$ \ mathcal {H} $中,这对于神经网络意味着从输入到最后一层的直接连接,而对于这两种技术,这意味着非线性预测变量具有访问所有线性特征(可以为最终ERM添加特征)。作为额外的效果,对于线性模型也适用的特征表示也将 也倾向于帮助非线性模型.

因此,现在您有一个原则性的方法可以对巨型数据集进行二次采样,这将在比类不平衡更一般的设置中工作。继续并丢弃一些数据!

2013年6月6日,星期四

生产力即将等待

我最近发表了有关应用数据科学的实用技巧的演讲,我认为我的最佳观察确实很简单:从业人员要经历长期运行的数据处理过程,这意味着要等待的时间很多。如果您可以减少等待时间,那么这将直接转化为您的生产力。有一部很酷的科幻书,叫做 碳改变 角色将自己上载到模拟器中以便更快地思考:在减少等待的程度上,您正在做类似的事情。

为了使事情简单,我在头脑中将事情分为不同的时间范围:
  1. 立即:不到60秒。
  2. 上厕所休息时间:少于5分钟。
  3. 午休时间:少于1小时。
  4. 隔夜:少于12小时。
即时休息次数是午休时间的20倍以上。您一个月只能工作20天,因此减少等待时间意味着您一天之内就可以完成别人一个月内的工作。 此外,由于您(人类)在面对更长的延迟时会更倾向于尝试执行多任务,并且当人们从即时区域移至洗手间区域时,生产率会出现超线性下降。 在多任务处理方面很恐怖.

这是我避免等待的一些技巧。

使用更少的数据

这是一个简单的策略,但是人们仍然无法利用。在进行试验或调试时,您对数据或软件的了解不足,无法证明对所有数据或软件进行计算都是合理的。正如埃迪·伊扎德(Eddie Izzard)所说, ``缩小一点!''

亚线性调试

这里的想法是随着计算的进行输出足够的中间信息,以在完成之前确定您是否注入了重大缺陷或重大改进。在线学习尤其适用于此,因为它取得了相对稳定的进步并提供了瞬时损失信息,但是可以采用其他技术来做到这一点。学习曲线有时会交叉,但是亚线性调试非常适合立即识别出您已经胖了一些东西。

巧妙的术语由John Langford提供。

线性特征工程

我发现线性模型的工程功能然后在相同表示形式(例如神经网络,梯度提升决策树)上切换到更复杂的模型是一个富有成果的模式,因为线性模型的速度有助于快速实验。某些适用于线性模型的事物将倾向于适用于其他模型。当然,要设计出适用于线性模型的特征比较困难。另外,您必须牢记要使用的最终模型,例如,如果最终要使用树,则单变量的单调变换只会对线性模型有所帮助。

将代码移至数据

这是Hadoop的存在点,但是即使在更简单的设置中,确保您在数据所在的位置附近进行工作也可以节省宝贵的传输时间。如果您的数据位于云存储提供商中,请在同一数据中心内启动虚拟机。

2013年5月5日,星期日

数据量大:相应地编码!

机器现在越来越大,越来越快:您可以租用一台具有244 GB RAM和数十个内核的机器,用于$每小时3.50。这意味着您可以删除庞大的数据集,而不必担心分布式编程的麻烦(如Jeff Hodges所指出的那样,`` 一台机器本地的问题很容易``)但是我尝试的大多数机器学习软件都不能真正胜任该任务,因为它没有尊重以下事实: 数据量大。对于想编写机器学习软件并希望通过使用大型单机进行扩展的人们来说,这是我的一些想法。

需要记住的数字是I / O昂贵;在单机环境中,尤其是将数据移入磁盘或从磁盘移出数据。当一件软件强迫您不必要地将数据移入或移出磁盘时,例如,强迫您将多个文件组合成一个文件,强迫您解压缩数据,或更普遍地强迫您实现任何易于计算的形式,这会很痛苦。数据转换。这里有一些避免引起最终用户(包括您自己!)痛苦的方法。

首先,如果可以的话,请流式传输数据,而不是在数据中随意查找。为什么这很重要?因为如果程序将输入视为流,则可以在输入到程序之前按需在内存中对其进行转换,这使程序的用途更加广泛。仅此一项就解决了许多其他问题。例如,如果我的数据分散在多个文件中,我可以即时将它们连接成一个流,或者如果我的数据以有趣的格式压缩,则可以即时对其进行解压缩。现在您可能会说``嘿,我没有在线算法'',但是尽管如此,许多程序还是错过了以流形式访问其输入的机会。例如,(否则确实很棒!) 线性 在数据上进行两次精确的顺序传递(第一个确定维度,第二个将数据读入核心),但是在这两次传递之间它调用 倒带 . That call to 倒带 makes things very difficult; if instead 线性 merely closed 和 reopened the file again, then I could play tricks with named pipes to avoid all sorts of I/O. Even 更好, if 线性 allowed one to specify two files instead of one (with the second file specification optional 和 default being that the second file is the same as the first), then things are even easier since 流处理重定向 技巧可以承担。 las,它都不做这些事情。

宗教上遵守流媒体访问模式是最佳的实践模式,但有时是不可能的。在那种情况下,仍然可以支持一些常见的模式。 不要让我串联文件: this is 更差 than 无用的猫,这是痛苦的缓慢,不必要地使用了猫。如果可以采用一个文件参数,则可以采用多个文件参数,就像它们被串联一样。 不要让我解压缩数据:您应该支持直接读取压缩数据。这不仅消除了实现数据的解压缩版本的需要,而且读取压缩数据并即时对其进行解压缩也比读取解压缩数据要快。 允许我假装输入比实际小 并且仅让您的程序在输入的第一个指定单位上运行(例如,前10000条记录);这有助于对逐渐更大的数据部分进行实验。 (我说数据科学就像求爱一样;我不喜欢一路走动去处理大量的数据,直到我偶然遇到了一些规模较小的偶然事件)。同样,如果您对待输入作为一个流,我可以在不需要您程序的额外帮助的情况下实现所有这些目标和其他目标,因此,这些警告仅适用于出于任何原因需要无顺序访问其输入的那些人。顺便说一下,您可以判断是否将输入视为流:只能执行打开,读取和关闭操作。

很少有机器学习工具包可以完全达到另一个层次,这是一个 DSL 用于实时数据转换。如果程序将输入数据视为流,并且只要转换后的数据不会太大,则可以使用进程间通信来模拟,而无需使用进程间通信来实现。 IPC 是可以接受的。这是mnist演示中的示例shell脚本摘录 Vowpal兔子
SHUFFLE='BEGIN { srand 69; };
         $i = int rand 1000;
         print $b[$i] if $b[$i];
         $b[$i] = $_; } { print grep { defined $_ } @b;'

paste -d' '                                                             \
  <(zcat train8m-labels-idx1-ubyte.gz | ./extract-labels)               \
  <(zcat train8m-images-idx3-ubyte.gz | ./extractpixels) |              \
perl -ne ${SHUFFLE} |                                                   \
./roundrobin ./pixelngrams 3 |                                          \
time ../../vowpalwabbit/vw --oaa 10 -f  mnist 8m11png.model               \
   -b 20 --adaptive --invariant                                         \
   --nn 5 --inpass                                                      \
   -l 0.05
在没有中间实现到磁盘的情况下,这里要解决的问题是:1)标签和数据位于不同的文件中(它们不是面向行的),需要将它们连接在一起; 2)有助于稍微整理数据以打破顺序相关性 新元 ;和3)需要计算其他像素图特征,这是CPU密集型的,因此为此使用了3个内核(通过辅助脚本循环)。

因此,上面看起来不错,为什么我们需要DSL才能在机器学习软件内部进行即时数据转换?一个很大的原因是中间体变大,IPC和解析输入的开销变得很大。在这种情况下,最好将转换推迟到学习核心内部(例如, 棺材 )。 的 -q , - 立方体 --ngram arguments to Vowpal兔子 constitute a simple mini-language with substantial practical utility; even 更好 would be something as expressive as R公式.

2013年2月21日,星期四

大声一点

我和尼科斯最近 向vee-dub添加了神经网络 通过减少。这不是深度学习的实现,它只是一个隐藏层,因此您可能会问``这有什么意义?''我们最初的动机是仅使用vee-dub赢得一些Kaggle比赛。尽管最近我一直很忙,无法参加任何比赛,但是减少的效果符合预期。特别是,我希望可以通过对线性模型有利的工程特征来继续解决大多数问题,并在末尾添加一些隐藏单元以进一步提高性能。在谈论一个 计算与数据集大小的权衡,但这是一个更明确的示例。

来自的拼接站点数据集 2008年Pascal大规模学习挑战赛 是5000万个标记的DNA序列的集合,每个序列的长度为200个碱基对。就我们的目的而言,这是一个字母有限的字符串的二进制分类问题。这里有些例子:
% paste -d' ' <(bzcat dna_train.lab.bz2) <(bzcat dna_train.dat.bz2) | head -3
-1 AGGTTGGAGTGCAGTGGTGCGATCATAGCTCACTGCAGCCTCAAACTCCTGGGCTCAAGTGATCCTCCCATCTCAGCCTCCCAAATAGCTGGGCCTATAGGCATGCACTACCATGCTCAGCTAATTCTTTTGTTGTTGTTGTTGAGACGAAGCCTCGCTCTGTCGCCCAGGCTGGAGTGCAGTGGCACAATCTCGGCTCG
-1 TAAAAAAATGACGGCCGGTCGCAGTGGCTCATGCCTGTAATCCTAGCACTTTGGGAGGCCGAGGCGGGTGAATCACCTGAGGCCAGGAGTTCGAGATCAGCCTGGCCAACATGGAGAAATCCCGTCTCTACTAAAAATACAAAAATTAGCCAGGCATGGTGGCGGGTGCCTGTAATCCCAGCTACTCGGGAGGCTGAGGT
-1 AAAAGAGGTTTAATTGGCTTACAGTTCCGCAGGCTCTACAGGAAGCATAGCGCCAGCATCTCACAATCATGACAGAAGATGAAGAGGGAGCAGGAGCAAGAGAGAGGTGAGGAGGTGCCACACACTTTTAAACAACCAGATCTCACGAAAACTCAGTCACTATTGCAAGAACAGCACCAAGGGGACGGTGTTAGAGCATT
事实证明,如果将这些字符串分解为$ n $ -grams,则逻辑回归效果很好。这是一个小程序,它将DNA序列处理成4克并输出vee-dub兼容格式。
% less Quaddna2vw.cpp
#include <iostream>
#include <string>

namespace
{
  using namespace std;

  unsigned int
  codec (const string::const_iterator& c)
    {
      return *c == 'A' ? 0 :
             *c == 'C' ? 1 :
             *c == 'G' ? 2 : 3;
    }
}

int
main (void)
{
  using namespace std;

  while (! cin.eof ())
    {
      string line;

      getline (cin, line);

      if (line.length ())
        {
          string::const_iterator ppp = line.begin ();
          string::const_iterator pp = ppp + 1;
          string::const_iterator p = pp + 1;
          unsigned int offset = 1;

          cout << " |f";

          for (string::const_iterator c = p + 1;
               c != line.end ();
               ++ppp, ++pp, ++p, ++c)
            {
              unsigned int val = 64 * codec (ppp) +
                                 16 * codec (pp) +
                                  4 * codec (p) +
                                      codec (c);

              cout << " " << offset + val << ":1";
              offset += 256;
            }

          cout << endl;
        }
    }

  return 0;
}
我将使用以下Makefile来驱动学习渠道。
% less Makefile
SHELL=/bin/zsh
CXXFLAGS=-O3

.SECONDARY:

all:

%.check:
        @test -x "$$(which $*)" || {                            \
          echo "ERROR: you need to install $*" 1>&2;            \
          exit 1;                                               \
        }

dna_train.%.bz2: wget.check
        wget ftp://largescale.ml.tu-berlin.de/largescale/dna/dna_train.$*.bz2

quaddna2vw: Quaddna2vw.cpp

quaddna.model.nn%: dna_train.lab.bz2 dna_train.dat.bz2 Quaddna2vw  大众 .check
        time paste -d' '                                        \
            <(bzcat $(word 1,$^))                               \
            <(bzcat $(word 2,$^) | ./quaddna2vw) |              \
          tail -n +1000000 |                                    \
         大众  -b 24 -l 0.05 --adaptive --invariant                 \
          --loss_function logistic -f $@                        \
          $$([ $* -gt 0 ] && echo "--nn $* --inpass")

quaddna.test.%: dna_train.lab.bz2 dna_train.dat.bz2 quaddna.model.% Quaddna2vw  大众 .check
        paste -d' '                                             \
          <(bzcat $(word 1,$^))                                 \
          <(bzcat $(word 2,$^) | ./quaddna2vw) |                \
        head -n +1000000 |                                      \
         大众  -t --loss_function logistic -i $(word 3,$^) -p $@

quaddna.perf.%: dna_train.lab.bz2 quaddna.test.% perf.check
        paste -d' '                                             \
          <(bzcat $(word 1,$^))                                 \
          $(word 2,$^) |                                        \
        head -n +1000000 |                                      \
        perf -ROC -APR
这是使用logistic回归对数据进行一次sgd传递的结果。
% make quaddna.perf.nn0
g++ -O3 -I/home/pmineiro/include -I/usr/local/include -L/home/pmineiro/lib -L/usr/local/lib  Quaddna2vw.cpp   -o Quaddna2vw
time paste -d' '                                        \
            <(bzcat dna_train.lab.bz2)                          \
            <(bzcat dna_train.dat.bz2 | ./quaddna2vw) |         \
          tail -n +1000000 |                                    \
         大众  -b 24 -l 0.05 --adaptive --invariant                 \
          --loss_function logistic -f quaddna.model.nn0                 \
          $([ 0 -gt 0 ] && echo "--nn 0 --inpass")
final_regressor = quaddna.model.nn0
Num weight bits = 24
learning rate = 0.05
initial_t = 0
power_t = 0.5
using no cache
Reading from
num sources = 1
average    since         example     example  current  current  current
loss       last          counter      weight    label  predict features
0.673094   0.673094            3         3.0  -1.0000  -0.0639      198
0.663842   0.654590            6         6.0  -1.0000  -0.0902      198
0.623277   0.574599           11        11.0  -1.0000  -0.3074      198
0.579802   0.536327           22        22.0  -1.0000  -0.3935      198
...
0.011148   0.009709     22802601  22802601.0  -1.0000 -12.1878      198
0.009952   0.008755     45605201  45605201.0  -1.0000 -12.7672      198

finished run
number of examples = 49000001
weighted example sum = 4.9e+07
weighted label sum = -4.872e+07
average loss = 0.009849
best constant = -0.9942
total feature number = 9702000198
paste -d' ' <(bzcat dna_train.lab.bz2)   53.69s user 973.20s system 36% cpu 46:22.36 total
tail -n +1000000  3.87s user 661.57s system 23% cpu 46:22.36 total
vw -b 24 -l 0.05 --adaptive --invariant --loss_function logistic -f    286.54s user 1380.19s system 59% cpu 46:22.43 total
paste -d' '                                             \
          <(bzcat dna_train.lab.bz2)                            \
          <(bzcat dna_train.dat.bz2 | ./quaddna2vw) |           \
        head -n +1000000 |                                      \
         大众  -t --loss_function logistic -i quaddna.model.nn0 -p quaddna.test.nn0
only testing
Num weight bits = 24
learning rate = 10
initial_t = 1
power_t = 0.5
predictions = quaddna.test.nn0
using no cache
Reading from
num sources = 1
average    since         example     example  current  current  current
loss       last          counter      weight    label  predict features
0.000020   0.000020            3         3.0  -1.0000 -17.4051      198
0.000017   0.000014            6         6.0  -1.0000 -17.3808      198
0.000272   0.000578           11        11.0  -1.0000  -5.8593      198
0.000168   0.000065           22        22.0  -1.0000 -10.5622      198
...
0.008531   0.008113       356291    356291.0  -1.0000 -14.7463      198
0.008372   0.008213       712582    712582.0  -1.0000  -7.1162      198

finished run
number of examples = 1000000
weighted example sum = 1e+06
weighted label sum = -9.942e+05
average loss = 0.008434
best constant = -0.9942
total feature number = 198000000
paste -d' '                                             \
          <(bzcat dna_train.lab.bz2)                            \
          quaddna.test.nn0 |                                    \
        head -n +1000000 |                                      \
        perf -ROC -APR
APR    0.51482
ROC    0.97749
挂钟训练时间为47分钟,测试APR为0.514。 (如果仔细阅读以上内容,您会注意到我将文件的前一百万行用作测试数据,将其余的几行用作训练数据。)大规模学习挑战的条目的APR约为0.2,这是从unigram logistic回归中得到的,而此数据集上最著名的方法需要多个核心天才能计算并获得约0.58的APR。

在以上运行期间 Quaddna2vw 使用100%的1 cpu和 大众 使用约60%的另一个。换一种说法, 大众 这不是瓶颈,我们可以花一些额外的cpu学习,而不会产生实际的挂钟影响。因此,通过指定少量隐藏单元并通过输入直接连接到输出层,可以大声一点 --nn 8 --inpass。其他所有内容都相同。
% make quaddna.perf.nn8
time paste -d' '                                        \
            <(bzcat dna_train.lab.bz2)                          \
            <(bzcat dna_train.dat.bz2 | ./quaddna2vw) |         \
          tail -n +1000000 |                                    \
         大众  -b 24 -l 0.05 --adaptive --invariant                 \
          --loss_function logistic -f quaddna.model.nn8                 \
          $([ 8 -gt 0 ] && echo "--nn 8 --inpass")
final_regressor = quaddna.model.nn8
Num weight bits = 24
learning rate = 0.05
initial_t = 0
power_t = 0.5
using input passthrough for neural network training
randomly initializing neural network output weights  和  hidden bias
using no cache
Reading from
num sources = 1
average    since         example     example  current  current  current
loss       last          counter      weight    label  predict features
0.600105   0.600105            3         3.0  -1.0000  -0.2497      198
0.576544   0.552984            6         6.0  -1.0000  -0.3317      198
0.525074   0.463309           11        11.0  -1.0000  -0.6047      198
0.465905   0.406737           22        22.0  -1.0000  -0.7760      198
...
0.010760   0.009331     22802601  22802601.0  -1.0000 -11.5363      198
0.009633   0.008505     45605201  45605201.0  -1.0000 -11.7959      198

finished run
number of examples = 49000001
weighted example sum = 4.9e+07
weighted label sum = -4.872e+07
average loss = 0.009538
best constant = -0.9942
total feature number = 9702000198
paste -d' ' <(bzcat dna_train.lab.bz2)   58.24s user 1017.98s system 38% cpu 46:23.54 total
tail -n +1000000  3.77s user 682.93s system 24% cpu 46:23.54 total
vw -b 24 -l 0.05 --adaptive --invariant --loss_function logistic -f    2341.03s user 573.53s system 104% cpu 46:23.61 total
paste -d' '                                             \
          <(bzcat dna_train.lab.bz2)                            \
          <(bzcat dna_train.dat.bz2 | ./quaddna2vw) |           \
        head -n +1000000 |                                      \
         大众  -t --loss_function logistic -i quaddna.model.nn8 -p quaddna.test.nn8
only testing
Num weight bits = 24
learning rate = 10
initial_t = 1
power_t = 0.5
predictions = quaddna.test.nn8
using input passthrough for neural network testing
using no cache
Reading from
num sources = 1
average    since         example     example  current  current  current
loss       last          counter      weight    label  predict features
0.000041   0.000041            3         3.0  -1.0000 -15.2224      198
0.000028   0.000015            6         6.0  -1.0000 -16.5099      198
0.000128   0.000247           11        11.0  -1.0000  -6.7542      198
0.000093   0.000059           22        22.0  -1.0000 -10.7089      198
...
0.008343   0.007864       356291    356291.0  -1.0000 -14.3546      198
0.008138   0.007934       712582    712582.0  -1.0000  -7.0710      198

finished run
number of examples = 1000000
weighted example sum = 1e+06
weighted label sum = -9.942e+05
average loss = 0.008221
best constant = -0.9942
total feature number = 198000000
paste -d' '                                             \
          <(bzcat dna_train.lab.bz2)                            \
          quaddna.test.nn8 |                                    \
        head -n +1000000 |                                      \
        perf -ROC -APR
APR    0.53259
ROC    0.97844
从挂钟的角度来看,这是免费的:总培训时间增加了1秒,并且 大众 Quaddna2vw 现在吞吐量大致相等。同时,实际年利率从0.515增加到0.532。这说明了一个基本思想:设计出适合您的线性模型的特征,然后当您精疲力尽时,尝试添加一些隐藏的单元。就像转动设计矩阵 最多十一.

I speculate something akin to gradient boosting is happening due to the learning rate schedule induced by the adaptive gradient. Specifically if the direct connections are converging more rapidly than the hidden units are effectively being asked to model the residual from the linear model. This suggests a more explicit form of boosting might yield an even 更好 free lunch.













2012年12月19日,星期三

你真的有大数据吗?

有个 宗教战争 在ML社区酝酿。一方面,那些认为大型集群是处理大数据的方式的人。另一方面,那些认为高端台式机可以提供足够的功能而又不那么复杂的人。我认为这场辩论是由不同的扩展动机驱动的。
  1. 对于数据。本质上,有人希望学习尽可能多的数据以获得最佳模型。大型群集可能是该数据的操作存储,并且将数据编组到高端台式机上是不可行的,因此算法必须在群集上运行。原型问题是使用文本特征的广告定位(高经济价值和高数据量)(这样,双线性模型可以很好地实现,但是特征是zipf分布的,因此大数据可以提供有意义的改进)。
  2. 用于计算。数据量可能相对较少,但是学习问题在计算上很激烈。这里的原型问题是在自然数据集上使用神经网络进行深度学习(计算成本较高)(尽管其大小通常适合于舒适地放置在桌面上, 这正在改变)以原始表示形式(因此需要非凸面的``特征发现''样式优化)。
因此,即使您仅针对计算进行扩展,为什么不使用群集?具有多个核心和多个GPU的高端台式机实质上是一个(小型)群集,但其中一个具有高速互连。使用时,这种高速互连是关键 新元 解决非凸优化问题。 新元 是一种惊人的通用优化策略,但具有致命弱点:它会生成许多小的更新,这在分布式环境中意味着高同步成本。在单台机器上,比在群集上减轻此问题(例如,通过微型批处理和流水线操作)更容易。目前,在商品交换集群上,我们几乎只知道如何很好地解决凸优化问题(使用批处理算法)。

单个桌面的带宽相对有限,这意味着单机工作流程可能始于将大型集群上的数据与运营商店争用(例如,通过Hive),但是在某些时候,数据被二次采样到可以由单机管理的大小。这种二次采样实际上可能很早就开始了,有时是在数据生成时开始的,在这种情况下,它变得隐含了(例如,使用编辑判断而不是行为穷举)。

Viewed in this light the debate is really: how much data do you need to build a good solution to a particular problem, 和 it is 更好 to solve a more complicated optimization problem on less data or a less complicated optimization problem on more data. The pithy summarizing question is ``do you really have big data?''. This is problem dependent, allowing the 宗教战争 to persist.

在这种情况下,以下示例很有趣。我拿了 mnist 和trained different predictors on it, where I varied the number of hidden units. There are direct connections from input to output so zero hidden units means a linear predictor. This is a type of ``model complexity dial'' that I was looking for in a 以前的帖子 (尽管这远非理想,因为从0到1的步长将东西从凸形更改为非凸形)。毫不奇怪,添加隐藏单元可以提高泛化能力,但也可以增加运行时间。 (注意:我选择了学习率,通过次数等来优化线性预测器,然后在添加隐藏单位的同时重复使用相同的设置。)


现在想象一下一个计算约束:训练线性预测器只需要27秒。我在每种情况下都随机抽样数据,以使训练时间在所有情况下均约为27秒,然后我评估了整个测试集的概括性(因此您可以将这些数字与上一张图表进行比较)。


对于mnist来说,抛弃数据以学习更复杂的模型似乎最初是个好策略。总的来说,我希望这是高度依赖问题的,作为研究人员或从业人员,最好直觉知道自己偏爱的方法在哪里竞争。 YMMV。

2012年12月2日,星期日

模型复杂度,数据资源和计算约束

阿布·莫斯托法(Abu-Mostofa)在他的精彩视频讲座之一(讲座8 在视频中@ 44:45)指出了“将模型复杂度与数据资源相匹配,而不是目标复杂度”。但是,在大数据机器学习中,这是没有做的。例如,如果您想赢得 卡格勒 涉及约10个数据集的竞赛5 行和大约102 在列中,您使用了庞大的增强决策树集合(与其他东西组合在一起)。但是,将这些数字缩放4个数量级,并且(主要)线性预测变量或接近朴素的贝叶斯风格的方法占主导地位。更多数据,更简单的模型。 ??

发生的事情是计算约束占主导。您可能会认为这是纯粹的工程问题,需要通过分布式学习,GPU等来扩展更复杂的模型。但是,您还可以利用所有额外的功能将更多的数据提供给更简单的模型。因此,这就引出了一个问题:为了学习更复杂的模型,值得丢弃一些数据资源吗?还是放弃一些模型复杂性以保留更多数据资源更好?请注意,考虑到生成模型所需的数据量和计算量,我只是考虑最终模型的质量:在实践中,诸如模型评估时间等用于预测面向消费者的互联网服务至关重要,但让我们忽略这一点。

In my recent career I just assumed it was 更好 to trade model complexity (less) for data resources (more), but I never really investigated or questioned this. Recently I started playing around on 卡格勒 和 I noticed there are many interesting data sets that are not that big, 和 top-heavy tournament-style payoffs incent the use of models more complicated than what I've typically used professionally. That got me itching to add some more powerful techniques to 威杜布 和now there's a neural network reduction but guess what? It's s-l-o-w. Vee-dub has distributed learning so voila I have a distributed neural network learning system but if I'm going to eat an entire cluster for a problem should I use relatively fast linear learning 和 more data, or relatively slow neural network learning 和 refore less data? 有个 data-model complexity frontier here, 和 correct tradeoff is unclear.

There are lots of examples where, for a fixed algorithm, more data is 更好, e.g., 阿加瓦尔(Agarwal)等。等; 和 re are lots of examples where, for a fixed data set, more complicated models are 更好 than simpler ones, e.g., mnist 。想象一个3维图,其中z轴是``模型真棒'',x轴是数据资源,而y轴是模型复杂度。这些结果基本上是关于此二维函数的一维轴平行语句。有没有可以在两个维度上进行比较的结果?一项很棒的研究将比较,例如,在同一问题上对万亿级线性学习与千兆深度学习进行了比较,并尝试对每种技术使用相同的计算资源。

我怀疑对于万亿级学习问题,拥抱线性预测器是一个好主意(到目前为止!),但是鉴于当前可用的数据资源和计算约束条件,在建模能力方面仍有一定的改进空间。这表明对于这种情况,所写的神经网络简化方法是不可取的,因为它没有从输入层到输出层的直接连接。如果我增加这些多余的连接,希望不会增加任何隐患,并且从相对较少的隐藏单元中获得一些适度的好处(尽管我在学习线性预测器的同时还难以学习低阶潜在模型,因此无法保证) 。

对于Kaggle区域,我非常确定能够将大约10台机器扔掉6 大约10行3 隐藏的单位将会很棒。

2012年10月21日,星期日

套袋!

我的 最近的Kaggle比赛 经验使我印象深刻,需要更快地选择模型。我最初的计划是创建一个交叉验证 威杜布 插件(减少),但是 尼科斯 说服我 套袋 was both more versatile 和 more intellectually coherent. The basic idea is to multiplex the 权重向量 inside 威杜布 和 learn an ensemble of models simultaneously, each one experiencing a different bootstrapped version of the input sequence. There are three benefits that result:
  1. 型号选择。 预算外估计 function analogously to cross-validated estimates. Monitoring out-of-bag estimates instead of progressive validation loss is a 更好 idea when looping over a data set multiple times.
  2. 置信区间。当开发一个独立的决策系统时,一个点预测通常就足够了;但是,当开发要集成到更大决策系统中的子系统时,区间预测为下游使用者提供了更丰富的摘要。
  3. 更好的结果。归纳可以提高模型的通用性 偏差方差权衡。到目前为止,我还没有看到对数据集的任何实际提升,这是可以理解并可以预期的:线性模型的方差低,因此不能从套袋中受益。为了从套袋中受益,您必须做一些最终输出对训练数据差异更敏感的事情,例如神经网络,树或具有自动数据驱动特征选择的线性模型。
选择模型是我最初的动机,因此这里是利用 KDD世界杯98 数据。竞赛提供了数百个预测功能,但获胜作品仅使用了少量,表明模型选择非常重要。比赛如下:要求您决定向谁发送邀请(蜗牛)邮件;每封邮件的成本为68美分。训练集由特征($ x_i $)对($(x_i,r_i)$)和对应于先前邮件活动的响应捐赠金额(r_i $)组成。评估集仅由$ x_i $组成(除了比赛已结束,因此我们可以窥视并看到评估集的$ r_i $);提交了评估集中每个实例的估计捐赠$ \ hat r_i $,然后根据$ 1 _ {\ hat r_i进行评分>0.68}(r_i-0.68)$。换句话说,即使决定是是否邮寄某人,该决定还是通过估计的大于或小于68美分的答复发送的;否则,就无法评估估计响应的准确性,而实际获得的总利润是评分标准。

我们可以将其建模为重要性加权分类问题,根据\ [将对$ {x_i,r_i)$转换为三元组$(x_i,y_i,c_i)$。
(x_i,r_i)\ to(x_i,1_ {r_i>0.68},| r_i-0.68 |)。
\] 对于评估集,我们可以解码是否直接将决定作为模型的预测类邮寄的决定。在这种情况下,常量预测变量对应于不发邮件或发邮件给所有人的策略。正如曾经拥有邮箱的任何人所能证明的那样,向所有人发送邮件比不向任何人发送邮件更有利可图,因此``向所有人发送邮件''是要克服的基本策略。 (从理论上讲:也许不应该使用机器学习的商业秘密垃圾邮件过滤器,而应该使用机器学习并公开分发 其实 想要购买伟哥并拯救其他所有人免于烦恼。)

我建立了一个幼稚的``厨房水槽''模型,方法是采用训练集中的所有功能,将日期自1900年1月起以数字形式编码为月,使用带有经验分母的样条曲线将数字编码为结点,并对所有其他变量进行分类编码。我还整理了一个模型,其中包含10个功能(通过查看获奖者的作品)(使用与厨房水槽相同的策略进行编码)。结果如下:\ [
\ begin {array} {c | c | c | c}
\ mbox {型号}&\ mbox {训练集利润}&\ mbox {培训设置的利润(实际支出)}&\ mbox {评估集利润} \\ \ hline
\ mbox {向所有人发送邮件}& \$10788.54 & \$10704 \pm \$529 & \$10560.08 \\
\ mbox {10个功能}& \$17596.35 & \$14617 \pm \$434 & \$14896.07 \\
\ mbox {厨房水槽}& \$24353.80 & \$493 \pm \$80 & \$154.92 \\
\ end {array}
\] 因此,厨房水槽严重超出了训练范围,但实际购买力不足以检测到这一点。哇

不幸的是,减少装袋并不比运行多个vee-dub快。对于具有大量I / O开销的简单模型来说,它的速度更快,但是对于更复杂的模型,摊销I / O只是一个适度的好处。在内部对所有内容进行编排更为方便,减少的内容应与vee-dub的分布式学习功能结合在一起,但是在笔记本电脑领域,这并不是一个巨大的胜利。

当然,一旦有了套袋,自然的下一步就是尝试一些不稳定的学习方法。敬请关注!




2012年10月2日,星期二

卡格勒 比赛提示

我最近进入了 卡格勒 第一次比赛。总体而言,这是一次积极的经历,我向有兴趣应用机器学习的任何人推荐它。

这是一场私人比赛,所以我只能讨论一般性,但是幸运的是有很多。经验验证了所有 机器学习民间智慧 尽管Pedro Domingos支持这些原则的应用,但这些支出的最高度量指标驱动的性质对其进行了修改。就像在扑克中一样,需要在锦标赛和桌面游戏之间进行战略调整,而机器学习竞赛则采用了在正常的工业环境中不合适的技术。

评价

对于比赛,我们首先了解评估指标。在现实生活中(又名``桌上游戏''),机器学习系统的目标通常没有被明确指定(例如,``改善相关性''或``检测出类似现象''),或者由于以下原因而难以直接优化:总体影响和不受控制的外部因素(例如,``提高长期客户保留率和满意度'')。在这种情况下使用代理指标,但希望没有人会太在意它们,因为每个人都理解为方便起见选择了代理指标。

在比赛中(又称``锦标赛比赛''),评估指标确定您获得的报酬。因此,需要非常认真地对待它。第一步是尝试使用简单模型(例如,常量模型)重现评估指标,该模型通常是应用于未知数据集的已知函数。可以使用评估泛化误差的方法($ k $倍交叉验证,袋外估计),但重要的是要记住,您并不是要泛化为来自相同分布的未来数据集,而是而是用于评估的特定固定数据集。注意,如果可能的话,过度拟合评估数据集绝对没有问题。是否可行取决于您分配的中间提交数和评分方式,以及是否可以看到评估功能。

在本次比赛中,训练集和评估集之间没有特定变量的配对,因此在对训练集进行交叉验证以估计最终分数时,必须考虑到这一点。但是,提交是在评估数据的固定(未知)子集上评分的,该子集是评估集的逐行随机拆分。因此,提交是探索评估指标的一种高质量方法,我们尽可能多地使用它们(以提交限制为准)。例如,由于评估集是已知的(但标签未知!),我们尝试使用协变量移位来对训练数据进行加权并改善模型。仅使用培训数据来估计其影响将需要实施交叉交叉,并且可能会产生误导。相反,我们准备了两份仅在这方面有所不同的意见书,并很快了解到这不是一个有希望的攻击路线。再举一个例子,我们通过准备一对提交并观察结果分数,在正则化参数的两个不同设置之间做出决定。 (我们使用了无聊的实验设计策略来探究评估集;也许有更好的方法来利用提交的内容。)

特征工程

在这里,比赛和桌上游戏机器学习更加统一,因为特征工程在这两者中都扮演着至关重要的角色。但是,由于比赛的获胜幅度很小,因此比赛功能设计更为疯狂。简而言之,如果它看起来完全可以改善模型,那么它仍然存在:在锦标赛中,可解释性,实现复杂性,可维护性或评估时间等问题并不重要,除非它们在建模期间会给建模者带来问题。竞赛。在桌面游戏中,功能受更细微的成本效益分析的影响,这些因素也考虑了这些因素。

由于特征工程是模型选择,因此监视评估指标很重要。在功能工程阶段,我们使用了 威杜布 专门为了尽快翻动模型。

是时候取消拉皮条功能了。
值得在比赛中花一些时间来提高评估估算的速度。我做了几个,但是错过了一个大比赛,直到比赛结束后才意识到:我通过使用不同的输入调用vee-dub 10次来进行10倍交叉验证,但这最好是在vee内部进行-通过还原接口复制以分摊I / O。希望我能在不久的将来实现它。

数据整形也非常重要且效率较低。通过数据整形,我的意思是选择如何代表学习算法的特定功能(例如,尝试获取该东西的日志并在此处,此处和此处设置一些样条线结)。能够直接向vee-dub指定这种数据整形将再次通过摊销I / O来促进快速实验和参数清除。

最后,我们在数据中发现了某些“特征”,这些特征显然是比赛数据的收集方式,不太可能“真正地泛化”。对于比赛而言,问题在于它们是否会泛化为评估集,因此我们准备了成对的评估稿。在桌面游戏中,除非预测提升很明显,否则根本不会使用这些功能,并且由于明显缺乏面部有效性,即使使用了附加数据,也要谨慎评估这些功能。

顺便说一句,我们确实发现了(显然)真实的功能,这些功能应该可以为比赛发起人提供见识。尽管与比赛相关的激励措施并不完善,但大多数情况下仍可以归结为做好工作。

模型平均

我们的获奖作品包括几种机器学习的模型,这些模型使用完全不同的程序进行训练并取平均。现在这是标准的锦标赛技术,尽管我从未在桌上游戏中明确使用过它(隐式的是,通过增强和装袋;但是平均树和神经网络并不是我在商业环境中做过的事情)。我多么震惊这是多么有效:将一个模型与另一个模型进行平均,这显然更糟,结果要好于任何一个,这要归功于 偏差方差权衡。迅速获得无所作为的习惯成为一种成瘾的习惯,但是最好的结果是结合使用完全不同的方法训练的模型(即,不易变形的模型),并且很难找到产生竞争性结果的完全不同的方法(例如,我们尝试了基于指标的方法,但这些方法太差了,以至于我们在最终的集成中没有使用它们。

Gettin的真实

关于比赛的最好的部分是比赛的激烈程度。在桌面游戏中,您通常会与其他机器学习专家合作,以产生一个有益于业务的良好模型。尽管您可能也在利用机器学习技术与其他企业竞争,但是您的雇主的命运与机器学习模型的质量之间的关系却被模糊了。在锦标赛中,比您在排行榜上表现更好的球队直接表明了您当前技术的次优状态。如果您确实碰巧发现自己处于领先地位,那么线索的微不足道和短暂的性质将驱使您找到进一步的改进和见解。我发现自己的工作远远超出了我的预期。

笑嘻嘻!