Probabilistic Grammar in Natural Language Processing

Context-Free Grammar

上下文无关语法,简称CFG,G定义为四元组

  • $N$ 是非终极符号的集合
  • $\sum$ 是终极符号的集合
  • $S$ 是初始符号
  • $P$ 是重写规则

规则的形式为:$A\to \beta$ ,$A$为单独的非终极符号,$\beta$ 是符号串,它可以由终极符号,非终极符号,终极符号和非终极符号混合组成。

Ex:

有如下的上下文无关语法{N,Σ, P, S}:
$N = \{S, NP, VP, PP, Prep, Verb, Noun\}$
$Σ = \{like, swat, flies, ants\}$
$S =\{S\}$
$P:$
$S \to NP\quad VP$
$S \to VP$
$NP \to Noun$
$NP \to Noun\quad PP$
$NP \to Noun\quad NP$
$VP \to Verb$
$VP \to Verb\quad NP$
$VP \to Verb\quad PP$
$VP \to Verb\quad NP\quad PP$
$PP \to Prep\quad NP$
$Prep \to like$(含义是“如,像”)
$Verb \to swat $(含义是“猛击”)
$Verb \to flies $(含义是“飞”,单数第三人称现在时)
$Verb \to likes$(含义是“喜欢”)
$Noun \to swat $(专有名词,苍蝇的名字)
$Noun \to flies$(含义是“苍蝇”,复数)
$Noun \to ants$ (含义是“蚂蚁”,复数)

使用上下文无关语法的剖析技术来剖析”swat flies like ants”,可以得到三个结构不同的树形图:
paste image
具有这个树形图结构 T1 的句子的含义是“像猛击蚂蚁一样地猛击苍蝇”。
paste image
具有这个树形图结构 T2 的句子的含义是“Swat 像蚂蚁一样地飞”。
paste image
具有这个树形图结构 T3 的句子的含义是“叫做 Swat 的一些苍蝇喜欢蚂蚁”。


Spark-kNN

pom.xml配置:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>

<groupId>cn.lisongqian</groupId>
<artifactId>knn</artifactId>
<version>1.0-SNAPSHOT</version>
<dependencies>
<!-- https://mvnrepository.com/artifact/org.scala-lang/scala-library -->
<dependency>
<groupId>org.scala-lang</groupId>
<artifactId>scala-library</artifactId>
<version>2.12.5</version>
</dependency>
<!-- https://mvnrepository.com/artifact/org.apache.spark/spark-core -->
<dependency>
<groupId>org.apache.spark</groupId>
<artifactId>spark-core_2.11</artifactId>
<version>2.1.0</version>
</dependency>

</dependencies>

</project>

Read More



Fake news analysis based on kg

基于Naïve Bayes和TF-IDF的真假新闻分类

用途:通过词包来对新闻的真假进行预测

去停用词

人类语言中包含的功能词,这些功能词极其普遍(’the’、’is’、’at’、’which’、’on’)—提高搜索性能

词频$tf_{ij}$

逆向文件频率$idf_i$

$idf_i=log\frac{|D|}{1+|\{d\in D: t\in d\}|}$ => $log\frac{文件总数}{包含该词语的文件数目+1}$

计算TF与IDF的乘积作为权重$tfidf_i$

通过计算得到包含词语权重的向量(指向该分类的词语带权向量)

计算概率(基于贝叶斯公式)

对每一篇训练集的相同词权重进行累加,条件概率=$该词条数目总词条数目\frac{该词条数目}{总词条数目}$,得出每个类别每个词条的概率向量

预测真假新闻

输入新闻,计算结果(可能是乘积,可能是条件概率),将向量对应位置相乘,求和,比较在两种词包的条件下谁的概率大。

Read More



聚类算法

各种聚类算法的系统介绍和比较

Hierarchical methods(层次)

算法流程

  • 将每个对象看作一类,计算两两之间的最小距离
  • 将距离最小的两个类合并成一个新类
  • 重新计算新类与所有类之间的距离
  • 重复2、3步,直至所有类最后合并为一类

算法优缺点

  • 优点:可解释性好(如当需要创建一种分类法时);还有些研究表明这些算法能产生高质量的聚类,也会应用在上面说的先取K比较大的K-means后的合并阶段;还有对于K-means不能解决的非球形族就可以解决了。
  • 缺点:时间复杂度高啊,$o(m^3)$,改进后的算法也有$o(m^2lgm)$,m为点的个数;贪心算法的缺点,一步错步步错;同K-means,处理不同大小的簇和凸形数据有困难。

    Read More