搬家~ lincccc.com

前段时间被blogbus的浮动视频广告恶心到了，就开始计划搬家的事。

大饼买了个主机空间，我就蹭着用了。新地址：lincccc.com

wordpress还不会用，凑活着看看先。有空再画个主题。

毕业前blogspot站还会同步更新，国内的blogbus就关掉了（让你弹广告！）。

新年快乐~

Fullmetal Fairy Tale ~「Real Steel」

今日大风。跑去UME办了张心心念念很久的会员卡，然后去看「Real Steel」。

我挺喜欢这片。暴力不血腥。大饼说，拥有一个机器人是每个男孩心中的梦想。我想起我们计划的赚够500万后要做的事情：买一座山，建一个城堡，种一坨果树，造一个洒水高达。

我看这片，就像在看睡美人、白雪公主之类的童话故事，一个小男孩从垃圾堆里捡到一个拥有超强模仿能力的机器人，最后打败代表邪恶势力的世界冠军，成为英雄的故事。

但我其实很喜欢暴力的事情，就是怕血腥怕痛，所以这片子很适合我。而且又是Happy Ending，Perfect！

遗憾的是，没有出现我期待的萝卜卖萌镜头。

PS：影片后期——就是银幕上打得正high的时候，机器人被调至模仿模式，某大叔体感操控，的时候。我忽然有种穿越感，仿佛坐回到实验室写视觉动作识别代码了；有些难以接受，这抗噪声抗高光，不完全捕获下的动作预测和补全功能，还高实时性，耐打防抖动，而且TM这准确率也太高了点吧。看看我手里温室下80%准确率就欢天喜地的实验结果，着实有些受伤。

还好，你丫只是个特效合成的电影。

[乱读书] 数据挖掘导论的导论

Book：Pang-Ning Tan, Michael Steinbach, Vipin Kumar. 数据挖掘导论（Introduction to Data Mining）. 机械工业出版社，2010年9月第1版.

---

这种训练程序一跑就是2个小时的时候最适合乱读书了。最近买了本「数据挖掘导论」和一本「模式识别」，混着读。读「数据挖掘导论」是因为不知道那是什么，读「模式识别」是因为做了很久这方面的东西最近感觉有些混沌想要重读基础知识。所以两边的「乱读书」也会混着更新，懒的看书的就看我瞎侃好了。

数据挖掘是最近挺热的一个方向，业内做的比较好的典型有Google的广告推送、Amazon的推荐服务等等等，都是和数据挖掘相关的。有一个流传甚广的描述DM重要性的案例模板，或者是“可乐和尿不湿摆在一起为什么能提高销量”的故事，或者是“口香糖和电池”的版本，大体的意思都是“数据挖掘可以帮助零售企业，自动地从其大规模的零售数据中，发现一些有用的信息”。这也是本书中对「数据挖掘」所下的定义，关键词是“自动”、“大规模”和“有用”。

数据中的知识发现过程包括：数据→预处理→数据挖掘→后处理→有效信息。预处理包括特征选择、降维、归一化等等，后处理则是为了保证信息的有效性，包括可视化、模式解释和过滤等。数据挖掘在其中最大的作用是自动总结和筛选知识（我认为）。这是一个交叉性和应用性很强的领域，以数据库、分布式技术为基础，涉及统计学、人工智能、机器学习和模式识别等多领域。

其主要难点在于：

可扩展性Scalability。指其处理大规模数据的能力，不单是时间复杂度上的高效，还有对存储空间上的要求，比如海量数据往往意味着无法将其一次性读入主存中。并行或分布式算法往往具有较高的可扩展性；
高维度High Dimensionality。通常会有成百或者上千的属性来修饰数据，可能是时域上的，也可能是空间域上的，这意味着我们需要应付高维向量，这对于某些对维度敏感的传统算法是灾难性的（这点和CV领域很像）；
非均匀的复杂的数据Heterogeneous and Complex Data。由于DM的应用领域很广泛，但不同领域的数据的属性是不同的；属性中可能同时混杂着不同类型（连续的、离散的），比如同时包含文本、超链接和图片的网页。这对DM前的数学建模是个挑战；
数据归属和分布式Data Ownership and Distribution。有时，数据并不存储在一个地方；有时，数据并不属于单一的组织。因此，我们需要分布式DM技术。这里的难点主要在三个方面：如何降低分布式系统的通信成本；如何有效地合并多方的DM结果；以及如何处理数据安全的问题；
非传统式的统计分析Non-traditional Analysis。传统统计方法通常是一个假设和验证的过程，需要手工地收集数据、设计实验来验证假说。但当面临大规模数据应用时，这种劳动密集型的实验方法是不可取的。DM是一个自动提出假说并自动收集数据、自动验证的过程，不再有精巧设计的实验，数据更趋于偶然性。

数据挖掘的主要任务可以分为预测Predictive和描述Descriptive两大类。预测类任务指通过数据的一些属性估计其他属性；描述类任务指从数据中获取其隐藏的模式（趋势、相关性、聚类、异常性等等）。

预测建模Predictive Modeling。主要用于解决分类Classification和回归Regression两类问题（这点上与机器学习对预测的定义一致）；
关联性分析Association Analysis。指从数据中发掘强烈存在的特征间的关系，这种关系通常通过隐藏的规则或者特征的子集来表示。我们开头提到的“可乐和纸尿布”就属于这类任务；
聚类分析Cluster Analysis。指从数据中发掘拥有相似外观的群体，使得类内距离最小，类间距离最大。比如，寻找商品的相似购买者，或者通过关键词对文档主题的聚类；
异常检测Anomaly Detection。指从数据中检测行为异常者，主要的目标是准确地发现异常行为，并且避免误判。这个应用十分有用，比如通过购买记录检测信用卡的异常消费行为——不符合持卡人的消费习惯或年龄等。

初步感觉这本书会讲到很多和机器学习、模式识别重复的内容，似乎可以理解为统计模型在大规模数据及具体环境下的应用问题，是个讲究实际的领域。

Job Hunting Season 终了！我想我要一份严肃的工作！

9月开始10月落幕，这一季算是过去了。
投出去一共33份简历，还有10家没有消息；
挂掉8家笔试，5家没去笔试；
收到9个面试：28所不要女生，科大讯飞放弃，百度明天我要问问他上海的问题再决定要否继续面下去，平安科技虽然我也不想去但的确二面被挂了，剩下的5个收到了offer。
（加了下发现少了1家，那家是sogou，恩，后来我发现简历一直处于未提交的状态，网上测评登陆进去就说通过了，但连笔试资格都没给，算是个奇葩）

学弟来问怎么找工作，我这个笔试老挂的人实在没什么说服力。但是真心的，再从头来过，我还是会做这么多项目，只是闲暇时间不会再按着自己的喜好写什么Handii读什么论文，而是会找陈越jj说“我要参加ACM拿奖”，或者熟读各种“程序员面试宝典”、“编程珠玑”和“Linux/数据库/网络精通”直到看到题目就能说出它和第几章某题差不多。不然，如何考得过那些早早地从实验室抽身开始脱产复习的勤奋的孩子，更考不过考场上见到的我拍过照的以及事后洋洋得意和我谈到的在笔试中组团Raid的孩子们。虽然这并不代表说，我在基础知识上觉得薄弱或者输于他们，只是一种手段。反正笔试嘛，也没有人要和我讨论CV算法的可并行性、多分类的混沌空间、统计模型的过拟合问题。（这是从找工作的角度，从个人成长的角度，还是多做事吧，为了几年后能接到猎头的电话）

另外就是职业目标的事情。本科的时候很梦想做游戏，但是又很纠结做游戏，一方面怀疑游戏行业的价值，一方面国内热衷的网络游戏实在不是我的菜。我要是去哪家网游公司做策划，这家公司会倒闭的，大饼这么说，我也觉得。投简历的时候，也没多想，后来才发现投的游戏公司不过寥寥几家，以前一直想去的盛大也转投了创新院做多媒体。有一晚在DM留守群上聊天，才发现自己的想法，“还是严肃一点的工作好”；游戏是我少年时的梦，但现在已经不是我想要追求的事业。我想追求人工智能，想做分布式，想继续做视觉做HCI，唯独没有想过要做游戏。人恐怕都是会变的，在追逐梦想的过程中，梦想也在改变。但无论做什么，我想工作真的还是严肃点的好，这样做起来容易找到人生的意义，容易说服自己努力，娱乐和生活也会更加有意思。

最后随便写点面经。面试其实我也没什么经验，认真面的就6家。

平安科技是我面的第一家公司，第一次遇到群P，第一次做面试前的自我介绍，很紧张，说话都有些发抖；但是完全没有技术面，在这点上对之后没有多少帮助。但有了第一次之后，以后的面试就感觉不到紧张了。

再接着是浙江大华。给不了多少钱，旁人总说你计算机的怎么看得上的一家公司。但我投它面它，是因为看重它未来的市场和前景，以及和我研究方向的高切合度。（大华是做安防、智能监控的，海康来的太晚，我就把它忽略了。）这场面试其实也没有具体的技术问题，似乎面试官是问过别人算法题的，不过到了我这里就变成“你做过的东西和我们部门的工作很相似，你要是愿意来，我们是很欢迎的”，就结束了。HR倒是问了些犀利的问题，还问了关于薪酬。在这之前我对薪酬是没有具体的概念的，就随便说了个数字，以致于后来谈offer都不好开口要求涨点。这是我对自身价值认知和不够坦率的问题，需要反省。

之后酱油阿里巴巴。一面遇到个做Java的，让随便写个冒泡排序，我刷刷刷写了，总觉得哪里错了但又想不起来，然后给他看，他居然说差不多（我擦，后来我会来重写了下，发现果然错了，内循环写错了点。。）那人后来还问我“你一直做C，让你做Java，会不会不行啊”，我当时脑子一热，心想不就是Java么，说“学Java只需要一个礼拜！”当时面试官就惊了，转而言其他。。现在想想，那应该是个好人，不然我当场就被赶出来了，居然当着人家Java程序员的面鄙视Java，活腻了，绝对活腻了。

之后等来了上海联影。联影是家刚起步的做医疗器械的新公司，但是听说有很多从西门子跳来的大牛。医疗器械是块大蛋糕，做的好了有市场了以后钱途无量，国外好多视觉图形学实验室都是靠医疗视觉的项目维持经费的。那天下午我接了大约6个电面电话，每个都长达半小时，面的范围包括OO概念、OS、视觉算法、Cuda、项目内容等等，接完还去现场面了技术和HR。真是虚脱了（中途我还酱油了完美的笔试，20+道选择题）。我很看好这家公司的前景，虽然他给钱不多，他加班，但这种创业型的公司拼的就是干劲、眼光、能力和运气。

第二天就面微策SE了。这是我面过最长时间的一个面试，4轮，每轮一个小时，从中午12点到下午5点。全英文。面到后来脑子都有点不灵清了，再加上前一天被轰炸过，面试官都说我“没睡醒”。。。都说微策爱面智力题，我却一题都没遇到，一下午尽写程序了；中途还被轰炸了些书本上的概念题，有些没答上来，回来翻了下博客才发现，我原来写过关于这方面的文章，垂足顿胸啊。一下午面下来，我对微策的感觉是很好的，正规，有条理，周到，面试官很nice（中途我把我的笔忘在了三面的地方，面试官还找到我四面的地方送过来，就是支便宜的自动铅笔，感动）。

AMD面试的流程就有些长了，从电面、笔试、再到面试，差不多有一个月的时间，也许这就是硬件公司的步调。不过AMD的人做事很认真，电面、笔试、面试前都特地电话过来确定我当天是否有空，把我感动的不行。最后面试的时候是3个面试官一起的，安排的40分钟，我差不多面了1个小时多10分钟，讲得口干舌燥。项目问的挺细，和他们做的方向不大一致，所以我就讲得浅显些。好在之前写过一些项目建议书，知道怎么通俗地描述我做的事情。沟通能力和描述问题的能力，在面试以及后续的工作中都很重要，这也是研究生2年半带给我最大的收获。

最后，感谢所有我面过、笔试过的公司。

怨妇贴。

这工作找的让人觉得大学7年就跟白读了一样，不如搞1年ACM，更不如上半年技校。

至今经历过的唯一我认为做的正确的笔试，只有WAP公司的三日编程题。虽然我最后因为时间关系没有实现完设计方案，当然更没有上交和之后的面试，但是很欣赏这样的笔试方式。

不过，大多的公司都不会有这家日企这么认真的态度，往往都是发张“代码不缩进”的卷子，好些的做个机考，考的也就是那些个题库里随机出来的ACM题。我从来不认为那些搞ACM的人有多牛掰，只是平日努力的方向不同而已。ACM得世界冠军固然难，可普通ACMer也就是“懂出题思路，懂ACM的通用Framework，做过90%题库”这样的水准。只是别人花在做项目、调系统、研究模型、发Paper的时间，他们花在了做ACM题上了而已。但就好比，料理竞赛再牛掰的大厨烧茶叶蛋也未必烧得好吃过一摆路边摊的一样，因为人家本来就是做这个的，而且天天做，日日做。

可是，公司们，说着“我们要找有坚实基础的、有解决问题能力的、有良好沟通能力和良好学习能力的人”，实际做的却是“来做ACM题吧”。也许公司并不是这么想的，但却这么做了。

我想我也是猜得到原因的。毕竟海面不可能，笔试是必须的。出优秀的题目太难，而且时效性很短，所以找题库或者根据题库改编是最方便的。而且ACM题有固定的标准，效率、内存，AC就是AC，不像开放题目，需要改卷管自己思考是否正确，而且标准模糊，从这个方面看也是最方便的。我并不否认考ACM题在某种意义上的公平性，但也是连高考也比不上的公平性。也许公司还认为“虽然不会做ACM不一定不是我们需要的人，但会做的人中笨的总不太多，反正应聘的人多，运气不好的我们也不要”。

所以，毕业求职季的种种笔试，成了又一次变相的高考，所有人看“程序员面试宝典”、看“编程珠玑”、看“编程之美”等等等，平日里碰都不会去碰的书。还有那些经典面试题，简直就是逼着你去看。大多数人也是从开始找工作的时候才开始看这些题，才开始了解到“原来还可以有这种题的”，比如我一直很不理解一道关于“单项链表查环”的题，为何不在插入链表时就保证无环呢？既然数据可能有环，为何不选择其他数据结构比如数组作为容器呢？这种笔试的结果通常是公司招到了看过这些题的人，而非会做这道题的人。

我并不希望做一个单纯的码农，并不喜欢捣鼓指针引用，代码只是工具，为了实现系统的一种交互不友善的软件而已，只是工具而已。也许是我在专业方向走的太远，再回过头来看这些充满Trick的ACM招式总觉得有些幼稚无聊。

不过现实就是这么无奈，逼着你同流合污，我也还是会去看这些书。写这篇日志的目的，是告诉10年20年后的我，如果做了笔试出题者或者面试管，记得己所不欲勿施于人，记得ACM考不出你想要的人。

八月中

君と夏の終わり　将来の夢　
大きな希望　忘れない
10年後の8月　また出会えるのを　信じて
最高の思い出を…

与你一起度过夏季的尽头 未来的梦想 庞大的希望 不会忘记
深信能够在十年后的八月重逢
成为最美好的回亿

今年四月番「あの日見た花の名前を僕達はまだ知らない。」我们仍未知道那天所看见的花的名字。这首ED至少贡献了这颗催泪弹80%的效果。据说是当年Zone乐队解散时的安可曲目，这种词，当年现场的一定哭翻了。

真TM煽情。

八月将逝。以此献给今生最后一个暑假。虽然不休假。

[基础算法] Random Forests

Random Forest(s)，随机森林，又叫Random Trees[2][3]，是一种由多棵决策树组合而成的联合预测模型，天然可以作为快速且有效的多类分类模型。如下图所示，RF中的每一棵决策树由众多split和node组成：split通过输入的test取值指引输出的走向（左或右）；node为叶节点，决定单棵决策树的最终输出，在分类问题中为类属的概率分布或最大概率类属，在回归问题中为函数取值。整个RT的输出由众多决策树共同决定，argmax或者avg。

Node Test
node test通常很简单，但很多简单的拧在一起就变得无比强大，联合预测模型就是这样的东西。node test是因应用而异的。比如[1]的应用是基于深度图的人体部位识别，使用的node test是基于像素x的深度比较测试：


简单的说，就是比较像素x在u和v位移上的像素点的深度差是否大于某一阈值。u和v位移除以x深度值是为了让深度差与x本身的深度无关，与人体离相机的距离无关。这种node test乍一看是没有意义的，事实上也是没多少意义的，单个test的分类结果可能也只是比随机分类好那么一丁点。但就像Haar特征这种极弱的特征一样，起作用的关键在于后续的Boosting或Bagging——有效的联合可以联合的力量。

Training
RF属于Bagging类模型，因此大体训练过程和Bagging类似，关键在于样本的随机选取避免模型的overfitting问题。RF中的每棵决策树是分开训练的，彼此之间并无关联。对于每棵决策树，训练之前形成一个样本子集，在这个子集中有些样本可能出现多次，而另一些可能一次都没出现。接下去，就是循序决策树训练算法的，针对这个样本子集的单棵决策树训练。
单棵决策树的生成大致遵循以下过程：
1）随机生成样本子集；
2）分裂当前节点为左右节点，比较所有可选分裂，选取最优者；
3）重复2）直至达到最大节点深度，或当前节点分类精度达到要求。
这一过程是贪婪的。
当然对于不同的应用场合，训练过程中，会有细节上的差别，比如样本子集的生成过程、以及最优分割的定义。
在[1]中，决策树的真实样本其实是图片中的像素x，变量值则是上文提到的node test。但是，对于一张固定大小的图片而言可取的像素x是可数大量的，可取的位移(u，v)和深度差阈值几乎是不可数无限的。因此，[1]在训练单棵决策树前，要做的样本子集随机其实涉及到像素x集合的随机生成、位移(u，v)和深度差阈值组合的随机生成，最后还有训练深度图集合本身的随机生成。
最优分裂通常定义为使信息增量最大的分类，如[1]中的定义：

H指熵，通过分裂子集的部位标签分布计算。

---

Reference：
[1] J. Shotton, A. Fitzgibbon, M. Cook, T. Sharp, M. Finocchio, R. Moore, A. Kipman, and A. Blake. Real-Time Human Pose Recognition in Parts from a Single Depth Image. In CVPR 2011.
[2] L. Breiman. Random forests. Mach. Learning, 45(1):5–32, 2001.
[3] T. Hastie, R. Tibshirani, J. H. Friedman. The Elements of Statistical Learning. ISBN-13 978-0387952840, 2003, Springer.
[4] V. Lepetit, P. Lagger, and P. Fua. Randomized trees for real-time keypoint recognition. In Proc. CVPR, pages 2:775–781, 2005.