Laskennallinen oppimisteoria

Computational learning theory ( englanniksi  computational learning theory tai yksinkertaisesti oppimisteoria ) on tekoälyteorian alakenttä, joka on omistettu koneoppimisalgoritmien [1] kehittämiseen ja analysointiin .

Yleiskatsaus

Koneoppimisen teoreettiset tulokset käsittelevät pääasiassa induktiivista oppimista, jota kutsutaan ohjatuksi oppimiseksi . Tällä lähestymistavalla algoritmille annetaan näytteitä jollain tavalla merkittyinä. Näytteet voivat olla esimerkiksi kuvauksia sienistä, ja etiketistä selviää, onko sieni syötävä vai ei. Algoritmi ottaa nämä merkityt näytteet ja käyttää niitä luokittelijan hankkimiseen . Luokitin on toiminto, joka määrittää näytteille tarrat, mukaan lukien näytteet, joita algoritmi ei ole aiemmin skannannut. Ohjatun oppimisen tavoitteena on optimoida jokin suorituskyvyn mitta, kuten minimoida uusissa näytteissä tehtyjen virheiden määrä.

Tehokkuusrajan lisäksi laskennallinen oppimisteoria tutkii algoritmin aikamonimutkaisuutta ja toteutettavuutta. Laskennallisessa oppimisteoriassa laskennan sanotaan olevan toteutettavissa, jos se voidaan tehdä polynomiajassa . Tulosten aikamonimutkaisuutta on kahta tyyppiä:

• Positiiviset tulokset osoittavat, että joitakin funktioluokkia voidaan harjoitella polynomiajassa.
• Negatiiviset tulokset osoittavat, että joitain funktioluokkia ei voida oppia polynomiajassa.

Negatiiviset tulokset perustuvat usein tiettyihin väitteisiin, joihin uskotaan mutta joita ei todisteta, kuten:

• Laskennallinen monimutkaisuus  - P ≠ NP ;
• Kryptografia  – Yksisuuntaisia ​​toimintoja on olemassa.

Laskennalliseen oppimisen teoriaan on olemassa useita erilaisia ​​lähestymistapoja. Nämä erot perustuvat oletuksiin, jotka on tehty päättelyperiaatteista , joita käytetään yleistämään rajoitetun tiedon perusteella. Nämä periaatteet sisältävät todennäköisyyden määritelmän (katso frekvenssitodennäköisyys , Bayesin todennäköisyys ) ja erilaisia ​​näytteiden muodostamista koskevia oletuksia. Erilaisia ​​lähestymistapoja ovat:

• Dana Angluinin ehdottama tarkka oppiminen ;
• Probabilistically Approximately Correct Learning (PCL), ehdotus Leslie Valiant ;
• Vladimir Vapnikin ja Aleksei Chervonenkiksen ehdottama Vapnik-Chervonenkiksen teoria ;
• Bayesin päättely ;
• Algorithmic learning theory kirjoittaja E. Mark Gold;
• Online-koneoppiminen Nick Littlestonen työstä.

Laskennallinen oppimisteoria johtaa joihinkin käytännön algoritmeihin. Esimerkiksi VPK-teoria synnytti tehostamisen , Vapnik-Chervonenkis-teoria johti tukemaan vektorikoneita ja Bayesin päättely johti Bayesin verkkoihin (kirjoittaja - Judah Pearl ).

Katso myös

• Kieliopillinen johtaminen
• Tiedon teoria
• Vakaus (oppimisteoria)
• Vikasietokyky (VPK-koulutus)
• Vapnik-Chervonenkis ulottuvuus
• ominaisuuden valinta
• induktiivinen päättely
• Optimaalinen O-oppiminen
• tehostaa
• Occam oppii
• Todennäköisesti suunnilleen oikea koulutus
• Hajautetun oppimisen teoria

Muistiinpanot

1. ↑ ACL - Association for Computational Learning . Haettu 5. joulukuuta 2018. Arkistoitu alkuperäisestä 25. tammikuuta 2012. (määrätön)

Kirjallisuus

• Angluin D. Laskennallisen oppimisen teoria: Tutkimus ja valittu bibliografia // Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (Toukokuu 1992. - 1992. - P. 351-369.).
• Haussler D. Luultavasti suunnilleen oikea oppiminen // AAAI-90 Proceedings of the Eight National Conference on Artificial Intelligence, Boston, MA . - American Association for Artificial Intelligence, 1990. - S. 1101-1108.
• Vapnik V., Chervonenkis A. Tapahtumien suhteellisten todennäköisyyksien yhtenäisestä konvergenssista // Todennäköisyysteoria ja sen sovellukset. - 1971. - T. 16 , no. 2 . — S. 264–280 .
• Dhagat A., Hellerstein L. PAC-oppiminen epäolennaisilla ominaisuuksilla // Proceedings of the IEEE Symp. Tietojenkäsittelytieteen säätiöstä . – 1994.
• E. Mark Gold. Kielen tunnistaminen rajassa  // Tiedot ja ohjaus. - 1967. - T. 10 , no. 5 . — S. 447–474 . - doi : 10.1016/S0019-9958(67)91165-5 .
• Oded Goldreich, Dana Ron. Yleismaailmallisista oppimisalgoritmeista . yhteenveto
• Kearns M., Leslie Valiant. Boolen kaavojen ja äärellisten automaattien oppimisen kryptografiset rajoitukset // Proceedings of the 21st Annual ACM Symposium on Theory of Computing . - New York: ACM, 1989. - S. 433-444.
• Robert E. Schapire. Heikon oppimisen vahvuus  // Koneoppiminen. - 1990. - V. 5 , no. 2 . — S. 197–227 .
• Blumer A., ​​Ehrenfeucht A., Haussler D., Warmuth MK Occamin partakone // Inf.Proc.Lett.. - 1987. - V. 24 . — S. 377–380 .
• Blumer A., ​​Ehrenfeucht A., Haussler D., Warmuth MK Learnability and the Vapnik-Chervonenkis -ulottuvuus // Journal of the ACM. - 1989. - T. 36 , no. 4 . — S. 929–865 .
• Valiant L. Opittavan teoria // ACM:n viestintä. - 1984. - T. 27 , no. 11 . — S. 1134–1142 .
• Michael Kearns, Ming Li. Oppiminen haitallisten virheiden yhteydessä  // SIAM Journal on Computing. - 1993. - elokuu ( nide 22 , numero 4 ). — S. 807–837 .
• Michael Kearns. Tehokas melua sietävä oppiminen tilastokyselyistä // Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing . - 1993. - S. 392-401.
• Haussler D., Kearns M., Littlestone N., Warmuth M. Equivalence of models for polynomial learningability // Proc. Ensimmäinen ACM-työpaja laskennallisen oppimisen teoriasta. - 1988. - S. 42-55.
• Pitt L., Warmuth MK Prediction-Preserving Reducibility  // Journal of Computer and System Sciences. - 1990. - T. 41 , no. 3 . — S. 430–467 . - doi : 10.1016/0022-0000(90)90028-J .

Linkit

• Bayesilaisen päättelyn perusteet