GNAP（GNAH's Not Another Programmer!）

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

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

导致我换博客的决定的原因是我希望能够方便的在博客里插入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黑板报上曾经提出，对于中文输入法的语言模型方案其实很多。但现实应用不得不牺牲智能化的算法而换取更小的资源占用，甚至连词库的规模都要小心控制。