刚刚过去的NIPS 2013是我参加的第一个机器学习会议，不愧是机器学习最高水平的盛会，几乎所有可以想象得到的知名学者都参加了会议，在会上也看到了好多有意思的idea。相比起之前参加的CVPR，NIPS的会议议程安排的要紧凑太多：主会期间从早上9点开始听报告，一直到下午6点，中午吃饭休息一个半小时，然后晚上7点到夜里12点是poster session，尽管有5个小时，可因为poster很多，有意思的也很多，5个小时有时候都不够用，往往大家还会讨论到十二点以后才回酒店。workshop期间，早上7点半就开始了，以至于我们不得不6点刚过就起床。我参加了主会和workshop，没有参加第一天的tutorial，整个5天的会议下来学到了很多新东西，在这里做个简单整理和索引。
整体上来讲，我的感觉这届NIPS除了deep learning火爆以外，大规模并行化的machine learning也是重要趋势，另外各个方面都在慢慢的向前推。deep learning的火爆，看看9号的deep learning workshop就知道了。当天的deep learning workshop占据了最大的一个workshop会场，而且场内座无虚席，并且请到了重量级嘉宾Facebook CEO Mark Zuckerberg参加，还爆出大新闻，convolutional neural net的先驱Yann LeCun将加入Facebook并担任刚刚新建的AI lab的director。相比之下，同一天的其他workshop大都黯然失色，有一个workshop甚至一度腾出自己的会场给deep learning workshop做直播会场，播放Zuckerberg Q&A以及panel discussion的实况。考虑到NIPS还有一个关于social network的workshop，Zuckerberg反而来参加deep learning workshop就确实能说明很多问题了。
5号晚上我才赶到，晚上十点半安顿下来就去了会场，本以为会只有寥寥几个人，结果没想到还有好多人在会场，看到Francis Bach还在亲自给别人讲poster，还很惊讶，因为在之前CVPR的时候，基本上都是学生讲poster，很少见到有知名学者亲自讲poster的。不过过了几天见得多了就习以为常了。但当晚毕竟时间有限，而且三个小时的时差也让我很困了，便早早回了酒店歇息。
周五有很多deep learning的文章：
来自华为诺亚方舟实验室的Z.Lu, H.Li的A Deep Architecture for Matching Short Texts介绍了一种做短文本Q&A匹配的方法。他们使用topic model抽取了一些文本匹配的feature，然后将这些feature固定住，再学一个神经网络来估计匹配的评分函数，学习的时候底层的feature并没有变。我不太明白为什么要用topic model加一些预处理的trick来抽取feature，如果能够jointly学习所有的部分应该会有更好的效果。
J. Martens, A. Chattopadhya, T. Pitassi, R. Zemel的文章On the Expressive Power of Restricted Boltzmann Machines将RBM转化为一种特殊的神经网络，从理论上探讨了RBM的表达能力。
T. Mikolov, I. Sutskever, K. Chen, G. Corrado, J. Dean的文章Distributed Representations of Words and Phrases and their Compositionality基本上是他们之前word2vec的一个补充版本，没有什么太多新内容。不过当时在会场看到传说中的Jeff Dean亲自讲poster，还是很意外，毕竟他是排名最后的作者，而且他在业界有如此高的身份。
Y. Bengio, L. Yao, G. Alain, P. Vincent的文章Generalized Denoising Auto-Encoders as Generative Models也是早就看到过，idea是用一个feed forward neural net来学习一个generative model，这样就可以避免partition function的难题。具体来讲使用denoising autoencoder，比如一层的网络就是feed forward，然后在hidden layer加noise，在reconstruct input，通过引入的noise就引入了reconstruction的概率分布，因而就可以当成一个generative model来用了。是个直观的idea，但我觉得这个方法在学习multi-modal distribution的时候会有困难，数学上也不见得很严谨。
I. Goodfellow, M. Mirza, A. Courville, Y. Bengio的Multi-Prediction Deep Boltzmann Machines我没有看上他们的poster，一开始前排deep learning的poster围的人太多，我只好到后面去看其他poster，再过来看的时候作者已经不在跟前了。但文章的idea好像是通过backdrop through variational inference来更好的学习DBM，也不知理解的对不对。
Y. Tang, R. Salakhutdinov的Learning Stochastic Feedforward Neural Networks通过使用binary的随机hidden unit来学习multi-modal的distribution，这个比Bengio的文章看起来更有道理。因为hidden unit是离散变量的话每个不同的取值就是一个mode，加noise就可以表示multiple modes，但Bengio的auto encoder是连续变量，如果加gaussian noise那还是只有一个mode，不过他的framework还是可以generalize到其他的noise distribution。
R. Socher, M. Ganjoo, C. Manning, A. Ng的Zero-Shot Learning Through Cross-Modal Transfer看的时间有点久了，好像是把text和image embed到同一个space里面，这样当给定一些没见过的物体的图像的时候，通过feature mapping可以找到space中邻近的text，以达到所谓的“zero-shot learning”。但印象中用的模型很弱，好像只是image feature做linear regression到text embedding上，image和text也没有做joint fine tuning。而且实验结果也相当弱，所以这一块还有很多工作可以做。
N. Srivastava, R. Salakhutdinov的Discriminative Transfer Learning with Tree-based Priors通过用一个class hierarchy来达到class之间的information sharing，这个在每个class training example少的时候会比较有效。
R. Grosse, C. Maddison, R. Salakhutdinov的Annealing between distributions by averaging moments介绍了一种annealed importance sampling的schedule方法，有别于通用的geometric mean，这里提出做moment averaging，并给出了很多理论上的解释，提供了不少对于AIS的insight。
H. Goh, N. Thome, M. Cord, J. Lim的Top-Down Regularization of Deep Belief Networks提出在学习DBN的时候在layerwise pretraining和discriminative fine tuning中间插入一个步骤做top-down regularization。他们的想法是，generative pre training和discriminative fine tuning中间差别很大，他们希望用一个中间步骤来弥合这两步之间的落差，以更好地初始化DBN中的参数。具体来讲，他们的top down regularization将output固定，这样DBN的两端都有了input，然后还是用类似RBM的方法做layerwise training，不同的是这时除了reconstruct底下一层的input，还同时reconstruct上面一层，这样就间接引入了output信息，同时training依旧基本上还是是generative的，所以就起到了两步中间的桥梁作用。他们实验结果说明这个方法略有一点点效果。不过最近的neural net研究已经发现了其实不用做layerwise pretraining都可以直接做discriminative training，这种改进DBN pretraining的这个idea实用性一般。
J. Ba, B. Frey的Adaptive dropout for training deep neural networks印象中是用另一个neural net来学习dropout rate，而不是使用固定的0.5。
P. Baldi, P. Sadowski的Understanding Dropout是一篇oral，提出了应该是第一个分析nonlinear unit的dropout的方法，报告当时听得不是很懂，印象中做了一些近似之后就比较好分析了，但只能分析sigmoid unit。
S. Wager, S. Wang, P. Liang的Dropout Training as Adaptive Regularization也是一篇分析dropout的文章，他们分析了最简单的linear model的dropout，并且发现在使用二阶近似的情况下dropout等价于一个data-dependent regularization，这个regularization term还和data的Fisher information matrix有关系，并且还可以用来作semi-supervised learning。
Ö. Aslan, H. Cheng, X. Zhang, D. Schuurmans的Convex Two-Layer Modeling提出了一种学习两层网络的方法，将每层的学习都建模成一个convex optimization问题，这样两层的学习就可以学的比较好。但方法好像扩展到多层有难度，跟作者聊他们也没认真和neural net进行比较。
除了deep learning，周五还有很多其他有意思的文章：
B. Mirzasoleiman, A. Karbasi, R. Sarkar, A. Krause的Distributed Submodular Maximization: Identifying Representative Elements in Massive Data提出了一种找出集合中有代表性的元素的并行化方法。找有代表性的元素这个问题被建模成一个submodular function optimization的问题。假定要用m个机器在n个元素中找出k个有代表性的，最直接的并行化方法是把数据分成m份，然后在每份中找出k/m个有代表性的元素，最后合起来得到k个。但这个方法并不能找到最优解，因为每部分里面的代表性元素往往会有重复。这篇文章提出的方法是在每份数据上都找出k个有代表性的元素，合起来得到mk个，之后再进行筛选得到k个，这样就能有一些理论保证。一个类似的问题是找出n个元素中最大的k个，如果在每一份数据中只找到最大的k/m个，那么由于数据在每一份中分布不绝对均匀，合起来的k个很可能并不一定是最大的；另一方面，如果每一份数据上都找最大的k个，合起来得到mk个，那总的最大的k个元素一定在这选出的mk个中。在并行化中引入的这些冗余性会牺牲少量的效率，但往往可以达到很好的效果，值得借鉴。
V. Mansinghka, T. Kulkarni, Y. Perov, J. Tenenbaum的Approximate Bayesian Image Interpretation using Generative Probabilistic Graphics Programs提出在做recognition的时候用graphics engine，他们的实验中用这个想法做了一个captcha识别的东西。模型还是相对来说比较简单，但我觉得是正确的方向。
T. Hazan, S. Maji, J. Keshet, T. Jaakkola的Learning Efficient Random Maximum A-Posteriori Predictors with Non-Decomposable Loss Functions提出了一种学习RandomMAP model的方法，有意思的一个地方是他们直接用了一个PAC Bayes bound，并且直接将这个bound作为优化的目标函数，这样直接就得到了expected loss objective。和我之前的文章差不多，使用了expected loss之后任何的loss都好优化了，因为loss function没有gradient，因此任何non-decomposable loss都可以用。和PAC Bayes bound的联系比较有意思，而且expected loss也很适合Random MAP model。
J. Domke的Structured Learning via Logistic Regression提出在structured prediction中优化非线性的score function。这个题目之前没什么人做过，我尝试过CRF+NeuralNet直接做梯度优化，虽然优化问题不再凸，但效果还是很不错。这篇文章的出发点是假设inference也是intractable的，然后就用到了Tamir和Raquel之前的一边做inference一边做learning的想法，并且加了一些decomposition，然后每个子问题就可以当成logistic regression来解。我的感觉这文章方法有点过于fancy了，对于inference intractable的问题，直接用一个approximate inference的方法做inference然后在做梯度优化效果应该也不错，但是这篇文章里面没有同这种简单方法进行比较。
K. Mohan, J. Pearl, J. Tian的Graphical Models for Inference with Missing Data我没有去看，但路过的时候看到图灵奖获得者Judea Pearl亲自讲poster，丝毫不摆架子，还是有些感慨，这才是一个健康的学术环境。
R. Matsushita, T. Tanaka的Low-rank matrix reconstruction and clustering via approximate message passing提出了一个挺有意思的idea：用belief propagation来做matrix factorization。效果不一定比gradient based matrix factorization好，但用belief propagation来做这个问题还是一个很有意思的想法，并且还可以加入一些更结构化的约束，这些约束用传统的gradient based MF是很难model的。
周六早上Daphne Koller的invited talk讲的非常好，coursera和其他的一些网站最近彻底改变了在线教育的面貌，而且还在飞速发展。从根本上，教育使得人们有了更好生活的机会，高质量的免费教育对促进社会平等的贡献可谓巨大。演讲的最后Daphne提到coursera帮助一些失业女工重新找到工作机会的故事，很感人也很振奋人心。我在coursera上也上过好几门课了，确实学到了不少东西。为社会做贡献有很多途径，作为一个学者和科研人员，做科研自然是理所当然的途径，但像Andrew和Daphne这样也有很多其他途径可走。周六的文章感兴趣的不多，也是回宾馆最早的一天，但也还是有一些有意思的文章。
R. Babbar, I. Partalas, E. Gaussier, M. Amini的On Flat versus Hierarchical Classification in Large-Scale Taxonomies从理论上分析了hierarchical classification。hierarchical classification是构建一个class hierarchy，所有的output类别都在最底层，分类时从顶端向下，每一层都只在很少的几个类中选一个然后到下一层。这本质上基本上是一个greedy的方法，因为在上层一旦出错下层就没办法改过来。因此在数据多的时候这种hierarchical classification基本上不会比flat classification好，但在每类数据少的时候，这种greedy方法反而会起到一些regularization的作用。这篇文章正是在理论上论证了这样的直观结论。另外，hierarchical classification除了对overfitting有帮助意外，在类别数量十分巨大的时候，会有巨大的效率优势，因为这种hierarchy结构能够将class activation的计算从O(n)减到O(log n)。
M. Cisse, N. Usunier, T. Artières, P. Gallinari的Robust Bloom Filters for Large MultiLabel Classification Tasks听说是用了binary representation而非1-of-K做output encoding，这样也能够有一个O(n)到O(log n)的效率提升，并且也能有一些class之间的sharing。
P. Loh, M. Wainwright的Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima给出了一个non-convex optimization的一个理论结果。历来non-convex optimization基本上就没有什么理论结果，这篇文章的这个结果是在这个方向上的一个进步，但结果的条件太强，基本上没什么用。按我的理解，这篇文章分析了regularized m-estimator的估计，目标函数由一个strongly convex的部分和一个不太concave的部分组成，由于在比较远的地方strongly convex的部分占主导使得远处基本上convex，所以optima只能在离原点比较近的区域。这篇文章的结果就是在理论上刻画了这样的现象，说明在这种条件下所有local optima都和global optima十分接近，因而不必过于担心local optima的问题。但就像之前说的，条件太强，所以基本上没什么实际作用。
Q. Ho, J. Cipar, H. Cui, S. Lee, J. Kim, P. Gibbons, G. Gibson, G. Ganger, E. Xing的More Effective Distributed ML via a Stale Synchronous Parallel Parameter Server提出了一种异步并行机器学习的框架。在并行的框架中一搬中央server把global的参数发给所有机器，所有机器并行处理自己的一份数据，结束后再把更新发给中央server统一处理，更新参数再发给所有机器。这就要求每一轮过后的同步，而这个同步操作成本较高。这篇文章提出可以允许异步并行学习，每个机器不一定都用同一份global参数的copy，而是有的机器可以用新的，有的可以用旧的，条件是不能太旧（每个机器的copy都大概在一个K轮的范围内，不能某一个机器再用最新的copy，另一个机器还在用K+1轮以前的copy）。这样就可以放松同步的要求，节省很多时间。这个K可以调整，K设的小一点就可以得到更准确一点的结果，但速度会慢一些；K舍得大一点结果会略不准一些，但速度会更快，这样就有了更多的灵活性。他们的实验说明使用一个很小的K就可以很显著的提升速度，并且不会对结果有太大的影响，比使用K=1（完全同步）要好很多。
F. Bach, E. Moulines的Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)提出了一种很有意思的不需要设置梯度方法学习速率schedule的方法。通常，在做随机梯度优化的时候，学习速率需要逐步递减以保证收敛。这篇文章提出一种不需要递减学习速率的方法，这样一来最后的结果就不一定收敛了，但文章巧妙的地方在于使用每一步累计的平均值作为最终的参数估计，这个平均数会保证收敛，而且作者证明了这种方法在解一类non-stronly-convex问题的时候比使用递减的学习速率能取得的理论收敛速率更快。另一个好处是省去了选择学习速率schedule这一步，少了一个需要调的hyperparameter。
B. Golshan, J. Byers, E. Terzi的What do row and column marginals reveal about your dataset?关注了一个有意思的问题，一个非负数据矩阵，如果给定每行的和和每列的和，能得到多少关于原矩阵的信息？令人有些意想不到的是行列和其实是挺强的一类约束，再加上非负约束（以及可能有整数约束），可以确定很多矩阵元素的信息。
B. Lake, R. Salakhutdinov, J. Tenenbaum的One-shot learning by inverting a compositional causal process提出一种做one-shot字符识别的方法。做法是使用非常细致详尽的建模，基本上接近graphics engine的级别了。但我觉得对于真正的recognition系统，这样的建模是不现实的，很多东西我们也不知道该如何建模，如果能学到这些模型本身就更好了。
周日是主会的最后一天，下午poster session就结束了。也有一些有意思的文章：
L. Shi的Sparse Additive Text Models with Low Rank Background是来自国内百度的一篇文章，做的是topic model，改进了background topic model。一般用background的时候只用一个background，而仅仅一个topic旺旺不够用，这篇文章提出每个topic都用一个background topic，然后限制这些background topic有low rank。另一种可行的方法是直接用一个mixture model做background，但他们没有和这种简单的想法进行比较。
A. Perina, N. Jojic, M. Bicego, A. Truski的Documents as multiple overlapping windows into grids of counts是一篇关于counting grid的文章。还是一个基于topic model的文章，不过有意思的地方是topic组织成按空间分布组成一个grid，比如一维的grid就可以表示topic随时间变化的情况，二维的grid可以表示topic随空间变化的情况，也可以用于做可视化。在generate document的时候选取一个window，然后从那个window包含的topic中生成document。window在grid上滑动，就可以表示topic随时间空间等的变化情况。
S. Lyu, X. Wang的On Algorithms for Sparse Multi-factor NMF做的是nonnegative matrix factorization，将一个非负矩阵分解为多个稀疏非负矩阵的乘积。区别于之前工作基本上都是one by one的greedy方法，他们这个有一个joint optimization。这种分解为多个非负矩阵的NMF其实和neural net很像，一个矩阵就是一层，而且非负性和稀疏性引入了nonlinearity，如果能把这个和类似结构的neural net做个比较会很有意思。这种NMF做visualization也很方便，尤其是对于高层的feature，visualization只需要把底下的几层都乘起来就可以直观的看到feature了。
D. Weiss, B. Taskar的Learning Adaptive Value of Information for Structured Prediction提出了一种在structured prediction中选取feature的方法。idea是使用所有的feature太expensive，往往也不需要，如果能针对具体的问题选取特定的少部分feature使用，效率会大大提高。他们的方法是使用reinforcement learning来动态的选择feature，这是挺有意思的一个idea。实验结果中他们发现这个方法不仅速度大大加快，有时候效果反而会更好，因为对于每个instance选用有针对性的feature会比对所有instance都用同一组feature要好。
E. Yang, P. Ravikumar, G. Allen, Z. Liu的On Poisson Graphical Models提出用Poisson graphical model而非Gaussian Random Field来学习网络结构，对于离散数据来讲这个有道理。
E. Yang, P. Ravikumar, G. Allen, Z. Liu的Conditional Random Fields via Univariate Exponential Families也是同一个idea，用Poisson distribution来model离散值，学习的时候使用pseudo likelihood。不过他们好像一点不关心inference问题，这个model里的inference似乎并不好做。
B. Savchynskyy, J. Kappes, P. Swoboda, C. Schnörr的Global MAP-Optimality by Shrinking the Combinatorial Search Area with Convex Relaxation的想法很有意思。问题是做MAP inference，理论上loopy graph的LP relaxation不保证整数解，但实际中’往得’的大部分变量都已经是整数了，只有少部分不是整数。这篇文章的出发点便是利用这一点，在非整数解的部分做一个小规模的combinatorial optimization，这样可以达到global optima。理论分析上用到了convex dual decomposition的东西，我先前只知道David Sontag做的相关工作，也看到他在这篇poster前面讨论了许久。这次听作者Bogdan讲，才知道有好多好多种decomposition的方法，这篇需要认真读一下，也学习一些背景知识。
N. Wang, D. Yeung的Learning a Deep Compact Image Representation for Visual Tracking做了一个用deep neural net做tracking的事情。整个工作非常简单，传统的tracking一般用的是particle filtering的framework，主要有两个部分，一个是dynamics model，一个是observation model。dynamics model负责运动的部分，observation model负责根据图像评估bounding box的好坏。observation部分一般的做法是从图像的对应区域抽一些feature，然后训练一个评分函数。这篇文章简单的把这一个部分换成一个deep neural net，就取得了很显著的效果提升。可见deep learning还是有很大的潜力的。需要注意的是tracking的训练数据往往很少，文章中的neural net是在一个大的数据集上做pre training，然后把底下几层固定，实际tracking的时候根据有标的第一帧学一下neural net的最上层，这样就可以大幅减少overfitting。另外由于tracking过程中被track的物体可能会变化，他们的另一个trick是当neural net的confidence下降到一个阈值以下后使用上一帧的tracking结果重新学习一下最上层，以适应物体的变化。总的来讲这只是一个非常初步的工作，还有很大的空间可以发展。
V. Vineet, C. Rother, P. Torr的Higher Order Priors for Joint Intrinsic Image, Objects, and Attributes Estimation做了intrinsic image和segmentation的joint estimation，idea是intrinsic image中的depth、albedo之类的可以帮助segmentation，segmentation也可以更好的帮助estimate intrisic image estimation。formulation的结果是一个复杂的模型，然后inference用dual decomposition。
C. Szegedy, A. Toshev, D. Erhan的Deep Neural Networks for Object Detection用了convolutional net学习foreground-background segmentation，然后用得到的foreground去fit一些box，之后好像是对这些box进行分类，已得到最终的detection结果。好像没有joint training，是分开的几个模块拼起来的。
主会结束后是两天的workshop。第一天的workshop highlight无疑是deep learning workshop，和我做的相关的还有output representation learning。deep learning workshop中的highlight又无疑是Zuckerberg的出现。越来越多的企业开始做AI，对我们来讲是很好的事情，更多的数据也有更大的挑战，可以做更有意思的事情。但现在学术界和业界的交流还很有限，在学校拿不到业界的数据，很多有意思的东西我们都做不了，所以就只能多去实习啦。deep learning workshop的poster session也有一些有意思的工作:
Kaisheng Yao, Baolin Peng, Geoffrey Zweig, Dong Yu, Xiaolong Li, Feng Gao的Recurrent Conditional Random Fields提出用recurrent net来做CRF的unary model。第一neural net要比很多固定的feature extraction要好，第二recurrent net可以综合周围的信息，并且自适应的选取context的大小，不需要预先指定比如5-gram之类的窗口大小。在和作者聊的时候还知道了一个他们用RNN学习长距离dependence的trick，就是把global feature加进feature中，这样就从feature上降低了学习的难度。
Rémi Lebret, Joël Legrand, Ronan Collobert的Is deep learning really necessary for word embeddings?做了不少实验说学习简单地word embedding不需要deep learning。
此外workshop中还看到不少multi-modal learning的文章，时间关系我也没有看全，好多其他有意思的工作都没看到。下午的talk结束后的panel discussion上有Zuckerberg、Yoshua Bengio、Google的Tomas Miklov、刚刚获得ImageNet第一名的Matt Zeiler以及Stanford的Chris Manning。我还问了一个问题，问deep learning的极限在哪里，最多可以做到什么程度。我觉得神经网络可能比较适合处理physical signals，但对于high level的reasoning可能不那么在行。但几个speaker都没有怎么正面回答问题，只是说还有很多东西可以做。
第二天我主要待在greedy algorithm和Frank-Wolfe的workshop。由于不是很了解这一块的东西所以能理解的也不是很多。有一个invited talk比较有意思，讲的是学习使用squaring unit的deep net。有别于sigmoid和其他类似的nonlinearity，作者提出了一种特殊的方法可以学习这类squaring unit net。一开始我还觉得很神奇，不过细想一下，这种squaring unit归根到底就是一个多项式函数。每个单元都平方，所以最终的多项式阶数是网络深度的指数函数。由于多项式函数可以近似任何函数，这类网络的表达能力也可以很强。talk中提出一种可以找到两层的这类网络的global optima的方法，初听有些惊讶，因为两层的sigmoid net就已经解不了了，而这个还可以解，但一细想就知道两层的这类网络学的就是个二次型，很容易就可以找到global optima。所以这类网络比起sigmoid还是要弱不少，只能靠深度弥补表达能力的弱势。但作者猜想文章提出的学习方法只能应用于学习对数深度的网络，这样一来整个多项式的阶数就大大受限，表达能力就很弱了。
这届NIPS还有一个demo我非常感兴趣。这是来自Brain Corporation的机器人套装。他们把很多sensor包括RGBD camera、audio、accelerometer等等以及通讯接口和motor control接口都集成在一起，并且芯片板子上包含了很强的处理能力，甚至还搭载了GPU，可以跑一个完整的ubuntu linux。他们还提供了python API将众多I/O都封装的很好。他们现场演示的demo是一个避障机器人，通过人遥控一段时间作为训练数据，然后训练一个convnet直接将input image map到output的方向、速度，代码全在python里面完成，而且由于用的是完整的ubuntu，可以用所有的python库。就这么一个简单的东西，demo的实际效果还不错。非常想弄到这样一套东西，可以做好多很有意思的project。
总的来讲学到了很多有意思的东西，希望明年可以再参加Montreal的NIPS！