ppt 如何做网站交互式带财运的公司名字

当前位置： 首页 > news >正文

ppt 如何做网站交互式,带财运的公司名字,seo技术教程博客,海口网站设计文章目录 统计学习方法 感知机模型定义学习策略学习算法原始算法对偶算法 学习算法的收敛性 统计学习方法 感知机 读李航的《统计机器学习》时#xff0c;关于感知机的笔记。 感知机#xff08;perceptron#xff09;是一种二元分类的线性分类模型#xff0c;属于判别模型… 文章目录 统计学习方法 感知机模型定义学习策略学习算法原始算法对偶算法 学习算法的收敛性 统计学习方法 感知机 读李航的《统计机器学习》时关于感知机的笔记。 感知机perceptron是一种二元分类的线性分类模型属于判别模型是 NN 和 SVM 的基础。 模型定义 感知机输入空间 X ⊆ R n \mathcal{X}\subseteq \R^n X⊆Rn 输出空间是 Y { 1 , − 1 } \mathcal{Y}\set{1,\,-1} Y{1,−1} 输入 x ∈ X x\in \mathcal{X} x∈X 表示实例的特征向量输出 y ∈ Y y\in\mathcal{Y} y∈Y 表示实例的类别。由输入空间到输出空间的如下函数 f ( x ) sign ( w ⋅ x b ) f(x)\text{sign}(w \cdot xb) f(x)sign(w⋅xb) 称为感知机。其中 w ∈ R n w \in \R^n w∈Rn 称为权重 b ∈ R b\in\R b∈R 称为偏置。 线性方程 w ⋅ x b w \cdot xb w⋅xb 对应特征空间 R n \R^n Rn 中的一个超平面 S S S 位于两边的点特征向量则被分为正、负两类 学习策略 当训练数据是完全线性可分的我们则可以找到一个超平面将正负类的数据完全分开。但数据不完全线性可分时我们则要定义损失函数找到一个感知机使得损失函数极小化。但其实即使完全线性可分也要定义损失函数不然怎么学习 [乐.jpg] 很容易想到用分类错误的点的总数作为损失函数但是这样对 w w w 和 b b b 就不是连续可导的了不好优化。所以我们选择所有误分类点到超平面 S S S 的总距离作为损失函数。 空间中任意一点 x 0 ∈ R n x_0\in \R^n x0​∈Rn 到超平面 S S S 的距离为 dis ( x 0 , S ) 1 ∣ ∣ w ∣ ∣ ∣ w ⋅ x 0 b ∣ \text{dis}(x_0,S)\frac{1}{||w||}|w\cdot x_0b| dis(x0​,S)∣∣w∣∣1​∣w⋅x0​b∣ ∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣ 是 w w w 的 L 2 L_2 L2​ 范数 其次对于误分类的数据 ( x i , y i ) (x_i,y_i) (xi​,yi​) 来说 y i y_i yi​ 与 f ( x ) f(x) f(x) 符号相反因此 − y i ( w ⋅ x i b ) 0 -y_i(w\cdot x_ib)\gt 0 −yi​(w⋅xi​b)0 我们利用这个大于零的性质可以将误分类点到超平面的距离表示为因为 y i y_i yi​ 只有可能是正负 1所以乘上去也不会改变距离的大小 dis ( x 0 , S ) − 1 ∣ ∣ w ∣ ∣ y i ( w ⋅ x i b ) \text{dis}(x_0,S)-\frac{1}{||w||}y_i(w\cdot xib) dis(x0​,S)−∣∣w∣∣1​yi​(w⋅xi​b) 因此所有误分类点到超平面 S S S 的距离之和 − 1 ∣ ∣ w ∣ ∣ ∑ x i ∈ M y i ( w ⋅ x i b ) -\frac{1}{||w||}\sum{x_i\in M} y_i(w\cdot xib) −∣∣w∣∣1​xi​∈M∑​yi​(w⋅xi​b) M M M 为被误分类点的集合 这里不考虑 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} ∣∣w∣∣1​ 即得到感知机的损失函数 L ( w , b ) − ∑ x i ∈ M y i ( w ⋅ x i b ) L(w,\,b)-\sum{x_i\in M} y_i(w\cdot x_ib) L(w,b)−xi​∈M∑​yi​(w⋅xi​b) 去掉 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} ∣∣w∣∣1​ 对损失函数的优化至关重要 y i ( w ⋅ x i b ) y_i(w\cdot x_ib) yi​(w⋅xi​b) 被称为样本点的函数间隔在 SVM 中会涉及到。 学习算法 感知机学习算法的原始形式和对偶形式与第7支待向量机学习法的原始形式和偶形式相对应。 原始算法 给定一个训练数据集 T { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ , ( x N , y N ) } T{(x_1,\,y_1),\,(x_2,\,y_2),\,\cdots,\,(x_N,\,y_N)} T{(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)} 其中 x i ∈ X R n x_i\in\mathcal{X}\bold{R}^n xi​∈XRn y i ∈ Y { − 1 , 1 } yi\in\mathcal{Y}{-1,\,1} yi​∈Y{−1,1} i 1 , 2 , ⋯ , N i1,\,2,\,\cdots,\,N i1,2,⋯,N 求参数 w w w 和 b b b 使得以下损失函数极小化 min ⁡ w , b L ( w , b ) − ∑ x i ∈ M y i ( w ⋅ x i b ) \min{w,\,b}L(w,\,b)-\sum_{x_i\in M}y_i(w\cdot x_i b) w,bmin​L(w,b)−xi​∈M∑​yi​(w⋅xi​b) 我们采用随机梯度下降法来学习参数 w w w 和 b b b 梯度为 ∇ w L ( w , b ) − ∑ x i ∈ M y i x i ∇ b L ( w , b ) − ∑ x i ∈ M y i \begin{align} \nablawL(w,\,b)\,-\sum\limits{x_i\in M}y_ix_i \ \nablabL(w,\,b)\,-\sum\limits{x_i\in M}y_i \ \end{align} ∇w​L(w,b)∇b​L(w,b)​−xi​∈M∑​yi​xi​−xi​∈M∑​yi​​​ 但学习的时候并不是一次使 M M M 中所有的误分类点都梯度下降而是一次随机选取一个误分类点使其梯度下降。 算法感知机学习算法的原始形式 输入训练数据集 T T T 学习率 η \eta η 0 η ≤ 1 0 \lt\eta\leq 1 0η≤1 输出 w w w b b b 感知机模型 f ( x ) sign ( w ⋅ x b ) f(x)\text{sign}(w\cdot xb) f(x)sign(w⋅xb)
选取初值 w 0 w_0 w0​ 和 b 0 b_0 b0​ 在训练集中选取数据 ( x i , y i ) (x_i,\,y_i) (xi​,yi​) 若 y i ( w ⋅ x i b ) ≤ 0 y_i(w\cdot x_ib) \leq 0 yi​(w⋅xi​b)≤0 w ← w η y i x i b ← b η y i \begin{align} w \leftarrow\, w\eta y_ix_i \ b \leftarrow\, b\eta y_i \end{align} w←b←​wηyi​xi​bηyi​​​ 若当前训练集中仍有误分类点则跳转至 2. 否则结束 对偶算法 我们前面对误分类点修改参数时的形式为 w ← w η y i x i b ← b η y i \begin{align} w \leftarrow\, w\eta y_ix_i \ b \leftarrow\, b\eta yi \end{align} w←b←​wηyi​xi​bηyi​​​ 因此我们可以认为模型参数是训练样本值的线性组合即最后学习到的 w w w 和 b b b 可以表示为 w ∑ i 1 N α i y i x i b ∑ i 1 N α i y i \begin{array}{c} w\sum\limits{i1}^N \alpha_iy_ixi \ b\sum\limits{i1}^{N}\alpha_iy_i \end{array} wi1∑N​αi​yi​xi​bi1∑N​αi​yi​​ 这里 α i ≥ 0 \alphai \geq 0 αi​≥0 i 1 , 2 , ⋯ , N i1,2,\cdots,N i1,2,⋯,N。 算法感知机学习算法的对偶形式 输入训练数据集 T T T 学习率 η \eta η 0 η ≤ 1 0 \lt\eta\leq 1 0η≤1 输出 α \alpha α b b b 感知机模型 f ( x ) sign ( ∑ j 1 N α j y j x j ⋅ x b ) f(x)\text{sign}(\sum\limits{j1}^N \alpha_jy_jx_j\cdot xb) f(x)sign(j1∑N​αj​yj​xj​⋅xb)
初始化 α ← 0 \alpha \leftarrow 0 α←0 b ← 0 b \leftarrow 0 b←0 在训练集中选取数据 ( x i , y i ) (x_i,\,y_i) (xi​,yi​) 若 y i ( ∑ j 1 N α j y j x j ⋅ x b ) ≤ 0 yi(\sum\limits{j1}^N \alpha_jy_jx_j\cdot xb) \leq 0 yi​(j1∑N​αj​yj​xj​⋅xb)≤0 α i ← α i η b ← b η y i \begin{align} \alpha_i \leftarrow\, \alpha_i\eta \ b \leftarrow\, b\eta y_i \end{align} αi​←b←​αi​ηbηyi​​​ 若当前训练集中仍有误分类点则跳转至 2. 否则结束 为了方便可以预先将训练集中的实例间的内积计算出来并以矩阵的形式存储即 Gram 矩阵 G [ x i ⋅ x j ] N × N \bold{G}[x_i \cdot xj]{N\times N} G[xi​⋅xj​]N×N​ 学习算法的收敛性 当数据集不可分时显然上述算法会震荡。现在证明对于线性可分数据集感知机学习算法原始形式收敛即经过有限次迭代就可以得到一个将数据集完全正确划分的分离超平面及感知机模型。 为了数学推导方面我们将偏置 b b b 放入权重向量 w w w 记作 w ^ [ w t , b ] T \hat{w}[w^t,\,b]^T w^[wt,b]T 。同样将输入向量进行增广得到 x ^ [ x T , 1 ] T \hat{x}[x^T,\,1]^T x^[xT,1]T 显然 w ^ ⋅ x ^ w ⋅ x b \hat{w}\cdot\hat{x}w\cdot xb w^⋅x^w⋅xb Th 2.1Novikoff 设训练数据集 T T T 是线性可分的则 存在满足条件 ∣ ∣ w ^ o p t ∣ ∣ 1 ||\hat{w}{opt}||1 ∣∣w^opt​∣∣1 的超平面 w ^ o p t ⋅ x ^ 0 \hat{w}{opt}\cdot \hat{x}0 w^opt​⋅x^0 将训练数据集完全正确分开且存在 γ 0 \gamma 0 γ0 对所有 i 1 , 2 , ⋯ , N i1,\,2,\,\cdots,\,N i1,2,⋯,N 都有 y i ( w ^ o p t ⋅ x ^ i ) y i ( w o p t ⋅ x i b o p t ) ≥ γ yi(\hat{w}{opt}\cdot \hat{x}_{i})yi(w{opt}\cdot x{i}b{opt})\geq \gamma yi​(w^opt​⋅x^i​)yi​(wopt​⋅xi​bopt​)≥γ 令 R max ⁡ 1 ≤ i ≤ N ∣ ∣ x ^ i ∣ ∣ R\max\limits{1\leq i\leq N}||\hat{x}{i}|| R1≤i≤Nmax​∣∣x^i​∣∣ 则感知机算法在训练数据集上的误分类次数 k k k 满足 k ≤ ( R γ ) 2 k\leq \left(\frac{R}{\gamma}\right)^2 k≤(γR​)2 证明第一点较为简单。因为训练数据集线性可分因此存在超平面 ( w o p t , b o p t ) (w{opt},\,b{opt}) (wopt​,bopt​) 可将数据集完全正确分开。只要令 γ min ⁡ i { y i ( w o p t ⋅ x i b o p t ) } \gamma\min_{i}{ yi(w{opt}\cdot xib{opt}) } γimin​{yi​(wopt​⋅xi​bopt​)} 就有 y i ( w ^ o p t ⋅ x ^ i ) y i ( w o p t ⋅ x i b o p t ) ≥ γ yi(\hat{w}{opt}\cdot \hat{x}_{i})yi(w{opt}\cdot x{i}b{opt})\geq \gamma yi​(w^opt​⋅x^i​)yi​(wopt​⋅xi​bopt​)≥γ 现在来看第二点看起来还蛮神奇的。感知机算法从 w ^ 0 0 \hat{w}_00 w^0​0 开始记每一次迭代得到的参数为 w ^ k \hat{w}_k w^k​ 。第 k k k 个参数下记 ( x i , y i ) (x_i,\,y_i) (xi​,yi​) 是被误分类的实例则条件是 y i ( w ^ k − 1 ⋅ x ^ i ) y i ( w k − 1 ⋅ x i b k − 1 ) ≤ 0 yi(\hat{w}{k-1}\cdot \hat{x}_i)yi(w{k-1}\cdot xi b{k-1})\leq 0 yi​(w^k−1​⋅x^i​)yi​(wk−1​⋅xi​bk−1​)≤0 w w w 和 b b b 的更新是 w k ← w k − 1 η y i x i b k ← b k − 1 η y i \begin{align} wk \leftarrow\, w{k-1}\eta y_ix_i \ bk \leftarrow\, b{k-1}\eta y_i \end{align} wk​←bk​←​wk−1​ηyi​xi​bk−1​ηyi​​​ 即 w ^ k w ^ k − 1 η y i x ^ i \hat{w}k\hat{w}{k-1}\eta y_i\hat{x}_i w^k​w^k−1​ηyi​x^i​ 下面证明两个不等式 ① 由于我们是从 w ^ 0 0 \hat{w}00 w^0​0 开始的因此迭代过程中的参数应当从小到大越来越接近 w ^ o p t \hat{w}{opt} w^opt​ 即 w k w{k} wk​ 与 w o p t w{opt} wopt​ 的内积越来越大 $\( \begin{align} \hat{w}k\cdot \hat{w}{opt} , \hat{w}{k-1}\cdot \hat{w}{opt}\eta y_i\hat{w}{opt}\cdot\hat{x}i \ \geq , \hat{w}{k-1}\cdot \hat{w}{opt}\eta \gamma \ \geq , \hat{w}{k-2}\cdot \hat{w}{opt}2\eta \gamma \ \geq , \cdots \ \geq , k\eta \gamma \end{align} \)\( 第二个大于等于是因为我们已经假设了 γ \gamma γ 是最小的 y i w ^ o p t x ^ i y_i\hat{w}_{opt}\hat{x}_i yi​w^opt​x^i​ 因此任意 i i i 都有 y i w ^ o p t x ^ i ≥ γ y_i\hat{w}_{opt}\hat{x}_i\geq \gamma yi​w^opt​x^i​≥γ 即 w ^ k ⋅ w ^ o p t ≥ k η γ \hat{w}_k\cdot \hat{w}_{opt}\geq k\eta \gamma w^k​⋅w^opt​≥kηγ ② 由于我们是从 w ^ 0 0 \hat{w}_00 w^0​0 开始的因此迭代过程中的参数更新过大时就会被后续的迭代给“拉”回来 \)\( \begin{align} ||\hat{w}k||2,||\hat{w}_{k-1}||22\eta y_i\hat{w}{k-1}\cdot \hat{x}i\eta2||\hat{x}_i||2 \ \leq , ||\hat{w}{k-1}||2\eta||\hat{x}_i||2 \ \leq , ||\hat{w}{k-1}||^2\eta R^2 \ \leq , ||\hat{w}{k-2}||^22\eta R^2 \ \leq , \cdots \ \leq , k\eta2R2 \end{align} \)\( 第一个等号是因为 ∣ ∣ w ^ k ∣ ∣ 2 w ^ k T w ^ k ( w ^ k − 1 η y i x ^ i ) T ( w ^ k − 1 η y i x ^ i ) ( w ^ k − 1 T η y i x ^ i T ) ( w ^ k − 1 η y i x ^ i ) w ^ k − 1 T w ^ k − 1 η y i ( w ^ k − 1 T x ^ i x ^ i T w ^ k − 1 ) η 2 y i 2 x ^ i T x ^ i ∣ ∣ w ^ k − 1 ∣ ∣ 2 2 η y i w ^ k − 1 ⋅ x ^ i η 2 ∣ ∣ x ^ i ∣ ∣ 2 (有 y i 2 1 ) \begin{align} ||\hat{w}_k||^2\,\hat{w}_k^T\hat{w}_k \\ \,(\hat{w}_{k-1}\eta y_i\hat{x}_i)^T(\hat{w}_{k-1}\eta y_i\hat{x}_i) \\ \,(\hat{w}_{k-1}^T\eta y_i\hat{x}_i^T)(\hat{w}_{k-1}\eta y_i\hat{x}_i) \\ \,\hat{w}_{k-1}^T\hat{w}_{k-1}\eta y_i(\hat{w}_{k-1}^T\hat{x}_i\hat{x}_i^T\hat{w}_{k-1})\eta^2y_i^2\hat{x}_i^T\hat{x}_i \\ \,||\hat{w}_{k-1}||^22\eta y_i\hat{w}_{k-1}\cdot \hat{x}_i\eta^2||\hat{x}_i||^2 \quad\text{(有\)\,y_i^21$)} \end{align} ∣∣w^k​∣∣2​w^kT​w^k​(w^k−1​ηyi​x^i​)T(w^k−1​ηyi​x^i​)(w^k−1T​ηyi​x^iT​)(w^k−1​ηyi​x^i​)w^k−1T​w^k−1​ηyi​(w^k−1T​x^i​x^iT​w^k−1​)η2yi2​x^iT​x^i​∣∣w^k−1​∣∣22ηyi​w^k−1​⋅x^i​η2∣∣x^i​∣∣2(有yi2​1)​​ 第二个小于等于是因为我们假设 ( x i , y i ) (x_i,\,y_i) (xi​,yi​) 是被误分类的实例因此 y i w ^ k − 1 ⋅ x ^ i 0 yi\hat{w}{k-1}\cdot \hat{x}_i0 yi​w^k−1​⋅x^i​0 第三个小于等于是因为我们假设 R R R 是最大的特征向量的模因此对于任意 i i i 都有 R ≥ ∣ ∣ x ^ i ∣ ∣ R \geq ||\hat{x}_i|| R≥∣∣x^i​∣∣
即 ∣ ∣ w ^ k ∣ ∣ 2 ≤ k η 2 R 2 ||\hat{w}_k||^2\leq k\eta^2R^2 ∣∣w^k​∣∣2≤kη2R2 综合不等式 ① 和 ② 得 k η γ ≤ w ^ k ⋅ w ^ o p t ≤ ∣ ∣ w ^ k ∣ ∣ ∣ ∣ w ^ o p t ∣ ∣ ≤ k η R ⇒ k 2 γ 2 ≤ k R 2 \begin{array}{c} k\eta \gamma \leq \hat{w}k\cdot \hat{w}{opt} \leq ||\hat{w}{k}||\,||\hat{w}{opt}|| \leq \sqrt{k}\eta R \ \Rightarrow k^2\gamma^2 \leq kR^2 \end{array} kηγ≤w^k​⋅w^opt​≤∣∣w^k​∣∣∣∣w^opt​∣∣≤k ​ηR⇒k2γ2≤kR2​ 第二个小于等于是柯西不等式 x ⋅ y ∣ ∣ x ∣ ∣ ∣ ∣ y ∣ ∣ cos ⁡ θ ≤ ∣ ∣ x ∣ ∣ ∣ ∣ y ∣ ∣ x\cdot y||x||\,||y||\,\cos\theta\leq ||x||\,||y|| x⋅y∣∣x∣∣∣∣y∣∣cosθ≤∣∣x∣∣∣∣y∣∣ 其中 θ \theta θ 是两个向量的夹角。 于是 k ≤ ( R γ ) 2 k\leq \left(\frac{R}{\gamma}\right)^2 k≤(γR​)2 该定理表明误分类次数 k k k 是有上界的即训练集线性可分时感知机学习算法原始形式迭代是收敛的。