时之碎片

logic programming

新年花了一天多点的时间阅读了一下《Introduction to Logic Progrmming》这本书（后称该书）。个人很早以前就阅读过逻辑式编程的书籍，但当时主要针对 prolog 语言进行学习。

logic programming 可以做数据库吗？

与以往阅读的 prolog 书籍不同，该书最开始就是以一种类似数据库的视角来推进逻辑式编程的讲解。一般的 prolog 书籍会从经典的家族关系作为切入点来讲解逻辑式编程的魅力，但该书从 datasets 开始讲起。
该书明确的指出了逻辑式编程的形式，即：
facts + rules + query
从逻辑式编程的形式我们便可以看出其与数据库千丝万缕的联系我们可以回想一下关系型数据库的形式，以 mysql 为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

假设我们有一个数据库
--------------------------
-- iD -- name -- age -----
-- 0  -- tim  -- 32  -----
-- 1  -- ada  -- 23  -----
-- 2  -- tom  -- 23  -----
--------------------------
此时我们利用 mysql的查询语句，查询名字为tim的客户的所有信息
select * from person where name = 'tim';
我们可以得到
--------------------------
-- iD -- name -- age -----
-- 0  -- tim  -- 32  -----
--------------------------

如果我们用 prolog 表达上述过程，我们可以如此构建 datasets

1
2
3
4
5
6
7
8
9
10
11
12
13
14

% facts

person(0,tim,32).
person(1,ada,23).
person(2,tom,23).

%query

person(X,tim,Y).

% result

X = 0.
Y = 32.

prolog 代码如上所述，我们首先构建了一组事实(facts)，然后根据这组事实查询想要的变量，最后我们可以得到查询结果。
但以这种方式构建 facts 可能有有些问题，以 person(0,tim,32)为例，我们并不能得到每个值得含义，例如 0 和 32 我们无法看出其为 id 和年龄。我们可以按照下面的方式构建。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

% facts

person(id(0),name(tim),age(32)).
person(id(1),name(ada),age(23)).
person(id(2),name(tom),age(23)).

%query

person(X,name(tim),Y).

% result

X = id(0).
Y = age(32).

这样我们就可以标注出每个位置值的含义了
当然，仅从这个例子来看，prolog 比起 mysql 没什么好处，反而可能增添一些存储负担。
我们能发现仅仅做这种简单的查询时，prolog 并不能展现其优势。我们还是得拿出经典的家族关系例子来展现 prolog（逻辑式编程）的某些特性。

家族关系的经典例子

我们可以想象一个大家族的族谱，不妨设计一个族谱关系

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
27
28
29
30
31
32
33
34
35

% 族谱关系的一些事实
male(charles).
male(william).
male(peter).
male(henry).
male(andrew).
male(edward).
male(viscount).
male(savanna).

female(elizabeth).
female(anne).
female(zara).
female(beatrice).
female(eugenie).
female(louise).
female(isla).

parent(elizabeth,charles).
parent(elizabeth,anne).
parent(elizabeth,andrew).
parent(elizabeth,edward).

parent(anne,peter).
parent(anne,zara).
parent(charles,william).
parent(charles,henry).
parent(andrew,beatrice).
parent(andrew,eugenie).
parent(edward,louise).
parent(edward,viscount).
parent(peter,savanna).
parent(peter,isla).

% 其中 male 表示男性，female 表示女性，parent(X,Y)表示 X 时 Y 的父母（父亲或母亲）

当我们面对一些逻辑问题时，使用逻辑式编程便可大大减少我们的时间，例如我们想查询 grandparent 这个关系时，我们只要写下这个规则。

1
2
3
4
5

grandparent(X,Y) :- parent(X,Z),parent(Z,Y).

% 这条规则（rules）说明了grandparent的逻辑关系，
% 即grandparent其实就是父母的父母

从这里我们能感受到逻辑式编程的一些好处，在我们编写程序时，其实我们就是在编写一个逻辑约束的规则，而逻辑式编程语言（例如 prolog）的引擎可以根据这个规则来寻找对应的解（其实本质上是搜索）。

updates

该书在讲解了 facts 和 querys 之后便开始讲解 updates,所以该书确实是以一种数据库的视角来介绍 logic programming 的。
书中举了一个 update syntax 的例子

1
2

p(a,b) & ~q(b) ==> ~p(a,b) & p(b,a)
p(X,Y) & ~q(Y) ==> ~p(X,Y) & p(Y,X)

这样我们便更新了数据库中的规则。

data structrue

该书紧接着讲述了 lists sets 和 trees 三种类型的数据结构，这里和其他介绍 prolog 的书籍区别不大。

总结

《introduce to logic programming》 这本书还是值得一读的，通过阅读这本书可以很好的了解 logic programming。先阅读这本书再阅读 prolog 相关书籍也是个不错的选择。

什么是 map,filter,fold

map

map 接受一个函数和一个列表，并将函数作用在列表中的每个元素上，最后返回函数作用后的列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

haskell 中map的类型签名
map :: (a -> b) -> [a] -> [b]

racket 代码
(define (mymap function mylist)
  (cond
     ((null? mylist) '())
     (else (cons (function (car mylist)) (mymap function (cdr mylist)) ))
  )
)
(define (add2 x) (+ 2 x))
(mymap add2 '(1 2 3 4 5 6 7 8))

=> (3 4 5 6 7 8 9 10)

filter

顾名思义，将列表中符合条件的值提取出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

haskell 中filter的类型签名
filter :: (a -> Bool) -> [a] -> [a]

racket代码
(define (myfilter condition? mylist)
  (cond
    ((null? mylist) '())
    ((condition? (car mylist)) (cons (car mylist) (myfilter condition? (cdr mylist))))
    (else (myfilter condition? (cdr mylist)))
  )
)

(define (odd? a)
  (eq? (modulo a 2) 1)
)

(myfilter odd? '(-1 -2 -3 -4 -5 -6 -7 -8 -9 -10))
=> (-1 -3 -5 -7 -9)

fold

fold 就是折叠的含义，一般来讲可以分为左折叠和右折叠

我们以左折叠（foldl）为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

haskell 中foldl的类型签名
foldl :: (a -> b -> a) -> a -> [b] -> a

racket代码
(define (myfoldl base function mylist)
  (cond
     ((null? mylist) base)
     (else (myfoldl (function base (car mylist)) function (cdr mylist)))
  )
)

(define (add x y)
  (+ x y)
)

(myfoldl 0 add '(1 2 3 4 5 6 7 8 9))
=> 45

演绎系统

谓词演算

知识单元的构造

对于知识我们可以用一种陈述性结论表示，例如：
天是蓝的
1+1=2
表示知识的陈述性形式称为命题。带有参数的命题被称作谓词。
例如 xx 是水果这就是一个谓词，我们可以设谓词 P 为 xx 是水果，那么有：
P1： P(苹果)
P2： P(葡萄)
我们说 P1 和 P2 是两个命题。它们的含义分别是：
P1： 苹果是水果
P2： 葡萄是水果
我们可以将不同的谓词结合起来形成新的谓词，如：
P3: fruit(X) -> sweet(X)
这个命题表示如果 X 是水果，那么水果是甜的。在这里我们必须注意的是，这个新的谓词在逻辑上被规定是正确的，但这并不能代表它就是真正意义上的正确。我们也可以轻轻松松举出反例来反驳这个命题，但计算机是无法做到的。
从某种程度上讲这也是演绎系统的一大问题，在人类社会并不是只存在逻辑支配着所有的规律（至少目前来看不是）。所以完全指望构建完美的演绎系统来模拟世界无论从工程角度还是理论角度恐怕都是不可能的。（参考哥德尔不完备定律）
如上所示，我们表示出了一个新的知识单元，如果构建出大量的知识单元并制定一些规则，那么计算机可以说有了一定的“智能”（只要这些规则足够复杂且规模庞大）。
谓词可以不断组合形成新的谓词，理论上一个逻辑链是可以无限延伸的，如 P1(X)->P2(X)->P3(X)->P4(X)->P5(X)->……->（无限延伸）。

朴素贝叶斯法的学习与分类

任务与数据

$ DATA = \lbrace (x_{1},y_{1}),(x_{2},y_{2}),…,(x_{N},y_{N}) \rbrace $
$ input space: \mathcal {X} \subseteq \mathbb{R}^{n} $
$ output space: \mathcal{Y} = {c_{1},c_{2},…c_{k}} $
其中$c_{i}$为类标记，该类标记可以有两个或多个。

基本方法

朴素贝叶斯通过训练数据集学习联合概率分布P(X,Y)。
其中先验概率分布为：
$ \displaystyle P(Y = c_{k}),k=1,2,…,K $
条件概率分布：
$ \displaystyle P(X=x|Y=c_{k}) = P(X^{(1)}=x^{(1)},…,X^{(n)}=x^{(n)}|Y=c_{k}), k=1,2,…,K $
学习到联合概率分布P(X,Y)。
朴素贝叶斯法对条件概率分布作了条件独立性假设。即：
$ \displaystyle P(X=x|Y=c_{k})=P(X^{(1)}=x^{(1)},…,X^{(n)}=x^{(n)}|Y=c_{k})= \prod_{j=1}^{n} P(X^{(j)}=x^{(j)}|Y=c_{k}) $
计算后验概率，将后验概率最大类作为x的类输出，后验概率计算根据贝叶斯定理进行。
$ \displaystyle P(Y=c_{k}|X=x)=\frac{P(X=x|Y=c_{k})P(Y=c_{k})}{\sum_{k}P(X=x|Y=c_{k})P(Y=c_{k})} $
可解朴素贝叶斯分类器：
$ \displaystyle y = \mathop{\arg\max}_{\mathbf c_{k}} P(Y=c_{k})\prod_{j}P(X^{(j)}=x^{(j)}|Y=c_{k}) $

后验概率最大化的含义

使用0-1损失函数有期望风险函数：
$ \displaystyle R_{exp}(f)=E[L(Y,f(x))] $
取条件期望有：
$ \displaystyle R_{exp}f(x)=E_{x} \sum_{k=1}^K [L(c_{k},f(X))]P(c_{k}|X) $
为了令期望风险最小化，于是对每个X=x逐个极小化可得：
$ \displaystyle f(x)= \mathop{\arg\max}_{\mathbf y \in Y} P(y=c_{k}|X=x)$
也即：
$ \displaystyle y = \mathop{\arg\max}_{\mathbf c_{k}} P(Y=c_{k}|X=x) $

前言

该系列总结曼昆微观经济学笔记。

经济学十大原理

人们如何做出决策

原理一：人们面临权衡取舍

做出决策就是要求我们在一个目标和另一个目标之间进行权衡取舍。例如社会面临的一种权衡取舍是在效率与平等之间。效率(effeciency)是指社会能从稀缺资源中取得到的最大利益，平等(equality)是指将这些利益平均分配给社会成员。
（注：为什么平等和效率是冲突的？这与平等的概念有关，平等究竟是什么？）

原理二： 某种东西的成本是为了得到它所放弃的东西

机会成本(opportunity cost)：是为了得到这种东西所放弃的东西。

原理三： 理性人考虑边际量

理性人(rational people)：系统而有目的地尽最大努力实现其目标的人。
边际变动(marginal change)：对行动计划的微小增量调整。

原理四： 人们会对激励作出反应

激励(incentive)：引起一个人做出某种行为得某种东西。
（注：此处的激励更像是反馈）

人们如何相互影响

原理五：贸易可以使每个人得状况都变得更好

原理六：市场通常是组织经济活动的一种好方法

市场经济(market economy)：当许多企业和家庭在物品与服务市场上相互交易时，通过他们的分散决策配置资源的经济。

原理七：政府有时可以改善市场结果

产权(property rights)：个人拥有并控制稀缺资源的能力。
市场失灵(market failure)：市场本身不能有效配置资源的情况。
外部性(externality)：一个人的行为对旁观者福利的影响。
市场势力(market power)：单个经济活动者（或某个经济活动小群体）对市场价格有显著影响的能力。
（注：什么时候市场会失灵？稀缺性的定义是否具有主体性？是否能找到所有的外部性并纳入成本？如何预防市场势力的产生？还是说市场势力是市场的正常结果？）

整体经济如何运行

原理八：一国的生活水平取决于它生产物品与服务的能力

生产率(productivity)：每单位劳动所投入的生产物品与服务数量。
（注：金融服务是否是一种服务？这种服务的稀缺性如何界定？该怎样看待利用金融体系吸血问题？还是说利用金融体系吸血这个命题根本不存在？）

原理九：当政府发行了过多货币时，物价上涨

通货膨胀(inflation)：经济中物价总水平的上升。

原理十：社会面临通货膨胀与失业之间的短期权衡取舍

经济周期(business cycle)：就业和生产等经济活动的波动。

前言

本系列主要为《Convex Optimization》学习笔记

凸集

直线与线段

设$x_{1} \neq x_{2}$为$\mathbb{R}^{n}$空间中两个点，则
$ y=\theta x_{1}+(1-\theta) x_{2},\theta \in \mathbb{R} $
为一条穿越$x_{1},x_{2}$的直线。当$\theta$在0~1变动时，可构成$x_{1}$与$x_{2}$之间的闭线段。y也可表示为：
$y=x_{2}+\theta(x_{1}-x_{2})$
这种形式可以解释成由基点$x_{2}$向方向$x_{1}-x_{2}$走一定距离的所有点的集合，当$\theta$在0~1之间时，构成了线段，若$\theta$可取任意值，则是直线。

仿射集合

设集合$C \subseteq \mathbb{R}^{n}$若$\forall x_{1},x_{2} \in C ,\theta \in \mathbb{R}$有$\theta x_{1}+(1-\theta) x_{2} \in C$则称集合$C$为仿射的。
该定义也可以扩展到多个点的情况。当$\theta_{1}+…+\theta_{k} = 1$时，我们称$\theta_{1}x_{1} + \theta_{2}x_{2}+…+\theta_{k}x_{k}$为$x_{1},…,x_{k}$的仿射组合。

凸集定义

集合$C$被称为凸集，如果$C$中任意两点间的线段仍在$C$，即对于$\forall x_{1},x_{2} \in C$和满足$0 \leqslant \theta \leqslant 1$均有$\theta x_{1}+(1-\theta)x_{2} \in C$
点$\theta_{1}x_{1} + \theta_{2}x_{2}+…+\theta_{k}x_{k}$为点$x_{1},x_{2},…x_{k}$的一个凸组合，其中$\theta_{1}+…+\theta_{k}$并且$\theta_{i} \geqslant 0, i=1,……,k$
与仿射集合类似，一个集合是凸集等价于集合包含其中所有点的凸组合。
我们称集合C为所有点的凸组合的集合为其凸包，记为 $conv C$:
$conv C = \lbrace \theta_{1}x_{1}+…+\theta_{k}x_{k}| x_{i} \in C, \theta_{i} \geqslant 0, i =1,…,k, \theta_{1}+\theta_{2}+…+\theta_{k}=1\rbrace$
凸包$conv C$总是凸的，它是包含$C$的最小的凸集。

人工智能学派

人工智能的主要流派有三个：1.符号主义(symbolicism)—数理逻辑 2.连接主义(connectionism)—仿生学 3.行为主义(actionism)—控制论
该系列博客主要写写其中的符号主义学派。
（注： 主要是总结所看过的书籍、博客等，并非完全原创）
符号主义学派的核心观点在于，人类的智能主要体现在推理能力。机器应当像人一样思考，这样一来机器才有获取智能的可能。符号主义学派的思路十分明了，建立一个庞大的知识库体系，并赋予机器推理能力这样便可以创造人工智能。至于为什么这种观点被称为
符号主义，原因在于该学派普遍认为人类认知基于符号，而思维是一种运算。如今的语义网络与专家系统很大程度上继承了符号主义学派的思路。

知识

按照符号主义学派的思路，构建人工智能首先要获取知识。给知识下定义是极其困难的，但我们可以简单总结一下生活中的几种知识：
1.事实性知识
2.过程性知识
3.行为性知识
4.实例性知识
5.类比性知识
6.元知识

事实性知识

这种知识一般采用直接表示的方式，例如：地球绕着太阳转、北京是中华人民共和国首都等。但要注意事实性知识的准确性，事实性知识如果出现错误，那么做出的推理必然结果也会不严密。
注：本文不讨论事实性知识能否正确被人类认知的哲学相关问题。

过程性知识

往往是一系列动作构成的知识，例如：如何做西红柿炒鸡蛋、如何维修电子计算机等

行为性知识

不给出事实本身，而是给出某方面的行为。例如微分方程刻画了一个函数的行为但并未给出函数本身。（这类知识往往是某种数学模型）行为性知识往往描述的是事物的内涵而非外延。
(注：
内涵：内涵往往指事物特有属性的反应
外延：外延往往指事物所组成的类
例如：当我们谈到人的内涵，指的是人类所具有属性(如：域：真核域 Eukarya \ 界：动物界 Animalia \ 门：脊索动物门 Chordata\ 亚门：脊椎动物亚门 Vertebrata \ 纲：哺乳纲 Mammalia \ 亚纲：真兽亚纲 Eutheria \ 目：灵长目 Primates \ 科：人科 Hominidae \ 属：人属 Homo \ 种：智人种(Homo sapiens sapiens) \ )而人的外延则指全体人类（即所有人类个体的集合）
从集合论的角度看内涵指集合所有元素共有的属性，而外延指集合中的所有元素。)

实例性知识

只给出实例而知识隐藏在实例中。例如：观察到打雷之后下雨了这便是一个实例性知识。（注：这并不是说打雷一定下雨，所有观察数据都是实例性知识）

类比性知识

不给出内涵也不给出外延，但给出它与其他事物的相似之处。这种知识虽然不准确，却能使不同领域之间的知识可以被快速理解。

元知识

即关于知识的知识。例如：一个专家系统要知道该系统能回答什么不能回答什么，这本身也是一种知识，只不过是关于知识的知识。

知识表示

大概了解了知识之后，问题便是如何表示知识，普遍上有如下几种：
1.演绎系统
2.产生式系统
3.框架结构
4.语义网络
5.过程性知识

在后续的文章中，我们将逐一解释这五种表示方法。

K 近邻算法

K 近邻算法是一种基本的分类与回归方法。K 近邻算法没有显式的学习过程，实际上式利用训练数据集对特征向量空间进行划分。
其任务与数据如下：

其中$y^{i}$是实例的类别。
任务是输出实例x的类别y。
k近邻算法的三个要素是：
1.k值选择 2.度量距离 3.分类决策规则
该算法流程如下：
根据给定的距离度量，在训练集中找出与x最近邻的k个点，涵盖这k个点的邻域记作$N^{k}(x)$
在$N^{k}(x)$中根据分类决策规则决定x的类别y：

其中 I 为指示函数当$y^{i} = c^{i}$时 I 为 1，否则为 0。当 k=1 时，该算法又可称最近邻算法。

距离度量

该算法的距离度量往往采用$L_{p}$距离。其定义为：

k 值选择

k 值不易选取过大，应在较小的值中选取，选取不同的 k 值并进行交叉验证来选取最优值。

分类决策规则

一般采用多数表决（majority voting rule），其误分类率是：

那么要使其最小就是使$\displaystyle \sum_{x_{i} \in N_{k}(x)} I(y_{i} = c_{j})$最大，多数表决函数可以等价于经验风险最小化。

实现

往往利用 kd 树方式构造：
构造根结点，不妨选择$x^{(1)}$为坐标轴，以 T 中所有的实例的$x^{(1)}$坐标的中位数为切分点，将根节点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴$x^{(1)}$垂直的超平面实现。由根节点生成深度为 1 的左右子节点；左子节点对应坐标$x^{(1)}$小于切分点的子区域，右子节点对应于坐标$x^{(1)}$大于切分点的子区域。将落在切分超平面上的点将被保存在根节点。
之后对深度为 j 的节点重复这种操作，选择$x^{(l)} \ l = j(mod k)+1$进行。
当两个子区域没有实例存在时停止。从而形成 kd 树的区域划分。

前言

好久没更新博客了，准备开一个新的系列总结一下自己机器学习的相关经验

单层感知机

我们今天看一个超级简单的模型，单层感知机。其结构可以看作是（以四元为例）

首先我们来看看任务和数据是什么样子的：

$Data = \lbrace (x_{1},y_{1}),(x_{2},y_{2})…(x_{m},y_{m}) \rbrace $
$x^{i} \in \mathcal {X} \subseteq \mathbb{R}^{n}$
$y^{i} \in \mathcal {Y} = \lbrace 1,-1 \rbrace $

这组数据给出的情景是：存在一个二分类任务，其中 n 维数据有 m 组，现要找到一个模型 f(·)来对数据进行分类，并求出其 w 与 b。
由于我们的任务是二分类任务，且输出为 1 或-1，不妨将 f(·)设为 sigmoid 函数(由于 sign 函数不可导)
在该任务中我们要找到一个超平面 w*x+b = 0 将正负实例分到平面两侧，则有

我们可以将这两个公式合为一个 $y_{i} * (w * x_{i}+b) \gt 0$，当一个数据符合该不等式时，该数据便被分类正确。
显而易见的，当误分类的点越少时，模型便越精准。因此我们可以定义 loss 函数为$\displaystyle \sum^{x^{i} \in M} 1$其中M为误分类点的集合。我们的目的就是找到合适的参数w与b将该loss函数取到最小值。但由于该loss函数是离散的，我们无法对其进行求导等操作。因此我们不妨将loss函数改为如下形式

这样一来我们便可以进行求导操作，利用随机梯度下降法(stochastic gradient descent)进行训练。loss 函数对 w 和 b 分别求导可得：

进而我们利用每个误分类点$(x^{i},y^{i})$对 w,b 进行更新：

其中$\eta$为学习率，我们可以取 0~1 中的任何一个数值。学习率的选取在很多时候对算法的收敛速度有很大的影响。
对上述式子我们可以不断地进行迭代，到没有误分类点后停止。
以上便是单层感知机模型。

上一节中我们对 scheme 有了初步印象，这节我们来介绍它的基本运算。
与 c 语言不同的是，scheme 种并没有真正意义上的变量。例如：

1

Int a = 3;

这种形式的语句在 scheme 中并不存在。在 c 语言中，一个变量必须声明类型，而 scheme 则有所不同。首先来看数的计算。
在 c 语言中，我们可以这样写：

1
2
3

Int a = 5；
Int b = 6;
Int c = a + b;

而在 scheme 中其书写是这样的：

1
2
3

(define a 5)
(define b 6)
(define c (+ a b))

这两者能达到同样的效果。但两者还是有较大的区别的，例如：

1
2
3
4

Int a = 5;
Int b = 6;
b = 9;
int c = a + b;

在这时，c 为 14 而在 scheme 中：

1
2
3
4

(define a 5)
(define b 6)
(define b 9)
(define c (+ a b))

此时则会报错，在 scheme 中所有的值都是常量，不可更改，而不像 c 语言，需要用 const 修饰才为常量。
四则运算在上节中也做过基本的介绍，这节中不再过多阐述。
同样的，scheme 中也有不同的类型，例如数字，字符，列表，其中列表是一个及其重要的组成。不夸张的说，scheme 的强大与列表有着很深的相关性。
接下来我们说说字符，在 c 语言中，我们有字符和字符串，例如：

1
2

char d = ‘h’;
string e = “abcdefg”;

在 scheme 中，我们如是表示：

1
2

(define d “h”)
(define e “abcdefg”)

值得注意的是，在 scheme 中，字符和字符串都用“xxxxxxxxx”表示，我们可以把字符理解成长度为一的字符串。
接下来我们说最重要的部分，列表：
列表主要由 cons car cdr 构成，其中 cons 是把两个组成部分合成一个序对，值得注意的时，cons 可以连接不同类型的单元，例如：

1
2

>(cons “abcdef” 6)
    '("abcdef" . 6)

如果我们想得到“abcdef” 只需 (car (cons “abcdef” 6))
如果要得到 6 只需要(cdr (cons “abcdef” 6))
上面简要说了说 scheme 中基本的要素，下节中我们将介绍更多内容。