感知机（Perceptron）
1.感知机模型
1.1感知机定义
输入空间$ mathcal{X} subseteq mathbb{R}^n$ ，输出空间(mathcal{Y})={+1, -1} ;
输入(x in mathcal{X})表示的实例的特征向量，对应于输入空间的点，输出(y in mathcal{Y})表示的实例的类别；
由输入空间到输出空间的如下函数：
f(x) = sign($ omega cdot x$+b)
(omega) : 权值，b : 偏置；
(omega cdot x) : (omega)和x的内积；
sign为符号函数;
1.2感知机几何解释
线性方程(omega cdot x + b = 0)对应于特征空间(mathbb{R}^n)中的一个超平面S,其中ω是超平面的法向量，b是超平面的截距。这个超平面将特征空间划分为两个部分。位于两部分的点分别被分为正负两类。因此，S成为分类超平面。
2.感知机学习策略
2.1数据集的线性可分性
给定一个数据集T， 如果存在某个超平面S: (omega cdot x + b = 0)能够将数据集的正实例点和负实例点完全正确的划分到超平面的两侧，即yi((omega cdot x + b) ge 0)，则称数据集T为线性可分数据集。
2.2 感知机的学习策略
首先，输入空间(mathbb{R})n 中任一点x0到超平面S的距离d：(frac{1}{||omega||}|omega cdot x_0 + b|)
证明如下：
在超平面S((omega cdot x + b = 0))任选一点v1，所需公式(vec{v_0v_1} = ||v_0||||v_1||costheta)
d = (||vec{v_0v_1}||cos(vec{v_0v_1}, omega))
= (||vec{v_0v_1}|| frac{|vec{v_0v_1} cdot omega|}{||vec{v_0v_1}||||omega||})
= (frac{|(x_1 - x_0) cdot omega|}{||omega||})
= (frac{|-b - x_0cdot omega|}{||omega||})
= (frac{1}{||omega||}|omega cdot x_0 + b|)
其次，对于误分类的数据（xi，yi）来说，(-y_i(omega cdot x_i + b) > 0)，因此，误分类点xi到超平面S的距离是(-y_ifrac{1}{||omega||}|omega cdot x_i + b|)。假设超平面S所有误分类点的集合为M，则所有误分类点的总距离为(-frac{1}{||omega||}sum_{x_i in M}y_i|omega cdot x_i + b|)。因此可得出损失函数为(L(omega, b) = - sum_{x_i in M}y_i(omega cdot x_i + b))
2.3 感知机算法
2.3.1原始形式(随机梯度下降法)
输入：训练数据集T = {(x1, y1), (x2, y2), ....., (xN,yN)},其中(x_i in mathcal{X} = mathbb{R}^n)，(y_i in mathcal{Y} = {+1, -1}, i = 1,2,...,N;) 学习率(theta(0 < theta le 1);)
输出：(omega),b;感知机模型(f(x) = sign(omega cdot x + b)。)
过程：
1.选取初值ω0， b0；
2.在训练集中选取数据（xi, yi）;
3.如果(y_i(omega cdot x_i + b) le0)，(omega leftarrow omega + theta y_ix_i)，(b leftarrow b+theta y_i)。
4.转至2，直至训练集中没有误分类点。
注：感知机学习算法由于采取不同的初值或选取不同的误分类点，解可以不同。
2.3.2算法的收敛性
证明：经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知机模型。
为了叙述与推导，(hat omega = (omega^T,b)^T, hat x = (x^T, 1)^T,hat omega cdot hat x = omega cdot x + b)。
训练数据集T = {(x1, y1), (x2, y2), ....., (xN,yN)},其中(x_i in mathcal{X} = mathbb{R}^n)，(y_i in mathcal{Y} = {+1, -1}, i = 1,2,...,N;) 则
（１）存在满足条件(||hat omega_{opt}|| = 1)的超平面(hat omega_{opt} cdot hat x = omega_{opt} cdot x + b_{opt} = 0) 将训练数据集完全正确分开；且存在(gamma > 0), 对所有的i= 1,2,...,N，(y_i(hat omega cdot hat x) = y_i(w_{opt} cdot x_i + b_{opt}) ge gamma)。
证明如下：
由于训练集是线性可分的，故存在一分离超平面。不妨设改平面为(hat omega cdot hat x = w_{opt} cdot x_{opt} + b_{opt} = 0)，使(||hat omega_{opt}|| = 1)。
于是对于所有有限的i，均有(y_i(w_{opt} cdot x_i + b_{opt}) > 0)。
取(gamma > 0),则(gamma = min_{i}{(y_i(omega_{opt} cdot x_i+b_{opt}))})。
所以，（1）得证。
（2）令(R = max_{1 le i le N}||hat x||),则在(f(x) = sign(omega cdot x + b))在训练数据集上的误分类次数k满足不等式(k le {(frac{R}{gamma})}^2)
证明：(hat omega_{k} cdot hat omega_{opt} ge kgammaeta)，$hat w_{k} $是第k个误分类点实例的扩充权重向量。
(hat omega_k cdot hat omega_{opt} = (hat omega_{k-1} + eta y_i hat x_i)hat omega_{opt} \ ge hat omega_{k-1} cdot hat omega_{opt} + eta gamma \ = (hat omega_{k-2} + eta y_i hat x_i)hat omega_{opt} \ ge hat omega_{k-2} cdot hat omega_{opt} + eta gamma \ ge... \ ge ketagamma)
证明：(||hat omega_{k}||^2 le k eta^2R^2)
(||hat omega_k||^2 = ||hat omega_k||^2 + 2eta y_i hat omega_{k-1} cdot hat x_i + eta^2||hat x_i|| \ le ||hat omega_{k-1}||^2 + eta^2||hat x_i|| \ le ||hat omega_{k-1}||^2 + eta^2R^2 \ le ||hat omega_{k-1}||^2 + 2eta^2R^2 \ le ... \ le keta^2R^2)
由上述可得，(ketagamma le hat omega_k cdot hat omega_{opt} le ||hat omega_k|| ||hat omega_{opt}|| le sqrt k eta R rightarrow k^2gamma^2 le k R^2 rightarrow k le (frac{R}{gamma})^2)
定理表明，误分类次数k是有上界的，经过有限次搜索可以找到分离超平面。即当训练数据集线性可分时，感知机学习算法原始形式迭代时收敛的。
2.3.3 对偶形式
输入：训练数据集T = {(x1, y1), (x2, y2), ....., (xN,yN)},其中(x_i in mathbb{R}^n)，(y_i in {+1, -1}, i = 1,2,...,N;) 学习率(eta(0 < eta le 1);)
输出：(alpha),b;感知机模型(f(x) = sign(sum_{j=1}^N alpha_j y_j x_j cdot x + b)。)
过程：
1.(alpha leftarrow0, b leftarrow 0)；
2.在训练集中选取数据（xi, yi）;
3.如果(y_i(sum_{j=1}^N alpha_j y_j x_j cdot x_i + b) le0)，(alpha_i leftarrow alpha_i + eta)，(b leftarrow b+eta y_i)。
4.转至2，直至训练集中没有误分类数据。
注：Gram矩阵：训练集中实例间的内积计算并以矩阵形式存储，该矩阵为Gram矩阵，记为(mathtt{G} = [x_i cdot x_j]_{N ast N})。
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
