Pagkilala ng padron

Ang pagkilala ng padron (Ingles: pattern recognition) ang pagtatalaga ng ilang mga uri ng output o tatak(label) sa isang naibigay na mga input (o halimbawa), ayon sa ilang mga tiyak na algoritmo. Ang isang halimbawa ng pagkilala ng padron ay klasipikasyon na nagtatangkang italaga ang bawat input sa isa sa mga ibinigay na hanay ng mga klase (halimbawa, upang matukoy kung ang isang naibigay na email ay "spam" o "hindi spam"). Gayunpaman, ang pagkilala ng padron ay isang pangkalahatang problema na sumasaklaw sa iba pang mga uri ng output. Ilang halimbawa nito ay regresyon na nagtatalaga ng isang output sa bawat input; sunod sunod na pagtatak na nagtatalaga ng isang klase sa bawat kasapi ng isang sunod-sunod na mga halaga (halimbawa, ang pagtukoy ng konteksto ng mga bahagi ng pananalita, na nagtatalaga ng isang bahagi ng pananalita sa bawat salita sa isang input pangungusap); at parsing, na nagtatalaga ng isang punong parse sa isang input na pangungusap input, na naglalarawan sa sintaktika na istraktura ng pangungusap.

Buod

Ang pagkilala ng padron ay pangkalahatang inuuri ayon sa uri ng pamamaraang pagkatutuo na ginagamit upang lumikha ng halaga ng output. Ang mga pinagtnubayan pagkatuto ay nagpapalagay na ang isang hanay ng mga sinasanay na data(training set) ay ibinigay na binubuo ng isang hanay ng mga instansiya na angkop na tinatakan(labelled) ng kamay na may tamang output. Ang isang pamamaraang pagkatuto ay lumilikha ng modelo na nagtatangkang pagtagpuin ang dalawa na minsan ay magkakasalungat na mga layunin: Magsagawa ng mahusay hangga't maaari sa sinasanay na data at lahatin din hangga't maaari sa mga bagong data (karaniwan ay nangangahulugan itong bilang simple hangga't maaari sa isang teknikal na depinisyon ng simple ayon sa Labaha ni Occam. Ang hindi pinapatnubayang pagkatuto sa kabilang dako ay nagpapalagay na ang data ay hindi tinatakan ng kamay at nagtatangkang hanapin ang mga likas na padron sa data na maaaring gamitin upang tukuyin ang tamang halagang output para sa mga bagong instansiya ng data. Ang isang kombinasyon ng dalawang ito na kamakailan sinuri ang kalahating-pinapatunubayan na pagkatuto na gumagamit ng kombinasyon ng mga tinatakan(labeled) at hindi tinatakan(unlabeled) na tipikal ay isang maliit na hanay ng tinatakang mga datos na sinamahan ng isang malaking halaga ng hindi tinatakang mga datos. Dapat tandaan na sa mga kaso ng hindi pinapatnubayang pagkatuto, maaaring walang sinasanay na data na maaaring salitaan. sa ibang salita, ang data na tatatakan ang sinasanay na data.

Dapat din tatakan na minsan ang iba't ibang mga termino ay ginagamit upang ilarawan ang tumutugong pinapatnubayan at hindi pinapatnubayang pamamaraan ng pagkatuto para sa parehong uri ng output. Halimbawa, ang hindi pinapatnubayang katumbas ng klasipikasyon ay normal na tinatawag na pagkukumpol batay sa karaniwang persepsiyon ng trabaho na sumasangkot sa walang data na sasalitan at ng pagpapangkat ng mga input na data sa mga kumpol batay sa ilang mga likas na sukat ng pagkakatulad(e.g. ang distansiya sa pagitan ng mga instansiya na tinuturing na mga bektor sa isang [[multi-dimensiyonal na espasyong bektor) kesa sa pagtatakda ng bawat instansiya ng input sa isang hanay ng paunang inilarawan na mga klase. Dapat tandaan na sa ilang mga larangan, ang terminolohiya ay iba. Halimbawa, sa ekolohiya ng pamayanan, ang terminong klasipikasyon ay ginagamit upang tukuyin ang karaniwang alam na pagkukumpol.

Ang pirasa ng input na data kung saan ang halagang output ay nililikhay ay pormal na tinatawag na instansiya. Ang instansiya ay pormal na inilalarawan bilang isang bektor ng mga katangian(features) na kung pagsasamahin ay bumubuo sa deskripsiyon ng lahat ng alam na mga katangian ng instansiya. Ang mga feature na bektor na ito ay maaaring makita na naglalarawan ng mga punto sa isang angkop na multidimensiyonal na espasyo at ang mga pamamaraan sa pagmamanipula ng mga bektor sa mga espasyong bektor ay maaaring ilapat sa kanila bilang pagkukwenta ng produktong tuldok o ang anggulo sa pagitan ng dalawang mga bektor. Sa karaniwan, ang mga feature ay maaring kategorikal(o nominal na binubuo ng isang hanay ng hindi inaayos na item gaya ng kasarian na "lalake" o "babae" o uri ng dugo na "A", "B", "AB" o "O"); ordinal na binubuo ng isang hanay ng inaayos na mga item gaya ng "malaki", "medium", "maliit"; may halagang intedyer gaya ng bilang ng mga pag-iral ng isang partikular na salita sa emali; o may halagang real na bilang gaya ng sukat ng presyon ng dugo. Kalimitan, ang kategorikal at ordinal na mga datos(data) ay pinapangkat ng magkakasama gayundin sa mga may halagang intedyer at real na bilang. Sa karagdagan, maraming mga algoritmo ay gumagana lamang sa mga termino ng kategorikal na data at nangangailangan na ang may halagang intedyer o real na bilang ay i-diskretisa(discretized o hindi tuloy tuloy) sa mga pangkat(e.g. mas maliit sa lima, sa pagitan ng 5 at 10, o mas malaki sa 10).

Maraming mga karaniwang algoritmo ng pagkilala ng padron ay probabilistiko sa kalikasan dahil sa ang mga ito ay gumagamit ng inperensiyan estadistikal upang hanapin ang pinamahusay na tatak para sa isang ibinigay na instansiya. Hindi tulad ng ibang mga algoritmo na simple naglalabas(output) ng pinakamahusay na tatak, kalimitan ang mga probabalistikong algoritmo ay naglalabas din ng probabilidad ng instansiya na inilalarawan ng ibinigay na tatak. Sa karagdagan, maraming mga probabalistikong algoritmo ay naglalabasn ng isang talaan ng N-pinakamahusay na mga tatak na may kaugnay na probabilida para sa isang halagan ng N imbis na simpleng isang pinakamahusay na tatak. Kapaga ang bilang ng posibleng mga tatak ay medyo maliit(halimbawa sa kaso ng klasipikasyon), ang N ay maaaring itakda upang ang probalidad ng lahat ng mga posibleng tatak ay ilalabas. Ang mga probabalistikong algoritmo ay maraming mga kalamangan sa mga hindi probabilistikong algoritmo:

Ang mga ito ay naglalabas ng halagang konpidensiyang kaugnay ng kanilang mga pinili. Tandaan na ang ilang mga algoritmo ay maaari ring maglabas ng mga halagang konpidensiya ngunit sa pangkalatahan, tanging sa mga probabilistikong algoritmo ang halagang ito ay nakasalig ng matematikal sa teoriya ng probabilidad,. Ang mga hindi probabilistikong halagang konpidensiya ay sa pangkalatahan hindi maaaring ibigay sa anumang spesipikong kahulugan at tanging ginagmait upang ikumpara laban sa ibang mga halagang konpidensiyang output ng parehong algoritmo.
Kaakibat nito, ang mga ito ay maaaring umiwas kung ang konpidensiyang pinili ng anumang partikular na output ay labis na mababa.
Dahil sa mga output ng probabilida, ang mga probabilistikong algoritmo ng pagkilala ng padron ay maaaring mas epektibong isama sa mas malaking trabahong pagkatuto ng makina sa paraan sa isang bahagi o sa kabuuan ay umiiwas sa problema ng paglaganap ng pagkakamali.

Ang mga tekniko upang baguhin ang hilaw na mga bektor ng feature ay minsan ginagamit bago ang paglalapat ng tumutugma ng padronng algoritmo. Halimbawa, ang mga algoritmo ng pagkakatas ng feature ay nagtatangkang paliitin ang isang malaking dimensiyonalidad na bektor na feature sa mas maliit na dimensionalidad na bektor na mas madaling siyasatin at nag kokodigo ng mas hindi paulit ulit gamit ang mga teknika gaya ng analisis ng mga pangunahing bahagi(principal components analysis o PCA). Ang mga algoritmo ng pagpili ng feature ay nagtatangka na direktang alisin ang mga paulit ulit o walang kaugnayang mga feature o katangian. Ang distinksiyon sa pagitan ng dalawang ito ay ang nagreresultang feature pagkatapos na ang pagkakatas ng feature ay mangyari ay sa ibang uri kesa sa orihinal na mga feature ay maaaring mas hindi madaling pakahulugan, samantalang ang ibang mga feature na natira pagkatapos ng pagpili ng feature ay simpleng pang-ilalim na hanay ng mga orihinal na feature.

Problemang pangungusap(bersiyong pinapatnubayang pagkatuto)

Sa pormal na paglalarawan, ang problema ng pinapatnubayang pagkilala ng padron ay maaaring magsaad ng sumusunod: Sa isang ibinigay na hindi alam na punsiyon na $g:{\mathcal {X}}\rightarrow {\mathcal {Y}}$ (ang saligang katotohan) na nagmamapa ng mga instansiyang input na ${\boldsymbol {x}}\in {\mathcal {X}}$ sa mga tatak na output na $y\in {\mathcal {Y}}$ kasama ang sinasanay na data na $\mathbf {D} =\{({\boldsymbol {x}}_{1},y_{1}),\dots ,({\boldsymbol {x}}_{n},y_{n})\}$ na ipinagpalagay na kumakatawan sa mga tumpak na halimbawa ng pagmamapa, ay lumilikha ng punsiyong $h:{\mathcal {X}}\rightarrow {\mathcal {Y}}$ tumatantiya na pinakamalapit hangga't maaari ang tamang pagmamapang $g$ . (Halimbawa, kung ang problem ay pagsala ng spam, kung gayon ang ${\boldsymbol {x}}_{i}$ ay isang pagkakatawan ng email at ang $y$ ay "spam" o "hindi spam". Sa teoriyang desisyon, ito ay tinutukoy sa pagtukoy ng isang punsiyong kawalan na nagtatakda ng isang spesipikong halaga sa "kawalan" na nagreresulta sa paglikha ng maling tatak. Ang layunin kung gayon ay paliitin ang ekspektasyong kawalan na ang ekspektasyon ay kinuha sa distribusyong probablidad ng ${\mathcal {X}}$ . Sa pagsasanay, kahit ang distribusyon o ang punsiyon ng saligang katotohanang $g:{\mathcal {X}}\rightarrow {\mathcal {Y}}$ ay eksaktong alam ngunit maaari lamang empirikal na kwentahin sa pamamagitan ng pagtitipon ng isang malaking bilang ng mga sampol ng ${\mathcal {X}}$ at tatakan ng kamay ang mga ito gamit ang tamang halaga ng ${\mathcal {Y}}$ (ito ay isang matagal na proseso na tipikal ang paktor na naglilimita sa halaga ng data ng uring ito na maaaring tipunin). Ang partikular na punsiyong kawalan ay nakabatay sa uri ng tatak ng hinuhulaan. Halimbawa, sa kaso ng klasipikasyon, ang simpleng kawalang punsiyong sero-isa ay hindi sapat. Ito ay simpleng tumutugon sa pagtatakda ng isang kawalang 1 sa anumang hindi tamang pagtatatak at katumbas sa pagkukwenta ng pagiging tumpak ng pamamaraang klasipikasyon sa ibabaw ng isang hanay ng mga sinusubukang data(i.e. bibilangin ang praksiyon ng mga instansiya na ang natutunang punsiyon $h:{\mathcal {X}}\rightarrow {\mathcal {Y}}$ ay nagtatatak ng tama). Ang layunin ng pamamaraang pagkatuto ay upang palakihin ang sinsubukang pagiging tumpak sa isang tipikal na sinusubukang hanay.

Para sa isang probabilistikong tagakilala ng padron, ang problema ay bagkus upang tantiyahin ang probabilidad ng bawat posibleng tatak ng output sa isang ibinigay na partikular na instansiyang input, i.e., upang tantiyahin ang isang punsiyong nasa anyong

p({\rm {tatak}}|{\boldsymbol {x}},{\boldsymbol {\theta }})=f\left({\boldsymbol {x}};{\boldsymbol {\theta }}\right)

kung saan ang bektor na feature input ay ${\boldsymbol {x}}$ at ang punsiyong f ay tipikal na pinarameterisa ng ilang mga parametrong ${\boldsymbol {\theta }}$ . Sa isang diskriminatibong modelong pakikitungo sa problema, ang f ay tinatantiya ng direkta. Sa isang heneratibong modelong pakikitungo, ang inberso o kabaligtarang probabilidad na $p({{\boldsymbol {x}}|{\rm {tatak}}})$ ay bagkus tinatantiya at sinasama sa mga prior na probabilidad na $p({\rm {tatak}}|{\boldsymbol {\theta }})$ gamit ang patakaran ni Bayes gaya ng sumusunod:

p({\rm {tatak}}|{\boldsymbol {x}},{\boldsymbol {\theta }})={\frac {p({{\boldsymbol {x}}|{\rm {tatak}}})p({\rm {tatak|{\boldsymbol {\theta }}}})}{\sum _{L\in {\text{lahat ng mga tatak}}}p({\boldsymbol {x}}|L)p(L|{\boldsymbol {\theta }})}}.

Kapag ang mga tatak ay tuloy tuloy na distribusyon gaya ng sa regresyong analisis, ang denominador ay sumasangkot sa integrasyon kesa sa sumasyong":

p({\rm {tatak}}|{\boldsymbol {x}},{\boldsymbol {\theta }})={\frac {p({{\boldsymbol {x}}|{\rm {tatak}}})p({\rm {tatak|{\boldsymbol {\theta }}}})}{\int _{L\in {\text{lahat ng mga tatak}}}p({\boldsymbol {x}}|L)p(L|{\boldsymbol {\theta }})\operatorname {d} L}}.

Ang halaga ng ${\boldsymbol {\theta }}$ ay tipikal na tinututunan gamit ang maksimum a posteriori(MAP) na pagtatantiya. Ito ay humahanap ng pinakamahusay na halaga na sabay na nagtatagpo ng magkakasalungat ng bagay: upang gumawa ng mahusay hangga't maaari sa sinasanay na data at upang hanapin ang pinakasimpleng model. Sa kalikasan, ito ay nagsasama ng maksimum na pagiging malamang na pagtatantiya sa regularisasyong pamamaraan na pumapabor sa mas simpleng mga modelo kesa sa mas komplikadong mga modelo. Sa kontekstong bayesian, ang pamamaraang regularisasyon ay maaaring makita bilang isang prior na probabilidad na $p({\boldsymbol {\theta }})$ sa iba't ibang mga halaga ng ${\boldsymbol {\theta }}$ . Sa matematikal na paglalarawan:

{\boldsymbol {\theta }}^{*}=\arg \max _{\boldsymbol {\theta }}p({\boldsymbol {\theta }}|\mathbf {D} )

kung saan ang ${\boldsymbol {\theta }}^{*}$ ang halagang ginagamit para sa ${\boldsymbol {\theta }}$ sa mga kalaunang pagsisiyasat na pamamaraan at ang $p({\boldsymbol {\theta }}|\mathbf {D} )$ ang posteior na probabilidad ng ${\boldsymbol {\theta }}$ ay ibinigay ng:

p({\boldsymbol {\theta }}|\mathbf {D} )=\left[\prod _{i=1}^{n}p(y_{i}|{\boldsymbol {x}}_{i},{\boldsymbol {\theta }})\right]p({\boldsymbol {\theta }}).

Sa pakikitungong Bayesian sa problemang ito, imbis ng pagpili ng isang paremetrong bektor na ${\boldsymbol {\theta }}^{*}$ , ang probabilidad ng isang ibinigay na tatak para sa bagong instansiyang ${\boldsymbol {x}}$ ay kinukwenta sa pamamagitan ng pag-iintegrado ng lahat ng mga posibleng halaga ng ${\boldsymbol {\theta }}$ ma tinimbang ayon sa posterior na probabilidad na:

p({\rm {tatak}}|{\boldsymbol {x}})=\int p({\rm {tatak}}|{\boldsymbol {x}},{\boldsymbol {\theta }})p({\boldsymbol {\theta }}|\mathbf {D} )\operatorname {d} {\boldsymbol {\theta }}.

Mga gamit

Sa agham medikal, ang pagkilala ng padron ang basehan ng mga sistemang computer-aided diagnosis (CAD). Ang CAD ay naglalarawan ng pamamaraan na sumsuporta sa mga interpretasyon at natuklasan ng doktor. Ang tipikal na aplikasyon ay automatikong pagkilala ng pananalita(speech recognition), klaspikasyon ng dokumento(spam o hindi spam na email), automatikong pagkilala ng sulat kamay sa mga liham, sistemang pagkilala ng mukha(facial recognition) o pagkakatas ng larawan ng sulat kamay sa mga anyong medikal.^[1]. Ang huling dalawang mga halimbawa ay bumubuo ng pang-ilalm na paksa ng pagsusuri ng larawan ng pagkilala ng padron na umuukol sa mga larawang digital bilang input ng mga sistemang pagkilala ng padron.^[2]^[3]

Mga algoritmo

Ang mga algoritmo ng pagkilala ng pateno ay nakabatay sa uri ng tatakng(label) output, sa kung ang pagkatuto ay pinapatunabay o hindi pinapatunabayan, sa kung ang algoritmo ay estadistikal o hindi estadistikal sa kalikasan. Ang mga estadistikal na algoritmo ay maaari pang karagdagang uriin bilang henereatibong modelo o diskriminatibong modelo.

Mga algoritmong klasipikasyon(mga pinapatnubayang algoritmo na humuhula ng mga tatakng kategorikal)

Pagkukumpol(hindi pinapatnubayang mga algoritmo na humuhula ng kategorikal na mga tatak

Kategorikal na pinagsamang modelo
K-means na pagkukumpol
Hierarkikal na pagkukumpol
Kernel na analisisn ng pangunahing bahagi (Kernel PCA)

Regresyon(humuhula ng mga may halagang real na tatak)

Pinapatnubayan:

Hindi pinapatnubayan:

Analisis ng pangunahing bahagi(PCA)
Independiyenteng analisis ng bahagi(ICA)

Kategorial na sekwensiyang pagtatatak(humuhula ng mga sekwensiya ng kategorial na tatak

Pinapatnubayan:

Tagong modelong Markov(HMM)
Maksimum na entropiyang modelong Markov(MEMM)
Kondisyonal na randomang field (CRFs)

Hindi pinapatnubayan:

Tagong modelong Markov(HMM)

May halagang real na sekwensiyang pagtatatak(humuhula ng mga sekwensiya ng mga may halagang real na tatak

Parsing(humuhula ng mga tatakng may istrakturang puno

Pinapatnubayan at hindi pinapatnubayan:

Probabilistikong kontekstong malayang grammar(PCFG)

Pangkalatahang mga algoritmo para sa paghula ng artbitaryong na istrakturang mga tatak

Pagkatutong ensemble(pinapatnubayang meta algoritmo para sa paghahalo ng maraming mga algoritmong pagkatuto

Bootstrap aggregating ("bagging")
Boosting
Ensemble na pag-aaberahe
Halo ng mga eksperto, hierarkikal na halo ng mga eksperto

Sanggunian

↑ Milewski, Robert; Govindaraju, Venu (31 Marso 2008). "Binarization and cleanup of handwritten text from carbon copy medical form images". Pattern Recognition. 41 (4): 1308–1315. doi:10.1016/j.patcog.2007.08.018.{{cite journal}}: CS1 maint: date auto-translated (link)
↑ Richard O. Duda, Peter E. Hart, David G. Stork (2001) Pattern classification (2nd edition), Wiley, New York, ISBN 0-471-05669-3
↑ R. Brunelli, Template Matching Techniques in Computer Vision: Theory and Practice, Wiley, ISBN 978-0-470-51706-2, 2009 ([1] TM book)

[1] Milewski, Robert; Govindaraju, Venu (31 Marso 2008). "Binarization and cleanup of handwritten text from carbon copy medical form images". Pattern Recognition. 41 (4): 1308–1315. doi:10.1016/j.patcog.2007.08.018.{{cite journal}}: CS1 maint: date auto-translated (link)

[duda2001-2] Richard O. Duda, Peter E. Hart, David G. Stork (2001) Pattern classification (2nd edition), Wiley, New York, ISBN 0-471-05669-3

[3] R. Brunelli, Template Matching Techniques in Computer Vision: Theory and Practice, Wiley, ISBN 978-0-470-51706-2, 2009 ([1] TM book)

[1]

[2]

[3]