2012年8月15日星期三

KDD 2012笔记2

闭幕了。
---
时间序列搜索
大概要从trillion量级的时间序列中找到query的时间序列子列,当然定义了两个时间序列子列之间的距离,是最近邻搜素。
实验数据大多来自生物医学,比如DNA序列,脑电波等。
用到了一些技术:z-normalization,每个点减均值除方差。还有是用两条平行的时间序列将目标时间序列夹住,夹得越紧越好,当然被夹的序列抖动比较厉害,夹人的比较平滑。然后用夹人的序列的特征刻画被夹的序列的特征。
还有各种剪枝,由于距离定义的可加性,如果当前子列的距离已经大于已知的最短距离,就可以放弃当前位置,换个地方重新计算。
采样技术,将时间序列连续地采一部分出来,得到了一个较短的子列,如果子列距离就已经超了,这个样本所在的总体就不用考虑了。
还有各种并行化技术,比如有的进程从左往右找,有的进程从右往左找。
不明白索引结构是怎么样的,难道都是这种很苦逼的遍历么,这叫哪门子搜索啊。
---
m6d做的事情和我们组现在做的很像,所以使劲听使劲听。
display ads做的就是browsing pattern。
m6d这个公司有5个data scientists,上千个分类器,每个model有上M个feature,从训练到部署全部自动化,极少人工干预。
个人感觉他们Engineering做得很好,有系统有效的Monitoring,运维的人的成本很低。
feature包括浏览过的网页,还有浏览器信息。
正例是有购买记录的用户。
各种measurement做得很好,比如他们会比同一个model,在不同数据源上的效果好坏。
数据量:production上500多个core,每天处理上B的event
---
Youtube讲视频流行度
很多视频内容都一样,只不过是克隆出来的翻版
建立了流行度和内容之间的线性模型,发现不怎么样,都通不过假设检验
流行度和非内容要素关系更大,例如人们上Youtube就喜欢看新视频,在搜索结果中,新视频也被赋予了很高的权重,总排到上面。
心想,不知Hulu的人看到这会不会鄙视他们。也许人家没把最好的研究拿出来讲吧。
---
Yahoo讲display ads的allocation
在book ad的时候,publisher要马上知道这块inventory上还能不能分配这么多impressions
在impression servering的时候,50ms内决定这个机会应该给哪个ad
5年前,Yahoo使用控制论,也就是负反馈技术,当一个ad deliver的数量超过按计划当前应该deliver的数量时,提高此ad的权重,保证所有ad永远on schedule。
这个算法非常简单,缺点是过于短视,没有往前看。结果有很多under delivery。
二分图匹配问题,把inventory分成许多小块,把ad targeting也分成许多小块。约束:所有ad的impression goal都要被满足,under delivery将得到很大的罚,inventory是根据历史预测出来的,可分配的impression不能超过capacity。得到一个plan,每个ad server按plan执行。
转化成KKT对偶问题,找到一个可行解很容易。online serving的时候很容易实时修正预测误差。
但这个算法有个问题(后边一个session里来自Google的人讲的),就是不好控制每个Ad的delivery pattern,比如都能deliver完,但是都集中在很短的时间,或者很特别的人群上。
advertiser要看top behavior的时候,allocation结果就很难看了,因为有太多的可行解。
当然我相信,引入一些阻尼项,可以让allocation的到很好的结果,但是top behavior可能没有那么鲁棒。
---
Yahoo讲display ad的用户行为分析
convert的过程分为三步:用户来到一个有广告的页面,用户意识到这个页面上有这个广告,用户对此感兴趣并来到广告目标网站上互动。
以前人们建模通常把感兴趣的概率作为model score,作者认为awareness也是一个很重要的因素。展示次数、上下文、广告大小、位置等等会影响awareness。
他建了个模型,融合到固定的interesting model里面,发现可以改进预测精度。
有时候,一个人得反复看才能注意到一个广告。有时候,一个人一个广告看多了就意识不到广告的存在了。
---
插播一个海报,出现在一个人的PPT里,很有意思:上面写着"I don't aways test my code. When I do I do it in production."
---
Google讲Display ad serving
为了smooth delivery,作者将时间切片,在每个时间片段里,用allocation model,控制每个ad的delivery上限。结果是显著降低over delivery,但是under delivery没什么变化。
Google做的是什么生意,竟能允许20%以上的under delivery。
---
下午有一些形而上的发言,有一个说得很好,大数据不是说数据量特别大,而是数据的复杂性高。我觉得很有道理。
另一个说的也很好,大数据的生意应该这样做,提出并解决一个问题,然后refine并scale它。
---
后面的讲座就非常理论了,估计工业界的人这时候都走得差不多了,留下的都是些穷学生等着吃晚饭不听也是闲着。
---
模式识别工作总是弄出来很多重复的pattern,作者定义了pattern之间的相似度和一个偏序,提出了从一堆pattern中,找到一组最小pattern覆盖的算法。
称A优于B,若TP(A)>=TP(B)且FP(A)<=FP(B),就是说,B能分对的,A也都能分对,A分不对的,B也都分不对。
下面给出了一个松弛
称A是delta优于B的,若TP(A)>=TP(B)且|FP(A)\FP(B)|<=delta/(1-delta)|B|,就是说,很少有A分不对B却能分对的。
这里说分对,是说分类器把正例分为正例。
delta优不同于优,他没有传递性。
作者证明了一个非常牛的引理:给一堆pattern,存在唯一一组pattern,完备且无冗余。这里完备和冗余的概念也是用delta优定义的,没记下来。
现实意义,用最小pattern覆盖替代一堆pattern,可以提高AUC。
---
当分布非常不均匀时,有一个多核算法可以让挖掘频繁项加速一个数量级。好像和编译原理有关,都是优化代码路径什么的。
---
click stream中回文的发现
一个序列反转后不变,就是回文。例如AA,ABA都是,AB,ABCA都不是。
内嵌回文:ABCBA中BCB就是内嵌回文。内嵌回文折叠后,外面仍然是回文。但是要注意叠好。例如ABCBDBCBA,如果只叠一个BCB,就成了ABDBCBA,就不是回文了。
有一个利用栈的算法,可以线性时间删除内嵌回文。感觉像一个数据结构的作业题啊。
互联网上很多网站的click stream中回文占90%以上。找出这个结构,可以发现网站导航的一些问题。
比如死链,点进去就点不回来了,只能后退。有的一个hub页面要反复出来进去。
sequence mining是一个很有趣的领域。
---
没了。

回来看到U盘里有一百多篇paper,够看一阵了。

2 条评论:

Yk Fang 说...

元涛,您好,
我是做数据挖掘的,今年因为工作忙,无缘kdd2012,有幸看到你这篇博文,甚是嫉妒羡慕恨哈,让我过了把瘾。
能否将论文共享一下呢,非常感谢!
liusha.fang@gmail.com

lobatt 说...

真好,看起来能学到很多东西!