GNAP（GNAH's Not Another Programmer!）

gnap.wordpress.com 一样的要翻墙。不过用户体验确实要胜过LJ一筹。这边的文章我会陆续的转移过去。

其实我对这里还是非常留恋的。虽然这个一直处于墙外，但是国内找到一个在多平台显示正常的博客还真不容易，因此一直坚持使用套翻墙在这里发文。

导致我换博客的决定的原因是我希望能够方便的在博客里插入Latex公式，就目前了解的只有Wordpress支持。很遗憾Wordpress也是墙外的。

以前一直不理解CFG解析中的Agenda的作用，今天在重构项目时才突然悟到：原来Agenda的存在是Dynamic Programming必不可少的一环。有了Agenda的存在，在其他的规则向Chart添加Edges之后，是可以以O(1)的复杂度处理Fundamental Rules的，而如果没有了Agenda，只考Chart本身做Memorilation的话，复杂度是O(n),如此一来整个解析过程需要O(n^4)的时间复杂度，而不是O(n^3)。NLTK中的CFG解析器，复杂度其实就是O(n^4)的。

原先的Chart Parsing实现是参照NLTK作的，最近由于想出了一套更一般化的用于和其他模块结合，所以需要对数据结构做一下改进。首先想到的是CKY算法中的结构。为了避免动用庞大的Boost库，所以先实现了一个矩阵。主要目的还是为了解析算法的方便，接口和语义大家是否认同就不重要了。

/**
 * Copyright (C)2008 George Ang (gnap.an AT gmail.com)
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.

 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.

 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#ifndef GMATRIX_H
#define GMATRIX_H

#include <vector>

template <typename _T>
class GMatrix
{
    public:
        GMatrix( size_t rows, size_t columns )
            : _rows( rows ), _columns( columns ), _storage( rows*columns, _T() )
        {

        }

        GMatrix( size_t rows, size_t columns, _T value )
            : _rows( rows ), _columns( columns ), _storage( rows*columns, value )
        {

        }
        ~GMatrix()
        {
            _storage.clear();
        }

        struct Row
        {
            Row( GMatrix& matrix, size_t row )
                : _matrix( matrix ), _row( row )
            {}

            GMatrix& _matrix;
            size_t _row;
            _T& operator [] ( size_t y )
            {
                return  _matrix._storage[ _row* _matrix.columns() + y ];
            }
        };

        Row operator [] ( size_t x )
        {
            return Row( *this, x );
        }

        size_t columns() { return _columns; }
        size_t rows() { return _rows; }

    protected:
        size_t _rows;
        size_t _columns;
        std::vector<_T> _storage;
};

#endif // GMATRIX_H

This Is My Life, Rated
Life:	7.9
Mind:	8.9
Body:	7.8
Spirit:	6.7
Friends/Family:	5
Love:	5.7
Finance:	8.1
Take the Rate My Life Quiz

最有说服力的结论还是实验得出的：

( S 1.95955e-05
    ( NP 'I' )
    ( VP 2.61274e-05
        ( VP 0.001008
            ( V 'saw' )
            ( NP 0.00168
                ( NP 'John' )
                ( PP 0.0336
                    ( P 'with' )
                    ( NP 0.056
                        ( Det 'a' )
                        ( N 'dog' ) ) ) ) )
        ( PP 0.0864
            ( P 'with' )
            ( NP 0.216
                ( Det 'my' )
                ( N 'cookie' ) ) ) ) )
( S 1.30637e-05
    ( NP 'I' )
    ( VP 1.74182e-05
        ( V 'saw' )
        ( NP 2.90304e-05
            ( NP 0.00168
                ( NP 'John' )
                ( PP 0.0336
                    ( P 'with' )
                    ( NP 0.056
                        ( Det 'a' )
                        ( N 'dog' ) ) ) )
            ( PP 0.0864
                ( P 'with' )
                ( NP 0.216
                    ( Det 'my' )
                    ( N 'cookie' ) ) ) ) ) )
( S 1.95955e-05
    ( NP 'I' )
    ( VP 2.61274e-05
        ( VP 0.15
            ( V 'saw' )
            ( NP 'John' ) )
        ( PP 0.000580608
            ( P 'with' )
            ( NP 0.00096768
                ( NP 0.056
                    ( Det 'a' )
                    ( N 'dog' ) )
                ( PP 0.0864
                    ( P 'with' )
                    ( NP 0.216
                        ( Det 'my' )
                        ( N 'cookie' ) ) ) ) ) ) )
( S 1.30637e-05
    ( NP 'I' )
    ( VP 1.74182e-05
        ( V 'saw' )
        ( NP 2.90304e-05
            ( NP 'John' )
            ( PP 0.000580608
                ( P 'with' )
                ( NP 0.00096768
                    ( NP 0.056
                        ( Det 'a' )
                        ( N 'dog' ) )
                    ( PP 0.0864
                        ( P 'with' )
                        ( NP 0.216
                            ( Det 'my' )
                            ( N 'cookie' ) ) ) ) ) ) ) )

以上的一个句子的两种歧义，由于条件概率的乘法公式，其NP和PP的组合歧义无法消除。
_________________________________________________________

下一步就是parser的词汇化。看了这么长时间的书，终于要实战了。

网络时代的一个热点词汇就是信息爆炸，象征着人类社会信息量的高速增长，已经达到了膨胀甚至爆炸的地步。信息爆炸一方面代表着由于通讯手段的进步，使得信息的传播速度，和获取信息的途径都有了进步，所以一个人在日常生活中所接受到的信息量比从前翻了N倍。个人产生的信息容易也更通过媒体向公众发布，也造成了服务商，政府和研究机构所要处理的信息量的猛增。另一方面，也以为着信息的冗余度也爆炸性的提高，同样的信息被复制无数此，同样的言语或观点被无数个人不断的重复。
有经验的网虫，往往擅长于“多任务”地在处理包括上网在内的各类工作。比如说一边开着完成任务所必备的程序，一边在浏览器上一目10行的处理各类帖子和搜索引擎的返回结果。并且利用网页加载和程序响应的间隔，进行切换。很显然这些人具备了应付互联网冗余信息的经验——大多数信息没有价值，掠过即可。即使是论坛上别人总价的经验，指南，也可以一眼带过。
比如，勉强合格的程序员，网络/系统工程师是怎样解决软件，系统/设备出现的某个问题的呢？百度＋Google，发现某个FAQ/HOWTO/帖子，然后看几眼问题分析甚至不看，直接跳过去看代码块……
这样解决问题起来又快又方便。对于一个刚刚工作的学生来说，往往被认为是聪明的，甚至认为是“牛”的。（当然，赞扬他的人如果不是处于客套奉承的话，那么很可能连搜索引擎都不会）
如果你真的相信别人对你夸奖的话，那么你就大错特错了。程序员需要做更有含量的项目，系统和网络工程师也终究要提升层次。你会渐渐的发现FAQ/HOWTO和帖子对你的价值越来越少了。这时候你通过什么来学习？程序员可能会读协议文档，技术论文。系统/网络工程师往往要读架构，方案设计之类的著作。一段文字的含量越高，意味着冗余度越低，通过上下文来推断理解的可能性就越小。最极端的就是形式化的语言表述的知识，你必须每个符号都仔细的理解，否则不可能正确无误领会到作者所要表达的意思。
这个时候问题来了。不少人已经适应了网络信息的处理习惯，很难安心下来读一些含量高的资料了。这个问题我最先发现的是在自己身上，我曾发现自己在读很多基础性的文章，比如教材和论文时，都喜欢一目十行的去看。最近才勉强的改正过来这种坏的习惯。
本来以为这类习惯只在我自己身上有，但是最近发现很多同行都有这个坏的习惯，甚至包括和我在同一项目组的同事。在我们对项目进行交流时，我发现同事会习惯性的断章取义，甚至只看了一两句话就匆忙的下了结论。结果是我不得不从新审视我加入这个项目之前同事所下的各类结论，包括从不同的书籍和材料中借鉴的观点等等。发现被曲解地方很多，很多本来可行的方案，都被鲁莽地否决了。幸运的是项目得以继续，遗憾的是我已经没办法劝说同事重拾对项目的信心了。这位同事现在已跳槽到了某门户互联网公司，希望他一路走好。
那么，怎样才能改正这种的阅读习惯呢？其实也非常简单，就是多看基础性的书籍或者有难度的技术资料/论文等。既在一目十行的处理大量冗余信息的同时，坚持通过精读来平衡自己的信息获取来源和质量。在认真阅读的同时，还要认真的思考，对获取的信息进行分析，划分成体系和类别。这样不但可以使自己掌握的知识系统化，也可以使得自己在读一些看似简单的文章时，不会草率的去断章取义。

按：什么是真正的耻辱？被侵略和被歧视，被征服？都不是，真正的耻辱是肤浅和它带来的恬不知耻！
肤浅意味着不思进取。长期以来我们陶醉在形而上学和迷信的边缘。满足于给任何一个问题套上一个模棱两可的答案。我们忘了打败我们的是坚船利炮，忘了我们的邻居在打个盹的时间内就超越了我们。我们尚未启蒙，就开始了愤青；我们尚未看全这个世界，却开始了排外；不知什么时候开始，我们居然抬起了高傲的头，向世人展示我们的肤浅……
其实李约瑟难题并不存在。科技同科学，乃至哲学之间有着本质的区别。中国从笛卡尔时期起就注定落后于西方列强。如果继续不思进取，满足于消耗资源换来的经济泡沫，屈辱的历史还会重演。
下面截一段罗兰的讲演（原始连接），这段话让我感受到了莫大的羞辱。今天我对八国联军进北京，日军侵华的历史已经麻木。对整天叫喊勿忘国耻的愤青嗤之以鼻。但是这段话却让我坐立不安，没有什么比突然发现自己肤浅更可怕的了：

美国的科学只存在未来，它没有今天和过去。在我这个位置上的人应该思考的问题是：我们必须要做些什么才能创造出我国的物理学，而不是把电报机、电灯和其它
的便利设施称之为科学。我并不是想低估所有这些东西的价值，世界的进步需要依靠它们，成功发明这些东西的人应该受到世界的尊重。但是，虽然一位厨师发明了
餐桌上的一道新鲜的美味佳肴，使世人在某种程度上享受到了口福，但是，我们并不会尊称他为化学家。但是，人们将应用科学与纯科学混为一谈并不是罕见之事，
特别是在美国的报纸上。一些卑微的美国人偷取过去伟大人物的思想，通过这些思想在日常生活中的应用让自己富裕，他们得到的赞美高于那些提出这些思想的伟大
原创者。如果这些原创者思想中有一些庸俗成分，他们早就可以做出成百种这样的应用。我时常被问及这样的问题：纯科学与应用科学究竟哪个对世界更重要。为了
应用科学，科学本身必须存在。假如我们停止科学的进步而只留意科学的应用，我们很快就会退化成中国人那样，多少代人以来他们(在科学上)都没有什么进步，
因为他们只满足于科学的应用，却从来没有追问过他们所做事情中的原理。这些原理就构成了纯科学。中国人知道火药的应用已经若干世纪，如果他们用正确的方法
探索其特殊应用的原理，他们就会在获得众多应用的同时发展出化学，甚至物理学。因为只满足于火药能爆炸的事实，而没有寻根问底，中国人已经远远落后于世界
的进步。我们现在只是将这个所有民族中最古老、人口最多的民族当成野蛮人。然而，我们的国家也正处于同样的状况。不过，我们可以做得更好，因为我们获得了
欧洲世界的科学，并将它们应用到生活的方方面面。我们就像接受从天空中落下的雨水那样理所应当地接过这些科学知识，既不问它们究竟从哪里来，也没有感激为
我们提供这些知识的伟大、无私的人们的恩情。就像天堂之雨一样，纯科学降临到我们的国家，让我们的国家更加伟大、富裕和强壮。

1、Ex falso quodlibet

The principle of explosion is the law of classical logic and a few other systems (e.g., intuitionistic logic)
according to which "anything follows from a contradiction" - i.e., once
you have asserted a contradiction, you can infer any proposition, or
its converse. In symbolic terms, the principle of explosion can be
expressed in the following way (where "" symbolizes the relation of logical consequence):

This can be read as, "If one claims something is both true () and not true (), one can logically derive any conclusion (ψ)."
The principle of explosion is also known as ex falso quodlibet, ex falso sequitur quodlibet (EFSQ for short), ex contradictione (sequitur) quodlibet (ECQ for short), and ex falso/contradictione (sequitur) (Latin: "from falsehood/contradiction (follows) anything", literally "... what pleases").

2、A fortiori

The Latin phrase argumentum a fortiori literally means one of the following:

• "from the stronger"
• "even more so"
• "with even stronger reason"

It denotes a proof of a claim by means of an already proved stronger
claim. For example, if it is forbidden to ride a bike with an extra
passenger, then it is also forbidden to ride a bike with two extra
passengers. Or, if one can lift a 100 lb object, then it follows that
one can lift a 50 lb object.

There are two types of the a fortiori argument:

• a maiore ad minus: from bigger to smaller
• a minore ad maius: from smaller to bigger

The a fortiori argument is most often used in order to reinforce a
claim, though sometimes also to incorrectly justify a claim taking it
as a premise (petitio principii).

3、Reductio ad absurdum

Reductio ad absurdum (Latin for "reduction to the absurd"), also known as an apagogical argument, reductio ad impossibile, or proof by contradiction, is a type of logical argument
where one assumes a claim for the sake of argument and derives an
absurd or ridiculous outcome, and then concludes that the original
claim must have been wrong as it led to an absurd result.

It makes use of the law of non-contradiction — a statement cannot be both true and false. In some cases it may also make use of the law of excluded middle — a statement must be either true or false. The phrase is traceable back to the Greek ἡ εἰς ἄτοπον ἀπαγωγή (hē eis átopon apagōgḗ), meaning "reduction to the absurd", often used by Aristotle.

4、Ad hominem

An ad hominem argument, also known as argumentum ad hominem (Latin: "argument to the man", "argument against the man") consists of replying to an argument or factual claim by attacking or appealing to a characteristic or belief of the person making the argument or claim, rather than by addressing the substance of the argument or producing evidence against the claim. The process of proving or disproving the claim is thereby subverted, and the argumentum ad hominem works to change the subject.

"Probabilistic grammars start where formal language
theory stops. Ambiguity resolution, robustness, efficiency,
learning/adaption and estimation from data is the starting point for
probabilistic grammars."

这是我从一段概率语法和面向数据的解析的课程介绍中看到的：
http://www.snlp.de/prescher/teaching/2004/ProbabilisticGrammars/

想起以前拜读刘挺老师的博文中的一段：

（3）统计方法的弱点

两位网友多提到计算所的机器翻译系统从规则改为统计后，取得了很大的提高，因此感到规则方法的无效，语言学研究者的无用。但据我所知，也有反例，比如东芝
中国研发中心的王海峰博士，他在东芝主持的机器翻译研究仍是以规则为基础的，他们一直有数名语言学背景的员工在机器翻译第一线工作，今年又新增两位从海外
归来的语言学研究人员。东芝比较低调，但他们的翻译系统是非常出色的，在国际博览会上受到国际学者的充分肯定，在ACL和MTSummit上连续发表文
章。现在的潮流是统计占有优势，因此做基于规则的方法不容易发表论文，但这并不意味着规则方法已经过时。规则是人的智慧的结晶，深刻而灵活，自有它存在的
价值。

短期内评测的成绩不能够决定未来的方向，凡事走到一个极端的时候就会回归了，统计的方法有一些明显的弱点，举例而言，在10万字的语料中你看到了1000
个不同的词，那么当语料扩大一倍，即达到20万字的时候，你可能看到了1200个词，语料增加100%，而新的语言现象可能只增加了20%，当语料庞大到
一定程度，再翻倍增长已经很难，即使翻倍增长，新的语言现象可能已经降到只增加1%以下，油水越来越少了。语言学的作用就是对语言的处理从统计方法所利用
的字词表层推向语法语义深层，每深入一层，就能够大幅度地对语言实例进行归纳，也就能够大幅度地较少对语料库规模和计算规模的无节制的依赖。台湾苏克毅老
师是最早开始从事统计自然语言处理的国际知名学者，但他在演讲中却用一个生动的比喻指出盲目信仰统计方法的可笑之处，他认为停留在语言表层的统计方式方法
是在爬树，尽管目前爬得很高，但机器翻译的目标是登月，完全依靠统计是无法实现机器翻译的目标的。

统计的方法还有一个要穴就是研究者在统计方法面前比较被动，用统计方法作出一套系统，输入一个句子进行测试，如果效果不佳，即使是开发者本人也无法解释其
中的原因，因为所有的参数都是自动计算出来的，人可控的余地很小，只好更换或追加语料库，或者调整统计方法，即使如此能不能修正原先的错误也很难说。于
是，就有人开始打补丁，也就是在统计方法做出结果后，再用一些针对性的规则把一些明显的错误修补一下，这只能说是一种权宜之计，如果换了统计方法，错误类
型也会改变，补丁程序也要跟着换，非常麻烦。

之前在读了这段博文后和同事产生过分歧，同事认为这说明统计模型可以抛弃了。应当转基于规则的语言模型的研究。个人认为这是对刘老师的意见的误解。其关键之处在于文章开头引用的那句话。统计模型从来都不是用来代替其他的语言模型的，而是弥补（个人不清楚机器翻译领域是怎样的情况，但是在句法分析这块，从90s开始的确是坚持规则和统计模型并用的方法进行句法分析器的研究的。而且越精确的句法分析器，其规则模型和统计模型都越趋于复杂。

概率是研究随机事件发生和分布规律的数学工具。语言可以被用来基于概率进行研究。是建立在一系列的假设基础上的。比如，我们认为抛硬币正反面的出现是随机事件，给定一个句子中的前一个词，后一个词是什么也是随机的事件。但如果我们为硬币加入了结构是否均匀，空气阻力，花纹不同而影响的运动状态等等模型，硬币的面就不再是一个随机事件。语言模型也是一样，当我们对其系统的构成不够了解时，可以完全借助概率来研究其分布。但是当我们对系统有一定了解时，就要利用了解的系统的结构，将问题进行细化，在子问题中使用统计模型。比如现代句法分析的统计模型，是建立在上下文无关语法，X-bar理论等一系列语言规律的基础之上的。新的语言规律不断的被发现，模型就会不断的被细化。统计计算的复杂度也会随之降低。

另一个使用统计模型的原因是计算能力和数据规模的限制。很多复杂的规则语言模型都因为需要消耗大量的资源，而无法摆脱实验室走向应用。在吴军的Google黑板报上曾经提出，对于中文输入法的语言模型方案其实很多。但现实应用不得不牺牲智能化的算法而换取更小的资源占用，甚至连词库的规模都要小心控制。

前两天看资料有点得意忘形，以至于开始出现学院派的作风。然而单位毕竟是实业性的公司。昨晚吃饭时头提醒了一下，睡前想了想的确如此。不能为了对思维“层次”的追逐而放弃产品实践。因此今天开始尝试将零星的算法转化为代码。在实践的前提下完善自己的思维。

给定一个概率分布D，假定其概率密度函数（连续分布）或概率聚集函数（离散分布）为f_D，以及一个分布参数θ，我们可以从这个分布中抽出一个具有n个值的采样，通过利用f_D，我们就能计算出其概率:

但是，我们可能不知道θ的值，尽管我们知道这些采样数据来自于分布D。那么我们如何才能估计出θ呢? 一个自然的想法是从这个分布中抽出一个具有n个值的采样X₁,X₂,...,X_n，然后用这些采样数据来估计θ.

一旦我们获得, 我们就能从中找到一个关于θ的估计。最大似然估计会寻找关于 θ的最可能的值（即，在所有可能的θ取值中，寻找一个值使这个采样的“可能性”最大化）。这种方法正好同一些其他的估计方法不同，如θ的非偏估计，非偏估计未必会输出一个最可能的值，而是会输出一个既不高估也不低估的θ值。

要在数学上实现最大似然估计法，我们首先要定义可能性:

并且在θ的所有取值上，使这个函数最大化。这个使可能性最大的值即被称为θ的最大似然估计。

最近在看［Collins 99］，290多页的电子书，几天才看了一半。满脑子的统计学公式和语言成分标记。觉得有必要把看论文和干其他事穿插一下，但是又找不到合适的事（走神看看新闻和youtube除外）。

看来有必要学习下有关GTD的知识了，暂时不准备买书，等下周发了薪水买个PSP在地铁上看电子书吧！囧rz

实践中很多问题的解决过程存在着某些共性，因此可以总结出一个过程或者方法来适用于所有相同类的问题，称之为一般化。维基百科上的定义为：

广义化（英文：Generalize），又称一般化、通常化、普遍化、概化，是指将事物的定义进行修改或者补充以使其适用于更加大的范围。

一个将事物广义化的简单例子是归类。例如：将“大雁”广义化（归类）之后是“鸟类”，将“鸟类”广义化（归类）之后是“动物”。

当然，这样的定义并不严谨。

从逻辑学的角度来定义，只有满足下面两个条件才能说，“A 是广义化之后的 B”，或者“ A 是广义上的 B”。条件如下：

1. 任何一个 B 概念的实例也是 A 概念的实例；并且
2. A 概念的实例并不一定是 B 概念的实例

就之前的例子，因为每只“大雁”（B）都是“鸟”（A），但是“鸟类”并不一定是“大雁”，所以我们可以说：“鸟类”是广义上的“大雁”。

以上是对一般化的更加“一般化“的定义。维基的定义比较偏重概念和类别。而个人的定义主要是方法和过程。

在大学时，自己曾经向一位同学解释C语言的struct时引用了以太网数据包的构造作为例子，这样的举例在多数人看来，包括我自己看来是不合适的。因为很可能由于引入了新的知识而导致同学对问题的理解更加的混乱，奇特的是这个同学居然听懂了，而是一脸恍然大悟的样子。

后来发现这位同学有个特点是几乎看所有的编程开发书籍都会产生类似的问题，每次都提一些很古怪的问题，要你举具体的应用，才能明白书上的概念是怎么回事。我当时对他说你在思考一个问题时，需要忽略其他的无关的问题，尤其是不和现在的问题在同一层次上的问题。比如在学习语言的时候只学习它的语义，而不去考虑汇编级别的跳转。那个时候自己还没有系统的对方法进行总结。只是隐约的觉得同学的思维缺少分层能力，不断的提醒他进行层次化的思考。现在看来他首要缺少的是对问题的一般化的概括能力。

一般化的能力在解决实际问题显得非常重要。尤其是对于计算机从业的人员，一般化往往是正确将实际问题转化为计算模型的基础，如果不能正确的概括问题的一般共性，主要步骤，就不能建立出正确的模型。在处理研究性的项目时，就会变得盲目，把时间和精力浪费在不必要的工作上。以个人目前从事的NLP工作为例。概率化的ML问题可以分解为3个子问题：定义模型结构，定义估计方法和设计搜索算法。以前刚刚接触这方面时对此不够了解，认为Chart Parsing就是句法解析的“最好的算法”。现在看来Chart Parsing只是一个搜索算法，一个好的PCFG还需要更加复杂的建模方法，既模型结构和估算方法。如Collins99中定义的head-driven模型和Stanford Parser中的Dependency Grammar等等。另一个更简单的例子是X-bar理论中的中心词，complements和adjuncts。是对语言短语构成所组成的一般化规律。此外，还有对句法解析的一般化定义:<S, T>有序对，中心词和修饰语的二元关系，我之前的博文转的“动态规划”等等。都是语言规律的一般化总结。语言的一般化规律，是用计算机处理自然语言的理论基础。也是计算机语言学和偏重研究个案的传统语言学的不同。

问题的一般化并不是凭空完成的。它需要对问题有足够的了解。通常问题的一般化定义需要经过几次修正，才能得到一个正确的模型。一般化也是系统化和层次化的基础，总结出问题的一般性，才能对问题的步骤，不同的方法进行系统性的分类和层次划分。如前面举的大学同学，其实也是一般化和层次化能力同时缺乏的例子。

问题的一般化也要伴随着具体化，才能最终真正的解决实际问题。一般化只是帮助建立一套理论性的知识体系或者是处理过程。在这个体系上/过程中，需要逐个的解决很多实际问题。一般化和系统化层次化，是指告诉你要解决哪些子问题，可以忽略哪些子问题。对于要解决的子问题我们还是要具体的解决。因此，我们一方面要提高宏观抽象的能力，一方面还要深究具体的技术。只有同时掌握两方面的能力，才能做一个优秀的研发人员。

精确度和完全度是两种应用广泛的衡量信息摘取结果质量的标准。精确度代表着结果的准确度，而完全度则用来衡量结果的覆盖程度。

在信息获取工作中，精确度的定义为：一次搜索中相关文档数除以总的获取的文档数。完全度的定义为一次搜索中相关文档数除以总的现实存在的相关文档数。前者代表着返回的结果中有多少想要的东西，后者代表自己想要的东西被返回了多少。两个数值综合起来可以评估查询系统的表现。

通常情况下，对两个数值并非是相互独立的进行来研究的。而是以一个数值处以固定级别时另一个数值来进行比较的。比如说完全度为0.75时的精确度。或者是把两个数值结合成一个，如F-measure的F1特例:
F=2*(precission*recall)/(precision+recall)
Presicion,Recall和F1在对概率Parser的评估中经常出现，如评估英语的Parseval，在当前的英文NLP项目中应用的非常普遍。中文的Parser表现评估还没有类似的标准，比较可惜。

按：本来想直接翻译wikipedia上的条目。但是找到了这篇翻译现成的博闻，就偷个懒转过来了。

动态规划是一种数学规划方法，用于解决具有overlapping subproblems
和 optimal substructure属性的问题，能比天真的算法节省很多时间。

首先讲一下什么是overlapping
subproblems。它是指可以被分解成若干次重用的子问题的那类问题。例如Fibonacci
sequence（斐波纳契数列，每个数等于前两个数的和，其中fib(0) =
1且fib(1) = 1）。对于overlapping
subproblems，天真的算法可能重复计算某些子问题，浪费时间。而dynamic
programming使用memoization来解决这个问题，即把计算的结果保存起来，需要的时候取出使用即可。

那么什么是optimal
substructure呢？如果可以从其子问题的最优解构造出该问题的最优解，则该问题具有optimal
substructure属性。据有optimal
substructure的问题适合用动态规划和贪心算法求解。例子是寻找一个图中两个顶点间的最短路径，先找到从开始点的所有邻居到目标的最短路径（递归地使用这一过程），然后选择整体的最短路径。


通常我们可以用三个步骤对具有optimal
substructure属性的问题求解：

1. 把问题分解成subproblems。
2. 递归地使用这三个步骤求出这些问题的最优解。
3. 使用局部最优解构造整体最优解。

综上，dynamic programming使用了三种技术：overlapping
subproblems, optimal substructure and memoization.

动态规划通常采取两种方法: top-down
approach(合并了recursion和memoization)和bottom-up
approach(性能稍好，但很难直观地列出所有子问题).

dynamic programming是由Richard
Bellman在1940s提出的。bellman的主要贡献是Bellman equation，aka,
dynamic programming equation.是dynamic
programming最优性的必要条件。

附：贪心算法

贪心算法的特点：每一阶段都追求局部最优，希望最终达到全局最优。


贪心算法能对具有两种属性的问题工作的很好：greedy choice
property和optimal substructure.

optimal substructure在上面已经介绍过，greedy choice
property是指在做每一步的选择时不需要和以前的选择一起考虑。

贪心算法不会回溯以前的选择，这是和动态规划的主要不同。

最近分析了几个多语言的句法分析项目的实现。澄清了很多以前片面性的认识。

首先，一个CFG的句法分析器，其内存占用是句子的长度和语法的复杂程度共同决定的。也就是说，实用化的分析器很可能会有相当高的内存占用。在基于Chart的实现中，一次分析的资源的是以分析Edge的数量来衡量的。由于要通过记住每一条边来存储以往的计算过程（对于PCFG，则还要回溯计算当前路径的score），所以分配的内存要保留到整个句子的分析结束。

其次，POS tagging时的歧义无法通过CFG来理想的消除。尤其是对于一个庞大的句法来说，总能通过已有的Production来将tag好的序列判断为合法。因此必须必须引入概率来对每个分析结果进行计算（所谓的nbest parsing)。

第三，消歧义的过程是发掘更多的约束的过程。CFG是通过语法规则进行约束，PCFG进一步引入概率进行约束。目前的概率多数是针对Production的概率进行的，而不是具体的词汇之间的概率。可以说约束越具体，歧义的消除的可能性越大。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
跑题谈一下NLP研究中的方法论。个人一下主张科研工作中是避免引入本体论的，作为唯物主义中的“唯心”部分，形而上学无法提供严密的自然哲学逻辑。一来本体论会带来无法解决的问题，二来单方面所提供的解决问题的回答总是无法证伪的。个人赞同很多科研方法的启示来源于哲学思想，但是不是所有的哲学思想都能拿来指导科研。在这个区分过程中，分类的能力显得至关重要。

另外一点和同事的分歧是关于中英文的差别。同事认为汉语和英语差异巨大，必须抛弃现有的“专属于”英文的研究体系。而个人认为现有的NLP的研究成果来扎根于数学理论，而并非担心的拘泥于一门语言。因此其模型一样可以用于汉语的分析。对于汉语的复杂度和信息熵值高等特征，的确会使中文处理面临更多的挑战，但是并不会影响现有的数学理论在中文处理中的应用。

A hidden Markov model (HMM) is a triple (,A,B).

		the vector of the initial state probabilities;
		the state transition matrix;
		the confusion matrix;

Each probability in the state transition matrix and in the
confusion matrix is time independent - that is, the matrices do
not change in time as the system evolves. In practice, this is
one of the most unrealistic assumptions of Markov models about
real processes.

Once a system can be described as a HMM, three problems can be
solved. The first two are pattern recognition problems: Finding
the probability of an observed sequence given a HMM
(evaluation); and finding the sequence of hidden states that
most probably generated an observed sequence (decoding). The
third problem is generating a HMM given a sequence of
observations (learning).

概率一直是经验主义的NLP研究人员最喜欢的工具。从POS到语义分析，概率的应用几乎无处不在。今天参考了两个将Chart改写成HMM，进行Viterbi分析的项目。個人觉得这意味着找到了一种从训练到解析的一条龙的解析方案。

今天为止正好上班一个月，也是加入这个项目一个月。这个月参阅了很多的资料。有些是公司购买的。有些是检索到的论文。觉得一直在成长，对Semantic Parsing这块的了解逐渐深入了。一个月来一个比较有意思的发现是多次发现参考项目＋论文获得太的信息在一本概括性的书上都有介绍。可以说发生了几次绕了一圈后发现提示就在最明显的地方一样。也许人的学习过程就是这样子的，只有最终发现应用的意义才会领会当初的学习知识有什么用途。反过来看也说明理论学习要和实践相结合，才能获得最大的动力和最佳的效果。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
跑两个题：
1、最近萌生了想买本《算法导论》和一本离散数学教材的想法。和头交流头没有同意，看来要自己掏腰包了；
2、最近有很多故人要来北京，非常高兴。

可能切换到QT开发环境下的人都会遇到过这个问题。QT提供了一套类似STL的容器供开发人员使用。多数情况下用法是尊重STL用户的习惯的，然而在当遇到性能和迭代器的有效性的时候，就要注意一些细小的差异了。如果忽视这些差异，不仅无法写出高效的程序，还会使程序遇到意想不到的问题。

比如QList，直觉就会觉得它是一个链表，可以他的存储方式却和std::list非常的不一样：

struct Q_CORE_EXPORT QListData {
struct Data {
QBasicAtomic ref;
int alloc, begin, end;
uint sharable : 1;
void *array[1];
};
。。。
Data *d;
。。。
inline int size() const { return d->end - d->begin; }
inline bool isEmpty() const { return d->end == d->begin; }
inline void **at(int i) const { return d->array + d->begin + i; }
inline void **begin() const { return d->array + d->begin; }
inline void **end() const { return d->array + d->end; }
};

可以看出其访问指针的存储是由一段连续的内存空间组成的，而不同元素之间的空间却不连续。这样保证了类似std::vector的下标访问，又不至于像Vector那样在元素增多时随机插入的性能下降得太多。但是QList依然无法获得稳定的插入和删除复杂度，也无法保证迭代器在插入和删除后的有效性。

而QLinkedList,则是一个和std::list类似的双向链表。从其实现可以看出：
template <typename T>
struct QLinkedListNode
{
inline QLinkedListNode(const T &arg): t(arg) { }
QLinkedListNode *n, *p;
T t;
};

其结构保存了前后相邻元素的指针。这样既可以获得稳定的元素随机插入性能，由可以保证在增删元素之后已赋值的迭代器依然有效。因此，STL的程序员应当使用QLinkedList来替代std::list.而对于没有连续内存操作，只希望下标随机访问的应当使用QList.