读Andrew Ng handout有感

loss function其实是个很奇怪的东西,只是概率模型和参数估计方法的最终表现。所以logistic regression的loss function那么奇怪——其实就是个伯努利分布下的最大似然估计。所以重点是概率模型的选取和参数估计的方法。

从概率模型到参数估计中间要先推出学习函数,这个也是个假设。有固定的方法,根据 1.exponential family 2.统计学习理论 3.函数假设空间。学习函数有了就剩下参数估计了,MLE, MAP 最终都化为优化问题。

generative学习算法,一般就不用学习函数来表达,直接从概率模型到参数估计。SVM连概率模型都没有。

所以给一个学习问题,先考虑有没有足够的knowledge做generative learning,没有就做discriminative或svm (也不全是酱紫)。做discriminative的时候先有概率模型假设,然后选函数假设空间,得到学习函数,最后做参数估计。要是ML不往深了搞,基本上知道用什么模型假设,知道怎么解优化问题就可以了。

所以人家说概率统计是内力,优化是轻功。ML只是招式。

有了这个认识就能从比较清楚的角度比较各种ML算法了。比如logistic regression和svm都是线性分类,有什么不同呢?可以比较3点:1. 概率模型 2. 学习函数的假设 3. 参数估计。先从前两点比较。logistic和svm在2上是一样的,都是线性分类。但是在1上logistic用了伯努利的假设得出的学习函数是非线性的,svm则直接是几何意义的线性函数。logistic似乎在1上更优雅,但svm成功了。它的成功在第3点,kernel使得feature可以在无限维上都能有快速的参数估计。

Feature 那些事

[to be added…]

荷兰的春天来了那么几天时间以后又藏起来了。骚过一段时间以后我也藏起来了。

三月初的时候重新回到公司但是不同的组,谁能想到事情正在其变化呢。姑娘看起来挺有意思,第一次见六姑娘的时候心里留下了这个印象。后来组里中国人民一起去吃饭的时候才算认识。再后来就是强行把六姑娘拉到我们饭友圈里,一起吃饭吃完饭一群人坐着update自己大小事和别人的八卦。六姑娘看起来还挺乐意的,但是不太爱讲自个的事儿。感觉越来越好的时候我就行动了,每天打着各种一看就是幌子的幌子往姑娘那儿送东西。六姑娘最终受不了,在我最后一次强塞给她豆浆之后直接把我的保温杯没收了。连带送给我一个评语,“你这个人啊,又敏感又计较”。原因是因为那天饭后一顿聊之后姑娘讲说对我的事情没兴趣。我就打着试探的态度问说我好感还没表达完你就给我打枪了,于是收到了这样一句评语。我心想啊,敏感和计较,对我都是从来都没有过的高评价,欣然接受了。下一周的时候继续各种理由送东西。六姑娘很无奈,连推我几次不同理由的邀约。我心想按照平时使劲互黑的节奏姑娘出来吃个饭打个球不应该拒绝得那么干脆呀。但是拒绝就是拒绝,谁的脾气都没那么好摸,慢慢只能把自己按住了。到现在事情一多,虽然还是照常黑,主动挑起来的互动就少了很多。

跟哥聊天的时候哥开我玩笑说我骚,我想想确实是。2013年的春天我骚了一把,用几句梨花体记录下来:
一个叫六姑娘的姑娘,
闷闷的很可爱,
脾气摸不准,
可黑我黑得很来劲,
可惜没我来劲。

哦我想重新学习音乐了,学习乐器写词编曲,这么蹩脚的文字要是能改改唱成歌儿多好。

把话写在这儿,还是期盼你能看到。
我喜欢你,非常非常喜欢你。
有多喜欢呢?就是能在脑海里看到你清晰的笑脸,
和脸上转动的眼珠,笑起来挤得圆圆的脸颊。
但是喜欢又能怎么样呢?
喜欢不一定懂,懂了又一定合适吗。。
认识你的心情就跟看到漂亮的夜空时候一样开心,
我想懂你的时候也有这样的心情,
也想你了解我以后给我仍旧是那印象里的笑脸。
还有还有……
我只是抱着最美好的愿望,等待你…

We know that frequent pattern mining from itemset database is a widely researched topic, good algorithms and tools have been developed. However there are still some problems to solve. One of the most important problems is that the size of the extracted pattern set can be much bigger than we really want. Sometimes it can be even bigger than the original database. This is called the pattern redundancy issue, which has become the mainstream of the research on this specific topic in the research community. People are working to reduce the size of the pattern set. They want to find some criteria other than just using the frequency to measure the goodness of the patterns.

One successful method is the minimum description length, where the goodness of a pattern is measured by how well it compress the raw data. Given the data, we usually do like this, we find a model, or a dictionary or you can call it pattern set in the context of pattern mining, this model is a summary of the original data. To fully express the data, we needs a encoding schema, so that the original data can be loselessly decoded from the model and the encoding. The size of the model plus the size of the encoding is much smaller than that of the raw data. In other words, the combination of the model and the encoding is a compact representation of the original data. We want to minimize this size to get the most compact representation of the original data. This is what we usually do using minimum description length. There is a theoretical foundation for this method, the size of the model plus encoding is called the description length of the data, minimizing this length gives the Kolmogorov complexity of the data, which is a intrinsic feature of the data in information theory.

This method has been successfully applied on itemset database, sequence database and even data streams. For sequence, things are more complex than itemset since we have to consider the issue of sequential structure, allowing gaps in pattern and pattern overlapping. For example, the patterns in the sequence can be interleaved with each other. This is problem is usually solved with statistical method such as dependency test. For streaming data, not only the description length but also the computational complexity is a critical issue since the large amount of data is dynamic, continuously reaches at high speed. Even quadratic complexity is not tolerable in this case. Some other constraints like single pass of the data should be addressed.

Above is the big picture of the most recent progress in the pattern mining research area. In fact, minimum description length is a method that requires more attention than just being used in pattern mining area. The power of this method lies in the fact that it takes the computer itself as a metric tool, thus can be used to discover some intrinsic feature of the data from a machine’s perspective, therefore it also can be used to reduce lots of parameters that should be tuned by human. Say, for a time series data, we want to find the regularity. This of course can be done by human interference, however it can be unreliable. There is a research work to discover the dimensionality of time series objects by incorporating the idea of minimum description length, where it is essentially a method of letting the computer to determine the dimension by measuring how much information it require to be stored. Another example is that in change detection, we usually use the sliding window model to keep track of the most recently occurred events. However it is always difficult to set the window size. By minimum description length, people can get rid of parameter setting by letting the computer make the decision.

实习两个月记

第一个月—————
做事情的感觉也不错。不断有新想法一致驱动着。
今天总算给新方法的试用做了个总结。结论是近乎没用的。但是被inspire出一些新的想法,证明是promising的。总算没有浪费这一个月。
其实也不会浪费,因为新认识了个姑娘。可惜留下的人品印象太差,相互吐槽太多。试着改变改变形象看看。。
第二个月—————
感慨下spline真是去噪的利器。
新feature效果不错,可惜不够generic,没有研究上的价值。想问题还是要往本质了去想。time series有啥呢?人家用MDL来搞,搞出个intrinsic dimension来,拿来一用,效果还挺好。但是不靠谱啊,而且MDL被使用得很ugly。名头好,没办法。不过信息论真是有大用处。接下去再整整。

time series 比起 sequence 要精细很多。就好像数学和计算机科学的差别。理论上很完美的东西到了计算上就变得很困难,能不能算,算多快,各种限制。sequence很多时候都只能用heuristic的方法,mine出来的pattern能不能用,效果多好很难保证。一旦把time series转换成sequence以后用信息论的方法做,弄出来的东西比直接用简单的在time series上搞可能就差了很多。

休息够了写两句

马上要开始硕士最后半年的毕业设计了。无所事事了近一个月,感觉要学的东西仍旧很多,但是什么都不想学,当做放松一下吧。扯两句。
硕士阶段读基础看理论到实际参与研究中都学到了不少东西,总算能够跟上最新的文章。但是发现公司的事情又大不相同。是偏应用的一个项目,之前的工作放着最好的模型不用用那么老的线性判别方法。但是每一步都做得很细,花几周把feature可视化一下,找一个feature能发一篇文章。理论这个东西,idea最重要,做实验能够验证就行。实际项目中,不会去寻找great idea,步步为营更重要。目标不一样,哲学不一样。
好的情况是,数据挖掘大概是少有的dist(理论,实际)特别小的一个领域。比如很多kdd的文章是解决新问题的,motivation经常直接是一个特殊的实际问题。即使很多不是这样,往往一个新的算法都要有real world dataset的实验结果支持。我们曾做过对jmlr数据集的分析,显示real world这个两个词是这些文章最representative的patterns之一。

补充:
实习快结束了,对项目与科研有了些新的思考。原先的想法太simple。真实且高质量的数据真的是非常非常重要的,而这也是学术界所缺失的。这是工业界的优势所在,即拥有大量real world的数据集。在这个基础上从feature extraction到各种normalization,smoothing,然后selection最后分类,一步一步要做出可信的成果都是很费时间的。虽然费时,但是可靠。学术界的人往往没这么大的耐心,导致的结果就是近乎所有顶尖数据挖掘会议的文章的实验部分不管怎么claim是extensive的,其bias都是值得怀疑的。
工业界搞方法还是不大行的,得靠搞学术的那帮人。很多实际项目中能够想到的问题,学术界的人基本都搞过,而且搞得很深,这是工业界不如学术界的地方。搞学术的人,长时间在理论上的训练能够产出非常有影响力的成果。但是怎么搞,不能靠空想。有种说法说做研究要顶天立地。天就是理论,地就是实践。从理论到实践都有突破才是一个有价值的研究。假设你有了长时间的实践,发现问题的时候就能变得有底气,做方法的时候考虑得也会更实际。当然也有另外一种更直接的方法就是紧跟最新成果,但是如前所述所有成果都是有bias的。所以好的成果必须是对实际问题有深刻的洞察力,同时有雄厚的理论积累足以用来解决这些问题。