深度学习、自然语言处理和表征方法

简介

过去几年,深度神经网络在模式识别中占绝对主流。它们在许多计算机视觉任务中完爆之前的顶尖算法。在语音识别上也有这个趋势了。

虽然结果好,我们也必须思考……它们为什么这么好使?

在这篇文章里,我综述一下在自然语言处理(NLP)上应用深度神经网络得到的一些效果极其显著的成果。我希望能提供一个能解释为何深度神经网络好用的理由。我认为这是个非常简练而优美的视角。

Read More

子数组最大乘积

题目

给定一个数组,至少有一个元素。请计算子数组最大乘积是多少?

例如:

  • 给定数组 [2, 3, -2, 4]
  • 经过计算,得到最大乘积为6。子数组为[2,3]。

题目来自Leetcode。

分析

这个题目,有经验的同学,看过一遍,就知道肯定是动态规划了,可具体要如何规划呢?我想,有的同学还记得子数组的最大和吧?是不是觉得很激动,O(n)就可以解决了。一样的思路!但是不好意思,错了!

错在哪里呢?乘法口诀还记得么?负负得正,就可恶在这里。在加法里,负负可得不到正。

Read More

美股关键词趋势指数

今天受到雪球@雷公资本 博文 的启发,百度指数、Google趋势都可以作为大家投资工具集里的一个小工具,对于趋势判断也许有帮助。正好,我们收集了很多美股市场的数据,正在琢磨怎么来用。于是就做了一个我们数据集上的趋势指数,希望对大家能有帮助。请大家玩玩:猛击

目前只支持美股,所以信息都是英文的。大家搜索时,可以采用英文的关键词。

主要数据:

  1. 财经新闻
  2. SeekingAlpha
  3. Twitter
  4. StockTwits
  5. Facebook

大家可以看出来,我们的数据除了Google有的,也有Google没有的~~~

Read More

最长01子串

最长01子串

原题

给定一个数组,数组中只包含0和1。请找到一个最长的子序列,其中0和1的数量是相同的。

例1:10101010 结果就是其本身。

例2:1101000 结果是110100

请大家展开自己的思路。

分析

这个题目,看起来比较简单,一些同学可能认为题目的描述符合动态规划的特征,然后就开始用动态规划解,努力找状态转移方程。这些同学的感觉,是很正确的。但,找状态转移方程,我们要对原来的数组进行变换一下。

原来是0和1的串,我们将0都换为-1。这样题目目标就变成,找到一个最长的子串,子串数字和是0。设原数组为A, DP[i]表示从0开始到i的子数组和。DP遍历一遍数组即可。例1中的数组产生的DP为:

0 1 2 3 4 5 6 7
1 0 1 0 1 0 1 0

这个例子,最后一个值是0,并且长度是偶数位。直接满足了结果。

再看例子2:

0 1 2 3 4 5 6
1 2 1 2 1 0 -1

5的位置为0,最长子串从0开始到5,长度为6。

上面这两个例子,所求的子串都是从头开始,如果不是从头开始,会是什么样的呢?看这个例子:1101100

0 1 2 3 4 5 6
1 2 1 2 3 2 1

通过观察上面的表格,我们可以得到,DP[0]==DP[6]==DP[2],DP[1]==DP[3]. 根据DP的定义,如果DP[i]==DP[j],i
一种方法,我们用map保存DP的值到位置的映射,如下表:

DP值 位置 最大位置 最小位置 最大长度
1 0,2,6 6 0 6
2 1,3 3 1 2
3 4 4 4 0
最长子串长度 6

我们最终的算法,要综合考虑最常穿是否从头开始的。
上面的这个思路,时间复杂度是O(n),空间复杂度也是O(n).

还有其他的思路,例如DP保存的是[0,i]的1的个数,那么DP[j] - DP[i] * 2 == j - i则表明A[i+1]…A[j]是一个满足条件的串,找到j-i最大的,就是最终的结果,这个思路的时间复杂度为O(n^2),空间复杂度为O(n).

社交圈子挖掘的问题

这是博客搬家到博客园之后的第一篇文章,也是我最近对微博社交圈子挖掘的一些思考和总结,最近主要的思考和研究,主要针对一下几个问题:

  • 层次性
  • 重叠性
  • ego network
  • 有向社交网络
  • 带权社交网络
  • 统一解决上面的问题(!)

这几个,都是社交圈子挖掘时候我们所面临的问题,在挖掘逐渐深入的过程中,问题会一个一个显现出来。我们就要一个一个解决掉,最后要能够统一在一个方法,一个框架中。我在思考的过程中,也阅读了之前的研究,绝大部分都是针对其中的一个问题,或者两个问题。很少能够解决全部的问题。那我下面尝试分析一下这些问题的产生原因,以及一些可尝试的方法。

层次性

层次性是一个社会属性,在我们的社交圈子中非常的明显。比如,我的一个大一点的圈子是计算所,小一点的圈子是实验室。这种层次结构非常多,很多这个包含关系的层次结构。而且,层次结构也是很重要的,在网络中学习、了解网络的结构性质很有帮助。有一个应用,比如说,猎头在找人的时候,想知道哪些人都是百度的,可是并不是每个人都在自己的profile中写了公司是百度的资料,这个时候,就可以通过圈子挖掘的算法,将潜藏的信息挖掘出来。不同的层次,可能代表着公司中的不同的组。这个需要在实验过程中,自己体会,很有乐趣。针对层次性的问题,一个很直接的揭发就是层次聚类。可以根据不同的阈值获得不同层次的结果。不过,这个方法,要针对不同的层次,设定不同的阈值,并不是那么直接。

重叠性

这个是有社会中人的属性决定的:人会有小学同学、中学同学、大学同学、以前的同事、现在的同事、家人,兴趣小组等等关系圈子。首先,以个人为中心,个人出现在所有的这些圈子中(这也是下面要谈的ego network的问题),具有重叠性。另外,现实中,我的小学同学可能是在中学、大学都是同学,甚至非常有缘分的,工作了还是同事。所以重叠性是客观存在的,我们要正视这个问题。目前,在我的实验中,k-clique算法,针对重叠性,要过比较好。我之前的博客,也有介绍,大家可以看看效果。不过,一般的聚类和基于图划分的方法,都不具备这个特点。但这是很重要的一个性质。

Ego network

以前,在做社交网络的时候,并没有明确提出要针对个人、以个人为中心进行检测。基本都是对整个网络进行划分,对划分的评价也是针对整个网络进行的,比如Q函数。那为什么要构建ego network,以个人为中心进行检测呢?直观上说,没有问题。那么深层的原因呢?这个仍旧要从社会因素、社会的个体因素的角度理解。以微博为例(微博可以认为是一个社会的缩影),微博上的用户活跃度不同,最直观的表现有:1)更新微博比较频繁;2)关注、粉丝比较多;3)关注、粉丝变化也比较多。有的用户喜欢和朋友们交流,有的用户不喜欢。有的用户觉得微博是媒体,有的用户觉得微博是SNS。这些特点,都会让不同用户的关注、粉丝结构变化比较大。间接的结果就是用户的圈子大小、多少不同。所以,圈子挖掘要针对个人构建ego network,然后对该网络进行分析等。既然是针对不同的用户,构建不同的个人网络。我们是否还能够采用统一的阈值呢?当然不能。所以,针对不同的用户,学出相应的阈值,是非常重要的。这也是我最近研究的重点之一。

有向和带权的社交网络

我在做社交圈子挖掘的时候,主要针对的是微博。由于微博自身的媒体、SNS的性质,微博的关系是有方向的。所以,我们在挖掘过程中,是否能够充分利用这一点呢。另外,产生关注关系的原因有很多,比如有的人会碍于面子的原因关注的。还有,用户之间的交互有的多有的少。这些因素就直接导致了,社交网络是一个带权的网络,社交网络中的边的权重,可以理解为用户之间的紧密度。我们可以考虑不同的紧密度计算方法。比如互相转发,评论,@的次数之类的。总而言之,充分考虑方向和权重的因素。能够很大程度上提升效果。在我的尝试方法中,这两个也是重要的因素。

总结

上面干巴巴的说了很多问题。可能不是很有趣,但确实是我们在做社交挖掘过程中需要注意的问题。上面是一些点,如何将这些点,有机的结合在一起,将是一件更有挑战的事情。到目前为止的研究,已经有一些尝试,我会逐渐在后续的博客中,和大家分享。

后记

博客写多了,就会发现,大家更喜欢有例子,有数据,有结果的博文。所以,我想类似这种概述性质的,还是少写为妙。多将一些论文中的观点总结,写出来,实现并且给出结果。这样会更有帮助,让大家直观的知道这些方法的优缺点。我想我更多的路子,会是这样。并且,我真心希望更多的关注社交网络的同学一起讨论。我们国内也可像国外的大学一样,做出一些社交网络挖掘的工具,让老外用我们的。