1) Multiple features(多维特征)

2) Gradient descent for multiple variables(梯度下降在多变量线性回归中的应用)

3) Gradient descent in practice I: Feature Scaling(梯度下降实践1：特征归一化)

4) Gradient descent in practice II: Learning rate(梯度下降实践2：步长的选择)

5) Features and polynomial regression(特征及多项式回归)

6) Normal equation(正规方程-区别于迭代方法的直接解法)

7) Normal equation and non-invertibility (optional)(正规方程在矩阵不可逆情况下的解决方法)

以下是每一部分的详细解读：

1) Multiple features(多维特征)

第二课中我们谈到的是单变量的情况，单个特征的训练样本，单个特征的表达式，总结起来如下图所示：

对于多维特征或多个变量而言：以房价预测为例，特征除了“房屋大小外”，还可以增加“房间数、楼层数、房龄”等特征，如下所示：

定义：

n = 特征数目

$x^{(i)}$= 第i个训练样本的所有输入特征，可以认为是一组特征向量

$x_j^{(i)}$ = 第i个训练样本第j个特征的值，可以认为是特征向量中的第j个值

对于Hypothesis，不再是单个变量线性回归时的公式：$h_\theta(x)=\theta_0 + \theta_1 x$

而是：

$$h_\theta(x)=\theta_0 + \theta_1 x_1 + \theta_2 x_2 + ... + \theta_n x_n$$

为了方便，记$x_0$ = 1，则多变量线性回归可以记为：

$$h_\theta(x)=\theta^Tx$$

其中$\theta$和x都是向量。

2) Gradient descent for multiple variables(梯度下降在多变量线性回归中的应用)

对于Hypothesis:

$$h_\theta(x)=\theta^Tx=\theta_0 + \theta_1 x_1 + \theta_2 x_2 + ... + \theta_n x_n$$

其中参数：$\theta_0$, $\theta_1$,...,$\theta_n$可表示为n+1维的向量  $\theta$

对于Cost Function:

$$J(\theta) = J(\theta_0, \theta_1, ... ,\theta_n) = \frac{1}{2m}\sum_{i=1}^m{(h_\theta(x^{(i)}) - y^{(i)})^2}$$

梯度下降算法如下:

对$J(\theta)$求导，分别对应的单变量和多变量梯度下降算法如下：

当特征数目为1，也就是n=1时：

当特征数目大于1也就是n>1时，梯度下降算法如下：

3) Gradient descent in practice I: Feature Scaling(梯度下降实践1：特征归一化)

核心思想：确保特征在相似的尺度里。

例如房价问题：

特征1：房屋的大小（0-2000）；

特征2：房间数目（1-5）；

简单的归一化，除以每组特征的最大值，则：

目标：使每一个特征值都近似的落在$-1\leq x_i \leq 1$的范围内。

举例：因为是近似落在这个范围内，所以只要接近的范围基本上都可以接受，例如：

0<=x1<=3, -2<=x2<=0.5, -3 to 3, -1/3 to 1/3 都ok;

但是：-100 to 100, -0.0001 to 0.0001不Ok。

Mean Normalization(均值归一化):

用$x_i - \mu_i$替换$x_i$使特征的均值近似为0（但是不对$x_0=1$处理），均值归一化的公式是：

$$x_i \leftarrow \frac{x_i - \mu_i} {S_i}$$

其中$S_i$可以是特征的取值范围（最大值-最小值），也可以是标准差(standard deviation).

对于房价问题中的两个特征，均值归一化的过程如下：

4) Gradient descent in practice II: Learning rate(梯度下降实践2：步长的选择)

对于梯度下降算法：

需要注意两点：

-"调试”：如何确保梯度下降算法正确的执行；

-如何选择正确的步长(learning rate):  $\alpha$;

第二点很重要，它也是确保梯度下降收敛的关键点。要确保梯度下降算法正确运行，需要保证 $J(\theta)$在每一步迭代中都减小，如果某一步减少的值少于某个很小的值 $\epsilon$ , 则其收敛。例如：

如果梯度下降算法不能正常运行，考虑使用更小的步长$\alpha$，这里需要注意两点：

1）对于足够小的$\alpha$,  $J(\theta)$能保证在每一步都减小；

2）但是如果$\alpha$太小，梯度下降算法收敛的会很慢；

总结：

1）如果$\alpha$太小，就会收敛很慢；

2）如果$\alpha$太大，就不能保证每一次迭代$J(\theta)$都减小，也就不能保证$J(\theta)$收敛；

如何选择$\alpha$-经验的方法：

..., 0.001, 0.003, 0.01, 0.03, 0.1, 0.3, 1...

约3倍于前一个数。

5) Features and polynomial regression(特征及多项式回归)

例子-房价预测问题：

特征$x_1$表示frontage(正面的宽度），特征$x_2$表示depth(深度)

同时$x_1, x_2$也可以用一个特征表示：面积 Area = frontage * depth

即 $h_\theta(x) = \theta_0 + \theta_1x$ , x表示面积。

多项式回归:

很多时候，线性回归不能很好的拟合给定的样本点，例如：

所以我们选择多项式回归：

对于特征的选择，除了n次方外，也可以开根号，事实上也是1/2次方：

6) Normal equation(正规方程-区别于迭代方法的直接解法)

相对于梯度下降方法，Normal Equation是用分析的方法直接解决$\theta$.

正规方程的背景：

在微积分里，对于1维的情况，如果$\theta$ 属于R:

$$J(\theta) = a\theta^2 + b\theta + c$$

求其最小值的方法是令：

$$\frac{d}{d\theta}J(\theta) = ...=0$$

然后得到$\theta$.

同理，在多变量线性回归中，对于$\theta \in R^{n+1}$，Cost Function是：

求取$\theta$的思路仍然是：

对于有4组特征(m=4)的房价预测问题：

其中X 是m * (n+1)矩阵：

y是m维向量：

则Normal equation的公式为：

$$\theta = (X^T X)^{-1}X^T y$$

注：这里直接给出了正规方程的公式，没有给出为什么是这样的，如果想知道原因，建议看看MIT线性代数 第4章4.3节“最小二乘法”的相关内容，这里面最关键的一个点是：

“The partial derivatives of $||Ax - b||^2$ are zero when $A^TA x = A^Tb$.

举例可见官方的PPT，此处略；

Octave公式非常简洁：pinv(X' * X) * X' * y

对于m个样本，n个特征的问题，以下是梯度下降和正规方程的优缺点：

梯度下降：

需要选择合适的learning rate $\alpha$;

需要很多轮迭代；

但是即使n很大的时候效果也很好；

Normal Equation:

不需要选择$\alpha$；

不需要迭代，一次搞定；

但是需要计算$(X^TX)^{-1}$，其时间复杂度是$O(n^3)$

如果n很大，就非常慢

7) Normal equation and non-invertibility (optional)(正规方程在矩阵不可逆情况下的解决方法)

对于Normal Equation，如果$X^TX$ 不可逆怎么办？

1) 去掉冗余的特征（线性相关）：

例如以平方英尺为单位的面积x1,  和以平方米为单位的面积x2，其是线性相关的：

$x_1=(3.28)^2 x_2$

2) 过多的特征，例如m <= n:

删掉一些特征，或者使用regularization--之后的课程会专门介绍。

参考资料：

相关文章:

1. Coursera公开课笔记: 斯坦福大学机器学习第二课“单变量线性回归(Linear regression with one variable)”
2. Coursera公开课笔记: 斯坦福大学机器学习第一课“引言(Introduction)”
3. HMM学习最佳范例五：前向算法2
4. HMM学习最佳范例五：前向算法3
5. 条件随机场文献阅读指南
6. WordPress中的公式编辑器插件
7. 腾讯搜索广告平台部招聘工程师
8. 立委随笔：机器学习和自然语言处理
9. HMM学习最佳范例五：前向算法4
10. HMM学习最佳范例六：维特比算法4

使用“多说”则是为了尝试一下社交化的评论系统，而这篇文章的目的也是想测试一下多说提供的一些功能，譬如自动同步到微博等等，另外读者如果使用中发现存在某些问题，也请告知，非常感谢！

相关文章:

1. Google's Python Class - SOS
2. 代友转发：发起成立中文机器翻译定期学术沙龙
3. Coursera公开课笔记: 斯坦福大学机器学习第一课“引言(Introduction)”
4. Coursera公开课笔记: 斯坦福大学机器学习第二课“单变量线性回归(Linear regression with one variable)”
5. 52NLP微博-当真李逵遇到假李逵

1) Model representation(模型表示)

2) Cost function(代价函数，成本函数)

3) Cost function intuition I(直观解释1)

4) Cost function intuition II(直观解释2)

5) Gradient descent(梯度下降)

6) Gradient descent intuition(梯度下降直观解释)

7) Gradient descent for linear regression(应用于线性回归的的梯度下降算法)

相关文章:

1. Coursera公开课笔记: 斯坦福大学机器学习第四课“多变量线性回归(Linear Regression with Multiple Variables)”
2. Coursera公开课笔记: 斯坦福大学机器学习第一课“引言(Introduction)”
3. 腾讯搜索广告平台部招聘工程师
4. MIT自然语言处理第五讲：最大熵和对数线性模型（第二部分）
5. 条件随机场文献阅读指南
6. MIT自然语言处理第五讲：最大熵和对数线性模型（第四部分）
7. MIT自然语言处理第五讲：最大熵和对数线性模型（第一部分）
8. MIT自然语言处理第五讲：最大熵和对数线性模型（第三部分）
9. MIT自然语言处理第四讲：标注（第四部分）
10. MIT自然语言处理第五讲：最大熵和对数线性模型（第五部分）

相关文章:

1. 招生：Ph.D research assistant in machine learning and NLP
2. recruiting Ph.D. students
3. From Google Research Blog: Google at ACL 2011
4. CFP: The 7th Young Researchers' Roundtable on Spoken Dialogue Systems
5. 追忆大师贾里尼克
6. ME for Machine Translation
7. ACL 2010 Paper国内研究单位录用情况
8. Free Online Stanford Course on NLP
9. Itenyh版-用HMM做中文分词五：一个混合的分词器
10. 自然语言处理公司巡礼三：Inxight

以下转自原文: Coursera公开课笔记: 斯坦福大学机器学习第一课“引言(Introduction)”

Coursera上于4月23号启动了6门公开课，其中包括斯坦福大学于“机器学习”课程，由机器学习领域的大牛Andrew Ng教授授课：

https://www.coursera.org/course/ml

课程刚刚开始，对机器学习感兴趣的同学尽量注册，这样即使没有时间学习，获取相关资料特别是视频比较方便。

由于工作繁忙的缘故，这批科目里我主要想系统的学习一下“机器学习”课程，所以计划在52opencourse和52nlp上同步我的机器学习课程笔记，一方面做个记录和总结，另一方面方便后来者参考。

Coursera上机器学习的课程学习过程是这样的：看Andrew Ng教授的授课视频或者看看课程相关的ppt；答系统随机出的题，一般5道题，单选、多选甚至填空，满分5分；编程作业，需用Octave(和 Matlab相似的开源编程语言)完成，提交给系统得分，在规定时间内完成，均取最高分，超过规定时间会对得分打折。

第一周（4月23日-4月29日）的课程包括三课：

3）有监督学习详解

有监督学习主要会提供一些标注样本，分为两大问题：回归和分类

房屋价格预测-回归(Regression): 预测连续的输出值（价格)

 

 

乳腺癌（良性，恶性）预测问题-分类(Classification): 预测离散的输出值(0, 1)

 

4) 无监督学习详解:有监督学习和无监督学习的对比，看图更形象：                             

例子: Google News， 基因序列分析，社会网络分析，市场切分等...

 

特别的例子：鸡尾酒会问题（Cocktail party problem）

“ 鸡尾酒会问题”（cocktail party problem）是在计算机语音识别领域的一个问题，当前语音识别技术已经可以以较高精度识别一个人所讲的话，但是当说话的人数为两人或者多人时，语音识别率就会极大的降低，这一难题被称为鸡尾酒会问题。

鸡尾酒会问题算法（一行代码）：

[W,s,v] = svd((repmat(sum(x.*x,1),size(x,1),1).*x)*x');

 

一些参考资料：

解决方法ICA demo: http://research.ics.tkk.fi/ica/cocktail/cocktail_en.cgi

http://www.vislab.uq.edu.au/education/sc3/2001/johan/johan.pdf

http://www.physorg.com/news75477497.html

http://en.wikipedia.org/wiki/Cocktail_party_effect

http://www.scientificamerican.com/article.cfm?id=solving-the-cocktail-party-problem

 

以下关于"cocktail party problem"的文字引用自该链接：http://xiaozu.renren.com/xiaozu/121443/thread/335879281

stanford机器学习公开课(ml-class.org)第一章unsupervised learning那段视频里解决鸡尾酒会问题(cocktail party problem)就写了一行代码：

[W,s,v] = svd ((repmat(sum(x.*x,1),size(x,1),1).*x)*x');

lz土人感觉是用了PCA的方法。。可是W运行出来丝毫没有unmixing的效果。。。用的是采样频率16kHz的Speech-Speech和Speech-Music两个样例。。

google这条代码有post说这是ICA，我就迷茫了。。。看不出来怎么是ICA了。。折腾一夜了，毫无头绪。。。

顺便求此问题的demo。。各种语言均无妨。。

本文链接地址：http://www.52nlp.cn/coursera%E5%85%AC%E5%BC%80%E8%AF%BE%E7%AC%94%E8%AE%B0-%E6%96%AF%E5%9D%A6%E7%A6%8F%E5%A4%A7%E5%AD%A6%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E7%AC%AC%E4%B8%80%E8%AF%BE%E5%BC%95%E8%A8%80introduct

 

相关文章:

1. Coursera公开课笔记: 斯坦福大学机器学习第二课“单变量线性回归(Linear regression with one variable)”
2. Coursera公开课笔记: 斯坦福大学机器学习第四课“多变量线性回归(Linear Regression with Multiple Variables)”
3. 腾讯搜索广告平台部招聘工程师
4. 立委随笔：机器学习和自然语言处理
5. 条件随机场文献阅读指南
6. 理解EM算法
7. 一个不错的自然语言处理词典
8. Moses训练脚本的一个问题

PYTHON自然语言处理中文翻译-NLTK Natural Language Processing with Python 中文版

　　翻看了一下翻译版，且不说翻译质量，单看排版就让人觉得向一本正式的翻译书籍，说明译者是非常有心的。以下是从翻译版中摘录的“译者的话”:

　　作为一个自然语言处理的初学者，看书看到“训练模型”，这模型那模型的，一直不知
道模型究竟是什么东西。看了这本书，从预处理数据到提取特征集，训练模型，测试修改等，一步一步实际操作了之后，才对模型一词有了直观的认识（算法的中间结果，存储在计算机中的一个个pkl 文件，测试的时候直接用，前面计算过的就省了）。以后听人谈“模型”的时候也有了底气。当然，模型还有很多其他含义。还有动词的“配价”、各种搭配、客观逻辑对根据文法生成的句子的约束如何实现？不上机动手做做，很难真正领悟。

　　自然语言处理理论书籍很多，讲实际操作的不多，能讲的这么系统的更少。从这个角度
讲，本书是目前世界上最好的自然语言处理实践教程。初学者若在看过理论之后能精读本书，必定会有获益。这也是翻译本书的目的之一。

　　本书是译者课余英文翻译练习，抛砖引玉。书中存在很多问题，尤其是第10 章命题逻
辑和一阶逻辑推理在自然语言处理中的应用。希望大家多多指教。可以在微博上找到我（w
eibo.com/chentao1999）。虽然读中文翻译速度更快，但直接读原文更能了解作者的本意。

　　原书作者在书的最后列出了迫切需要帮助改进的条目，对翻译本书建议使用目标语言的
例子，目前本书还只能照搬英文的例子，希望有志愿者能加入本书的中文化进程中，为中文
自然语言处理做出贡献。

　　将本书作学习和研究之用，欢迎传播、复制、修改。山寨产品请留下译者姓名和微博。
用于商业目的，请与原书版权所有者联系，译者不承担由此产生的责任。

翻译：陈涛（weibo.com/chentao1999）

2012 年4 月7 日

　　 最后希望大家在读这本书的过程中，记录一下需要勘误的地方，可以在“评论”中给出勘误建议，一起来修正这本书。谢谢！

相关文章:

1. Google's Python Class
2. 如何学习自然语言处理
3. Google's Python Class - SOS
4. “知行合一”与自然语言处理
5. MapReduce与自然语言处理
6. 提供几本自然语言处理书
7. Beautiful Data-统计语言模型的应用三：分词8
8. Google’s Python Class SOS 续 --下载
9. HMM在自然语言处理中的应用一：词性标注6
10. 自然语言处理百科正式发布

这篇讲LDA更"人道"一些，比那些用来证明自己算法正确的文章清楚很多。不过也提到，LDA或者概率模型要用好，需要不断的筛选features、精选进行操作的token才行。// Topic modeling made just simple enough http://t.cn/zOpOc4D //喜欢这样的文章是不是就是Sheldon看不上Leonard很重要的方面，呵呵

就打开链接看了一下，然后转发了，再之后有同学反映文章被墙了，才发现这篇文章发表在wordpress.com上，转载在这里吧，有需要的同学可以看看，原文见：Topic modeling made just simple enough

 

Topic modeling made just simple enough.

Right now, humanists often have to take topic modeling on faith. There are several good posts out there that introduce the principle of the thing (by Matt Jockers, for instance, and Scott Weingart). But it’s a long step up from those posts to the computer-science articles that explain “Latent Dirichlet Allocation” mathematically. My goal in this post is to provide a bridge between those two levels of difficulty.

Computer scientists make LDA seem complicated because they care about proving that their algorithms work. And the proof is indeed brain-squashingly hard. But the practice of topic modeling makes good sense on its own, without proof, and does not require you to spend even a second thinking about “Dirichlet distributions.” When the math is approached in a practical way, I think humanists will find it easy, intuitive, and empowering. This post focuses on LDA as shorthand for a broader family of “probabilistic” techniques. I’m going to ask how they work, what they’re for, and what their limits are.

How does it work? Say we’ve got a collection of documents, and we want to identify underlying “topics” that organize the collection. Assume that each document contains a mixture of different topics. Let’s also assume that a “topic” can be understood as a collection of words that have different probabilities of appearance in passages discussing the topic. One topic might contain many occurrences of “organize,” “committee,” “direct,” and “lead.” Another might contain a lot of “mercury” and “arsenic,” with a few occurrences of “lead.” (Most of the occurrences of “lead” in this second topic, incidentally, are nouns instead of verbs; part of the value of LDA will be that it implicitly sorts out the different contexts/meanings of a written symbol.)

Of course, we can’t directly observe topics; in reality all we have are documents. Topic modeling is a way of extrapolating backward from a collection of documents to infer the discourses (“topics”) that could have generated them. (The notion that documents are produced by discourses rather than authors is alien to common sense, but not alien to literary theory.) Unfortunately, there is no way to infer the topics exactly: there are too many unknowns. But pretend for a moment that we had the problem mostly solved. Suppose we knew which topic produced every word in the collection, except for this one word in document D. The word happens to be “lead,” which we’ll call word type W. How are we going to decide whether this occurrence of W belongs to topic Z?

We can’t know for sure. But one way to guess is to consider two questions. A) How often does “lead” appear in topic Z elsewhere? If “lead” often occurs in discussions of Z, then this instance of “lead” might belong to Z as well. But a word can be common in more than one topic. And we don’t want to assign “lead” to a topic about leadership if this document is mostly about heavy metal contamination. So we also need to consider B) How common is topic Z in the rest of this document?

Here’s what we’ll do. For each possible topic Z, we’ll multiply the frequency of this word type W in Z by the number of other words in document D that already belong to Z. The result will represent the probability that this word came from Z. Here’s the actual formula:

Simple enough. Okay, yes, there are a few Greek letters scattered in there, but they aren’t terribly important. They’re called “hyperparameters” — stop right there! I see you reaching to close that browser tab! — but you can also think of them simply as fudge factors. There’s some chance that this word belongs to topic Z even if it is nowhere else associated with Z; the fudge factors keep that possibility open. The overall emphasis on probability in this technique, of course, is why it’s called probabilistic topic modeling.

Now, suppose that instead of having the problem mostly solved, we had only a wild guess which word belonged to which topic. We could still use the strategy outlined above to improve our guess, by making it more internally consistent. We could go through the collection, word by word, and reassign each word to a topic, guided by the formula above. As we do that, a) words will gradually become more common in topics where they are already common. And also, b) topics will become more common in documents where they are already common. Thus our model will gradually become more consistent as topics focus on specific words and documents. But it can’t ever become perfectly consistent, because words and documents don’t line up in one-to-one fashion. So the tendency for topics to concentrate on particular words and documents will eventually be limited by the actual, messy distribution of words across documents.

That’s how topic modeling works in practice. You assign words to topics randomly and then just keep improving the model, to make your guess more internally consistent, until the model reaches an equilibrium that is as consistent as the collection allows.

What is it for? Topic modeling gives us a way to infer the latent structure behind a collection of documents. In principle, it could work at any scale, but I tend to think human beings are already pretty good at inferring the latent structure in (say) a single writer’s oeuvre. I suspect this technique becomes more useful as we move toward a scale that is too large to fit into human memory.

So far, most of the humanists who have explored topic modeling have been historians, and I suspect that historians and literary scholars will use this technique differently. Generally, historians have tried to assign a single label to each topic. So in mining the Richmond Daily Dispatch, Robert K. Nelson looks at a topic with words like “hundred,” “cotton,” “year,” “dollars,” and “money,” and identifies it as TRADE — plausibly enough. Then he can graph the frequency of the topic as it varies over the print run of the newspaper.

As a literary scholar, I find that I learn more from ambiguous topics than I do from straightforwardly semantic ones. When I run into a topic like “sea,” “ship,” “boat,” “shore,” “vessel,” “water,” I shrug. Yes, some books discuss sea travel more than others do. But I’m more interested in topics like this:

You can tell by looking at the list of words that this is poetry, and plotting the volumes where the topic is prominent confirms the guess.

This topic is prominent in volumes of poetry from 1815 to 1835, especially in poetry by women, including Felicia Hemans, Letitia Landon, and Caroline Norton. Lord Byron is also well represented. It’s not really a “topic,” of course, because these words aren’t linked by a single referent. Rather it’s a discourse or a kind of poetic rhetoric. In part it seems predictably Romantic (“deep bright wild eye”), but less colorful function words like “where” and “when” may reveal just as much about the rhetoric that binds this topic together.

A topic like this one is hard to interpret. But for a literary scholar, that’s a plus. I want this technique to point me toward something I don’t yet understand, and I almost never find that the results are too ambiguous to be useful. The problematic topics are the intuitive ones — the ones that are clearly about war, or seafaring, or trade. I can’t do much with those.

Now, I have to admit that there’s a bit of fine-tuning required up front, before I start getting “meaningfully ambiguous” results. In particular, a standard list of stopwords is rarely adequate. For instance, in topic-modeling fiction I find it useful to get rid of at least the most common personal pronouns, because otherwise the difference between 1st and 3rd person point-of-view becomes a dominant signal that crowds out other interesting phenomena. Personal names also need to be weeded out; otherwise you discover strong, boring connections between every book with a character named “Richard.” This sort of thing is very much a critical judgment call; it’s not a science.

I should also admit that, when you’re modeling fiction, the “author” signal can be very strong. I frequently discover topics that are dominated by a single author, and clearly reflect her unique idiom. This could be a feature or a bug, depending on your interests; I tend to view it as a bug, but I find that the author signal does diffuse more or less automatically as the collection expands.

What are the limits of probabilistic topic modeling? I spent a long time resisting the allure of LDA, because it seemed like a fragile and unnecessarily complicated technique. But I have convinced myself that it’s both effective and less complex than I thought. (Matt Jockers, Travis Brown, Neil Fraistat, and Scott Weingart also deserve credit for convincing me to try it.)

This isn’t to say that we need to use probabilistic techniques for everything we do. LDA and its relatives are valuable exploratory methods, but I’m not sure how much value they will have as evidence. For one thing, they require you to make a series of judgment calls that deeply shape the results you get (from choosing stopwords, to the number of topics produced, to the scope of the collection). The resulting model ends up being tailored in difficult-to-explain ways by a researcher’s preferences. Simpler techniques, like corpus comparison, can answer a question more transparently and persuasively, if the question is already well-formed. (In this sense, I think Ben Schmidt is right to feel that topic modeling wouldn’t be particularly useful for the kinds of comparative questions he likes to pose.)

Moreover, probabilistic techniques have an unholy thirst for memory and processing time. You have to create several different variables for every single word in the corpus. The models I’ve been running, with roughly 2,000 volumes, are getting near the edge of what can be done on an average desktop machine, and commonly take a day. To go any further with this, I’m going to have to beg for computing time. That’s not a problem for me here at Urbana-Champaign (you may recall that we invented HAL), but it will become a problem for humanists at other kinds of institutions.

Probabilistic methods are also less robust than, say, vector-space methods. When I started running LDA, I immediately discovered noise in my collection that had not previously been a problem. Running headers at the tops of pages, in particular, left traces: until I took out those headers, topics were suspiciously sensitive to the titles of volumes. But LDA is sensitive to noise, after all, because it is sensitive to everything else! On the whole, if you’re just fishing for interesting patterns in a large collection of documents, I think probabilistic techniques are the way to go.

Where to go next
The standard implementation of LDA is the one in MALLET. I haven’t used it yet, because I wanted to build my own version, to make sure I understood everything clearly. But MALLET is better. If you want a few examples of complete topic models on collections of 18/19c volumes, I’ve put some models, with R scripts to load them, in my github folder.

If you want to understand the technique more deeply, the first thing to do is to read up on Bayesian statistics. In this post, I gloss over the Bayesian underpinnings of LDA because I think the implementation (using a strategy called Gibbs sampling, which is actually what I described above!) is intuitive enough without them. And this might be all you need! I doubt most humanists will need to go further. But if you do want to tinker with the algorithm, you’ll need to understand Bayesian probability.

David Blei invented LDA, and writes well, so if you want to understand why this technique has “Dirichlet” in its name, his works are the next things to read. I recommend his Introduction to Probabilistic Topic Models. It recently came out in Communications of the ACM, but I think you get a more readable version by going to his publication page (link above) and clicking the pdf link at the top of the page.

Probably the next place to go is “Rethinking LDA: Why Priors Matter,” a really thoughtful article by Hanna Wallach, David Mimno, and Andrew McCallum that explains the “hyperparameters” I glossed over in a more principled way.

Then there are a whole family of techniques related to LDA — Topics Over Time, Dynamic Topic Modeling, Hierarchical LDA, Pachinko Allocation — that one can explore rapidly enough by searching the web. In general, it’s a good idea to approach these skeptically. They all promise to do more than LDA does, but they also add additional assumptions to the model, and humanists are going to need to reflect carefully about which assumptions we actually want to make. I do think humanists will want to modify the LDA algorithm, but it’s probably something we’re going to have to do for ourselves; I’m not convinced that computer scientists understand our problems well enough to do this kind of fine-tuning.

相关文章:

1. COLING 2010前瞻——规则与统计共舞，语言随计算齐飞
2. CFP: The 7th Young Researchers' Roundtable on Spoken Dialogue Systems
3. 中文翻译技术沙龙第九次活动
4. 专业老友痛批立委《迷思》系列搅乱NLP秩序，立委固执己见
5. ACL 2012 Accepted Long Papers (ORAL)
6. ACL-IJCNLP 2009会议进行时一
7. ACL-IJCNLP 2009会议进行时二

通用型的语义网浏览器，支持WordNet，WikiNet，JA-WordNet。由于提供了统一的数据库接口，所以有其他形式的语义网络格式都比较容易支持，只要为其写一个数据库接口（适配）。以下是数据库（策略）选择菜单。

使用方法等细节就不在这里多说了，项目站点都有。希望使用之后多提反馈意见。当然也欢迎大家根据自己的需求进行后续开发。另外一点，由于中文的WordNet似乎缺少完全开放的（比如台湾中科院的需要去信索取），所以就没有做这方面的工作，请大家理解。

相关文章:

1. abcNLP: AB-Natural Chinese Languange Processing
2. 招生：Ph.D research assistant in machine learning and NLP
3. recruiting Ph.D. students
4. Itenyh版-用HMM做中文分词五：一个混合的分词器
5. LDC上免费的中文信息处理资源
6. Moses的一些新变化
7. 自然语言处理公司巡礼六：Metaweb
8. 语义网新闻一则：Google收购语义网公司Metaweb

       介绍一下分词使用的词典，在《中文分词入门之资源》有提到：

        Mandarin.dic                             分词词典，约40000条词汇

        对于一段文本，找出所有可能的切分结果叫做全切分，全切分可以保证切分结果集对正确切分结果100%的召回率，换句话说全切分中一定包含正确结果（在不包含未登录词的前提之下）。长度为n的句子，最大全切分数量可以达到2`(n-1)个，因此全切分计算量会随着句子长度增加急剧上升。举例，句子“研究生命起源”的全切分如下：

研/究/生/命

研/究/生命

研究/生/命

研究/生命

研究生/命

共有5个切分方案，其中倒数第二个是正确切分。下面讲一下我对句子进行全切分用的具体算法。

        如上图，考虑构建一颗多叉树，其中每一条从root到叶子节点的路径均为一种分词结果，所有root到叶子节点的路径就是全切分的结果。树的建立方法是使用的递归：

        对句子进行正向词典匹配，结果为：

        研            对剩余句子：究生命    进行词典匹配

        研究        对剩余句子：生命        进行词典匹配

        研究生    对剩余句子：命            进行词典匹配

        全切分结果准备就绪，下面的问题是如何从备选分词中选出最佳分词结果，因为备选结果只有有限的数量，因此可以使用枚举算法求最佳解：

                                                          ArgmaxC,O  P(C|O)

解法在第2集中已经提到，等价于求：

ArgmaxC,O  P(O|C)P(C)

       为了避免计算溢出（小数位数太多计算机无法表示），我们改为求：

                                                          ArgminC,O  -lnP(O|C) – lnP(C)

        对于句子“研究生命”，分词结果如下：

        研/究/生/命:44.24491284128293

        研/究/生命:37.12604972173189

        研究/生/命:33.59480382540995

        研究/生命:26.49050292705271

        研究生/命:32.15705471620734

        其中“研究/生命”拥有最低值，被选为最优解。再举一些有意思的分词结果：

        研究生/研究/生活

        结合/成/分子

        他/说/的/确实/在/理

        可以看出这种混合分词器能够灵活的掌握字符间的分和，消除一些歧义分词。

        下面是我对几种分词方法的实验结果，同时使用了ICTCLAS2011作为一个权威的分词效果比对，其中ICTCLAS2011使用的是它自带的词典，其他分词方法使用的词典是Mandarin.dic：

                                      每秒分词     P         R            F

普通最大词匹配          5482401      0.76   0.85      0.80

扩展的最大匹配          1118591      0.79   0.75      0.77

普通的Markov           1590173      0.76   0.72      0.74

混合的Markov           46818        0.73   0.84      0.78

ICTCLAS2011           942973       0.92   0.92     0.92

          可以看出ICTCLAS果然是名不虚传，相对于混合的Markov，ICTCLAS使用的是层叠式的HMM模型，可以很好的识别出未登录词；其次ICTCLAS使用了基于N-最短路径的切分，对计算效率也有很大的提高。

          PS：因为之前没有想过要分享分词的程序，所以写得比较混乱，最近也很忙，我会尽快整理发上来的。

相关文章:

1. Itenyh版-用HMM做中文分词四：A Pure-HMM 分词器
2. Itenyh版-用HMM做中文分词三：前向算法和Viterbi算法的开销
3. Itenyh版-用HMM做中文分词二：模型准备
4. Itenyh版-用HMM做中文分词一：序
5. 初学者报道(3) CRF 中文分词解码过程理解
6. HMM在自然语言处理中的应用一：词性标注5
7. HMM在自然语言处理中的应用一：词性标注3
8. HMM在自然语言处理中的应用一：词性标注2
9. MIT自然语言处理第四讲：标注（第四部分）
10. MIT自然语言处理第二讲：单词计数（第四部分）

Introduce

abcNLP

AB-Natural Chinese Languange Processing, The movement of C makes it ab-natural.

Thanks to censorship of internet, people oftern meet trouble to express themselves freely. Usually the SYSTEM will filter contents by (keywords) pattern matching. If we can make the language hard understood to SYSTEM, but not to human, we make the expression “Immune 2 Censorship” (at least, to some extent)!

Requirements

• develop: CJKLIB, sqlite3
• use: sqlite3

Usage

• for example :

   abc = abcChineseChar()
   for word in abc.getHxWords(u'茉莉花',  maxnum=5):
       print word

• output:

 苿峲芘
 苿峲芼
 苿萂芘
 炗峲芘
 苿峲芭

(~ use tempory db, need to refine ~)

• for example :
• output :
• ouput of 锦

   abc = abcChineseChar()
   for char in abc.getHxCharacters(u'锦'):
       print char

   jǐn
   钅帛
   仅
   尽
   錦
   馑

• ouput of 陈水扁:

   abc = abcChineseChar()
   for word in abc.getHxWords(u'陈水扁',  maxnum=15):
       print word

   <chén><shuǐ><biān>
   <阝东><shuǐ><biān>
   <chén><shuǐ>边
   <阝东><shuǐ>边
    尘<shuǐ><biān>
    臣<shuǐ><biān>
   <chén><shuǐ>便
   <chén><shuǐ>碥
    <chén><shuǐ>艑
   <chén>氵<biān>
    <阝东><shuǐ>便
    <阝东><shuǐ>碥
    <阝东><shuǐ>艑
    <阝东>氵<biān>
    尘<shuǐ>边

(~ use db version 1 ~)

Develope / Design

Methods to Immune 2 Censorship

Semantical Substitutes

Metaphor related methods. Thi is not used in this project.

Use variants of the Character

The variant of a character is alao a valid character. It can be seen as another shape (form) of original one. But some of forms are rare used nowdays.

 㒲 --> 財
 㒲 --> 才
 㒲 --> 财
 㒲 --> 纔
 㒷 --> 興
 㒷 --> 兴
 㓁 --> 网
 㓁 --> 網
 㓁 --> 罔

Use Character with same reading(Pinyin)

In the following list, value in brackets is score for the replacement. More small, more better.

 㐲 --> dài (0) * Pinyin is a special type
 㐲 --> 大 (3)
 㐲 --> 代 (5)
 㐲 --> 黱 (22)

 㐳 --> wù (0)
 㐳 --> 兀 (3)
 㐳 --> 乌 (4)
 㐳 --> 鼿 (17)

Split Character to two or three parts

After split character, each of its part can be further replaced with its similar character, which has ending mark of “1” in the following list.

 川 --> <丿丨丨> 0
 巧 --> <工丂> 0
 垛 --> <土朶> 1
 垜 --> <土朵> 1
 ⽻ --> <習習> 1
 ⾽ --> <镸三> 1
 䜌 --> <⺯讠⺯> 1
 丬 --> <氷丨> 1
 乢 --> <山隠> 1
 乣 --> <庅乚> 1
 乨 --> <枱乚> 1
 乩 --> <佔乚> 1
 ⽻ --> <习习> 0
 ⾽ --> <镸彡> 0
 丬 --> <冫丨> 0
 乢 --> <山乚> 0
 乣 --> <幺乚> 0
 乨 --> <台乚> 0
 乩 --> <占乚> 0
 亿 --> <亻乙> 0
 什 --> <亻十> 0
 仁 --> <亻二> 0
 亿 --> <人乙> 1
 什 --> <人十> 1
 仁 --> <人二> 1
 仂 --> <人力> 1
 仃 --> <人丁> 1
 仅 --> <人又> 1
 仆 --> <人卜> 1
 仇 --> <人九> 1

Choose a character looks like the origion. ( AI ?)

The score smaller is the better.

 ⺡ --> ⺍ (1)
 ⺡ --> 乊 (3)
 ⺡ --> 丬 (3)
 ⺡ --> 习 (4)
 ⺡ --> 乥 (8)
 ⺆ --> ⼌ (2)
 ⺆ --> ⼓ (3)
 ⺆ --> ⼏ (4)
 ⺆ --> 九 (4)
 丨 --> ⼁ (0)
 丨 --> ⼃ (2)
 丨 --> 丿 (2)
 丨 --> ⼅ (2)

This is the most important part of the project. After the module is refined, more examples will be added.

相关文章:

1. 初学者报到: 实现了一个最大匹配的分词算法
2. Moses基本框架
3. 初学者报道（2）：实现 1-gram分词算法
4. 基于字标注的中文分词方法
5. 安装Srilm的一点新变化
6. Beautiful Data-统计语言模型的应用三：分词8
7. MIT自然语言处理第四讲：标注（第二部分）
8. 单词也疯狂——漂亮的“单词云”
9. Beautiful Data-统计语言模型的应用三：分词6
10. MIT自然语言处理第四讲：标注（第一部分）