网站设计色彩搭配,深圳做网站要多少钱,企业logo标志设计免费,余姚建设局网站感知机(perceptron)是二分类的线性分类模型#xff0c;输入为实例的特征向量#xff0c;输出为实例的类别(取1和-1)。感知机对应于输入空间中将实例划分为两类的分离超平面。感知机旨在求出该超平面#xff0c;为求得超平面导入了基于误分类的损失函数#xff0c;利用梯度下…感知机(perceptron)是二分类的线性分类模型输入为实例的特征向量输出为实例的类别(取1和-1)。感知机对应于输入空间中将实例划分为两类的分离超平面。感知机旨在求出该超平面为求得超平面导入了基于误分类的损失函数利用梯度下降法 对损失函数进行最优化(最优化)。感知机的学习算法具有简单而易于实现的优点分为原始形式和对偶形式。感知机预测是用学习得到的感知机模型对新的实例进行预测的因此属于判别模型。感知机由Rosenblatt于1957年提出的是神经网络和支持向量机的基础。行文脉络感知机模型感知机学习策略感知机学习算法原始形式对偶形式4. Github地址1. 感知机模型定义假设输入空间(特征向量)为X⊆Rn输出空间为Y{-1, 1}。输入x∈X表示实例的特征向量对应于输入空间的点输出y∈Y表示示例的类别。由输入空间到输出空间的函数为f(x)sign(w·x b)(1)称为感知机。其中参数w叫做权值向量b称为偏置。w·x表示w和x的内积。sign为符号函数即 (2)几何解释感知机模型是线性分类模型感知机模型的假设空间是定义在特征空间中的所有线性分类模型即函数集合{f|f(x)w·xb}。线性方程 w·xb0对应于特征空间Rn中的一个超平面S其中w是超平面的法向量b是超平面的截踞。这个超平面把特征空间划分为两部分。位于两侧的点分别为正负两类。超平面S称为分离超平面如下图学习与预测感知机学习即由训练数据集T{(x1,y1),(x2,y2)...(xN,yN)}(其中xi∈XRnyi∈Y{-1, 1}i1,2...N)求得感知机模型(1)即求得参数w,b感知机预测即根据得到的感知机模型(1)对新的输入实例给出对应的类型。2. 感知机学习策略假设训练数据集是线性可分的感知机学习的目标是求得一个能够将训练数据的正负实例点完全分开的分离超平面即最终求得参数w、b。这需要一个学习策略即定义(经验)损失函数并将损失函数最小化。损失函数的一个自然的选择是误分类的点的总数。但是这样得到的损失函数不是参数w、b的连续可导函数不宜优化。损失函数的另一个选择是误分类点到分里面的距离之和。首先对于任意一点xo到超平面的距离为 (3)其次对于误分类点(xi,yi)来说 -yi(w·xib)0这样假设超平面S的总的误分类点集合为M那么所有误分类点到S的距离之和为 (4)不考虑1/||w||就得到了感知机学习的损失函数。经验风险函数给定数据集T{(x1,y1),(x2,y2)...(xN,yN)}(其中xi∈XRnyi∈Y{-1, 1}i1,2...N)感知机sign(w·xb)学习的损失函数定义为 (5)其中M为误分类点的集合这个损失函数就是感知机学习的经验风险函数。显然损失函数L(w,b)是非负的。如果没有误分类点那么L(w,b)为0误分类点数越少L(w,b)值越小。一个特定的损失函数在误分类时是参数w,b的线性函数在正确分类时是0.因此给定训练数据集T,损失函数L(w,b)是w,b的连续可导函数。3. 感知机学习算法最优化问题给定数据集T{(x1,y1),(x2,y2)...(xN,yN)}(其中xi∈XRnyi∈Y{-1, 1}i1,2...N)求参数w,b,使其成为损失函数的解(M为误分类的集合) (6)3.1 感知机学习的原始形式感知机学习是误分类驱动的具体采用随机梯度下降法。首先任意选定w0、b0然后用梯度下降法不断极小化目标函数(6)极小化的过程不知一次性的把M中的所有误分类点梯度下降而是一次随机选取一个误分类点使其梯度下降。假设误分类集合M是固定的那么损失函数L(w,b)的梯度由(7)(8)给出 (7) (8)随机选取一个误分类点(xi,yi),对w,b进行更新 (9) (10)式中η(0≤η≤1)是步长在统计学是中成为学习速率。步长越大梯度下降的速度越快更能接近极小点。如果步长过大有可能导致跨过极小点导致函数发散如果步长过小有可能会耗很长时间才能达到极小点。算法(感知机学习算法的原始形式)输入T{(x1,y1),(x2,y2)...(xN,yN)}(其中xi∈XRnyi∈Y{-1, 1}i1,2...N学习速率为η)输出w, b;感知机模型f(x)sign(w·xb)(1) 初始化w0,b0(2) 在训练数据集中选取(xi, yi)(3) 如果yi(w xib)≤0w w ηyixib b ηyi(4) 转至(2)直观解释当一个实例点被误分类时调整w,b使分离超平面向该误分类点的一侧移动以减少该误分类点与超平面的距离直至超越该点被正确分类。例1对于训练数据集其中正例点是x1(3,3)T,x2(4,3)T负例点为x3(1,1)T用感知机学习算法的原始形式求感知机模型f(x)w·xb。这里w(w(1),w(2))Tx(x(1),x(2))T解构建最优化问题按照算法求解w b。η1(1)取初值w00, b00(2)对于(33):-(00)00未被正确分类。更新w,bw1w01*y1·x1 (0,0)T1(3,3)T(3,3)Tb1b0y11得到线性模型w1xb1 3x(1)3x(2)1(3)返回(2)继续寻找yi(w·xib)≤0的点更新w,b。直到对于所有的点yi(w·xib)0没有误分类点损失函数达到最小。分离超平面为x(1)x(2)-30感知机模型为 f(x)sign(x(1)x(2)-3)在迭代过程中出现w·xib-2此时取任意一个点都会是其小于0不同的取值顺序会导致最终的结果不同因此解并不是唯一的。为了得到唯一的超平面需要对分离超平面增加约束条件这就是支持向量机的想法。实现代码importosimportsys#An example in that book, the training set and parameters sizes are fixedtraining_set []w[]b0lens0n0#update parameters using stochastic gradient descentdefupdate(item):globalw, b, lens, nfor i inrange(lens):w[i] w[i] n * item[1] *item[0][i]b b n * item[1]print w, b #you can uncomment this line to check the process of stochastic gradient descent#calculate the functional distance between item an the dicision surfacedefcal(item):globalw, bres0for i inrange(len(item[0])):res item[0][i] *w[i]resbres* item[1]returnres#check if the hyperplane can classify the examples correctlydefcheck():flagFalsefor item intraining_set:if cal(item) 0:flagTrueupdate(item)if not flag: #Falseprint RESULT: w: str(w) b:str(b)tmp for keys inw:tmp str(keys) tmptmp.strip()modelFile.write(tmp \n)modelFile.write(str(b) \n)modelFile.write(str(lens) \n)modelFile.write(str(n) \n)modelFile.close()os._exit(0)flagFalseif __name____main__:if len(sys.argv) ! 4:print Usage: python perceptron.py n trainFile modelFileexit(0)n float(sys.argv[1])trainFile file(sys.argv[2])modelFile file(sys.argv[3], w)lens0for line intrainFile:chunk line.strip().split( )lens len(chunk) - 1tmp_all[]tmp[]for i in range(1, lens1):tmp.append(int(chunk[i]))tmp_all.append(tmp)tmp_all.append(int(chunk[0]))training_set.append(tmp_all)trainFile.close()for i inrange(lens):w.append(0)for i in range(1000):check()print The training_set is not linear separable.View Code3.2 感知机学习的对偶形式对偶形式的基本想法是将w,b表示成为实例xi和标记yi的线性组合的形式通过求解其系数而得到w和b。不失一般性将初始值w0,b0设为0.对误分类点(xi,yi)通过w w ηyixib b ηyi的转换逐步修该w,b设修改了n次则w,b关于(xi,yi)的增量分别为aiyixi和aiyi这里ainiη最终学习到的w,b可以表示为实例点更新次数越多意味着它距离分离超平面越近也就越难正确分类。换句话说这样的实例对学习结果影响很大。算法(感知机学习算法的对偶形式)输入T{(x1,y1),(x2,y2)...(xN,yN)}(其中xi∈XRnyi∈Y{-1, 1}i1,2...N学习速率为η)输出a,b;感知机模型f(x)sign(w·xb)(1) 初始化w0,b0(2) 在训练数据集中选取(xi, yi)(3) 如果ai ai ηb b ηyi(4) 转至(2)对偶形式中训练数据仅以内积的形式出现为了方便可以预先把训练数据间内积计算出来并以矩阵的形式存储起来这个矩阵就是所谓的Gram矩阵。实现代码importosimportsys#An example in that book, the training set and parameters sizes are fixedtraining_set []w[]a[]b0lens0n0Gram[]defcalInnerProduct(i, j):globallensres0for p inrange(lens):res training_set[i][0][p] *training_set[j][0][p]returnresdefAddVector(vec1, vec2):for i inrange(len(vec1)):vec1[i] vec1[i] vec2[i]returnvec1defNumProduct(num, vec):for i inrange(len(vec)):vec[i]*numreturnvecdefcreateGram():globallensfor i inrange(len(training_set)):tmp[]for j inrange(0, len(training_set)):tmp.append(calInnerProduct(i, j))Gram.append(tmp)#update parameters using stochastic gradient descentdefupdate(k):globala, b, na[k]nb b n * training_set[k][1]print a, b #you can uncomment this line to check the process of stochastic gradient descent#calculate the functional distance between item an the dicision surfacedefcal(k):globala, bres0for i inrange(len(training_set)):res a[i] * int(training_set[i][1]) *Gram[i][k]resbres* training_set[k][1]returnres#check if the hyperplane can classify the examples correctlydefcheck():globalw, aflagFalsefor i inrange(len(training_set)):if cal(i) 0:flagTrueupdate(i)if not flag: #Falsefor i inrange(len(training_set)):w AddVector(w, NumProduct(a[i] * int(training_set[i][1]), training_set[i][0]))print RESULT: w:, w, b:, btmp for keys inw:tmp str(keys) tmptmp.strip()modelFile.write(tmp \n)modelFile.write(str(b) \n)modelFile.write(str(lens) \n)modelFile.write(str(n) \n)modelFile.close()os._exit(0)flagFalseif __name____main__:if len(sys.argv) ! 4:print Usage: python perceptron_duality.py n trainFile modelFileexit(0)n float(sys.argv[1])trainFile file(sys.argv[2])modelFile file(sys.argv[3], w)lens0for line intrainFile:chunk line.strip().split( )lens len(chunk) - 1tmp_all[]tmp[]for i in range(1, lens1):tmp.append(int(chunk[i]))tmp_all.append(tmp)tmp_all.append(int(chunk[0]))training_set.append(tmp_all)trainFile.close()createGram()for i inrange(len(training_set)):a.append(0)for i inrange(lens):w.append(0)for i in range(1000):check()print The training_set is not linear separable.View Code4. GitHub地址
