存档

2011年6月 的存档

漫谈在线学习：在线梯度下降

2011年6月29日 1 条评论

转载不能太监,转载limu童鞋的在线学习,原文在此

在线凸优化

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

虽然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遭受的累计损失被记成\sum_{t=1}^T\ell_t(h_t) ，如果挑选h_t 的策略集\mathcal{H} 是凸的，而且损失函数\ell_t(h_t) 关于h_t 是凸的，那么我们称这个问题为Online Convex Optimization（OCP）。通常我们将h_t 表示成一个向量w_t ，例如WM中的维护的m 专家信任度，所以这时\mathcal{H}\subseteq\mathbb{R}^m 。

在线梯度下降

Zinkevich提出的算法很简单，在时刻t 做两步操作，首先利用当前得到数据对w_t 进行一次梯度下降得到w_{t+1} ，如果新的w_{t+1} 不在\mathcal{H} 中，那么将其投影进来：

\displaystyle w_{t+1}=\Pi_{\mathcal{H}}(w_t-\eta_t\nabla\ell_t(w_t)),

这里\nabla\ell_t(w_t) 是\ell_t(w_t) 关于w_t 的导数（如果导数不唯一，就用次导数），\eta_t 是学习率，\Pi_{\mathcal{H}}(w) 是投影子，其将不在\mathcal{H} 中的向量w 投影成一个与w 最近的但在\mathcal{H} 中的向量（如果w 已经在\mathcal{H} 中了，那就不做任何事），用公式表达就是\Pi_{\mathcal{H}}(w)=\arg\min_{u\in\mathcal{H}}\|w-u\| 。此算法通常被称之为 Online Gradient Descent。

先来啰嗦几句其与离线梯度下降的区别。下图是一个区别示意图。在离线的情况下，我们知道所有数据，所以能计算得到整个目标函数的梯度，从而能朝最优解迈出坚实的一步。而在online设定下，我们只根据当前的数据来计算一个梯度，其很可能与真实目标函数的梯度有一定的偏差。我们只是减少\ell_t(w_t) ，而对别的项是否也是减少就难说了。当然，我们一直在朝目标前进，只是可能要走点弯路。

那online的优势在哪里呢？其关键是每走一步只需要看一下当前的一个数据，所以代价很小。而offline的算法每走一个要看下所有数据来算一个真实梯度，所以代价很大。假定有100个数据，offline走10步就到最优，而online要100步才能到。但这样offline需要看1000个数据，而online只要看100个数据，所以还是online代价小。 阅读全文…

分类: 新闻 标签: , ,

google papers@cvpr2011

2011年6月27日 2 条评论

如google research blog上所说:

is at the core of many products, such as Image Search, YouTube, Street View, Picasa, and Goggles, and as always, Google is involved in several ways with .

不过这里面没有汽车自动驾驶的相关内容啊，要知道，内华达州已经通过了一项法案允许无人驾驶汽车合法上路了，看这里，当然，google是幕后的推手，看这里。

下面是google在cvpr2011上的论文列表：

  • Where’s Waldo: Matching People in Images of Crowds by Rahul Garg, Deva Ramanan, Steve Seitz, Noah Snavely
  • Visual and Semantic Similarity in ImageNet by Thomas Deselaers, Vittorio Ferrari
  • Multicore Bundle Adjustment by Changchang Wu, Sameer Agarwal, Brian Curless, Steve Seitz
  • A Hierarchical Conditional Random Field Model for Labeling and Segmenting Images of Street Scenes by Qixing Huang, Mei Han, Bo Wu, Sergey Ioffe
  • Kernelized Structural SVM Learning for Supervised Object Segmentation by Luca Bertelli, Tianli Yu, Diem Vu, Salih Gokturk
  • Discriminative Tag Learning on YouTube Videos with Latent Sub-tags by Weilong Yang, George Toderici
  • Auto-Directed Video Stabilization with Robust L1 Optimal Camera Paths by Matthias Grundmann, Vivek Kwatra, Irfan Essa
  • Image Saliency: From Local to Global Context by Meng Wang, Janusz Konrad, Prakash Ishwar, Yushi Jing, Henry Rowley

    • 鉴于blogspot被墙，我还是把全文转过来吧：

    阅读全文…

    分类: 新闻 标签: ,

    CVPR的最佳论文奖出炉了

    2011年6月26日 10 条评论

    2011委员会宣布了以下奖项：

    Longuet-Higgins Prize（介绍）
    Rapid Object Detection using a Boosted Cascade of Simple Features,（连接）
    Paul A. Viola, Michael J. Jones.
    Sponsored by Microsoft
    经典的viola-jones算法,用过opencv的都知道


    Real-time Human Pose Recognition in Parts from Single Depth Images,
    Jamie Shotton, Andrew FItzgibbon, Mat Cook, Toby Sharp, Mark Finocchio, Richard Moore, Alex Kipman, Andrew Blake.
    Sponsored by

    不出火炉童鞋所料呀。。。。附上当初预计的连接，论文的连接

    Best Paper Honorable Mention
    Discrete-Continuous Optimization for Large-scale Structure from Motion,（链接）
    David Crandall, Andrew Owens, Noah Snavely, Daniel Huttenlocher
    Sponsored by Google
    Best Student Paper
    Recognition Using Visual Phrases,（链接）
    Ali Farhadi, Mohammad Amin Sadeghi
    Sponsored by United Technologies Research Center

    阅读全文…

    分类: 新闻 标签: , ,

    转：卖萌的大牛你桑不起啊 ——记CVPR2011一篇极品文章

    2011年6月23日 15 条评论

    转自庞宇童鞋的校内

    2011正在如火如荼的进行中，在网上能看到的部分文章中，我终于找到一篇让我眼前冒光的文章。虽然，其实，也许，主要的理由是我好不容易能看懂一篇。不过，这并不妨碍该文章定会成为今年CVPR的一朵奇葩这件事。不过它肯定拿不了best paper啦，因为它只是篇poster，但我猜也许是组委会认为如果让他们当oral，大牛现场卖萌会雷死观众，并可能引起大面积恐慌。

    鉴于我没有找到更好的平台共享这一发现，就只好先放到校内了。不过这个主题不光是对计算机视觉的人有意义，只要是搞数据的人都会有些用处吧。

    文章题目是：Unbiased Look at Dataset Bias，无偏见的研究数据集偏见。首先看看作者，一个是MIT的Antonio Torralba，另一个是CMU的Alexei A. Efros。 MIT和CMU在计算机视觉领域是两个绝对的巨人，无人能望其项背。这两个人这几年刚拿到副教授职位，而且又是那种论文又高产又高质的家伙。要注意哦，这篇文章没有研究僧，也就是说，这是一篇大牛和大牛的强强联合之作。也正是如此，该文章发挥出了大牛卖萌的极致。满篇充斥着“矮油”(alas)，“让我们玩儿个游戏/玩具实验(toy experiment)”等等，各种你很难在一般论文里看到的搞笑语言。特别是文章的致谢和声明：

    阅读全文…

    分类: 新闻 标签:

    zz：Lytro

    2011年6月23日 没有评论

    ifanr上有一个更好的lytro的介绍。与君共享。

    又一个 Color ?

    Color 创始人满嘴炮火车的忽悠了一通关于地点判断的影像技术，融资四千五百万美金之后， 凭借焦点控制技术，融到五千万美金。

    他和 Color 一样，是个更大的忽悠？或者，是一场真正的革命？

    阅读全文…

    分类: 新闻 标签: , ,

    Lytro

    2011年6月22日 5 条评论

    Si04

    看起来这会是继panorama，HDR之后，computational photography的又一个热门应用： Photography。

    lytro是硅谷的一家初创公司，就是要发行这么一款相机（未上市），通过记录light field，从而使得在成像之后，仍有机会调整焦点。

    这里看原理介绍：http://www.lytro.com/science_inside

    根据这里说说法，lytro将在今年发行一款“价格很有竞争力”的光场相机（是不是翻译成全光相机更给力一些）。

    官网 阅读全文…

    分类: 新闻 标签: , , ,

    OpenCV for iOS

    2011年6月22日 3 条评论

    大家都知道苹果系统是一个很奇怪的系统。有最精美的UI，确实基于最古老的系统。有最好的编程软件，确有自己的编程语言。这里提供一个专门为iOS准备的opencv的sh。链接

    不过大家也都知道跨平台是一件巨痛苦的事情，所以貌似要读以下的一个国外网站的教程（其实那个sh也是那个网站提供的）

    分类: 新闻 标签: , ,

    OpenCV 2.3出炉，NVidia出力帮助开发Android版本（可能Tegra GPU加速？）

    2011年6月22日 8 条评论

    今天刚发布的Release candidate，估计下周正式版本就要出来了。

    大家到这里看看what’s new：新增加了一个stitching拼接模块，Android支持更加方便了，使用Google test框架，其他变化主要是内部性能改进。

    Update 关于手持设备方面的:

    首先， 2.3的Android build终于变成了官方支持的NDK-Build的方式了。以前的方法相当让人头疼，使用的非Android官方的方法去写JNI接口，tutorial跟着走一遍也不知道所以然。

    其次，What’s new里面说道，新的Android支持是NVidia在开发，让然浮想连篇啊！本来OpenCV就是支持CUDA显卡加速的，那请细读下面的报道：http://computervisioncentral.com/content/nvidia-releases-opencv-android-tegra-301677 Tegra 3 support，会不会有硬件加速？OpenCV在Apple A4 这个级别的ARM处理器的性能要比桌面x86处理器慢~20倍，GPU加速让人期待。

    最后小八卦，文中提到的Kari Pulli原来在Nokia，他和Stanford合作的FCam API是基于跑在Nokia N900/800 Maemo Linux上的Computational Photograph的API。现在转投NVidia门下把FCam带入到Tegra？有意思，看来NVidia很看中未来手持设备的Visual computing的能力，到处发力找突破。

    –幻肢老杨

    分类: 新闻 标签:

    cvpr周

    2011年6月21日 6 条评论

    Home

    cvpr周啊。求新闻，求照片。

    话说nvidia有一个computer vision development on tegra的tutorial。AR在装备tegera2的平板上是不是大有可为？

    分类: 新闻 标签: , , , ,

    图书资源

    2011年6月21日 1 条评论

    今天发现有免费的图书下载的地方http://www.intechopen.com/
    CV/PR/IP方面的书有不少，看了一些，发现主要是论文集性质的。

    分类: 新闻 标签: ,