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,够看一阵了。

2012年8月14日星期二

KDD 2012 笔记1

很高兴可以用上班时间参加KDD的会议。读研的时候总幻想可以参加这样的会议,可是参加的却是华人数学家大会,各种代数拓扑神马的在他们看来和HTML5一样令人兴奋。
然而我觉得,数学家很难创造什么,他们更多的是发现。构造性的证明总被认为是好的。然而构造性的证明能证明的,往往是不太具有基础的重要性的命题。
构造性的证明,具有积极的建设性,这个和知识发现的工作是相通的。
工作之后第一份工作是程序员,参加的是敏捷开发大会之类的,很文科。所以今天参加KDD会议,很高兴。
---
Bootstrap for big data
把样本空间n切分成大小为b(n)=n^0.6的若干小空间,分别Bootstrap,将结果平均以得到总体的估计。好处是可以并行化。
Matrix completion
将矩阵按列切分,每个分块分别分解,得到总体的近似。
Chinese restaurant process
---
Twitter
典型的用户行为包括hashtag和retweet
twitter用户创造了大量新词汇
不用负样本训练模型
用户贡献了大量标签数据
用户的徽章和行为如何互相解释
7M的用户,只有31个徽章
实验在75K用户上进行,采了300K行为
10%的数据藏起来,做真值
将关键词聚类,得到标签云,有时候很有意思,有时候很不靠谱
可以通过用户行为反过来预测用户的人口统计学信息
用户的行为频率越高,反映的偏好越明确,但是有一个临界值,再多就没有偏好了,成了平均脸。是条抛物线
---
Yahoo
给定一些实体,找到给定用户最感兴趣的实体。
平均每件商品的评论数:Amazon 30K,Yelp 3K(这么多?!)
Ranking based on coverage
真值:Rank review by helpfulness rate by user
每个用户由他的评论在lable上加分,比如David=java(4) algorithm(6)
相机的评论有几个方面:续航能力、便携性等
评论说的全面,说的别人没说过,分就高。稀缺性作为评判的指标。
cover score,一个实例在coverage指标上的边际贡献。
---
效用函数
推荐相关新闻的数量,和用户满意度的关系是亚线性的。
好的推荐系统应该在相关性和多样性之间平衡,比如推荐前面几条推荐和用户兴趣相关的,后面几条推荐五花八门的,扩大用户视野。
当然每个用户效用曲线形状不一样,有的用户就只喜欢看和自己兴趣相关的新闻,给他推荐别的就是浪费。
作者找出了一个方法估计每个用户的效用曲线。
---
播放列表推荐
曲目的元数据很重要
曲目编排的顺序很重要
---
社交计算
例子:每个人是图上的一个点,给定有限种颜色。请选一种颜色画在你的点上,如果和你相邻的点颜色都不相同,你就赢了。
民主选举中的投票
---
编写好的教科书
一本教科书不好的一个特征,就是在解释一个概念之前,就使用它。称之为理解灾难。
作者设计了一个工具,找到一本教科书中,那些章节具有最多的理解灾难,那些概念带来最多的理解灾难。帮助出书者改进教科书。
工具还考虑了如何处理书中对外部概念的引用。好的教科书应该尽量少引用外部概念。
---
把破坏市场经济秩序的坏人揪出来
通过证券交易记录,发现联手操盘的一小撮人。
定义了一种特别的自相关系数。
在用户行为建模方面:如果一个人的意图不能自洽,就不要将他的行为用于构建物品之间关联。
---
推荐系统攻击
一些人想推广商品A,选定一些流行的商品B,注册大量马甲,给B打5分,再给A打5分,然后再假装给不相关的一些物品打2或3分。
根据一般的推荐算法,当普通人浏览B的页面时,系统会推荐A。攻击者就阴谋得逞了。
作者发明了一套算法,把这种人干掉。结果显著提升了user based CF的准确性。
真值:Amazon专家标注的攻击者
Amazon将攻击者分为三类:从来不买东西的蓄意破坏者(删id)、全职写手(显著降低言论的权重)、兼职写软文的(适当降低言论的权重)
---
HP电力管理
在写字楼里,如何安排电路开关和电表?
安装的多了,控制粒度细了,但是费料。
装的少了,控制得不够细,可能造成浪费,有故障电器不能将破坏控制在局部。
---
Twitter抽取突发事件
很多突发事件是从microblog上报道的,如何抽取?
定义了三元组:对象、时间、类型
类型是可枚举的,分类器学出来的
---
如何建立功能和蛋白质之间的联系,构建了二分图,多标签分类模型
---
文本分类
有一个未经检验的假设:被lable的样本和总体同分布。
---
实体匹配
一个Yahoo的Researcher讲,他上来很沮丧地说
这篇Paper的联合作者还有3个人,可是他们现在分别去了facebook, twitter和google,what a shame
如何将internet上重复的entity识别出来?
再给定准确率下界的约束下,最大化召回率。
通过拉格朗日松弛,将问题转化为无约束优化问题。



一天听下来,非常疲惫。感觉也就听懂了2%,对5%的未知事物感兴趣想去进一步了解,剩下的93%既不知所云,也没兴趣。