Մոնտե Կառլոյի Մեթոդներ, Պատրաստված Պարզ

Օգտագործելով քաոսը՝ պարզություն գտնելու համար

Պատկերացրեք 10 x 10 քառակուսի կոորդինատային ցանցի վրա: Որոշ ձևեր գծված են այդ ցանցի վրա, բայց դուք չգիտեք, թե ինչ տեսք ունի: Այնուամենայնիվ, կարող եք հարցումներ կատարել f(x, y), որտեղ (x, y) կոորդինատն է, իսկ ելքը կա՛մ 1 (ձևի մեջ) կա՛մ 0 (ձևի մեջ չէ): Ինչպե՞ս կգտնեք ձևի մակերեսը:

Պատասխանը բավականին պարզ է. Այն բխում է վիճակագրության մեկ սկզբունքից՝ Մեծ թվերի օրենքից, որն ասում է, որ որքան շատ անգամ է պատահականորեն ընտրվում ֆունկցիան, այնքան ավելի ճշգրիտ է նրա մոտարկումը: Այնուհետև, մեր լուծումն այն է, որ պարզապես պատահականորեն ընտրենք կետեր 10×10 ցանցում, հաշվենք, թե քանի հողատարածք կա ձևով և բաժանենք այն նմուշառված կետերի ընդհանուր թվի վրա:

Թեև պատահական նմուշառման այս բնազդային գաղափարը պարզ է, այն կիրառություն ունի բազմաթիվ ոլորտներում՝ օրենքից մինչև կլիմայի կանխատեսում, և, հավանաբար, ամենաարդիականը այս հոդվածի, մեքենայական ուսուցման և վիճակագրության համար: Այն կրում է պաշտոնական անվանում՝ Մոնտե Կառլոյի մեթոդներ:

Երբ ներկայացվում է մի խնդիր, որը բաղկացած է դետերմինիստական ​​սկզբունքներից, օրինակ՝ ձևի տարածքը, ֆունկցիայի բաշխումը կամ այն ​​քայլը, որը խաղացողը պետք է ընտրի հաջորդ խաղում, Մոնտե Կառլոյի մեթոդները հիմնովին ենթադրում են, որ այն կարող է մոդելավորվել հավանականության և ստոխաստիկության միջոցով ( պատահականություն):

Մոնտե Կառլոյի մեթոդները հիմնվում են բաշխումից կրկնվող պատահական նմուշառման վրա՝ թվային արդյունք ստանալու համար: Դա ավելի շուտ մոտեցում է, քան ալգորիթմ:

Ձևի վրա հիմնված մեկ այլ օրինակի համար ստուգեք Գտնել շրջանակի տարածքի բանաձևը առանց որևէ մաթեմատիկայի օգտագործման (Մոնտե Կառլոյի նմուշառումով և բազմանդամ ռեգրեսիայով): Պատահական նմուշառումը կարող է օգտագործվել որպես ֆունկցիայի ինտեգրալը (կորի տակ գտնվող տարածքը) գտնելու էժան միջոց: Հայտնի է, որ pi-ի արժեքը՝ շրջանի կարևոր հաստատունը, կարող է նաև մոտավորվել Մոնտե Կառլոյի նմուշառման միջոցով.

Ընդհանուր առմամբ, Մոնտե Կառլոյի նմուշառման երեք դաս/կիրառություն կա.

  • Ուղիղ նմուշառում: Նմուշառում բաշխումից միամտորեն և ուղղակիորեն առանց նախնական տեղեկատվության: Այսպես մենք մոտեցանք ձևի անհայտ տարածքի մոտավորմանը:
  • Կարևորության նմուշառում: Այն դեպքում, երբ բաշխումը չափազանց թանկ է նմուշի համար, ընտրեք ավելի պարզ մոտարկման ֆունկցիայից: Սա Բայեսյան օպտիմալացման և փոխնակ օպտիմալացման հիմնական բաղադրիչն է:
  • Մերժման նմուշառում: Այն դեպքում, երբ բաշխումն անհայտ է, առաջարկեք նոր կետեր և ընդունեք դրանք, եթե դրանք համապատասխանում են որևէ չափանիշի:

Մոնտե Կառլոյի նմուշառումը սովորաբար օգտագործվում է երկու համատեքստում.

  • Օպտիմալացում: Բնականաբար, օպտիմալը գտնելը պահանջում է առողջ հավասարակշռություն հետազոտության և շահագործման միջև: Երբ Մոնտե Կառլոյի նմուշառումը (հետախուզումը) հագեցած է շահագործման վերահսկման այլ մեխանիզմով, այն կարող է հզոր գործիք լինել օպտիմալը գտնելու համար:
  • Հավանականությունների և գործառույթների մոտավոր գնահատում: Մոնտե Կառլոյի նմուշառումը հիանալի միջոց է որոշ հավանականությունների կամ ֆունկցիաների (և հաճախ՝ հավանականության ֆունկցիաների) անուղղակի գնահատման համար, երբ դա չափազանց դժվար է անել այլ մեթոդով:

Քանի որ Մոնտե Կառլոյի մեթոդների հիմքում ընկած գաղափարները պարզ են, բայց կարող են օգտագործվել բավականին բարդ և ստեղծագործ ձևերով, ավելի լավ է մտածելակերպը ուսումնասիրել մի քանի օրինակների միջոցով:

Օրինակ՝ դիտարկենք Markov Chain Monte Carlo (MCMC) մեթոդները, որոնք փորձում են պատահական նմուշներ ստեղծել թիրախային բաշխումից՝ առանց իմանալու, թե որն է բաշխումը: Այս բաշխումները ներկայացնելու համար օգտագործվում են Մարկովյան շղթաները՝ գրաֆիկ, որտեղ յուրաքանչյուր հանգույց մի վիճակ է, որն ունի այլ վիճակ տեղափոխելու որոշակի հավանականություն p:

Դիտարկենք այս եղանակը Մարկովյան շղթան մի քաղաքում (սարսափելի եղանակով), որտեղ եղանակային միակ հնարավոր պայմաններն են քամին, կարկուտ/ձյուն, ամպրոպ կամ անձրև: Ամեն օր, հաջորդ օրվա եղանակը կարելի է կանխատեսել՝ հիմնվելով ընթացիկ օրվա եղանակից տարածվող հավանականության վրա: Օրինակ, եթե այսօր ձյուն է գալիս, ապա 80 տոկոս հավանականություն կա, որ քամու է, իսկ վաղը անձրևի հավանականությունը՝ 20 տոկոս:

Մարկովյան շղթայի շուրջ թափառելու համար մենք սկսում ենք մի տեղից s և տեղափոխվում մեկ այլ՝ s’,նշված հավանականությամբ: Այնուհետև s-ը դառնում է նոր s և գործընթացը կրկնվում է: Չնայած այս օրինակը ներկայացնում է փոքր Մարկովյան շղթա, հսկայական գրաֆիկները՝ հազարավոր հանգույցներով և հարյուր հազարավոր կապերով, կարող են օգտագործվել բարդ հավանականական հարաբերությունների մոդելավորման համար:

Եթե ​​մենք վազում ենք Մարկովյան շղթայով զգալի ժամանակից հետո (օրինակ՝ 10000 մոդելավորված օր), մենք սկսում ենք հասնել «հավանականության հավասարակշռության»: Սա պարզապես նշանակում է, որ մենք կարող ենք գնահատել ստատիկ հավանականությունը, որ անձրև կգա՝ հիմնվելով այն բանի վրա, թե մեր ճանապարհորդած նահանգներից քանիսն են անձրևում (հիմնված է Մեծ թվերի օրենքի վրա):

Օրինակ, եթե մենք ստանանք հետևյալ (հիպոթետիկ) արդյունքները Մարկովյան շղթայով ավելի քան 10,000 նահանգների միջոցով.

  • Նահանգում Քամին 2754 նահանգների համար
  • Նահանգում ամպրոպ՝ 1034 նահանգներում
  • Նահանգում կարկուտ/ձյուն՝ 4301 նահանգներում
  • Raining նահանգում 1911 նահանգներում

Մենք կկարողանանք ստեղծել հետևյալ հավանականությունները.

  • P (Քամի) = 0,2754
  • P (Ամպրոպ) = 0,1034
  • P(Կարկուտ/Ձյուն) = 0,4031
  • P (Անձրև) = 0,1911

Այնուհետև կարելի է պարզապես նմուշառել բաշխումից համապատասխանաբար՝ պատահականորեն վիճակ նկարել Մարկովյան շղթայից՝ առանց այն անցնելու անհրաժեշտության: Մարկովյան շղթայի կրկնվող կրկնությունների և պատահական անցման միջոցով (գործընթացի «Մոնտե Կառլո» մաս) համակարգը կարողացավ փլուզվել և ներկայացվել որպես հավանականության բաշխում:

Մարկովյան շղթաները կարող են կառուցվել բարդ հարաբերությունների մոդելավորման համար, որոնք չեն կարող ուղղակիորեն նմուշառվել, այնուհետև պարզեցվել՝ գտնելու դրանց հիմքում ընկած հավանականության բաշխումները:

Կան բազմաթիվ լավ կայացած MCMC ալգորիթմներ, ինչպիսիք են Մետրոպոլիս-Հասթինգս ալգորիթմը կամ Գիբսի նմուշառումը: Բոլորը ձգտում են անել նկարագրվածի նման մի բան՝ մոդելավորել համակարգի հիմքում ընկած հավանականությունները:

Տեսությունից մի քայլ դուրս գալու և կիրառության մեջ մտնելու համար նայեք Մոնտե Կառլոյի ծառի որոնումը (MCTS), որը խելացի խաղային ուժեղացման ուսուցման համակարգերի հիմնական մասն է: Վաղ խաղերի համակարգերը, ինչպիսիք են IBM DeepBlue-ի նախնական հաղթանակը շախմատի չեմպիոն Գարի Կասպարովի նկատմամբ 1997 թվականին, հիմնված էին մինիմաքսի նման ալգորիթմների վրա, որոնք խաղում էին բոլոր հնարավոր խաղերը ընթացիկ քայլից և որոշում այն ​​մեկը, որն առաջարկում էր որոշակի հաղթանակ (կամ ամենաբարձր հնարավորությունը): .

Քանի որ փորձարկված խաղերը դարձել են ավելի բարդ, ամենահայտնիը՝ Go խաղը կամ նույնիսկ առաջադեմ գրաֆիկական հրաձիգ խաղերը, ինչպիսին է DOTA-ն, բոլոր հնարավոր սցենարները կատարելը հաշվողականորեն անիրագործելի և հիմար է: Փոխարենը, խաղացողի համար ավելի խելամիտ է ուսումնասիրել պոտենցիալ շահավետ քայլերը՝ միաժամանակ հրաժարվելով ձախողման մեծ հավանականություն ունեցող քայլերից և օգտագործել հայտնի քայլերը:

Ասենք, որ մենք սկսում ենք կառուցել ծառ, որպես այդպիսին, որտեղ յուրաքանչյուր հանգույց ներկայացնում է խաղի որոշակի վիճակ: Մենք կարող ենք անցում կատարել հանգույցների միջև՝ կատարելով որոշակի գործողություններ: Խաղի սկզբնական մեկնարկային վիճակից մենք կարող ենք վերցնել մի քանի հնարավոր հանգույցներ։

Արժեքային նեյրոնային ցանցերը փորձում են արժեք դնել յուրաքանչյուր քայլի վրա. հաշվի առնելով այս քայլը, ո՞րն է հավանականությունը, որ գործակալը կհաղթի: Նշենք, որ սկզբում, քանի որ արժեքային ցանցը չի վերապատրաստվել, այն կտա պատահական գուշակություններ: Քանի որ համակարգը բավականաչափ խաղեր է խաղում, այնուամենայնիվ, այն ավելի լավ կլինի խելամտորեն վերլուծել որոշակի քայլերի հետևանքները:

Պարզապես ընտրելու, թե որ հանգույցն ունի ամենամեծ հավանականությունը, մենք կատարում ենք «կշռված Մոնտե Կառլոյի նմուշառում»: Եթե ​​ցանցը կարծում է, որ հանգույց 2-ը կհանգեցնի 90% հաղթելու հավանականության, ապա այն ընտրվելու ավելի մեծ հնարավորություն ունի, բայց հնարավոր է նաև, որ ընտրվեն 3 և 1 հանգույցները: Քաղաքականությունը, կամ ինչպես են ընտրվում հնարավոր հանգույցները, նույնպես սովորում են:

Սրա հիմքում ընկած տրամաբանությունն այն է, որ որոշակի քայլի կանխատեսելի արժեքը սահմանափակ է և սահմանափակված է պատահականությամբ (հնարավոր է, որ հակառակորդը անսպասելի քայլ կանի): Բացի այդ, այլ ոլորտներ ուսումնասիրելու և պոտենցիալ ավելի շահավետ քայլեր գտնելու համար ռիսկի դիմելու փոխարեն միայն հայտնի քայլերի օգտագործումը կհանգեցնի ոչ մրցակցային և ծույլ մոդելի, ինչը անցանկալի է ուժեղացման բարդ ուսումնական միջավայրերում:

Այնուհետև ընտրված հանգույցը ավելի է ընդլայնվում, և գործընթացը կրկնվում է մինչև խաղի ավարտը: Հավանականությունը որոշումների կայացման մեջ ներառելը «լավագույն» արժեքի դետերմինիստական ​​ընտրության փոխարեն օգնում է ամրապնդման ուսուցմանը հավասարակշռել շահագործման/հետախուզման փոխզիջումը:

Եթե ​​մենք դրան նայենք վիճակագրական տեսանկյունից, ապա Մոնտե Կառլոյի նմուշառումն օգտագործվում է հավանականության օպտիմալ բաշխումը մոդելավորելու համար p(v), որպեսզի ընտրվի հանգույց, հաշվի առնելով, որ այն ունի որոշակի կանխատեսելի արժեքը v:

Monte Carlo Tree Search-ն այն շրջանակն էր, որում AlphaGo-ն՝ DeepMind-ի ամրապնդող ուսուցման համակարգը, որը հաղթեց (և շարունակում է հաղթել) Go-ի լավագույն խաղացողներին: MCTS-ն ունի այլուր հավելվածների լայն տեսականի:

Մոդելացված կռումը Մոնտե Կառլոյի նմուշառման ևս մեկ կիրառություն է, որն օգտագործվում է որպես ոչ գրադիենտ ֆունկցիայի օպտիմալացման արդյունավետ մեթոդ գլոբալ օպտիմա գտնելու գործում: Ինչպես Մոնտե Կառլոյի մեթոդները կիրառվող այլ խնդիրների պես, որոնման տարածքը դիսկրետ է (օրինակ՝ մենք չենք փորձում օպտիմալացնել շարունակական արժեքները, ինչպես նեյրոնային ցանցի պարամետրերը):

Այն խնդիրներում, որտեղ ֆիքսված ժամանակի ընթացքում մոտավոր գլոբալ օպտիմա գտնելն ավելի արժեքավոր է, քան դրա ճշգրիտ արժեքները, մոդելավորված կռումը իրականում կարող է նախընտրելի լինել գրադիենտ անկման նման ալգորիթմներից:

Մոդելավորված կռման գաղափարը գալիս է մետալուրգիայից կամ մետաղների մանիպուլյացիայից: Մետաղագործության մեջ կռելը նյութի վերահսկվող ջեռուցումն է կամ հովացումը՝ դրա չափը մեծացնելու և թերությունները վերացնելու համար։ Նմանապես, նմանակված կռումը վերահսկում է էներգիայի քանակությունը համակարգում, որը որոշում է, թե որքան ռիսկ է նա պատրաստ վերցնել նոր հնարավորություններ ուսումնասիրելու համար:

Ջերմաստիճանը սկսվում է որոշակի նախնական քանակից, որը ներկայացնում է մի տեսակ ժամաչափ: Յուրաքանչյուր նահանգում s, սիմուլյացված եռացումը տեղափոխվում է որոշ հարևան պետություն s' կախված երկու վիճակների արժեքից (գնում է s' շահույթ կամ կորուստ?), ինչպես նաև ներկայիս ջերմաստիճանը T, հավանականությամբ P(s, s' , T):

Քանի որ ջերմաստիճանը նվազում է (մնացած ժամանակը նվազում է) յուրաքանչյուր ժամանակաչափով, մոդելը դառնում է ավելի քիչ ուսումնասիրող և ավելի շահագործող: Մոդելացված կռումը թույլ է տալիս առաջադեմ անցում կատարել հետախուզումից դեպի շահագործման՝ կապված այն ժամանակի հետ, որը շատ շահավետ է գլոբալ օպտիմալը գտնելու համար:

Մոնտե Կառլոյի նմուշառումը և Բայեսյան մեթոդները օգտագործվում են հավանականության ֆունկցիան մոդելավորելու համար P(s, s', T) . Իրականում, հաճախ Metropolis-Hastings ալգորիթմը, ինչպես հիշում եք, Մարկովյան շղթայի Մոնտե Կառլոյի մեթոդն է (կամ դրա հիման վրա մոդելավորված մեթոդները) օգտագործվում են անցումային շեմերը գտնելու համար (հավանականությունը, որով պետք է անցում կատարել):

Սա բնական է, քանի որ նմանակված եռացումը լուծումները վերաբերվում է որպես վիճակների և փորձում է գտնել անցումային օպտիմալ հավանականությունները՝ կատարյալ լանդշաֆտ Մարկովյան շղթայի մոդելավորման համար:

Հաճախ Մոնտե Կառլոյի մեթոդները կամ Մոնտե Կառլոյի նման մտածողությունը հայտնվում են այնպիսի վայրերում, որտեղ մենք դա ամենաքիչն ենք սպասում: Թեև դա պարզ մեխանիզմ է, այն ունի խորը և բարդ արմատներ անթիվ ծրագրերում:

Ամփոփում/Հիմնական միավորներ

  • Մոնտե Կառլոյի մեթոդները հիմնված են այն գաղափարի շուրջ, որ պատահականության ներարկումը համակարգ հաճախ կարող է արդյունավետորեն լուծել այն:
  • Ընդհանուր առմամբ, Մոնտե Կառլոյի նմուշառման երեք դաս կա՝ ուղղակի նմուշառում, կարևորության նմուշառում և մերժման նմուշառում:
  • Մոնտե Կառլոյի երկու ընդհանուր կիրառությունները ներառում են օպտիմալացում և բարդ հավանականությունների և գործառույթների գնահատում:
  • Դիսկրետ (ոչ շարունակական) և դետերմինիստական ​​խնդիրներում Մոնտե Կառլոյի մեթոդները օգտագործում են ստոխաստիկություն+հավանականություն, մեծ թվերի օրենքը և դրանք արդյունավետ լուծելու արդյունավետ շրջանակ:

Շնորհակալություն կարդալու համար:



Բայեսյան օպտիմիզացիայի գեղեցկությունը՝ պարզ տերմիններով բացատրված
Հնարամիտ ալգորիթմի ետևում ընկած ինտուիցիանtowardsdatascience.com