SNE与t-SNE降维算法理解

1. SNE概要

数据降维,大体分为线性方法和非线性方法。其中线性方法例如PCA和LDA,而非线性方法又有保留局部特征、基于全局特征等方法。有人整理了一张分类图,下面这张图从网上引用而来:

相比于其他降维方法,t-SNE是近年比较火热的一种高维数据可视化技术,能够通过降维,将高维数据降维并给出二维或三维的坐标点,从而可以在人能够轻易理解的平面或立体空间内将数据可视化出来。这个方法是SNE的变种,SNE是Hinton在2002年提出来的方法。Stochastic Neighbor Embedding,好吧,又是embedding。目标是将高维数据映射到低维后,尽量保持数据点之间的空间结构,这样在高维空间里距离较远的点,在低维空间中依然保持较远的距离。在传统的方法中,PCA和MDS是线性技术,用于保持相距较远的数据点之间的低维表示。Maaten将t-SNE的降维结果与其他7种降维方法的结果,在5种不同的数据集中作了对比。

1.1 高维数据的相似度概率分布

SNE将数据点之间高维的欧氏距离转换为表示相似度的条件概率,即用条件概率\(p(j|i)\)表示点\(x_j\)到点\(x_i\)的相似度,这个含义可以理解为:若以\(x_i\)为中心的高斯分布来选取邻居,则\(x_i\)选择\(x_j\)作为自己邻居的概率是\(p(j|i)\)。若数据点相距较近,则\(p(j|i)\)较大,相反若数据点相距非常远,\(p(j|i)\)则可以接近无穷小。条件概率\(p(j|i)\)定义如下:

继续阅读SNE与t-SNE降维算法理解

Word2Vec原理之负采样算法

这篇主要根据前人的文章内容,整理了一遍skip-gram模型下negative-sampling的基本推导思路,只作学习之用,并不完整。公式也都是来自于已有论文。

分布式假设

Word2Vec虽然一直火热,也引发了各种词嵌入,但实际上不可否认依然是缺乏严谨的可解释性。所谓的分布式假设,就是处于相似上下文中的词具有相似的含义,一般认为这种相似包含了语义层面的相似,但却很难使用自然语言的词法、句法或语义的层面的现有知识来充分地解释。这可能也是词向量的一个缺陷,不过另一方面,这种分布式假设的概念可以应用到很多其他的领域的数据分析,比如广告分析、app点击数据分析等,毕竟只要能替代词和语料的关系,并且有上下文和中心词的类比关系,就可以一试,所以应用的广度可以说无法估计。

继续阅读Word2Vec原理之负采样算法

Word2Vec原理之层次Softmax算法

在这个人工智能半边天,主流话题一天一变的现代世界里,不乏进步,也不乏泡沫,但Word2Vec依然是很富极客精神的典型代表,作者思路很巧妙,工程层面又很实用主义。

词嵌入的假设,是通过一个词所在的上下文可以获得词的语义甚至语法结构,有相似上下文的词在向量空间中是邻近的点。

1 背景概念

Word2Vec要解决的根本问题,说到底是自然语言处理的问题。一般认为自然语言处理模型氛围两大派系,分别是形式文法和统计语言模型。

1.1 统计语言模型

统计语言模型在分词、词性标注、语义理解等NLP基本任务,以及语音识别、机器翻译等领域有广泛应用。关于统计语言模型,文献资料非常多,这篇博客也讲的很详细。简单地说,可以用统一地形式化表示:

\[p(S)=p(w_1,w_2,…,w_n)=\prod_{i=1}^{n} p(w_i|w_1,w_2,…,w_{i-1})\]

上述表示可以看做是用来计算词构成一个句子的概率模型,这就是统计语言模型的本质。但是概率的计算是个大问题,数据稀疏、参数过多,很难实际运用。前辈们研究了各种模型。例如n-gram、n-pos、决策树模型、最大熵模型等。

继续阅读Word2Vec原理之层次Softmax算法

Genymotion Virtual Device文件下载大法

大名鼎鼎的Genymotion很多人都说好,一直没自己用过,直到今天因为某些原因需要在电脑给客户演示app,终于想到要使用一下。不过Virtual Device的下载过程很蛋疼,科学上网工具稍有不稳定就会timeout,或文件损坏。

原本计划跟一下network记录寻找ova真实路径,Stackoverflow了一下发现暴多老外也在讨论这问题的,纳闷,一直以为只有在天朝才会困惑。

言归正传,Genymotion依靠VirtualBox来跑虚机,所以可以利用log来查看虚机ova文件的绝对下载路径,使用靠谱的工具下载,再拷贝到它本该在的本地目录。

Genymotion安装后在本地的数据文件夹在用户目录下,例如我的:

genymotion.log文件中有这样的记录:

那个.ova就是你的目标,然后就简单了,比如迅雷😄?然后拷贝到:

问题是,在我的电脑上拷贝完并重启Genymotion后,并不能直接找到虚机。无奈之下用VirtualBox打开ova文件并导入虚机后重启Genymotion,它却在那里了。

ChinaVis2016见闻与所思

前言

每年都争取出去参加一次跨界的知识学习,去年是CCL,今年是ChinaVis。ChinaVis2016(7月21日-23日,湖南长沙)是国内可视化与可视化分析领域的专业会议,今年是第三届。去年的时候开始关注,没能去参加,今年终于排上了日程并说走就走。站在可视化领域的外围看这个世界,一直都不是很清晰,所以有机会能够以一个外行的身份过来感受一下这个圈子的氛围,是件令人兴奋的事情。下面整理的内容无法面面俱到,有些内容甚至都是大会以外的,但是希望把我的几个关注点上学习到的内容作一个简单的总结,如有不正确之处,希望得到指正。

理解可视化与交互

可视化的概念不用说了,但“可视化分析”一词,我是至今才有一个稍微清晰一点的认识,很是惭愧。所谓分析,一般可以拆解为不通的步骤,从数据的获取开始,可以往后写一堆。作为一个GIS人,在我以前的理解里,可视化呈现的是一种结果,所以一直对“可视化分析”这个词的科学性持质疑态度。

实际上,不同领域里,对此可以有不同的解释。例如,清华大学的朱军在谈到交互式机器学习与可视化的话题时,交互式机器学习在如下环节中都需要可视化的协助:

  1. 数据预处理时可以用到可视化
  2. 学习过程里可以可视化,因为机器学习本身黑箱
  3. 对机器学习评价也需要可视化交互式界面

继续阅读ChinaVis2016见闻与所思

中文维基百科文本数据分析之一(数据获取与预处理)

照例,先讲下环境,Mac OSX 10.11.2 ,Python 3.4.3。

下载数据

方法1:使用官方dump的xml数据

最新打包的中文文档下载地址是:https://dumps.wikimedia.org/zhwiki/latest/zhwiki-latest-pages-articles.xml.bz2 。

方法2:也是官方,结构化数据(json)

下载地址是:https://dumps.wikimedia.org/wikidatawiki/entities/ 。目前尚未测试使用此数据,不多作介绍。但数据模型和已有的工具都可以在wikidata的站点上找到。

继续阅读中文维基百科文本数据分析之一(数据获取与预处理)

隐马尔可夫模型的基本概念

自然语言处理领域,隐马尔可夫模型在语音识别、词性标注、分词等方面都有不少研究和应用。

对于一个典型的HMM示意图(图来自维基百科:隐马尔可夫模型)如下:

Hmm

在正常的马尔可夫模型中,状态对于观察者是直接可见的,因此状态的转换概率即是参数。而在HMM中,状态(x)不是直接可见的,但每个状态下输出的某些输出(y)是可见的。每个状态在可能输出的符号上都有一个概率分布(b),即(符号)输出概率-(symbol)emission probabilities。另外,少不了隐含状态间的转换概率(a),即transition probabilities。由此可见5大要素:

X — 隐含状态集合
Y — 可观察的输出集合
A — 转换概率
b — 输出概率
π — 初试状态的概率分布

其中,π和A决定了状态序列,且这里用到马尔可夫假设,即当前隐含状态只取决于前一个隐含状态。而B决定了观测序列。所以一般认为隐马尔可夫模型λ可以用三元符号表示:

 lambda =left( A,B,pi right)

关于如何理解隐含变量以及HMM的大致原理,好的文章太多了,其中简单易懂的,我觉得这条知乎上Yang Eninala的回答写的很有耐心。

统计自然语言处理的基本概念

NLP的几个层次

以下是学习宗成庆著作中相关内容整理,详细内容可参考其著作《统计自然语言处理》。自然语言的处理包含语音、形态、语法、语义、语用几个层面,若暂不考虑语音和语用,以下三个概念非常重要:

形态学(Morphology)

词汇形态学(或词法)研究词的内部结构。

语法学(Syntax)

研究句子结构元素之间的关系与规则。主要关注一句话该怎么讲。

语义学(Semantics)

研究语言各级单位(词素、词、词组、句子、句子群、整段整篇、甚至整个著作)的意义,重点是研究符号与符号所指对象之间的关系。

NLP的基本方法

自然语言处理真的很困难,词汇形态歧义消解并不容易。有研究结论称,歧义结构分析结果的数量随介词短语数目的增加呈指数上升的,其歧义组合的复杂程度随着介词短语个数的增加而不断加深,这个歧义结构的组合数目称为开塔兰数(Catalan numbers),下式中,n为介词短语个数:

c_{n}=left( begin{matrix} 2n\ nend{matrix} right) dfrac {1} {n+1}

上面讲的是英文情况,中文自然语言里,各种歧义、指代等,也是相当的复杂。对于这些复杂问题的理解,存在两种不同的“主义”,即理性主义方法和经验主义方法。

理性主义方法

理性主义方法的代表是著名的乔姆斯基理论,认为人的语言能力是与生俱来的。因此对于NLP的难题,需要首先由词法分析器按照人工编写的词法规则对输入的句子的单词进行词法分析,然后根据人工设计的语法规则对输入的句子进行句法结构分析,最后再根据一套变换规则将语法结构映射到语义符号(如逻辑表达式、语义网络、中间语言等)。

经验主义方法

经验主义认为,人(孩子)的大脑一开始具有一些基本的处理能力(联想、模式识别、通用化),因此可以在后期通过感官输入来不断学习和掌握自然语言的结构。因此在实践层面,经验主义方法主张通过建立数学模型来学习语言结构,然后利用统计学、模式识别和机器学习等方法来训练模型的参数,以扩大语言使用的规模。从方法上看,经验主义的思路是很明确的统计自然语言处理(SNLP)方法。

统计方法中的基本概念

统计方法中,概率论和信息论是最基本的部分,必须掌握地相当靠谱才行:

  1. 概率论基本概念:概率、条件概率、贝叶斯法则、贝叶斯决策理论、随机变量、参数估计方法、二项式分布、联合概率分布和条件概率分布、期望和方差等。
  2. 信息论基本概念:熵、联合熵、条件熵、相对熵、交叉熵、互信息、困惑度、噪声信道模型等。

 

时空平稳性的概念与STARMA模型

时空相关性

时空相关性反映了序列对时空的依赖,一般会讨论到时空自相关性和时空偏相关性两个概念。

时空平稳性

时空平稳性(Space-time Stationarity)的概念,是说如果是平稳的,那意味着在时空范畴内不存在任何趋势或者模式。在统计上,表现为均值、方差、协方差等不随时间和空间的变化而变化。在实际应用中,很少能够满足统计上绝对的不变值,因此只要求近似为常数即可认为时空序列平稳。

因此,对于时空平稳的时空变量来说,

时空非平稳性,可能是大尺度的趋势,也可能是局部效应。

  1. 大尺度的非平稳:描述均值的总体变化。通常称为“一阶”效应。
  2. 局部的非平稳:是对时时空相关局部特征的描述。通常称为“二阶”效应。对于时间序列分析,一般用自相关移动平均描述因时间依赖造成的局部效应;对于空间数据分析,一般用空间自相关描述其局部效应。

STARMA模型

严格说来,STARMA模型是由时间序列模型模型ARMA(自回归-移动平均)向空间层面扩展而来。该模型在时间序列的基础上,增加考虑了空间相邻位置的影响,因此从时空结合角度讲,更为准确。模型有两个基本假设:

  1. 序列是平稳的
  2. 随机误差符合正态分布

因此,随之而来的处理方式中,首先要解决序列的平稳化问题,过程中需要通过观察空间自相关系数来发现非平稳的存在,并可能会用到各种手段来实现平稳化,例如进行周期性差分处理。

空间权重矩阵(SWM)

基本原理

如何利用数学(如用面积、距离等)建立空间数据和非空间数据之间的关系?对于空间统计而言,空间权重矩阵是一种有效的表达空间关系的方式。因此,它是用量化的方法表示了数据之间的“空间结构”。

关于如何进行要素间实际交互方式的概念化,ESRI举出的例子:

如果要测量森林中某种特定种类的种子繁殖树种的聚类,使用某种形式的反距离可能最适合。但是,如果要评估某一地区通勤者的地理分布,行程时间和行程成本可能是更好的选择。

空间权重矩阵是N*N的表,N为数据集中的要素数量。因此给定行列组合后,其对应的值即为权重。这种空间关系的权重矩阵在许多空间统计工具里都有用,比如空间自相关、热点分析、聚类和异常值分析等。

创建策略

  1. 二进制策略:某个要素要么是邻域-1,要么不是-0。例如:固定距离、K 最近邻域、Delaunay 三角测量、邻接或空间 – 时间窗口。
  2. 权重策略:邻近要素有不同量级的影响,并通过计算权重来反映该变化。例如:反距离或无差别的区域。

工具使用

arcgis中的SWM使用稀疏矩阵存储,因此只存非零部分。实际情况,每个要素一般只跟其他某几个要素发生关系。

工具名字:Generate Spatial Weights Matrix (Spatial Statistics),工具界面如图:

SWM的使用:以热点分析为例

具体权重的使用,以热点分析为例,几个主要的步骤如下:

integrate与collect event

collect event的结果数据

重点是需要生成feature class,并且确保这个feature class有一个唯一id字段。

Generate Spatial Weights Matrix

Hot Spot Analysis (Getis-Ord Gi*)