{"id":478,"date":"2016-01-30T20:33:00","date_gmt":"2016-01-30T12:33:00","guid":{"rendered":"http:\/\/note.systw.net\/note\/?p=478"},"modified":"2023-11-02T20:36:05","modified_gmt":"2023-11-02T12:36:05","slug":"pla","status":"publish","type":"post","link":"https:\/\/systw.net\/note\/archives\/478","title":{"rendered":"PLA"},"content":{"rendered":"\n

1.\u5047\u8a2d
X={x1(\u7dad\u5ea61\u7684\u503c), x2(\u7dad\u5ea61\u7684\u503c)}
W={w1(\u7dad\u5ea61\u6b0a\u91cd),w2(\u7dad\u5ea62\u6b0a\u91cd)}
\u800c\u4e14\u4ee5\u4e0b\u689d\u4ef6\u53ef\u4ee5\u5224\u65b7allow\u548cdeny
if x1*y1+x2*y2 > threshold:
\u3000allow
else:
\u3000deny<\/p>\n\n\n\n

2.\u4e0a\u8ff0\u53ef\u5b9a\u7fa9\u4ee5\u4e0b
(W^T)*(X) > threshold, allow
(W^T)*(X) < threshold, deny<\/strong>
=\u4ee5\u4e0b
h(X)=sign( (W^T)*(X) – threshold )<\/strong>
sign\u8868\u793a\u53d6\u5f97\u6b63\u6216\u8ca0\u7684\u7d50\u679c
\u82e5h(X)\u70ba\u6b63,\u8868\u793a\u6709\u904ethreshold,allow
\u82e5h(X)\u70ba\u8ca0,\u8868\u793a\u6c92\u904ethreshold,deny
ps:
h\u4e5f\u7a31\u70baperceptron
ps:
inner product=x1*y1+x2*y2+….xn*yn,\u9019\u88e1\u4ee5\u7b26\u865f(X^T)*(Y)\u8868\u793a
\u3000<\/p>\n\n\n\n

3
\u5c07\u539f\u672c\u7684X\u591a\u52a0\u4e00\u500b\u7dad\u5ea6\uff0c\u6b64\u503c\u6c38\u9060\u70ba+1
\u5c07\u539f\u672c\u7684W\u591a\u52a0\u4e00\u500b\u7dad\u5ea6\uff0c\u6b64\u503c\u70ba\u8ca0\u7684threshold
\u6240\u4ee5X\u548cW\u6703\u8b8a\u6210\u4ee5\u4e0b
X={x0(+1),x1(\u7dad\u5ea61\u7684\u503c), x2(\u7dad\u5ea61\u7684\u503c)}
W={w0(-threshold),w1(\u7dad\u5ea61\u6b0a\u91cd),w2(\u7dad\u5ea62\u6b0a\u91cd)}
\u6240\u4ee5\u516c\u5f0f(\u5f9estep2\u5f97\u5230)
h(X)=sign( (W^T)*(X) – threshold )
\u6703\u8b8a\u6210\u4ee5\u4e0b
h(X)=sign( (W^T)*(X) + (-threshold)*(+1) )<\/strong><\/p>\n\n\n\n

4
\u7531\u65bcw0\u548cx0\u90fd\u5728W,X\u5167\uff0c\u53ef\u4e00\u8d77\u7528inner product\u8868\u793a
w0=(-threshold)
x0=(+1)
\u6240\u4ee5\u516c\u5f0f(\u5f9estep3\u5f97\u5230)
h(X)=sign( (W^T)*(X) + (-threshold)*(+1) )<\/strong>
\u53ef\u5316\u6e1b\u70ba\u4ee5\u4e0b
h(X)=sign( (W^T)*(X) )<\/strong>
\u82e5h(X)\u70ba+1,\u6709\u904ethreshold
\u82e5h(x)\u70ba-1 ,\u6c92\u904ethreshold
=\u4ee5\u4e0b
h(x)=sign(w0x0+w1x1+w2x2)<\/strong>
ps:
\u622a\u8ddd\u516c\u5f0f: (-1)+X*(1\/A)+Y*(1\/B)=0
ps:
x \u5c0d\u61c9\u5230\u4e00\u500b\u9ede
y \u5c0d\u61c9\u5230\u7d50\u679c 1or0
h(hypothesis) \u5c0d\u61c9\u5230\u7dda<\/p>\n\n\n\n

………………………………………………………………..\uff0e<\/p>\n\n\n\n

perceptrons learning algorithm<\/strong><\/p>\n\n\n\n

H=all possible perceptrons
\u76ee\u6a19: \u8981\u5f9eH\u4e2d\u627e\u51fa\u4e00\u689dg, \u800cg\u53ef\u4ee5\u7528\u4e00\u689d\u7dda\u505a\u70ba1\u548c0\u754c\u7dda<\/p>\n\n\n\n


Algorithm<\/strong>
1
\u5148\u8b93 g0\u70ba \u958b\u59cb\u7684\u7b2c\u4e00\u689d\u7dda
\u4e26\u8b93g0=W
2. Cyclic PLA,
for data in X: \u628a\u6240\u6709\u9ede\u653e\u9032\u53bb\u6aa2\u67e5
if ismistake(W,data): \u82e5\u9019\u500b\u9ede\u4e0d\u5c0d
w=correct(data) \u66f4\u65b0
return w
\u5b8c\u6210\u5f8c\u5f97\u5230W of Perceptron Learning Algorithm<\/p>\n\n\n\n

ismistake() \u6aa2\u67e5\u9019\u500b\u9ede\u662f\u5426\u6709\u932f<\/strong>
sign[ ((W^T)*Xn) ] != Yn<\/p>\n\n\n\n

correct() \u6839\u64da\u932f\u8aa4\u8abf\u6574\u659c\u7387<\/strong>
\u8981\u6b63\u7684,\u4f46\u7d50\u679c\u662f\u8ca0\u7684, \u8868\u793a\u89d2\u5ea6\u592a\u5927, \u628a\u4ed6\u8f49\u5c0f\u63a5\u8fd1X, W+(+1)*X
\u8981\u8ca0\u7684,\u4f46\u7d50\u679c\u662f\u6b63\u7684, \u89d2\u5ea6\u592a\u5c0f, \u628a\u4ed6\u8f49\u958b\u9060\u96e2X, W+(-1)*X

\u66f4\u65b0\u539f\u5247<\/strong>
\u5047\u8a2d\u4ee5\u4e0b\u5169\u7a2e \u9edex \u5206\u932f\u7684\u60c5\u6cc1
1.\u5b83\u662f\u985e\u52251\uff0c\u4f46\u537b\u88ab\u5206\u5728\u985e\u52252,\u9019\u4ee3\u8868 wt \u5411\u91cf\u8207 x \u4e4b\u9593\u7684\u593e\u89d2\u592a\u5927\uff0c
\u6240\u4ee5\u8981\u8b93\u5b83\u5011\u4e4b\u9593\u7684\u593e\u89d2\u8b8a\u5c0f\uff0c\u53ef\u7528\u5411\u91cf\u76f8\u52a0\u7684\u65b9\u5f0f\u4f86\u505a\u5230, \u53ef\u900f\u904eW+(+1)*X\u5f97\u5230\u65b0\u7684W
2.\u5b83\u662f\u985e\u5225 2\uff0c\u4f46\u537b\u88ab\u5206\u5728\u985e\u52251,\u9019\u4ee3\u8868 wt \u5411\u91cf\u8207 x \u5411\u91cf\u4e4b\u9593\u7684\u593e\u89d2\u592a\u5c0f\uff0c
\u6240\u4ee5\u8981\u8b93\u4ed6\u5011\u4e4b\u9593\u7684\u593e\u89d2\u8b8a\u5927\uff0c\u53ef\u7528 wt \u5411\u91cf\u6e1b\u6389 x \u5411\u91cf\u4f86\u505a\u5230, \u53ef\u900f\u904eW+(-1)*X\u5f97\u5230\u65b0\u7684W<\/p>\n\n\n\n

refer
http:\/\/wizmann.tk\/ml-foundations-pla.html
http:\/\/shaoxiongjiang.com\/2013\/03\/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E5%85%A5%E9%97%A8-%E6%84%9F%E7%9F%A5%E5%99%A8-perceptron\/
http:\/\/cpmarkchang.logdown.com\/posts\/189108-machine-learning-perceptron-algorithm<\/p>\n\n\n\n

…….<\/p>\n\n\n\n

linear and non-linear separable<\/strong>
linear separable\u8868\u793a\u4e0d\u540c\u7684\u8cc7\u6599\u7d50\u679c\u53ef\u4ee5\u7528\u4e00\u689d\u7dda\u5206\u958b
\u6240\u4ee5\u7576\u627e\u5230\u9019\u689d\u7dda,PLA\u5c31\u6703\u505c\u4e0b\u4f86
non-linear separable\u8868\u793a\u4e0d\u540c\u7684\u8cc7\u6599\u7d50\u679c\u7121\u6cd5\u7528\u4e00\u689d\u7dda\u5206\u958b
\u5728\u6b64\u60c5\u6cc1\u4e0b, \u7121\u6cd5\u627e\u5230\u4e00\u689d\u5b8c\u7f8e\u7684\u7dda(\u7121\u72af\u932f\u7684\u7dda)
\u82e5\u8981\u89e3\u6c7a\u6b64\u8fa6\u6cd5,\u5c31\u8981\u9000\u800c\u6c42\u5176\u6b21
\u627e\u4e00\u689d\u72af\u7684\u932f\u6700\u5c0f\u7684\u7dda
ps:
Off-Training-Set error is used for estimating how your hypothesis perform on the dataset which is not used in training<\/p>\n\n\n\n


modify PLA algorithm\/Pocket Algorithm<\/strong>
\u6bcf\u8dd1\u4e00\u6b21,\u5c31\u7b97\u4e00\u4e0b\u7dda\u7684\u5206\u6578,
\u4e0d\u65b7\u7684\u8dd1,\u82e5\u4e0b\u4e00\u6b21\u7dda\u7684\u5206\u6578\u8f03\u597d,\u5247\u4f7f\u7528\u6b64\u7dda
\u8dd1N\u6b21\u5f8c,\u770b\u6700\u5f8c\u662f\u90a3\u4e00\u689d\u7dda
ps:
modify PLA algorithm \u6703\u6bd4 PLA \u6162, \u56e0\u70ba\u6703\u505a\u8f03\u591a\u4e8b\u6240\u4ee5\u7528\u8f03\u591a\u8cc7\u6e90\u800c\u8b8a\u6162<\/p>\n\n\n\n

…………….<\/p>\n\n\n\n

example for python<\/strong><\/p>\n\n\n\n

#vi file.csv<\/strong>
-1,8,9
-1,7,8
1,1,2
1,3,4<\/p>\n\n\n\n

#vi pla.py<\/strong><\/p>\n\n\n\n

rawdata=loadtxt('file.csv', delimiter=',')\nfeature=rawdata[:,1:]\ntag=rawdata[:,0]\ndatas=list()\nfor f1,t1 in zip(feature,tag):\n\u3000datas.append([f1,t1])\n\ndef pla(datas):\n\u3000w = datas[0][0]\n\u3000iteration = 0\n\u3000while True:\n\u3000\u3000iteration += 1\n\u3000\u3000false_data = 0\n\u3000\u3000for data in datas:\n\u3000\u3000\u3000t = dot(w, data[0])\n\u3000\u3000\u3000if sign(data[1]) != sign(t):\n\u3000\u3000\u3000\u3000error = data[1]\n\u3000\u3000\u3000\u3000false_data += 1\n\u3000\u3000\u3000\u3000w = w+error * data[0]\n\n\u3000\u3000print 'iter%d (%d \/ %d)' % (iteration, false_data, len(datas))\n\u3000\u3000if not false_data:\n\u3000\u3000\u3000break\n\u3000return w\npla(datas)\n<\/code><\/pre>\n\n\n\n
<\/p>\n\n\n\n
ps:
\u4ee5\u4e0aexample\u82e5\u9047\u5230non-linear separable\u4e0d\u6703\u81ea\u52d5\u505c\u4e0b\u4f86<\/p>\n","protected":false},"excerpt":{"rendered":"
1.\u5047\u8a2dX={x1(\u7dad\u5ea61\u7684\u503c), x2(\u7dad\u5ea61\u7684\u503c)}W= …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"","fifu_image_alt":"","_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[13],"tags":[],"class_list":["post-478","post","type-post","status-publish","format-standard","hentry","category-dataanalysis"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/478","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/comments?post=478"}],"version-history":[{"count":0,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/478\/revisions"}],"wp:attachment":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/media?parent=478"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/categories?post=478"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/tags?post=478"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}