增强视觉 | 计算机视觉 增强现实

以前贴过各种排序的图形可视化，但是可比不上这个真人版的，真心好玩。

Primal-dual的观点

《红楼梦》第三一回云：天地间都赋阴阳二气所生。世间有阴便有阳，在优化界也是如此。我们将需要最小化的目标函数称之为primal problem. 其对应就有dual problem. 例如常见的Lagrange Duality. 如果primal是凸的，那么dual便是凹的。且在常见情况下，最小化primal等价于最大化dual. 有时候直接求解primal problem很麻烦，但dual却方便很多。或是通过考察dual problem的性质能得到最优解的一些性质。一个经典的案例就是SVM.

上节我们通过子空间投影来处理罚，这里我们直接考虑最小化损失+罚的形式，既（罚前的参数在这里写进了里了）。注意到罚的存在，使得目标函数不能如前面那样自然的分成块，从而不能直接对每块做梯度下降得到online gradient descent. 于是我们转向dual problem.

Shai Shalev-Shwartz提出可以用Fenchel Duality来研究其对偶式。Shai最近在online/stochastic界相当活跃。虽然和他不熟，不过因为他姓比较长，所以下面亲切的用Shai来称呼他。Shai 毕业于耶路撒冷希伯来大学，PHD论文便是online learning. 然后他去了online learning重地TTIC, 更是习得满身武艺，现在又回了耶路撒冷希伯来大学任教。他的数学直觉敏锐，善于将一些工具巧妙的应用到一些问题上。

阅读全文…

在线凸优化

回顾下上次聊的专家问题，在时刻专家的损失是，于是这个时刻Weighted Majority（WM）损失的期望是，是关于这个专家的损失的一个线性组合（因为权重关于的和为1，所以实际上是在一个simplex上）。将专家在时刻的损失看成是这个时候进来的数据点，于是我们便在这里使用了一个线性的损失函数。

虽然WM的理论在上个世纪完成了[Littlestone 94, Freund 99]，将其理论拓展到一般的凸的函数还是在03年由Zinkevich完成的。当时Zinkevich还是CMU的学生，现在在Yahoo! Research。话说Yahoo! Research的learning相当强大，Alex Smola（kernel大佬），John Langford（有个非常著名的blog），这些年在large scale learning上工作很出色。

回到正题。我们提到在online learning中learner遭受的累计损失被记成，如果挑选的策略集是凸的，而且损失函数关于是凸的，那么我们称这个问题为Online Convex Optimization（OCP）。通常我们将表示成一个向量，例如WM中的维护的专家信任度，所以这时。

阅读全文…

有点像wordlens的图像版。不错！

via

我在想，如果我用一本原版书勾引你们，你们会来做cvchina的贡献者，每周更新一次，坚持一年么？

比如这本书：

再比如这本书：

一直觉得AR跟数字艺术结合起来很是夺人耳目。可以起名为AR²T，是ARART的简写。 现在的AR演示往往流于粗糙，简陋不堪。如果把AR从业人员和数字艺术家丢到一个工作室，肯定能出不少好玩的应用。 贴两个视频。

阅读全文…

配合一下LiMu。

• [5] Z. Kalal, K. Mikolajczyk, and J. Matas, “Face-TLD: Tracking-Learning-Detection Applied to Faces,” International Conference on Image Processing, 2010.
  [pdf][poster][
  ]
• [4] Z. Kalal, K. Mikolajczyk, and J. Matas, “Forward-Backward Error: Automatic Detection of Tracking Failures,” International Conference on Pattern Recognition, 2010, pp. 23-26.
  [pdf][
  ]
• [3] Z. Kalal, J. Matas, and K. Mikolajczyk, “P-N Learning: Bootstrapping Binary Classifiers by Structural Constraints,” Conference on Computer Vision and Pattern Recognition, 2010.
  [pdf][poster 1][poster 2][
  ]
• [2] Z. Kalal, J. Matas, and K. Mikolajczyk, “Online learning of robust object detectors during unstable tracking,” On-line Learning for Computer Vision Workshop, 2009.
  [pdf] [
  ]

阅读全文…

Pang Jiahao同学推荐了一个华南理工大学开发的人脸合成系统，以前见过一个国外的做平均脸的网站，这是第一次看过国内类似的网站，挺好玩的，以飨读者。

阅读全文…

Mu.Li同学计划撰写一个系列的文章来介绍online training，这里是第一篇（LiMu你很威武啊）。原文在此，全文转载如下。

两个故事

很久很久以前有一老师和一学生，每天老师让学生回答一个问题，然后老师告诉学生正确答案，学生则比较正确答案来更新自己的知识。就这样学生终成大师，与老师幸福的生活了下去。

不过，在现实的世界里，故事是另外一个版本：在网络的一头住着一挨踢男，另一头住着一小编。每天小编写一封垃圾邮件给挨踢男。苦命的挨踢男日日分析邮件设计过滤器来过滤小编的垃圾邮件。但聪明的小编如果一发现邮件没有成功的被寄送，那么就会在下一封里加上更多的甜言蜜语来忽悠挨踢男。较量一直进行下去，挨踢男是否能摆脱小编的骚扰呢？

以上两故事都属于博弈论里的重复游戏（repeated game），它是对在线学习（online learning）最贴切的刻画：数据不断前来，我们需根据当前所能得到的来调整自己的最优策略。

熟悉机器学习的稳拿可能注意到了在线学习与在机器学习（统计学习）里所讨论的（离线）学习的区别。前者认为数据的分布是可以任意的，甚至是为了破坏我们的策略而精心设计的，而后者则通常假定数据是服从独立同分布。这两种不同的假设带来不一样的设计理念和理论。

统计学习考虑算法所求得到的模型与真实模型的差距。数据由真实模型产生，如果能有无限数据、并在包含有真实模型的空间里求解，也许我们能算出真是模型。但实际上我们只有有限的有噪音的数据，这又限制我们只能使用相对简单的模型。所以，理想的算法是能够用不多的数据来得到一个不错的模型。

在线学习的一个主要限制是当前只能看到当前的和过去的数据，未来是未知，有可能完全颠覆现在的认知。因此，对在线学习而言，它追求的是知道所有数据时所能设计的最优策略。同这个最优策略的差异称之为后悔（regret）：后悔没能一开始就选定最优策略。我们的希望是，时间一久，数据一多，这个差异就会变得很小。因为不对数据做任何假设，最优策略是否完美我们不关心（例如回答正确所有问题）。我们追求的是，没有后悔（no-regret）。

如果与统计学习一样对数据做独立同分布假设，那么在线学习里的最优策略就是在得知所有数据的离线学习所能得到最优解。因此在线学习可以看成是一种优化方法：随着对数据的不断访问来逐步逼近这个最优解。

很早以前优化界都在追求收敛很快的优化算法，例如牛顿迭代法。而最近一些年，learning的人发现，这类算法虽然迭代几下就能迭出一个精度很高的解，但每一步都很贵，而且数据一大根本迭不动。而向来被优化界抛弃的在线学习、随机优化算法（例如stochastic gradient descent），虽然收敛不快，不过迭代代价很低，更考虑到learning算法的解的精度要求不高，所以在实际应用中这些方法通常比传统的优化算法快很多，而且可以处理非常大的数据。

随便看看这些年ICML，NIPS，JMLR上online, stochastic关键字文章的数量就知道这类算法的大红大紫了。一个通常的规律是learning界火过的topic在computer vision，data mining等偏应用的方向上会接着火几年，所以肯定CVPR, ICCV, KDD之类会议上还会有茫茫多这类paper。因为我最早的topic（见我CVPR’10文章）关于online learning，所以想乘自己知识还新，就自己的理解来谈谈它。希望能用通俗的语言为大家介绍这个topic，为国内learning界做做贡献。

当然，相对于老地主online learning，stochastic绝对是新贵。我会接下来谈这类算法，以及他们动辄数页的convergence rate的证明。我的另外一个topic（见我ICML’10, CVPR’11文章）是大规模矩阵的低秩近似，也算大规模机器里面的一个重要问题，我想有时间也来浅出一下。

阅读全文…

闲来做了下logo检测，拿大众车标测试：

intel core2 2.8G，320×240的图像，5ms每帧。

algorithm：类HoG Feature+SVM

更多效果图：

阅读全文…