| |
[1. Feb 2016|21:00] |
Tātad. Datorikā ir daudz slavenu problēmu, kuras neviens nemāk efektīvi atrisināt. Var ievērot, ka tās ir visnotaļ praktiskas problēmas. Bet tas savukārt nozīmē, ka tādu problēmu instances mums dzīvē apkārt ir papilnam un cilvēki tās kaut kā spēj atrisināt. Paradoksāli? Viena teorija ir tāda, ka cilvēki risina grūtos (un ne tikai) uzdevumus pēc "probably approximately correct" metodes - tas ir, iznākums "ar labu varbūtību ir aptuveni pareizs". Datori, kā zināms, ir labāki par cilvēkiem. Līdz ar to datori spēj atrisināt ne tikai "ar varbūtību pareizi" (Montekarlo algoritmi), bet arī "pilnīgi pareizi, tikai varbūt ļoti lēni" (Lasvegasas algortimi).
Kad es mācījos augstskolā, tad tur apguvu tikai to, ka no teorijas viedokļa sarežģītās problēmas visticamāk nav efektīvi atrisināmas. Ja nu kaut ko līdzīgu risinājumam tomēr gribas, tas nākas samierināties ar aptuvenām heiristikām, no kurām reizēm var saņemt ļoti kļūdainus rezultātus. Bet, kā hintoju iepriekšējā rindkopā, patiesībā viss nav tik vienkārši, un datori spēj vairāk. (Var teikt, ka praksē ir zināma atšķirība starp praksi un teoriju.) Situācija nav tik bezcerīga, kā tas varētu likties ar algoritmu teoriju tikko iepazīstinātam studentam, jo pat ja kāda problēma nav atrisināma vispārīgajā gadījumā, tā tik un tā var būt praktiski uzveicama - jāizpildās tikai nosacījumam, ka lielākā daļa praktiski sastopamo gadījumu ir kaut kādā ziņā "vienkārši".
(Man patiešām pārsteidzošs liekas fakts, ka līdz šīs situācijas seku apzināšanai datorika masveidā ir aizdomājusies tikai nesen, nevis visi masveidā metušies strādāt pie tās izmantošanas.)
Paliek jautājums, kā tādu intuīciju par praktisko vienkāršumu var pārvērst formalizētos, uz datora izpildāmos algoritmos. Iespējams, tieši šis punkts agrāk ir bijis tas galvenais šķērslis šis idejas realizācijā, līdzīgā veidā kā novecojušas programmēšanas valodas mēdz kavēt progresu IT industrijā. Te nu ir laiks nosaukt vārdā to pieeju, kura iedvesmoja šo ierakstu: tā ir constraint programming. Savā būtībā tā ir kārtējā metode optimizācijas uzdevumu risināšanai, un ļauj datoram sistemātiski pārmeklēt iespējamo risinājumu telpu.
Constraint programming ir pa pusei matemātiska pieeja un tās modeļus bieži vien būvē ļoti augsta līmeņa programmēšanas valodās. (Nāk prātā, ka viens no eks-kolēģiem universitātes profesoriem kā humoru bija izlicis publiskai apskatei kāda sava raksta recenzijas fragmentu. Recenzijas autors bija profesora prezentēto modeli nokritizējis, apsaukājot to par "nepraktisku pseidokodu" - tātad būtībā palaidis garām raksta jēgu.) Tas nozīmē, ka veidot konstreintu modeļus var risināt arī parastie lietotāji, ne tikai programmētāji - piemēram dažādi savu jomu speciālisti, tādi kā dabaszinātnieki (nu, vismaz tas tā ir teorijā).
Tai pašā laikā constraint programming ir arī "otra puse", backend - optimizācijas risinājumu meklēšanas programmas. Lai konkrēta veida problēmai dators spētu efektīvi atrisināt tās praktiski sastopamos gadījumus (instances), bieži vien ir nepieciešams uzlabot risināšanas programmas šai problēmai specifiskā veidā. Tādas optimizācijas tipiski izpaužas ieteikumi datoram formā "ja mainīgajam x ir piešķirta vērtība a, tad nav jēga mainīgajam y piešķirt vērtību b <= a", izejot no konkrētās problēmas struktūras un lietotāja dotajiem "konstreintiem". Tas ir darbs datoriķiem, jo tā būtībā ir netriviālu algoritmu izstrāde - mazliet programmēšanas, mazliet domāšanas, mazliet konkrētās problēmnozares specifikas apgūšanas. Pie viena atšķirībā no dažādiem citiem programmēšanas aspektiem, kas bieži vien ir "nezinātniski", intuitīvi, te paveras arī iespēja viegli empīriski pārbaudīt savas idejas, nomērot to ietekmi uz konkrētu instanču risināšanas ātrumu - zinātniskā metode!
Constraint programming atšķiras no integer programming un citām tāda veida optimizācijas metodēm, jo neprasa veidot tik matemātiski stingrus un ierobežotus modeļus; tā ir elastīgāka un fleksiblāka pret lietotāju un ļauj "konstreintus" aprakstīt gandrīz vai cilvēku valodā. Novitātes ziņā tā drīzāk līdzinās tai datorikas daļai, kura mēģina automatizēt loģisko spriešanu - te es domāju pirmkārt SAT/SMT solverus, kuri pēdējo padsmit gadā ir rādījuši līdzīgu iespaidīgu praktisku progresu neskatoties uz teorētiķu pierādījumiem tam, ka daudzām tāda veida problēmām ātri algoritmi vispār nav iespējami.
Constraint programming un SAT/SMT solveri ne tikai "dod" zinātnei, bet arī "ņem" no tās - piemēram, viena klasiska ideja šajā jomā ir ņemta no ekonomikas un saucas "portfeļu metode". Līdzīgi kā investīciju portfeļus sastāda no vairāku veidu vērtspapīriem, ideja te ir palaist nevis vienu, bet vienlaicīgi vairākus algoritmus no dažādām "riska klasēm". Dažas problēmas ātrāk atrisinās "konservatīvie" algoritmi (optimizē jau atrastā risinājuma tuvumā), citas algoritmi ar augstu riska pakāpi (bieži meklē jaunus risinājumus arī ārpus šaura "komforta apgabala"), un pie gudras portfeļa izvēles tā performance būs labāka nekā jebkurš no algoritmiem ņemts atsevišķi. Sākotnējais raksts par šo tēmu pirms gadiem 20 ir publicēts žurnālā "Science", kas datorikai ir visnotaļ netipiska publicēšanās vieta.
Bet vislabākais laikam ir tas, ka tā ir tīra, labdzimusi datorika - atšķirībā gan no mašīnmācīšanās, gan no aparatūras jaudas pieauguma (general-purpose GPU, cloud...). Pirmā nevirza datoriku uz priekšu, jo izpratnes pieaugums tiek kompensēts ar aizvien lielāku skaitu un aizvien jaudīgākām melnajām kastēm (varētu pat teikt "aizstāts" ar tām [1]). Hardware attīstība savukārt to nedara, jo domāšanu un inovācijas tā ļauj aizvietot ar brute force tradicionālajām metodēm. Constraint programming ir kaut kas cits - tās pastāvēšana nozīmē, ka datoriķa profesija tik drīz neizmirs :)
_______
[1] - "Just yesterday, a few hours before the Go paper was made public, I went to a talk where a graduate student of a deep learning expert acknowledged that people in that field still don’t really understand why their models work as they well as they do". |
|
|
![[info]](http://klab.lv/img/userinfo.gif){kind=small}