Support Vector Machine¶

ក្នុងអត្ថបទមុនៗ យើងបានណែនាំអំពីការធ្វើចំណាត់ថ្នាក់ទិន្នន័យ២ឬច្រើនក្រុមដោយប្រើម៉ូឌែលតម្រែតម្រង់(Linear regression, Logistic regression)។ ប៉ុន្តែមានចំណុចខ្សោយសំខាន់ពីរកើតមានឡើងក្នុងការប្រើប្រាស់ម៉ូឌែលតម្រែតម្រង់ក្នុងការធ្វើចំណាត់ថ្នាក់ក្រុមទិន្នន័យ ដូចបង្ហាញក្នុងរូបទី១ខាងក្រោម។ ក្នុងរូបខាងឆ្វេង ដោយសារមានទិន្នន័យប្រមូលផ្តុំច្រើននៅផ្នែកខាងក្រុមក្រហម ម៉ូឌែលតម្រែតម្រង់លីនេអ៊ែរនឹងផ្តល់ឱ្យនូវបន្ទាត់ព្រំដែនដែលខិតទៅជិតក្រុមក្រហមខ្លាំង (បន្ទាត់ខៀវ)។ ប៉ុន្តែតាមពិតបន្ទាត់ព្រំដែនទឹកក្រូចអាចមើលឃើញថាល្អប្រសើរជាង។ ក្នុងករណីរូបកណ្តាលនិងរូបខាងស្តាំ ច្បាស់ណាស់ថា ទិន្នន័យទាំងនេះមិនអាចធ្វើការបែងចែកដោយបន្ទាត់ត្រង់បានឡើយ ពោលគឺជាប្រភេទដែលមិនអាចបែងចែកលីនេអ៊ែរ(linear non-seperable data)។

ដើម្បីដោះស្រាយបញ្ហាទាំងនេះ ការធ្វើចំណាត់ថ្នាក់ក្រុមទិន្នន័យដោយប្រើSupport Vector Machineត្រូវបានប្រើ។ ក្នុងអត្ថបទនេះយើងនឹងណែនាំអំពីដំណើរការគណិតវិទ្យាក្នុងការដោះស្រាយបញ្ហាធ្វើចំណាត់ថ្នាក់ក្រុម២ឬច្រើនក្រុមដោយប្រើSupport Vector Machine។ យើងនឹងពិនិត្យទាំងករណីទិន្នន័យដែលអាចធ្វើបំណែងចែកលីនេអ៊ែរបាន(Linear Seperable) និងមិនបាន(Linear Non- Seperable)។

SVM-1

ចំណាត់ថ្នាក់២ក្រុម¶

នៅទីនេះយើងសិក្សាលើទិន្នន័យពីរក្រុម $(+1,-1)$ $\mathcal{D}=\left\{\left(\pmb{x}_\pmb{i},y_i\right)\right\}_{i=1}^N$ ដែល $\pmb{x}_\pmb{i}\in\mathbb{R}^d\ ,\ y_i\in\left\{+1,-1\right\}$ ។ យើងចង់បង្កើតម៉ូឌែលចំណាត់ថ្នាក់ក្រុមមួយដែលធ្វើការបែងចែកតាមម៉ូឌែលលីនេអ៊ែរដែលតាងដោយទម្រង់ខាងក្រោម។

$\mathcal{M}=\left\{sign\left(f\left(\pmb{x}\right)\right)\ |\ f\left(\pmb{x}\right)=\pmb{w}^\top\pmb{x}+b\ ,\ \pmb{w}\in\mathbb{R}^d,b\in\mathbb{R}\right\}$

ក្នុងករណីដែលមាន $m\left(\pmb{x}\right)=sign\left(\pmb{w}^\top\pmb{x}+b\right)$ ដែលផ្ទៀងផ្ទាត់ $m\left(\pmb{x}_i\right)=y_i ∀ i=1,2,…,N$ នោះ ទិន្នន័យដែលមានហៅថា អាចធ្វើបំណែងចែកលីនេអ៊ែរបាន(Linear Seperable)។ ពោលគឺយើងអាចកំណត់បន្ទាត់ឬប្លង់ព្រំដែនដើម្បីបែងចែកទិន្នន័យទាំងពីរប្រភេទបានច្បាស់លាស់ដោយគ្មានកំហុសចំពោះគ្រប់ទិន្នន័យ។ ផ្ទុយទៅវិញ ករណីដែលមិនអាចរកបានម៉ូឌែលណាដែលផ្ទៀងផ្ទាត់លក្ខខណ្ឌខាងលើ យើងហៅថា មិនអាចធ្វើបំណែងចែកលីនេអ៊ែរបាន(Linear Non-Seperable)។

SVM-2

ករណីទិន្នន័យដែលអាចធ្វើបំណែងចែកលីនេអ៊ែរបាន(Linear Seperable)¶

ក្នុងករណីទិន្នន័យដែលអាចធ្វើបំណែងចែកលីនេអ៊ែរបាន ចំពោះទិន្នន័យ $\mathcal{D}=\left\{\left(\pmb{x}_\pmb{i},y_i\right)\right\}_{i=1}^N$ យើងអាចសរសេរទំនាក់ទំនងខាងក្រោមបាន

$y_i=+1\ \Longrightarrow\ \ \pmb{w}^\top\pmb{x}_i+b>0$

$y_i=-1\ \Longrightarrow\ \ \pmb{w}^\top\pmb{x}_i+b<0$

ឬ ជារួម

$y_i\left(\pmb{w}^\top\pmb{x}_i+b\right)>0\ \ \left(i=1,2,\ldots,N\right)$

ជាទូទៅ តម្លៃនៃប៉ារ៉ាម៉ែត្រ $\left(\pmb{w},b\right)$ ដែលផ្ទៀងផ្ទាត់លក្ខខណ្ឌខាងលើមានច្រើនលើសពីមួយ។ ក្នុងចំណោមនោះ ដើម្បីជ្រើសបានប៉ារ៉ាម៉ែត្រដែលប្រសើរ គោលគំនិតក្នុង Support Vector Machine គឺកំណត់យកករណីដែលតម្រឹម(margin)នៃទិន្នន័យនិងព្រំដែនមានទំហំធំបំផុត។ ការកំណត់តម្រឹម(margin)ដែលធំបំផុតនៅទីនេះ គឺសំដៅដល់ការយកប៉ារ៉ាម៉ែត្រណាដែលធ្វើឱ្យចន្លោះរវាងទិន្នន័យទាំងពីរក្រុមនិងបន្ទាត់(ឬប្លង់)ព្រំដែនមានគម្លាតឆ្ងាយពីគ្នាបំផុត(រូបទី៣)។

SVM-3

យើងនឹងបង្ហាញបញ្ហាខាងលើជាទម្រង់គណិតវិទ្យា។ សន្មតបន្ទាត់ឬប្លង់ព្រំដែនមានទម្រង់ដូចម៉ូឌែលខាងលើ $\pmb{w}^\top\pmb{x}+b=0$ ។ ចម្ងាយពីចំណុច $\pmb{x}_0\in\mathbb{R}^d$ ទៅព្រំដែនអាចកំណត់បានដូចខាងក្រោម។

$\frac{|\pmb{w}^\top \pmb{x}_0 + b|}{||\pmb{w}||}$

ហេតុនេះ ការកំណត់ប៉ារ៉ាម៉ែត្រ $\left(\pmb{w},b\right)$ ដែលធ្វើឱ្យតម្រឹមអតិបរមាអាចកំណត់បានជាចំណោទបរមាដូចខាងក្រោម។

$\underset{\pmb{w}\in\mathbb{R}^d, b\in\mathbb{R}}{\max} \underset{\{i=1,\cdots,N\}}{\min}\frac{|\pmb{w}^\top \pmb{x}_i+b|}{\left \| \pmb{w} \right \|}$

ក្រោមលក្ខខណ្ឌ

$y_i\left(\pmb{w}^\top\pmb{x}_i+b\right)>0\ \ \left(i=1,2,\ldots,N\right)$

ចំណោទបរមាខាងលើអាចសរសេរជាទម្រង់សមមូលបែបងាយដូចខាងក្រោមបានដោយសារតែអនុគមន៍គោលដៅដែលត្រូវធ្វើបរមាកម្មមិនប្រែប្រួលតម្លៃឡើយពេល $\pmb{w},b$ ត្រូវបានគុណនឹងចំនួនថេរក៏ដោយ។

$\underset{\{i=1,\cdots,N\}}{\min}\frac{\left \| \pmb{w} \right \|^2}{2}$

ក្រោមលក្ខខណ្ឌ

$y_i\left(\pmb{w}^\top\pmb{x}_i+b\right)>0\ \ \left(i=1,2,\ldots,N\right)$

អនុគមន៍គោលដៅខាងលើមានទម្រង់ជាអនុគមន៍ប៉ោងដឺក្រេទី២ ហើយលក្ខខណ្ឌរបស់វាដែលត្រូវផ្ទៀងផ្ទាត់មានទម្រង់ជាលីនេអ៊ែរ។ ចំណោទបរមាបែបនេះហៅថាចំណោទប្រូក្រាមលំដាប់២(QP:Quadratic Programming)។ ក្នុងការដោះស្រាយចំណោទបែបនេះមានalgorithmដែលមានប្រសិទ្ធិភាពខ្ពស់ជាច្រើនត្រូវបានស្រាវជ្រាវ។នៅទីនេះយើងនឹងមិនធ្វើការបកស្រាយលំអិតឡើយ។ សន្មតថាចម្លើយនៃចំណោទបរមាខាងលើគឺ $\hat{\pmb{w}}\in\mathbb{R}^d,\hat{b}\in\mathbb{R}$ នោះការធ្វើចំណាត់ថ្នាក់ក្រុមទិន្នន័យអាចធ្វើបានដោយគណនាតាមទម្រង់ខាងក្រោម។

$\hat{m}\left(\pmb{x}\right)=sign\left({\hat{\pmb{w}}}^\top\pmb{x}+\hat{b}\right)$

ជាមួយPython អ្នកអាចប្រើ sklearn.svm packageបានប្រើSupport Vector Machine Model។

from sklearn.svm import SVC,LinearSVC
sv_model = SVC(kernel="linear", C=1.0, random_state=1)
sv_model.fit(Xtrain,ytrain)

SVM-4

ករណីទិន្នន័យដែលអាចធ្វើបំណែងចែកលីនេអ៊ែរបាន(Linear Seperable)¶

ក្នុងករណីដែលទិន្នន័យមិនអាចធ្វើបំណែងចែកលីនេអ៊ែរបាន ចំណោទបរមាខាងលើគ្មាន តម្លៃប៉ារ៉ាម៉ែត្រណាដែលផ្ទៀងផ្ទាត់លក្ខខណ្ឌឡើយ។ ហេតុនេះដើម្បីដោះស្រាយបញ្ហាបំណែងចែកបែបនេះករណីកំហុស(មិនបំពេញលក្ខខណ្ឌ $y_i\left(\pmb{w}^\top\pmb{x}_i+b\right)>0 \left(i=1,2,\ldots,N\right)$ )ក្នុងបំណែងចែកខ្លះត្រូវបានលើកលែង។ដំណោះស្រាយបែបនេះហៅថា Soft Support Vector Machine។

នៅទីនេះដោយប្រើម៉ូឌែលបំណែងចែក $m\left(\pmb{x}\right)=sign\left(\pmb{w}^\top\pmb{x}+b\right)$ ករណីទិន្នន័យ $\left(\pmb{x}_i,y_i\right)$ តម្លៃនៃការពិន័យ(Loss)លើកំហុសនៃចំណាត់ថ្នាក់ក្រុមត្រូវបានកំណត់ដូចខាងក្រោម។

ចំពោះ $y_i\left(\pmb{w}^\top\pmb{x}_i+b\right)\geq1$ យើងសន្មតថាម៉ូឌែលអាចបែងចែកបានល្អ ដោយកំណត់តម្លៃពិន័យ $0$
ចំពោះ $y_i\left(\pmb{w}^\top\pmb{x}_i+b\right)<1$ យើងសន្មតថាម៉ូឌែលអាចបែងចែកមិនបានល្អដោយកំណត់តម្លៃនៃ ពិន័យ $1-y_i\left(\pmb{w}^\top\pmb{x}_i+b\right)>0$

ក្នុងករណីនេះដើម្បីកំណត់ប៉ារ៉ាម៉ែត្រដែលប្រសើរសម្រាប់ធ្វើចំណាត់ថ្នាក់ក្រុមជាមួយSoft Support Vector Machine យើងនឹងកំណត់តម្លៃប៉ារ៉ាម៉ែត្រណាដែលធ្វើឱ្យតម្រឹមធំបំផុត តែកម្រិតពិន័យ (Loss)តូចបំផុត។ យើងអាចបង្ហាញបញ្ហានេះជាទម្រង់ចំណោទបរមាបានដូចខាងក្រោម។

$\underset{\pmb{w}\in\mathbb{R}^d,b\in\mathbb{R}}{\min}{\frac{C}{N}\sum_{i=1}^{N}\max{\left\{1-y_i\left(\pmb{w}^\top\pmb{x}_i+b\right)\ ,\ 0\right\}}+\frac{1}{2}}||w||^2$

$C$ ជាតម្លៃសម្រាប់កំណត់កម្រិតនៃការផ្តោតលើបរមាកម្មរវាងតម្រឹម(margin)និងពិន័យ(loss)។ នៅទីនេះដូចដែលអ្នកអាចចាប់អារម្មណ៍បាន ការកំណត់តម្លៃ $C$ ជារឿងពិបាក។ វិធីដែលច្រើនអនុវត្តគឺការធ្វើ Cross-validation ។ យើងនឹងមិនលំអិតលើវិធីសាស្រ្តនេះឡើយនៅទីនេះ។

SVM-7

SVM-8

តាមលទ្ធផលក្នុងរូបខាងលើ យើងអាចផ្ទៀងផ្ទាត់ពីការធ្វើបំណែងចែកក្រុមបានល្អប្រសើរក្នុងករណីប្រើSoft Support Vector Machine ប្រើប្រៀបធៀបទៅនឹងម៉ូឌែលតម្រែតម្រង់ដែលបានសិក្សាកន្លងមក។ប៉ុន្តែទោះជាយ៉ាងណា ករណីទិន្នន័យដែលមិនអាចធ្វើបំណែងចែកលីនេអ៊ែរបាន កម្រិតត្រឹមត្រូវនៃការធ្វើចំណាត់ថ្នាក់ក្រុមនៅមានកម្រិតទោះបីជាប្រើSoft Support Vector Machineក្តី។

Kernel Support Vector Machine¶

ក្នុងករណីដែលទិន្នន័យមិនអាចបែងចែកលីនេអ៊ែរបាន ការប្រើKernelជាជំនួយត្រូវបាន អនុវត្តជាទូទៅ។ ជាមួយការប្រើប្រាស់Kernel សមត្ថភាពនៃការបង្ហាញលក្ខណៈពិសេសរបស់ទិន្នន័យនឹងត្រូវបានបង្កើន។ កាលពីសិក្សាពីម៉ូឌែលតម្រែតម្រង់ យើងបានលើកឡើងអំពីការប្រើអនុគមន៍គោលដែលជាអនុគមន៍មិនលីនេអ៊ែរដើម្បីបង្ហាញលក្ខណៈពិសេសរបស់ទិន្នន័យមួយចំនួន។

ស្រដៀងគ្នានេះជាមួយគោលគំនិតក្នុងការប្រើKernel ឧបមាថាយើងមានអនុគមន៍គោល $\varphi_1\left(\pmb{x}\right),\varphi_2\left(\pmb{x}\right),\ldots,\varphi_D\left(\pmb{x}\right)$ នោះអនុគមន៍Kernel ត្រូវបានកំណត់ដូចខាងក្រោម ដែលនៅទីនេះ $\Phi\left(\pmb{x}\right)=\left(\begin{matrix}\varphi_1\left(\pmb{x}\right)&\cdots&\varphi_D\left(\pmb{x}\right)\\\end{matrix}\right)^\top$ ។

$k\left(\pmb{x},\pmb{x}^\prime\right)=\sum_{d=1}^{D}{\varphi_d\left(\pmb{x}\right)\varphi_d\left(\pmb{x}\prime\right)}=\Phi\left(\pmb{x}\right)^\top\Phi\left(\pmb{x}\prime\right)$

ក្នុងករណីនេះ ទម្រង់នៃ ម៉ូឌែលចំណាត់ថ្នាក់ក្រុមនិងបន្ទាត់ឬប្លង់ព្រំដែនអាចបង្ហាញដូចទម្រង់ខាងក្រោម ដោយសន្មតយក $\pmb{\beta}=\left(\begin{matrix}\beta_1&\cdots&\beta_n\\\end{matrix}\right)^\top$ ជំនួស $\pmb{w}$ ។

$f\left(\pmb{x}\right)=\pmb{w}^\top\Phi\left(\pmb{x}\right)+b$

$f\left(\pmb{x}\right)=\sum_{i=1}^{N}{\beta_ik\left(\pmb{x},\pmb{x}_i\right)}+b$

ដូចគ្នានឹងករណីទូទៅនៃSupport Vector Machine ដែរ ក្នុងករណី Kernel Support Vector Machine បញ្ហាខាងលើអាចបង្ហាញជាទម្រង់ចំណោទបរមាដូចខាងក្រោម។

$\underset{\pmb{\beta},b}{\min}{\frac{C}{N}\sum_{i=1}^{N}\max{\left\{1-y_if\left(\pmb{x}_i\right)\ ,\ 0\right\}}+\frac{1}{2}}\pmb{\beta}^\top K\pmb{\beta}$

ក្រោមលក្ខខណ្ឌ

$f\left(\pmb{x}_i\right)=\sum_{j=1}^{N}{\beta_iK_{ij}}+b\ \ \left(i=1,2,\ldots,N\right)$

ដែល $K_{ij}=k\left(\pmb{x}_i,\pmb{x}_j\right)$ ។

ជាមួយPython អ្នកអាចជ្រើសរើសប្រភេទ Kernel ដែលនិយមប្រើដូចជា: លីនេអ៊ែរ linear , ពហុធា poly , Gaussian Kernel: rbf , Sigmoid Kernel: sigmoid ។

from sklearn.svm import SVC

sv_model = SVC(kernel="rbf", C=1.0, random_state=1)
sv_model.fit(Xtrain,ytrain)

SVM-9

SVM-10

Machine Learning

Support Vector Machine¶

ចំណាត់ថ្នាក់២ក្រុម¶

ករណីទិន្នន័យដែលអាចធ្វើបំណែងចែកលីនេអ៊ែរបាន(Linear Seperable)¶

ករណីទិន្នន័យដែលអាចធ្វើបំណែងចែកលីនេអ៊ែរបាន(Linear Seperable)¶

Kernel Support Vector Machine¶