分类目录归档:技术分享

贝叶斯分类器

这是3月25日我在TM组机器学习讨论会上的分享。

Content


  1. 贝叶斯决策论
  2. 朴素贝叶斯分类器
  3. 半朴素贝叶斯分类器
  4. 贝叶斯网络

1. 贝叶斯决策论


贝叶斯决策论是一种基于概率的决策理论。当所有相关的概率都已知的理想情况下,贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优的类别标记。

Example

哈工大与哈师大的同学举办大型联♂谊♀会,两个学校分别有500人参与。在联谊会上随机找到一个同学,请猜测他是那个学校的学生?

如果我们一点额外信息都不知道的话,只能随机猜测给出答案。如果我们能够提前知道一点点信息的话,就能够更大程度地猜中正确答案。比如,性别信息:

 

如此的话,假若这个同学是男生,我们肯定会猜测他是哈工大的学生。而从贝叶斯决策论的角度来看,我们需要比较以下两个概率大小:

  • P(工大学生=是 | 性别 = X)
  • P(师大学生=是 | 性别 = X)

上述两个概率被称作后验概率。后验概率往往难以直接获得,我们需要采用一定的手段进行计算。一些算法采用直接对后验概率进行建模的方法,例如SVM、决策树等,这些模型称为判别式模型。而先对联合概率进行建模、进而计算后验概率的模型,称为生成式模型

\(P(c|\boldsymbol{x})=\frac{P(\boldsymbol{x}, c)}{P(\boldsymbol{x})}=\frac{P(c)P(\boldsymbol{x}|c)}{P(\boldsymbol{x})}\)

由此可以计算得到,P(工大学生=是 | 性别 = 男)为4/5,P(师大学生=是 | 性别 = 男)为1/5.

在上面的例子中,我们直接使用了后验概率对类别进行估计。实际问题中,如果将某一类估计错误的代价比较大的话,可以选择在后验概率前乘以一个系数,变为期望损失。分类也从最小化分类错误率变为最小化期望损失。

在上面的式子中,\(P(c)\)代表的是类先验概率。在样本足够大的情况下,直接使用频率即可作为这一概率;\(P(\boldsymbol{x}|c)\)叫做类条件概率,它跟属性x的联合概率有关。上面的例子中,x只有一维,而在实际问题中,往往会选择很多个Feature。此时他们的联合概率就变得难以计算,因此我们需要一些手段对它们进行估计。

继续阅读

深度学习简介及单词的向量化表示

Content

  • 深度学习简介
  • NLP与深度学习
  • 单词的向量化表示

1. 深度学习简介

首先应当明确的是,深度学习是机器学习中的一个领域。然而与传统机器学习所不同的是,传统的机器学习的重点在于特征的设计。在设计过特征之后,就变成了研究如何调整权重、优化参数来得到一个最优的结果。

图片1

然而特征设计所涉及的知识、经验的储备往往只有博士级别的研究人员才能够得心应手,而且特征设计的优劣往往直接影响最终的分类结果。与之相反,深度学习应用的是多层特征学习,其中特征学习指的是计算机能够自动地学习到特征的表示,这就解决了手工选择特征局限性较大的问题。深度学习提供了一个近乎统一的框架。它够表达各种信息,能够自动学习,并且非常灵活。这个框架也同样支持监督学习与非监督学习两种学习方式。

除此之外,深度学习还具备以下特点:

  1. 数据量增大时,深度学习的获益更多;
  2. 能够利用多核CPU、GPU加速
  3. 不断涌出的新模型、新算法
  4. 最终性能的提升

2. NLP与深度学习

事实上,在NLP领域,深度学习已经开始展现它的威力了。在应用方面,机器翻译、情感分析、问答系统等都依靠深度学习取得了重大的进步;而在NLP的各个层次上,例如语音识别、形态分析、句法分析、语义解释等,深度学习也发挥了重要的作用。接下来

选区_006

语音

在语音层面,传统的表示形式采用了表格的形式来表示每一个音素。而在深度学习中,将每一个音素表示为向量。

字形

对于一个单词来说,传统的表示形式将词根、前缀和后缀分开表示,例如un-interest-ed。而在深度学习中,往往将一个词素表示为一个向量。

图片3

句法

传统的表示方法会显示地标注出每一个短语的具体类别,例如VP、NP等。而在深度学习中,会将一个词或短语均表示为向量。

语义

lambda演算是一种在语义层面的传统表示方式。例如,将likes视作接受两个参数的函数,每一次合并都相当于柯里化的过程:

图片4

而在深度学习中,仍然将语义表示为向量的合并。

可以看出,向量形式是NLP中所有层次的表达形式。


3. 文本的向量化表示

意义

语言文字或一些符号具备一定的意义。例如,苹果和apple所指代的意义相同。而对于一个外星人来讲,■△▲〓※↓↑〓↓说不定就代表“苹果”。因此,如果想要让计算机理解这一层意义,那么它也需要一种表示;反之,如果我们认为某种表示是计算机所理解的“苹果”,那么即便我们无法阅读(例如■△▲〓※↓↑〓↓),这也是在合理范围之中的。

意义在计算机中的表示

一种表达意义的方式是利用同义词和上位词。例如,熊猫属于动物一类,我们可以用“动物”来表达熊猫的某些方面的意义。再比如,good和well有时意义相近,那么我们可以用well来代表good的某些方面的意义。

然而,这样的表示的问题在于:

  • 缺乏语义差别的信息
  • 难以适应新词
  • 主观
  • 需要人工标注
  • 相似度难以计算

究其根本原因,在于这种方式将单词视为了一种原子符号。或者说,如果在向量空间中对其进行表示的话,我们把它叫做one-hot:

选区_007

one-hot的问题在于,无法表示单词之间的意义相近的关系。例如,hotel和motel两个词,如果利用one-hot形式来表示的话:

hotel  = [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]

motel = [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

我们无法使用向量运算来获得它们之间意义上的相似度。

You shall know a word by the company it keeps.

–J.R.Firth

J.R.Firth是50年代著名的语言学家,他的这句话被誉为当代NLP领域中最成功的思想之一。对于一个单词的意义,较好的方式是考虑它的上下文。

图片5

而这个“上下文”,则有不同的范围可以选择:其一是将整个文档作为上下文,另一种是选择一个较小的固定的窗口作为上下文。对于“全文档共现”来说,单词向量的维数是文档的个数,如果这一单词在某一篇文档中出现,则该维置1。全文档共现的方式能够挖掘单词的隐含语义。例如,对于“足球”和“教练”来说,它们很有可能在多篇文档中共同出现,则它们的向量也有多维同为1;如果取and的话,就可以获得它们之间的相似程度。

而对于基于窗口的共现来说,其能够同时获得语法与语义的信息。下面我们通过一个例子来看一下基于窗口共现方式的词向量学习过程。

我们选取三句话:

  • I like deep learning.
  • I like NLP.
  • I enjoy flying.

窗口大小取为1,即向前看1一个词、向后看1个词,窗口中一共3个词。通过对共现次数的计数,可以得到以下的矩阵:

图片6

我们可以发现,这个矩阵有这样的几个问题。一是维度过高,它与整个vocabulary相关,因此维度也会随着词汇量的增加而增加;而是矩阵十分稀疏,这将导致难以训练出有效的模型。我们可以通过两种方法来降低词向量的维度:一是用数学方法对这个矩阵进行降维(如SVD奇异值分解);或是不通过这个矩阵,而是直接估计出词向量。

SVD奇异值分解

通过SVD分解,可以将一个mxn的矩阵分解为3个维度分别为rxn、rxr、mxr的矩阵。我们所需要的词向量信息都存储在第一个rxn的矩阵当中。第二个rxr的矩阵是一个对角矩阵,通过调整对角线上的数值可以对第一个rxn矩阵的列进行排序,从而让比较重要的维排在前面。

图片7

使用numpy可以很容易地进行SVD分解计算:

U, s, Vh = numpy.linalg.svd(X, full_matrices=False)

下图是取前两维生成的plot:

图片1

可以看出,相对相近的单词距离更近。

使用SVD方法时,可以进行一些hack,例如通过阈值或过滤的方法对停用词进行处理、添加权重、使用Pearson相关系数代替count等。

图片2

然而,SVD奇异值分解有一些弊端。例如,计算复杂度与m×n相关、难以加入新的单词等。最后,它与深度学习的审美不同:深度学习通常追求从某一个例子中学习一些东西然后再移动到下一个,而SVD方法却需要对所有语料进行整体地处理。

直接学习低维向量

除了利用SVD方法把高维矩阵降维处理外,还可以直接学习低维向量。例如word2vec,他直接预测每个单词相邻单词的概率。除了word2vec,2014年出现了Glove: Global Vectors for Word Representation. Pennington et al. (2014)。它们可以向语料库中不断添加新词。

word2vec的核心思想是:当窗口长度为c时,预测与中心词共现的单词。其目标函数为:

图片3

其中p为

图片4

然而当单词量增大后,其计算将会变得缓慢。因此,我们可以通过采取采样、简化概率函数等方式进行近似。

  基于频数的方法 直接预测方法
优势 训练速度快充分利用了统计信息

性能更好可以获得到比单词相似性更复杂的信息

劣势 主要用来获得单词之间的相似度当频数较少时,获得的比重不合适

与语料库的大小有关没有利用统计信息

 

Reference

http://cs224d.stanford.edu/

Jump Out of C++:面向对象编程探索(二)

这次是这一个系列技术分享的第二部分,主要介绍的是C++对象模型。这里所讲的对象模型,是指如何在内存中(空间上)表达对象的性质和特征,以及如何在运行时(时间上)提供完成面向对象系统中的必要操作的能力。

Table of Content


C++并不是天生地庞大而迟缓

—— Stanley B. Lippman

  1. 概述
  2. 对象的内存布局
  3. 运行期环境

1. 概述


对于传统的C语言程序来讲,数据与算法是分离的:

struct Circle  
{ 
int x, y;  
int radius;  
}; 

Circle MakeCircle(int x, int y, int radius) { //.... } void DrawCircle(Circle c) { //.... }  

在C++中,将这样的与传统C语言结构体内存布局兼容的对象叫做Plain Old Data(POD)。

此外,我们还可以将数据和算法整合在一起:

class Circle  
{ 
public:  
    Circle(int x, int y, int radius); 
    void Draw(); 
private:  
    int x, y; 
    int radius; 
};

对于这样的代码,在时空上是否增加了什么负担?同时,C++还支持继承、多重继承等很多机制,它们呢?

class Point {  
public:  
    Point(int x, int y); 
private:  
    int x, y; 
}; 
class Circle : public Point { //... };  

我们先从最朴素的模型开始,看一看如何来安排对象的内存空间:

  • 简单对象模型

在简单对象模型中,对象中只存储指向成员(包括数据成员和方法成员)的指针,所有操作均通过指针索引来完成。

  • (双)表格驱动模型

双表格驱动模型是指在对象中仅存储两个指针:一个指向数据成员table的指针,一个指向方法成员table的指针。这种模型的优点在于所有对象的内存空间占用及内存布局均完全一致。早期的某款C++编译器采用了这一种模型。

以上两种模型都是可以在一定程度上满足需求的,但并未被大多数编译器所采用。目前主流的模型如下:

  • 非静态数据存放于对象内部
  • 静态数据、非virtual函数存放于对象之外
  • 每一个class至少有一张虚函数表
  • 每一个object中包含一个指向该表的指针

1

本文将探讨在单继承、多继承、虚拟继承下C++对象模型是如何应对的。

2. 对象的内存布局


 2.1 类

对于如下的代码来说:

class Circle  
{ 
public:  
    Circle(int x, int y, int radius); 
    void Draw(); 
    static void Print(); 
private:  
    int x, y; 
    int radius; 
    static int count;
};

根据前述的对象模型,其其布局与在C语言中使用结构体时是一致的:

circle

同时C++标准保证,在同一个权限声明块中(即同一个public、protected或private块中),后声明的成员在内存中位于高地址(更靠后)。但并没有规定其一定紧邻,其间可以插入其他编译器所需的数据。

 2.2 不包含虚函数的单继承

而对于单继承来说:

class Point  
{ 
public:  
    Point(int x, int y); 
protected:  
    int x, y; 
}; 
class Circle : public Point { protected: int radius; };  

其内存布局如下:

绘图7

可以看出,其占用内存的成本并没有增加。然而是否一定不会增加呢?如果我们有如下代码:

class Point {  
public:  
    //... 
protected:  
    int x, y; 
    char c1, c2; 
}; 
class Circle : public Point {  
public:  
//... 
protected:  
    char c3, c4; 
    int radius; 
};

此时的内存布局将为:

绘图7_

由于需要对其内存,编译器很可能会插入padding字节。这时,继承的内存占用将会比数据全部在同一个类中的时候大。不过,我们是否可以取消掉padding呢?

答案自然是否定的。取消padding后,Point对象和Circle对象中Point部分在内存中占用的大小将会不同,此时如果存在以下代码:

void some_func(Point* point) { Point a; *point = a; }  

由于Circle和Point存在继承关系,我们不能在编译期确定代码中point的真实类型是什么。如果point一旦为Circle类型,那么在执行到*point=a这一句代码时,将会多覆盖两个字节的内存,即c3和c4将被内容不确定的内存覆盖。

2.3 包含虚函数的单继承

对于包含虚函数的单继承来说,其内存中将会增加一个指向虚表的指针。

class Point {  
public:  
    virtual void Print(); 
protected:  
    int x, y; 
}; 
class Circle {  
public:  
    virtual void Print();
protected:  
   int radius; 
};

circle<em>with</em>poly” title=”” /></a></p>
<p>需要说明的是,虚表指针_vptr可以在Point中的任意位置。上图中其位于Point对象的末尾,也可以位于最前,甚至在中间也可以。在末尾的好处在于其前面的部分仍然与C语言结构体兼容,在最前的好处是可以省去一步计算过程(对象的地址即为虚表指针的位置,不需要额外的计算)。而一般来讲没有编译器选择在中间位置插入虚表指针。</p>
<p>对于一个Point对象来讲,其<em>vptr将指向Point类的虚表;而对于一个Circle对象来讲,虽然图中标明了</em>vptr在Point部分中,但这仅表明它是由Point继承而来,其仍将指向Circle类的虚表,如下图所示:</p>
<p><a href=circle<em>with</em>poly_2″ title=”” /></a></p>
<h3 id=2.4 包含虚函数的多重继承

假如有如下代码:

class Point {  
public:  
    virtual void Print();
protected:  
    int x, y; 
}; 
class Text {  
public:  
    virtual void OutputText(); 
protected:  
    char buffer[4]; 
}; 
class Circle : public Point { protected: int radius; };  
class CircleWithText : public Circle, public Text  
{ protected: int text_x, text_y; };

在多重继承中,标准并未要求在内存中多个父类之间的顺序。一种可能的内存布局如下:

绘图1

从上图可以看出,此时CircleWithText中将存在两个虚表指针,分别从两条继承线路中继承而来。也就是说,此时CircleWithText类将包含两张虚表,一张中存放由Circle带来的虚函数,一张存放由Text带来的虚函数。假如CircleWithText自己还有新的虚函数,则可以择一存放。

与单继承相比,多重继承除了内存布局的复杂程度增加了之外,在几种情况下运行时的指针运算同样非常重要:

  • 指针的类型转换
  • 通过子类调用由第二个父类(内存中靠后的父类)继承而来的虚函数
  • 通过指向第二个父类(内存中靠后的父类)的指针调用被子类覆盖的虚函数

让我们逐一观察这几种情况。

1. 指针类型转换

CircleWithText cwt;  
Circle *pCircle = &cwt;  
Point *pPoint = &cwt; 

Text *pText = &cwt;  
//pText = (Text*)((char*)&cwt + sizeof(Circle));

对于前两条赋值语句来说,不需要额外的计算,因为在CircleWithText对象中,Circle部分和Point部分的起始地址与cwt一样。而如果要转换为第二个父类的指针,则需要一定的计算。在计算中应当对NULL进行判断,如果需要转换的指针是空指针的话,转换后的指针也应该为空指针。

2. 通过子类调用由第二个父类(内存中靠后的父类)继承而来的虚函数

CircleWithText cwt;  
CircleWithText *pcwt = &cwt;  
pcwt->OuputText();  

上述代码中,使用了子类指针pcwt调用了由Text父类继承而来的虚函数OutputText。由于我们需要传入this指针,这个指针不应当传入pcwt,而是pcwt中Text部分的起始地址。可是很可惜,这只是一种情况;我们无法在编译期确定究竟需要传入哪个this,因为很有可能存在第三种情况:

 3. 通过指向第二个父类(内存中靠后的父类)的指针调用被子类覆盖的虚函数

class CircleWithText : public Circle, public Text  
{ 
public:  
 virtual void OutputText(); 
}; 

CircleWithText cwt;  
Text *pText = &cwt;  
pText->OutputText();  

我们首先需要注意这一段代码与上段代码的不同。这段代码中CircleWithText覆盖了Text中的OutputText函数。此时在pText->OutputText()这一调用中,传入的应为cwt的起始地址。

关键的问题终于出现了:第一:如何确定应当传入哪一个this指针?第二,假设已经确定应当传入CircleWithText的起始地址,那么如何从pText指针重新找到CircleWithText的起始地址呢?在编译期,我们无法知晓这些问题,就如我们不知道下面代码中p的真实类型是什么:

void some_func(Text* p) { p->OutputText(); }  

因此,我们只能通过一定的运行时机制来解决这个问题。下面介绍两种可以解决这一问题的方法。

方案一:在虚函数表中同时存储函数地址和this指针的偏移

示例图如下:

mb_vftable

此时在虚表中同时存储函数地址和所需的this指针偏移(注意,是偏移而不是地址)。因为this指针的“地址”是跟每个对象相关的,而每一个类只有一张vtable。不过偏移却是对于一个类的所有对象都适用的(比如,在一个CircleWithText对象中,想把Text部分的起始地址转换为CircleWithText对象的起始地址所需的偏移是一定的)。这种方法的弊端在于增加了单继承时虚表的成本。

方案二:为函数添加thunk入口

mb_thunk

这种方法不改变虚表的结构,而是将原本指向成员函数的指针改为指向一段由编译器自动生成的thunk代码的地址。在这一小段代码中,对指针进行调整,然后再跳转到真正的函数中去。

2.5 虚拟继承

虚拟继承所要解决的问题时在继承树中同一个父类出现多次的情况。有时我们仅需要一个基类,这就需要虚拟继承来解决:

class Drawable { public: virtual void Draw(); };  
class Point : virtual public Drawable;  
class Text : virtual public Drawable;  

图片1

实现虚拟继承的难度在于,如何将两个Drawable对象变为一个,同时要解决指针计算的相关问题。下面介绍几种方案:

方案一:虚基类指针

在虚拟继承的子类中,额外存储一个指针用于指向直接虚继承的父类:

绘图2

然而这一方案的问题在于,如果有多层的虚拟继承,其间接访问的时间成本也将增加。如果存在多个虚继承父类,则需要多个指针。

方案二:对象的虚基类指针表

对于方案一的一种改进是将这些指针都存放在一张表里,通过一个指针来访问:

vbtable

这一方案解决了方案一中的问题。然而正如之前所说,“地址”是与对象相关的,如果采用了方案二,就是说每一个CircleWithText对象都需要两张虚基类的指针table。

方案三:在虚函数表的负索引处存放偏移

为了解决方案二中的弊端,可以考虑使用偏移,这样的话就不必为每一个对象都生成几个虚基类表了。同时,鉴于虚函数表的负索引还没有被利用,我们可以在这里存放虚基类的偏移。

vb_vftable

3. 运行时环境


3.1 运行时类型识别

在虚函数表的第0项中,并不存储函数指针,而是运行时类型信息type_info。dynamic_cast和typeid是与运行时类型相关的操作。

一个典型的type_info 类可能定义如下:

图片2

3.2 异常

对于如下代码,我们如何判断应当析构哪些对象?

图片3

一种方法是根据程序计数器PC,然而这可能与特定平台相关。另一种方案是使用一个标识变量step,在每一个对象构建或析构之后将step加1。同时存放一张表,用于查询当step为n时应当析构哪些对象。

2.3 C++与动态链接库

对于某一种C++编译器编译产生的动态链接库,将很难其与其他编译器一同使用。原因在于C++标准并没有规定在二进制上的实现方式,编译器在名称改编、成员布局以及异常等机制上均存在着差异。不过,使用抽象类可以一定程度上解决这个问题,详情可以参考一些面向对象系统的实现,例如COM。

感知器算法

这是我之前在实验室的机器学习讨论会上的分享。


Table of Contents

  • 人脑的启示
  • 感知器算法
  • 双层感知器
  • 反向传播算法
  • 应用

人脑的启示


人的神经是由一个个神经元组成的,包括树突、轴突、胞体等。

Picture1

人脑具有以下特征:

  • 超过100亿个神经元
  • 神经元响应时间:约1毫秒
  • 人脸识别:约0.1secs
  • 平均每个神经元与1000个神经元相连
  • 计算高度并行

人脑擅长于模式识别、联想,并可以容忍噪声;电脑则擅长于计算,罗辑清晰。人脑的操作速度很慢,并且运算的结果不可靠,但其可以大规模地并行计算;而电脑的运算速度相当快,并且结果非常可靠。

模拟神经元的结构和工作方式,是感知器算法的主要机制。例如,刺激程度决定了这个神经元的兴奋程度,并且与其他神经元连接紧密时,信号强度大;连接疏松时,信号强度弱。

感知器算法


感知器算法的原理非常简单:

感知器算法

首先对输入信号的求和,当超过阈值时即使感知器兴奋。算法描述如下(from A Course in Machine Learning):

感知器算法

从算法描述可以看出,学习的意义在于向正确的结果靠拢。两组同样的数据,第一次分错了,第二次将会更加接近正确结果。

MaxIter是需要人工指定的参数,如果MaxItger 过大,容易发生过拟合;过小则容易学不到什么东西 。

同时,整个学习的过程就是在一个平面上寻找判别边界。为了简化问题,假设有一个线性可分问题,b=0,则感知器算法即在寻找分界面B:

snapshot7

B就是虚线,而由wd组成的向量w垂直于B:

snapshot8

由此也可以得出,w的绝对大小并不重要。

感知器算法的特点有:

  1. 在线学习,不需要一次性考虑整个数据集

  2. 错误驱动,当分类正确时,不进行学习操作

  3. 对训练集的输入顺序敏感。例如,有10000条训练数据,前9000条数据在默认的参数上就分类正确,则此次迭代只有最后1000条数据得到了训练。因此,不断地调整训练数据的顺序将有助于加快训练速度:

Picture4

朴素的感知器算法仍然存在一定的缺陷,例如后训练的数据会更加重要。参考上面举得例子,如果有10000条训练数据,前100条数据已经训练出足够好的分类器,一直到最后一条之前全部分类正确。最后一条数据就会掉了一个在99.9%的数据上工作得都非常好的分类器。

从以上的分析也可以看出,单层的感知器算法只能用于解决线性可分的问题。

算法改进

投票感知器算法

投票感知器算法会在训练时记录每一个分类器的存活时间,在最终预测时根据权重进行投票。

Picture5

但是由于需要保存每一个超平面,并且预测时需要使用每一个分类器进行预测,时空开销将非常大。

平均感知器算法

平均感知器算法仅记录加权平均后的分类器:

Picture6

除此之外,还有像信任权感知器、被动主动感知器、权表决感知器等。信任权感知器通过对输入添加信任权重的概率分布,使得信任度大的输入会得到更大幅度的修正;被动主动感知器可以主动修正学习速率;权表决感知器会为每一维输入产生一个分类器,最终由虽有分类器结果汇总投票产生,并对错误的分类器予以惩罚。

双层感知器


 snapshot9

在双层感知器中,将有两层感知器需要训练。除此之外,在单层感知器中,我们使用的是线性函数来计算感知器是否被激活;这种用于判断感知器是否激活的函数叫做激活函数(link function)。双层感知器中,隐含层通常采用非线性的sigmoid(tanh)函数来作激活函数。

对于双层感知器来说,它可以模拟任意连续函数;隐含层节点越多,函数越复杂。如果隐含层层数再增加,则可以模拟任意函数。

反向传播算法


对于感知器计算输出的过程来说,相当于正向传播;而通过计算结果反馈给隐含层和输出层来调整参数,则属于反向传播。例如:

Picture1

我们可以通过输出结果与标准值的误差,来修正向量v和矩阵w。常用的方法是梯度下降法,目标函数为结果误差的几何均值。通过对目标函数f求w和v的偏导,就可以求出v和w的梯度。

目标函数:

Picture5

计算结果:

Picture3

Picture4

总结


优势

  • 数学基础 如果有线性解则可以找到(单层)
  • 可以容忍噪声
  • 可以处理任意连续/非连续函数(多层)
  • 可以学到复杂的输入输出映射关系

劣势

  • 知识表示不易解释
  • 依赖于hidden层激励函数
  • 输入输出的设计对结果具有影响
  • 参数较多(神经元数目、层数、学习速率等)
  • 可能需要使用者的经验
  • 训练时间长
  • 过拟合

Jump Out of C++:面向对象编程探索(一)

这是今年3月29号在IBM俱乐部做的技术分享的文字整理版。


 ppt_cover

这次的系列分享叫做“Jump out of C++:面向对象编程探索”,标题可以分为两部分:一个是关于C++的,一部分是关于面向对象编程的。其实我本来并没有想将太多关于C++的东西,才起名叫“Out of C++”,不过大家一致希望听一些,就把它单独拿出来分享一次。面向对象编程探索的“探索”两个字,其实也有两方面的含义。一个是面向对象编程的发展,另一个就是我自己对它的探索了。

整个讲座大概分为三个部分:第一部分主要介绍C++,以及C++ 11新引进的一些特性。其实C++在语法方面并没有太多想要说的,大家已经都已经很熟悉了;只是有一些不是那么常见、但还比较有用的东西,跟大家分享一下。介绍过了这个之后,我们可以有从两方面继续进行探索:一方面是更加具体:C++的一些运行时机制是如何实现的?另一方面是更加抽象:面向对象编程语言有哪些共同的特性?可以将它们分类吗?这两个方面将分别在第二部分和第三部分中介绍。

Table of Content


  1.  C++是如何诞生的?
  2. 面向过程:C语言兼容性与扩展
  3. 面向对象
  4. 模板与泛型编程
  5. C++ 11 新特性 

1. C++ 是如何诞生的?


  • 具有Simula那样的对程序组织的支持
  • 运行得像BCPL一样快
  • 高度可移植的实现

—— Bjarne Stroustrup

B.Stroustrup在《C++语言的设计和演化》一书中曾提到,上面这三点是他在创造C++时希望这一门语言所拥有的特点。这三点也指导了他整个语言的设计过程。

他是在读博士的时候产生了对C语言进行改进的想法的。他希望编写一个模拟程序,模拟分布式程序的执行。最初使用了Simula进行编写,编写的过程很愉快;可是运行时却不尽人意。Simula的优点在于可以使用类对数据和方法进行管理,同时还支持协程,可以很好地进行并发运算;可是缺点也很明显:编译效率低、运行效率也很低。B.S分析后认为,Simula的垃圾收集机制、运行时类型检查、变量初始化检查是拖慢运行时效率的罪魁祸首之三。

随后他用BCPL语言重新编写了模拟器,运行效率极佳;然而编写的过程却极为痛苦:没有类型检查,运行时的支持也几近为零。

这使他下定决心:如果没有好用的工具,是不会进行下一步工作的。

为什么是C?

C语言有着这些优点:灵活、高效、常用、可移植。灵活高效不必多说,常用是指当时几乎每一台机器上都有较为成熟的C语言编译器和运行环境;可移植更是正中B.S的初衷之一。

然而,C语言也同样有着一些缺点,比如安全性的缺失、以及古怪的声明语法。

比如:

int* v[10];

int (*p)[10];

typedef int DtoI(double);

typedef DtoI *V10[10];

V10* f(char);

我们无法按照正常的习惯从左到右读下去,复杂的声明要借助typedef才能获得一定的可读性。

他曾设想一种新的声明方式,类似如下这种:

v: [10]->int;

p: ->[10];

int f(char)->[10]->(double)->;

可惜的是,貌似是他最开始的时候忘记了;而后又已经无法将其加入语言当中了。

2. 面向过程:C语言兼容性与扩展


隐含的int类型

在C语言中,如果不加类型进行声明,默认即为int。比如

f();

static a;

void f(const T);

由于C++支持了模版机制,对于第三种声明来讲,将对编译器造成极大困惑:T是一种类型,还是类型为const int的变量?

最终废除隐含的int类型终于进入了C++标准。而为了这一结果,花费了整整十年的时间。在最初C++对C语言改革的最大阻力,不是来自B.S,不是来自开发者,不是来自标准委员会,而是C语言的用户。

结构标志与类型名

struct S a;

S a;

在C语言中,只有第一种变量声明是合法的;C++中第二种同样合法。这使得用户自定义类型的地位有所提高。

然而,事情并不是这么简单:

struct

对于C语言来讲,struct S中的符号S与int S中的符号S并不在一个名称空间中;而对于C++来讲,只有一个全局名称空间。这也就意味着,在遇到S时,C++会产生冲突:究竟是类型名还是变量名呢?

最终的选择是当冲突发生时,默认为变量名。原因在于当时有相当多的程序是有着上面左图那样的写法的,而最关键的在于Unix头文件中同样有很多类似的写法。兼容性的需求最终取胜。

全局变量的初始化

在C语言中,全局变量的初始化只能用稍微扩展一点的常量表达式来进行。这使得编译器可以在编译期求值,即不需要在运行时动态初始化。而C++则不同,如果要支持用户自定义类型的全局变量,则动态初始化是不可避免的。也因此支持了内置类型变量的动态初始化。

double p = 10.0 / 3;  //ok in C

double q = sqrt(10.0); //error in C, ok in C++ (Cfront >= 2.0)

class Double;

Double d = sqrt(10.0); //ok in C++

声明语句

支持了任意位置声明,以及在if/for中的声明语句。

其他不兼容的情况

  • 全局名称局部于文件,除非显式引出
  • 默认进行静态类型检查,除非显式抑制
  • 一个类代表一个作用域

在C语言中,void f();表示的是函数f可以接受任意参数。对于调用f(1, 2, 3);来说,C语言中是合法的。同样还有一些隐式类型转换,在C++中都有了更加严格的限制。

同时,在C语言中,结构体对内部的结构体并不起到对作用域的限制:

struct outer{

    struct inner{

        int a;

    };

};

struct inner in = {1};

C++修改了这一特性。

3. 面向对象


说到面向对象,大概就这几个方面:封装、继承、多态、抽象。我们从继承中的多重继承开始说起。

多重继承

多重继承是在Cfront release 2.0引入的。原因大概有这么几点:一个是能够使得设计进一步的推进,而且并不需要太多的扩充即可实现。当然,还有一点“主观因素”:一些人认为实现多重继承比实现参数化类型(即C++模板)更难,甚至有人在自己的书中谈到想要给C++添加多重继承是不可能的。B.S当时也是年少方刚正值气盛,当然要做来给他们看看了。他在之前很早就开始构想了多重继承的实现方式,并且已经想到了一个很好的实现。

对于多重继承,有一些人尚有争论。比如用处不大、增加负担、机制太弱、增加代码复杂程度……

但B.S的态度是:它(实现、运行起来)很便宜,又能解决关键问题,何乐而不为呢?

多重继承带来的典型问题是菱形继承问题。

菱形继承问题

对于多重继承来说,如果父类们有着相同的基类,那么在子类中将有祖父类的多份拷贝。有些时候这并不合理,我们希望子类中只有一个祖父类。C++引入了虚基类来解决这个问题:

虚基类

 事实上,继承也是一种封装:当我们使用父类时,它将子类的信息进行了隐藏。

多态

C++中,多态是利用虚函数实现的。想要表现出多态的效果,需要使用父类的指针或引用。

同时,dynamic_cast动态类型转换也必须对在具有虚函数的类型使用。这是因为他所依赖的运行时类型信息(RunTime Type Information, RTTI)是保存在虚表中的。

抽象类

带有纯虚函数的类叫做抽象类。纯虚函数允许没有函数实体,抽象类不能实例化。

抽象类的作用:

  1. 避免了无意义的对象产生

  2. 抽象类可以用来做界面(接口)

在很多语言中,接口是有单独的关键字来表示的,比如interface之类。C++中,抽象类就可以充当接口的作用:只提供使用方式,而将实现细节完全隐藏。

这样做的好处在于能够使得接口与实现相互分离,用户不需要清楚实现,更不需要显式地依赖具体实现。这也限制了修改后重新编译的范围,降低了耦合度。

4. 模板与泛型编程


 C++的模板支持模板参数的自动推断,以及非类型的参数。比如

template<int b, class T>  
T add(T a) {  
    return a + b;
}
int a = add(1); //a == 3  

同时,C++的模板并没有对类型进行显式限制的功能,例如必须继承自某个类,或是必须有那些方法才可以。C++模板对类型的限制是在使用上,比如 T a; a.print(); 如果类型T没有print方法,则在编译器会报错。

有时候我们需要对模板进行特化。即定义一个特定类型参数的版本,以处理一些特殊的情况。例如

template <class T>  
bool equal(T a, T b) {  
    return a == b;
}

template <>  
bool equal(const char* a, const char*b) {  
    return !strcmp(a, b);
}

同时模板还支持偏特化,即部分特化。例如多个类型参数,只特化其中一部分;或将其不完全特化,例如将普适的类型特化为指针类型。

模板元编程

C++的模板是图灵完备的。也就是说,理论上它可以执行任何计算任务。但由于模板是由编译器在编译期进行计算,受到编译器的限制。

模板元编程与函数式编程语言很像:没有可变变量,所有“函数”都没有副作用。例如下面是在编译期计算斐波那契数列:

template <int n>  
struct Fib {  
    enum {
        Result = Fib<n - 1>::Result + Fib<n - 2>::Result
    };
};

template <>  
struct Fib<1> { enum { Result = 1 }; };

template <>  
struct Fib<0> { enum { Result = 0 }; };

int main() {  
    int i = Fib<5>::Result;
    std::cout << i << std::endl;
    return 0;
}

模板在最初设计的时候只是为了参数化容器而设计的,最终能够用来进行元编程是一种“意外”,因此从语法上来说也并不是很舒服。

5. C++ 11 带来了什么?


  • 更优雅的初始化
  • 更优雅的委托
  • 更优雅的RAII
  • 更高的效率
  • 更强大的模板

更优雅的初始化

更优雅的初始化方式包括初始化列表、新增的类成员初始化方式、代理构造函数以及统一的初始化语法等。例如:

class IntArray {  
public:  
    IntArray(int s) : size(s) { ptr = new int[s]; } 
    IntArray() : IntArray(50){}     
    IntArray(std::initializer_list<int> list) : 
    IntArray(list.size()) { //... } 
private:  
    unsigned size = 0; 
    int* ptr = nullptr; 
}; 
IntArray intArray = { 1, 2, 3 };  

 上例中,使用std::initializer_list将可以接受类似数组方式定义的初始化成员值;在第三个接受初始化列表的构造函数中,其调用了第一个只接受整型长度的构造函数;而在类的内部,则可以直接使用赋值语法对成员进行初始化。如果在构造函数的成员初始化列表(冒号之后的列表,不是initializer_list)中没有对相应成员进行初始化,则使用在类中声明的值用作初始化。

同时,C++ 11还统一了初始化的语法。任何类型均可以使用大括号进行成员的初始化,例如:

class Test {  
public:  
    Test(int a, int b){} 
    virtual ~Test(){} 
}; 

int main() {  
    Test t{1, 2}; 
    Test t2 = {1, 2}; 
    int t3 = {1}; 
    int t4{1}; 
}

 上述代码中,四条初始化语句都是正确的。当存在接受initializer_list作为参数的构造函数时,大括号将会被解释为initializer_list(例如之前的IntArray)。

更优雅的委托

什么是委托?

class A {  
public:  
    void p(); 
}; 

class B {  
    A a; 
public:  
    void p(){ a.p(); } 
};

 当B有一件事情,转交给A去做的情况,就叫做委托。事实上,委托也可以用来实现继承;而在C++的早期,B.S也曾经设想过使用委托来实现继承,但最终放弃了这一想法。对于近几年新出炉的Go语言来说,自动委托是用来实现类似于继承思想的一种方式。

对于稍微复杂一点的委托,例如B希望A能够执行一些自己设定的任务(比如回调),则稍稍有些麻烦。在C语言中,函数指针经常用来承担这种任务:

typedef void (*FUNC)();  
class A {  
public:  
    void q(FUNC func) (func();) 
}; 
void f() {/*...*/}  
int main() {  
    A a; 
    A.q(f); 
    return 0; 
}

 然而,上述代码对于类的成员函数则不适用。对于以下三个f函数来说,他们的类型是不同的:

class B {void f();};  
// void B::(*)(); 

class C {void f();};  
// void C::(*)(); 

void f();  
// void (*)();

底层的原因则在于B和C有着一个不同类型的隐含参数:this指针。因此,这三个f函数,只有最后一个能够传给A.q作为委托的任务。

一个典型面向对象解决方案可以统一B和C参数不同的问题。使用一个Listener纯虚类作为接口,类A接受一个Listener作为参数,而B和C均继承自Listener:

class Listener {  
public:  
    virtual void f() = 0; 
}; 

class A {  
public:  
    void q(Listener *listener){listener->f();} 
};

class B : public Listener {  
public:  
    void f(){} 
}; 

class C : public Listener {  
public:  
    void f(){} 
}; 

int main() {  
    A a; 
    B b; 
    C c; 
    a.q(&b);
    a.q(&c); 
    return 0; 
}

 这种方式在Java中非常常见。然而,这种方法使用了面向对象的方式仅仅解决了面向对象那一部分的问题——A仍然无法接受不属于任何类的f()。

 C++ 11新引入了多态函数对象包装器std::function,可以很好地解决这个问题。

class A {  
public:  
    void q(function<void> f){f();} 
}; 

class B {  
public:  
    void Callback() {} 
}; 

void normalFunc(){} 

int main() {  
    A a; 
    B b; 
    a.q(bind(&B::Callback, &b)); 
    a.q(normalFunc); 
    return 0; 
}

实际上,藉由std::function,C++ 11还提供了闭包的功能,并引入了匿名函数来简化语法:

void someFunc(function<void> q){q();}  
int main() {  
    int a = 2, b = 3; 
    auto f = [=]() -> void { //[&a, &b] 
        cout << a + b << endl;
    };
    someFunc(f);
    return 0;
}; 

 更优雅的RAII

RAII(资源获取即初始化)是C++中对于资源管理比较重要的一个概念,最初由B.S在他的The C++ Programming Language中提到。在C语言中,一个常见的资源管理策略是:谁申请,谁释放。“谁”可以指函数,也可以指模块。

谁申请,谁释放

举例来说,例如一个负责字符串编码转换的函数:

bool Charset1ToCharset2( const char* input, unsigned input_size, char* output, unsigned output_size ) {  
    //Convert charset return true; 
}

显然,根据谁申请、谁释放的原则,这个函数不应该在函数内部申请内存,而应当由外部调用者申请好资源后传入。可是调用者如何知道最终转换后的字符串需要多大的空间呢?

因此,将函数修改如下:

bool Charset1ToCharset2( const char* input, unsigned input_size, char* output, unsigned output_size, unsigned* output_needed ) {  
    *output_needed = calc_output_size(); 
    if (output_size < *output_needed)
        return false;

    //Convert charset
    return true;
}

此时在func1中需要调用两次Charset1ToCharset2,第一次用以查询需要多少空间;第二次真正接收字符串编码转换的结果。这种方式在Windows API中也非常常见。

然而,这种方式在有很多分支、很多资源需要申请时,资源释放是一件相当繁琐的事情。尤其在C++支持了异常之后,很有可能会出现资源没有释放,函数就返回的情况。

RAII就是为了解决这一问题而产生的管理方式。它通过对象的生命周期来管理资源,当对象的生命周期结束时,自动释放所持有的资源:

class FileRAII {  
public:  
    FileRAII(const char* n, const char* m) 
    { /*fp = fopen(n, m); */} 

    FileRAII(FILE* p) { fp = p; }

    ~FileRAII() { fclose(fp); } 

    operator FILE*() { return fp; } 
private:  
    FILE* fp; 
}; 

bool func() {  
    FileRAII fp(fopen("1.txt", "r")); 
    if (fp == NULL) 
        return false; 
    //Use fp... 
    return true; 
}

不论func正常退出,或是在使用fp时触发了C++异常而导致异常退出,fp都会被析构,即fclose(fp)都会被执行。

在C++ 11 之前,实现一个通用的RAII类是比较复杂的。然而,当匿名函数和闭包被引入了之后,它变得十分简单:

class ScopeGuard {  
public:  
    ScopeGuard(function<void> on_exit) : _on_exit(on_exit){} 
    ~ScopeGuard() { _on_exit(); } 
    ScopeGuard(const ScopeGuard&) = delete; 
    ScopeGuard & operator=(const ScopeGuard&) = delete; private: 
    function<void> _on_exit; 
}; 

void func5() {  
    FILE* fp = fopen("1.txt", "r"); 
    ScopeGuard s([=] {fclose(fp); }); 
}

 垃圾收集:为什么不支持?

  1.  不适合低层次的工作
  2. 效率
  3. C语言兼容性
  4. 对象布局、创建的限制
  5. 不确定状态

  6. 很多GC算法在运行时要求暂时中断程序的运行。对于很多程序来讲,这可能并不是太大的问题;但是,这将使得C++不再适用于低层次的工作。在当时,C++已经被广泛地用于各种实时系统、嵌入式系统中,他们对这个问题实在是太过敏感。

  7. 时空开销。对于今天的硬件发展来说,这个问题小了很多,但弊端同上一点。如果真的要支持GC,提供一个开关也是比较合理的考虑。

  8. C语言支持一些底层的功能,比如指针运算、联合、强制类型转换等,还有不加检查的数组、不加检查的函数参数等等对于GC算法的设计非常不利的功能。比如,当用户申请了一块堆内存时,如何判断用户已经不再需要这块内存了呢?由于C语言支持指针运算,用户可以轻易地将指针算走之后再算回来。

  9. 垃圾收集同样将导致与其他语言的接口变得复杂。

  10. 用户难以知道某一块内存是否被释放了,它的状态是不确定的。

更高的效率

C++ 11中引入了右值引用、move语义和常量表达式来实现效率的提升。

“值”是指无法被进一步求值的表达式。对于“值”来说,通常我们分为左值和右值。一开始,左值被定义为“赋值号左面的值”,右值相反。可是,这种定义明显不再适用于C++。C++ 11中,明确定义了3种值类型:

左值:可以取地址的值

临终值:生命期即将结束,但其值尚未被取走。例如返回右值引用的函数的返回值,或是强制转换后的右值。

纯右值:不具有标志,可以移动。

广义的左值是指左值+临终值,他们可以表现多态;广义的右值指纯右值+临终值,他们不能被取地址。

在C++ 11之前,“引用”可以引用左值,“常量引用”可以引用左值+右值,然而缺乏一种方式只能引用右值。例如,在C++ 11之前,当一个函数返回一个对象时,将会有临时对象被创建。此时临时对象的构造将会增加程序运行的成本。

class IntArray  
{
public:  
    IntArray(int s) : size(s)
    {
        ptr = new int[s];
        cout << "constructor" << endl;
    }
    IntArray(const IntArray& a)
    {
        delete[] ptr;
        size = a.size();
        ptr = new int[size];
        memcpy(ptr, a.ptr, sizeof(int) * size);
        cout << "copy constructor" << endl;
    }

    IntArray& operator=(const IntArray& a)
    {
        //......
        cout << "assgin operator" << endl;
        return *this;
    }
private:  
    unsigned size = 0;
    int* ptr = nullptr;
};

在VS中的测试结果是:未优化版本将有一次构造、一次拷贝和一次赋值;优化版本将有一次构造和一次赋值。Move语义在这里就派上了用场,它与Copy不同之处在于:

Move语义Copy语义 

当Object1对象是右值时,通过Move方式得到资源将会省去一次拷贝的过程。反正Object1也即将被释放,倒不如把资源送给Object2。

class IntArray  
{
public:  
    IntArray(const IntArray&& a)
    {
        delete[] ptr;
        size = a.size();
        ptr = a.ptr;
        a.ptr = nullptr;
        cout << "move constructor" << endl;
    }

    IntArray& operator=(const IntArray&& a)
    {
        //......
        cout << "move assign operator" << endl;
        return *this;
    }
};

constexpr关键字代表了新的常量表达式,它将在编译期被求值。例如:

constexpr int GetValue() {  
    return 5;
} 

int main() {  
    int a[GetValue() + 1];
    return 0; 
}

`
 在constexpr出现之前,这是不能编译通过的。带有constexpr修饰的语句将会在编译期被求值,如果无法求值的话将会出现编译错误。

常量表达式可以替代部分宏函数的功能,比如

enum Flags { good=0, fail=1, bad=2, eof=4 }; 

constexpr int operator|(Flags f1, Flags f2) {  
    return Flags(int(f1)|int(f2)); 
} 

void f(Flags x) {  
    switch (x) { 
    case bad: break; 
    case eof: break; 
    case bad|eof: break; 
    default: break; 
    } 
}

还有一些情况,是曾经无法支持的。例如,对于一个字符串常量来说,它其中的每一个字符也应当可以在编译器求值。但在constexpr出现之前,我们必须在运行时计算地址,然后取值;现在则不同:

constexpr char* str = "Hello World";  
int main() {  
    constexpr char a = str[1]; 
    cout << a << endl;
    return 0;
}

a将在编译期被取值。同样,我们也可以在编译期求值很多东西,它可以替代一部分模板的功能:

constexpr int exp(int a, int b) {  
    return (b == 0) ? 1 : a * exp(a, b - 1); 
} 
constexpr int a = exp(2, 10);  

 一个函数能否在编译期被求值是有要求的,例如不能有循环语句等。

更强大的模板

C++ 11 加强了模板的功能:模板不定参数、完美转发、编译期Assert、模板别名、返回类型后置(用来进行类型推导)等。

其他常见C++ 11特性

  • Range-based for
  • 强类型枚举
  • 新字符串字面值
  • thread
  • long long int
  • STL:tuple/unordered_map/regex/….