Монте-Карло әдісі және Гиббс сынамасы

Кіріспе

Монте-Карло алгоритмі

Статистикада Гиббс үлгі алуы немесе Гиббс самплері – бұл Марков тізбекті Монте-Карло (MCMC) алгоритмі, бірлескен ықтималдық үлестірілімінен тікелей үлгі алу қиын болғанда, бірақ шартты үлестірілімнен үлгі алу оңайрақ болғанда қолданылады. Бұл тізбекті бірлескен үлестірілімді жуықтау үшін (мысалы, үлестірілімнің гистограммасын жасау үшін); айнымалылардың бірінің шеттік үлестірілімін немесе айнымалылардың кейбір ішкі жиынтығын (мысалы, белгісіз параметрлер немесе жасырын айнымалылар) жуықтау үшін; немесе интегралды есептеу үшін (мысалы, айнымалылардың бірінің күтілетін мәнін) пайдалануға болады. Әдетте, кейбір айнымалылар мәндері белгілі байқауларға сәйкес келеді, сондықтан оларды үлгілеудің қажеті жоқ. Гиббс үлгі алуы статистикалық қорытындылау құралы ретінде, әсіресе Байес қорытындылауында жиі қолданылады. Бұл кездейсоқ алгоритм (яғни кездейсоқ сандарды пайдаланатын алгоритм) және статистикалық қорытындылау үшін детерминистік алгоритмдерге балама болып табылады, мысалы, күтуді максимизациялау алгоритмі (EM). Басқа MCMC алгоритмдері сияқты, Гиббс үлгі алуы үлгілердің Марков тізбегін жасайды, олардың әрқайсысы жақын орналасқан үлгілермен байланысты. Сондықтан, тәуелсіз үлгілерді алу қажет болғанда сақ болу керек. Жалпы, тізбектің басындағы (қабылдау кезеңіндегі) үлгілер қажетті үлестірілімді дұрыс көрсетпеуі мүмкін және әдетте олар алынып тасталады.

Кіріспе

Гиббс үлгісі физик Джозиа Виллард Гиббстің есімімен аталады, бұл үлгі алу алгоритмі мен статистикалық физика арасындағы аналогияға сілтеме жасайды. Алгоритмді ағайынды Стюарт және Дональд Геман 1984 жылы, Гиббс қайтыс болғаннан кейін шамамен сексен жыл өткен соң сипаттады және ол статистикалық қоғамдастықта шекті ықтималдық үлестірімін, әсіресе артқы үлестірімін есептеу үшін кеңінен танымал болды. Негізгі нұсқасында Гиббс үлгісі Метрополис-Хестингс алгоритмінің ерекше жағдайы болып табылады. Дегенмен, кеңейтілген нұсқаларында (төменде қараңыз) ол әрбір айнымалыны (немесе кейбір жағдайларда, айнымалылар тобын) кезекпен үлгілеу арқылы үлгі алудың жалпы құрылымы ретінде қарастырылуы мүмкін, сондай-ақ бір немесе бірнеше үлгі алу қадамдарын жүзеге асыру үшін Метрополис-Хестингс алгоритмін (немесе кесінді үлгілеу сияқты әдістерді) қосуға болады. Гиббс үлгісі бірлескен үлестіру нақты белгілі болмаған немесе тікелей үлгі алу қиын болған жағдайларда қолданылады, бірақ әрбір айнымалының шартты үлестірілуі белгілі және оны үлгілеу оңай (немесе кем дегенде, оңайрақ) болады. Гиббс үлгі алу алгоритмі басқа айнымалылардың ағымдағы мәндеріне байланысты әрбір айнымалының үлестірілімінен бір мысал жасайды. Үлгілер тізбегі Марков тізбегін құрайтынын және осы Марков тізбегінің стационарлық үлестірілімі ізделіп отырған бірлескен үлестірілімге тең екенін көрсетуге болады. Гиббс үлгі алуы Байес желісінің артқы үлестірілімін үлгілеуге өте қолайлы, себебі Байес желілері әдетте шартты үлестірілімдер жиынтығы ретінде беріледі.

Іске асыру

Гиббс үлгі алуы, негізгі түрінде, Метрополис-Хестингс алгоритмінің ерекше жағдайы болып табылады. Гиббс үлгі алуының мақсаты – көпөлшемді үлестірім берілгенде, бірлескен үлестірімді интегралдау арқылы шеттеуге қарағанда, шартты үлестірімнен үлгі алу оңайырақ. Егер біз бірлескен үлестірімнен үлгілер алуды қаласақ, келесідей әрекет етеміз: біз белгілі бір бастапқы мәнмен бастаймыз. Келесі үлгіні аламыз. векторы болғандықтан, біз вектордың әрбір компонентін , осы уақытқа дейін алынған басқа барлық компоненттерге байланысты осы компоненттің үлестірімінен үлгілейміз. Бірақ бір нюанс бар: біз компоненттерін дейін, ал кейін компоненттерін дейін шарттаймыз. Осыған жету үшін, біз компоненттерді бірінші компоненттен бастап ретімен үлгілейміз. Формальды түрде, үлгісін алу үшін, біз оны үлестіріміне сәйкес жаңартамыз. Біз компонентінің үлгісіндегі мәнін, емес үлгісіндегі мәнін пайдаланамыз. Жоғарыдағы қадамдарды рет қайталаңыз.

Қорытындылау

Гиббс үлгі алуы статистикалық қорытынды жасау үшін қолданылады (мысалы, параметрдің ең жақсы мәнін анықтау, мысалы, белгілі бір күні белгілі бір дүкенге қанша адам келуі мүмкін екенін анықтау, сайлаушының қай кандидатқа дауыс беруі ең мүмкін екенін және т.б.). Идеясы мынада: байқалған деректерді үлгі алу процесіне енгізу үшін әрбір байқалған дерек үшін жеке айнымалылар жасалады және осы айнымалылардан үлгі алудың орнына, байқалған мәндерге сәйкес айнымалылар бекітіледі. Қалған айнымалылардың үлестірілімі, осылайша, байқалған деректерге шартты түрде кейінгі үлестірілім болып табылады. Көзге түсетін параметрдің ең ықтимал мәнін (режимді) ең көп кездесетін үлгі мәнін таңдау арқылы анықтауға болады; бұл параметрдің ең жоғары апостериорлық бағалауына тең. (Параметрлер көбінесе үздіксіз болғандықтан, режимді бағалау үшін үлгідегі мәндерді шектеулі диапазонға немесе "интервалға" жіктеу қажет). Бірақ көбінесе үлгіленген мәндердің күтілетін мәні (орташа) таңдалады; бұл Байес бағалаушысы, ол Байес үлгілеуінен қол жетімді бүкіл үлестіру туралы қосымша деректерді пайдаланады, ал күтуді максимизациялау (EM) сияқты максимизациялау алгоритмі тек бір нүктені қайтара алады. Мысалы, мономодальды үлестіру үшін орташа (күтілетін мән) әдетте режимге (ең көп таралған мәнге) жақын, бірақ егер үлестіру бір бағытта қисайса, орташа сол бағытта жылжиды, бұл осы бағыттағы қосымша ықтималдық массасын ескереді. (Егер үлестіру мультимодальды болса, күтілетін мән мағыналы нүктені қайтармайды, сондықтан кез келген режим жақсырақ таңдау болып табылады.) Кейбір айнымалылар қызығушылық тудыратын параметрлерге сәйкес келсе, ал басқалары айнымалылар арасындағы қатынастарды дұрыс көрсету үшін модельге енгізілген пайдасыз ("қарсы") айнымалылар болып табылады. Үлгіленген мәндер барлық айнымалылар бойынша бірлескен үлестіруді көрсетеді, бірақ күтілетін мәндерді немесе режимдерді есептеу кезінде пайдасыз айнымалыларды ескермеуге болады; бұл пайдасыз айнымалыларды шеттетуге тең. Егер бірнеше айнымалы үшін мән қажет болса, күтілетін мән әр айнымалы бойынша жеке есептеледі. (Бірақ режимді есептеу кезінде барлық айнымалыларды бірге қарастыру қажет.) Бақылаумен оқыту, бақылаусыз оқыту және жартылай бақылаумен оқыту (яғни, мәндері жоқ деректермен оқыту) барлық айнымалылардың мәндерін бекіту және қалғандарынан үлгі алу арқылы жүзеге асырылуы мүмкін. Байқалған деректер үшін әрбір байқау үшін бір айнымалы болады – мысалы, байқаулар жиынтығының үлгілік орташасы немесе үлгілік дисперсиясына сәйкес келетін бір айнымалы емес. Шын мәнінде, "үлгілік орташа" немесе "үлгілік дисперсия" сияқты ұғымдарға сәйкес айнымалылар мүлдем болмайды. Оның орнына, мұндай жағдайда белгісіз нақты орташа және нақты дисперсияны көрсететін айнымалылар болады, ал осы айнымалылар үшін үлгілік мәндерді анықтау Гиббс үлгілеушісінің жұмысынан автоматты түрде шығады. Жалпыланған сызықтық модельдер (яғни, сызықтық регрессияның нұсқалары) кейде Гиббс үлгі алуымен де жүзеге асырылуы мүмкін. Мысалы, берілген бинарлық (иә/жоқ) таңдаудың ықтималдығын анықтау үшін пробит регрессиясы, регрессия коэффициенттеріне қалыпты үлестіріммен орналастырылған априорлық мәндермен, Гиббс үлгі алуымен жүзеге асырылуы мүмкін, өйткені қосымша айнымалыларды қосу және конъюгацияны пайдалануға болады. Алайда, логистикалық регрессияны осылай жүзеге асыруға болмайды. Бір мүмкіндік – логистикалық функцияны қалыпты үлестірімдердің қоспасымен (әдетте 7–9) жуықтау. Бірақ көбінесе Гиббс үлгі алуының орнына Метрополис-Хэстингс қолданылады.

Gibbs sampling is commonly used for statistical inference (e. g. determining the best value of a parameter, such as determining the number of people likely to shop at a particular store on a given day, the candidate a voter will most likely vote for, etc.). The idea is that observed data is incorporated into the sampling process by creating separate variables for each piece of observed data and fixing the variables in question to their observed values, rather than sampling from those variables. The distribution of the remaining variables is then effectively a posterior distribution conditioned on the observed data. The most likely value of a desired parameter (the mode) could then simply be selected by choosing the sample value that occurs most commonly; this is essentially equivalent to maximum a posteriori estimation of a parameter. (Since the parameters are usually continuous, it is often necessary to "bin" the sampled values into one of a finite number of ranges or "bins" in order to get a meaningful estimate of the mode.) More commonly, however, the expected value (mean or average) of the sampled values is chosen; this is a Bayes estimator that takes advantage of the additional data about the entire distribution that is available from Bayesian sampling, whereas a maximization algorithm such as expectation maximization (EM) is capable of only returning a single point from the distribution. For example, for a unimodal distribution the mean (expected value) is usually similar to the mode (most common value), but if the distribution is skewed in one direction, the mean will be moved in that direction, which effectively accounts for the extra probability mass in that direction. (If a distribution is multimodal, the expected value may not return a meaningful point, and any of the modes is typically a better choice.) Although some of the variables typically correspond to parameters of interest, others are uninteresting ("nuisance") variables introduced into the model to properly express the relationships among variables. Although the sampled values represent the joint distribution over all variables, the nuisance variables can simply be ignored when computing expected values or modes; this is equivalent to marginalizing over the nuisance variables. When a value for multiple variables is desired, the expected value is simply computed over each variable separately. (When computing the mode, however, all variables must be considered together.) Supervised learning, unsupervised learning and semi supervised learning (aka learning with missing values) can all be handled by simply fixing the values of all variables whose values are known, and sampling from the remainder. For observed data, there will be one variable for each observation—rather than, for example, one variable corresponding to the sample mean or sample variance of a set of observations. In fact, there generally will be no variables at all corresponding to concepts such as "sample mean" or "sample variance". Instead, in such a case there will be variables representing the unknown true mean and true variance, and the determination of sample values for these variables results automatically from the operation of the Gibbs sampler. Generalized linear models (i. e. variations of linear regression) can sometimes be handled by Gibbs sampling as well. For example, probit regression for determining the probability of a given binary (yes/no) choice, with normally distributed priors placed over the regression coefficients, can be implemented with Gibbs sampling because it is possible to add additional variables and take advantage of conjugacy. However, logistic regression cannot be handled this way. One possibility is to approximate the logistic function with a mixture (typically 7–9) of normal distributions. More commonly, however, Metropolis–Hastings is used instead of Gibbs sampling.

Дирихле таралымдарының құлдырауы

Иерархиялық Байес модельдерінде, категориялық айнымалылары бар, мысалы, жасырын Дирихлеттік бөлініс және табиғи тілді өңдеуде қолданылатын басқа да әртүрлі модельдерде, категориялық айнымалылар үшін алдын ала бөліністер ретінде қолданылатын Дирихлеттік бөліністерді жою жиі кездеседі. Мұндай жоюдың нәтижесінде берілген Дирихлеттік алдын ала бөлініске тәуелді барлық категориялық айнымалылар арасында тәуелділік пайда болады, ал жоюдан кейін осы айнымалылардың бірлескен үлестірілімі Дирихлеттік көпмүшелік үлестірімі болады. Бұл үлестірімде берілген категориялық айнымалының басқаларына шартты үлестірілімі өте қарапайым түрін қабылдайды, бұл Гиббс үлгілеуін жою жасалмаған жағдайдағыдан да оңай етеді. Ережелер келесідей: Дирихлеттік алдын ала түйінін жою тек алдын ала түйіннің ата-аналық және балалық түйіндеріне әсер етеді. Ата-анасы көбінесе тұрақты болғандықтан, көбінесе тек балаларын ескеру жеткілікті. Дирихлеттік алдын ала бөліністі жою осы алдын ала бөлініске тәуелді барлық категориялық балалар арасында тәуелділікті тудырады, бірақ басқа категориялық балалар арасында қосымша тәуелділіктер пайда болмайды. (Бұл, мысалы, бір гиперприормен байланысты бірнеше Дирихлеттік алдын ала бөліністер болған кезде есте сақтау маңызды. Әр Дирихлеттік алдын ала бөлініс өздігінен жойылып, тек тікелей балаларына ғана әсер етеді.) Жоюдан кейін бір тәуелді баланың басқаларына шартты үлестірілімі өте қарапайым түрін қабылдайды: берілген мәнді көру ықтималдығы осы мән үшін сәйкес гиперприордың қосындысына пропорционалды және басқа тәуелді түйіндердің сол мәнді қабылдауының санына пропорционалды. Осы алдын ала бөлініске тәуелді емес түйіндерді есепке алу қажет емес. Бұл ереже басқа итеративтік қорытындылау әдістерінде де қолданылады, мысалы, вариациялық Байес немесе күтуді максимизациялау; алайда, егер әдіс ішінара сандарды сақтауды қамтитын болса, онда сұраныстағы мәннің ішінара сандары барлық басқа тәуелді түйіндер бойынша қосылуы керек. Кейде мұндай жиынтықталған ішінара сандар күтілетін сандар немесе осыған ұқсас деп аталады. Ықтималдық алынған мәнге пропорционалды; нақты ықтималдықты анықтау үшін категориялық айнымалы қабылдай алатын барлық мүмкін мәндер бойынша қалыпқа келтіру қажет (яғни категориялық айнымалының әрбір мүмкін мәні үшін есептелген нәтижені қосып, барлық есептелген нәтижелерді осы сомаға бөлу). Егер берілген категориялық түйіннің тәуелді балалары болса (мысалы, ол қоспа модельдегі жасырын айнымалы болса), алдыңғы қадамда есептелген мән (күтілетін сандарға қосылған алдын ала бөлініс немесе есептелген кез келген мән) барлық балалардың ата-анасына берілген нақты шартты ықтималдықтарына көбейтілуі керек (ықтималдыққа пропорционалды есептелген мән емес!). Дирихлеттік көпмүшелік үлестірімі туралы мақаланы қараңыз. Егер Дирихлеттік алдын ала бөлініске тәуелді түйіндердің топтық мүшелігі басқа бір айнымалыға байланысты динамикалық түрде өзгеруі мүмкін болса (мысалы, тақырыптық модельдегідей, басқа жасырын категориялық айнымалымен индекстелген категориялық айнымалы), бірдей күтілетін сандар әлі де есептеледі, бірақ дұрыс айнымалылар жиынтығы енгізілсін деп мұқият жасау керек. Дирихлеттік көпмүшелік үлестірімі туралы мақаланы қараңыз, бұл тақырыптық модельдің контекстінде де қарастырылған.

In hierarchical Bayesian models with categorical variables, such as latent Dirichlet allocation and various other models used in natural language processing, it is quite common to collapse out the Dirichlet distributions that are typically used as prior distributions over the categorical variables. The result of this collapsing introduces dependencies among all the categorical variables dependent on a given Dirichlet prior, and the joint distribution of these variables after collapsing is a Dirichlet multinomial distribution. The conditional distribution of a given categorical variable in this distribution, conditioned on the others, assumes an extremely simple form that makes Gibbs sampling even easier than if the collapsing had not been done. The rules are as follows:
Collapsing out a Dirichlet prior node affects only the parent and children nodes of the prior. Since the parent is often a constant, it is typically only the children that we need to worry about. Collapsing out a Dirichlet prior introduces dependencies among all the categorical children dependent on that prior — but no extra dependencies among any other categorical children. (This is important to keep in mind, for example, when there are multiple Dirichlet priors related by the same hyperprior. Each Dirichlet prior can be independently collapsed and affects only its direct children.) After collapsing, the conditional distribution of one dependent children on the others assumes a very simple form: The probability of seeing a given value is proportional to the sum of the corresponding hyperprior for this value, and the count of all of the other dependent nodes assuming the same value. Nodes not dependent on the same prior must not be counted. The same rule applies in other iterative inference methods, such as variational Bayes or expectation maximization; however, if the method involves keeping partial counts, then the partial counts for the value in question must be summed across all the other dependent nodes. Sometimes this summed up partial count is termed the expected count or similar. The probability is proportional to the resulting value; the actual probability must be determined by normalizing across all the possible values that the categorical variable can take (i. e. adding up the computed result for each possible value of the categorical variable, and dividing all the computed results by this sum). If a given categorical node has dependent children (e. g. when it is a latent variable in a mixture model), the value computed in the previous step (expected count plus prior, or whatever is computed) must be multiplied by the actual conditional probabilities (not a computed value that is proportional to the probability!) of all children given their parents. See the article on the Dirichlet multinomial distribution for a detailed discussion. In the case where the group membership of the nodes dependent on a given Dirichlet prior may change dynamically depending on some other variable (e. g. a categorical variable indexed by another latent categorical variable, as in a topic model), the same expected counts are still computed, but need to be done carefully so that the correct set of variables is included. See the article on the Dirichlet multinomial distribution for more discussion, including in the context of a topic model.

Басқа конъюгат приорлардың құлдырауы

Жалпы, кез келген конъюгаттық алдынғы үлестірім, егер оның жалғыз баламалары оған конъюгаттық болса, ыдыратылуы мүмкін. Тиісті математикалық есептер құрама үлестірімдер туралы мақалада талқыланады. Егер тек бір балама түйін болса, нәтиже белгілі бір үлестірімді қабылдайды. Мысалы, бір Гаусс баламасы бар желіден кері гамма үлестірімді дисперсияны ыдырату Стьюденттің t үлестірімін береді. (Сонымен қатар, бір Гаусс баламасының орташа және дисперсиясын ыдырату, егер екеуі де конъюгаттық болса, Стьюденттің t үлестірімін береді, яғни Гаусс орташа, кері гамма дисперсиясы.) Егер бірнеше балама түйіндер болса, олардың барлығы Дирихлеттік категориялық жағдайдағыдай тәуелді болады. Нәтижесінде пайда болған бірлескен үлестірім жабық формаға ие болады, ол кейбір жағынан құрама үлестірімге ұқсас, бірақ оның құрамында әр балама түйін үшін факторлардың көбейтіндісі болады. Сонымен қатар, ең маңыздысы, балама түйіндердің бірінің шартты үлестірілімі басқаларына (сондай-ақ ыдыратылған түйіндердің ата-аналарына, бірақ балама түйіндердің баламаларына емес) берілгенде, барлық қалған балама түйіндердің кейінгі болжамдық үлестірімімен бірдей тығыздыққа ие болады. Бұдан әрі, кейінгі болжамдық үлестірім бір түйіннің негізгі құрама үлестірімімен бірдей тығыздыққа ие, бірақ әртүрлі параметрлермен. Жалпы формула құрама үлестірімдер туралы мақалада келтірілген. Мысалы, шартты тәуелсіз, бірдей үлестірілген Гаусс үлестірімді түйіндерінің жиынтығы бар Байес желісінде, орташа және дисперсияға конъюгаттық алдынғы үлестірімдер орналастырылған болса, орташа және дисперсияны ыдыратқаннан кейін басқа түйіндердің шартты үлестірімі Стьюденттің t үлестірімі болады. Сол сияқты, бірнеше Пуассон үлестірімді түйіндердің гамма алдынғы үлестірімін ыдырату, басқаларының біріне берілгенде шартты үлестірімнің теріс биномдық үлестірімді қабылдауына себеп болады. Ыдырату белгілі бір үлестірімді тудыратын жағдайларда, тиімді үлгі алу процедуралары жиі болады, оларды қолдану көбінесе (қажет болмаса да) ыдыратпаудан гөрі тиімдірек болады, және оның орнына алдынғы және балама түйіндерді бөлек үлгілеу. Алайда, құрама үлестірім жақсы белгілі болмаған жағдайда, одан үлгі алу оңай болмауы мүмкін, өйткені ол әдетте экспоненциалдық отбасыға жатпайды және әдетте лог-қоңыр болмайды (бұл бейімделген бас тарту үлгілеуін қолдану арқылы үлгілеуді жеңілдетеді, өйткені жабық форма әрқашан бар). Егер ыдыратылған түйіндердің баламаларының өзінде баламалар болса, графиктегі барлық басқа түйіндерге берілген осы балама түйіндердің бірінің шартты үлестірілімі осы екінші деңгейдегі баламалардың үлестірімін ескеруі керек. Атап айтқанда, алынған шартты үлестірім жоғарыда анықталғандай құрама үлестірімнің көбейтіндісіне және олардың ата-аналарына берілген барлық балама түйіндердің шартты үлестірімдеріне пропорционалды болады (бірақ олардың өз баламаларына емес). Бұл толық шартты үлестірімнің бірлескен үлестірімге пропорционалды екендігінен көрінеді. Егер ыдыратылған түйіндердің баламалары үздіксіз болса, бұл үлестірім әдетте белгілі бір формада болмайды және жабық форманы жазуға болатынына қарамастан, жақсы танылмаған құрама үлестірімдер үшін үлгі алу қиын болуы мүмкін. Алайда, балама түйіндер дискретті болған жағдайда, осы балама түйіндердің баламалары үздіксіз немесе дискретті болғанына қарамастан, үлгі алу мүмкін. Шын мәнінде, бұл жерде қолданылатын принцип Дирихлеттік көпмүшелік үлестірім туралы мақалада егжей-тегжейлі сипатталған.

In general, any conjugate prior can be collapsed out, if its only children have distributions conjugate to it. The relevant math is discussed in the article on compound distributions. If there is only one child node, the result will often assume a known distribution. For example, collapsing an inverse gamma distributed variance out of a network with a single Gaussian child will yield a Student's t distribution. (For that matter, collapsing both the mean and variance of a single Gaussian child will still yield a Student's t distribution, provided both are conjugate, i. e. Gaussian mean, inverse gamma variance.) If there are multiple child nodes, they will all become dependent, as in the Dirichlet categorical case. The resulting joint distribution will have a closed form that resembles in some ways the compound distribution, although it will have a product of a number of factors, one for each child node, in it. In addition, and most importantly, the resulting conditional distribution of one of the child nodes given the others (and also given the parents of the collapsed node(s), but not given the children of the child nodes) will have the same density as the posterior predictive distribution of all the remaining child nodes. Furthermore, the posterior predictive distribution has the same density as the basic compound distribution of a single node, although with different parameters. The general formula is given in the article on compound distributions. For example, given a Bayes network with a set of conditionally independent identically distributed Gaussian distributed nodes with conjugate prior distributions placed on the mean and variance, the conditional distribution of one node given the others after compounding out both the mean and variance will be a Student's t distribution. Similarly, the result of compounding out the gamma prior of a number of Poisson distributed nodes causes the conditional distribution of one node given the others to assume a negative binomial distribution. In these cases where compounding produces a well known distribution, efficient sampling procedures often exist, and using them will often (although not necessarily) be more efficient than not collapsing, and instead sampling both prior and child nodes separately. However, in the case where the compound distribution is not well known, it may not be easy to sample from, since it generally will not belong to the exponential family and typically will not be log concave (which would make it easy to sample using adaptive rejection sampling, since a closed form always exists). In the case where the child nodes of the collapsed nodes themselves have children, the conditional distribution of one of these child nodes given all other nodes in the graph will have to take into account the distribution of these second level children. In particular, the resulting conditional distribution will be proportional to a product of the compound distribution as defined above, and the conditional distributions of all of the child nodes given their parents (but not given their own children). This follows from the fact that the full conditional distribution is proportional to the joint distribution. If the child nodes of the collapsed nodes are continuous, this distribution will generally not be of a known form, and may well be difficult to sample from despite the fact that a closed form can be written, for the same reasons as described above for non well known compound distributions. However, in the particular case that the child nodes are discrete, sampling is feasible, regardless of whether the children of these child nodes are continuous or discrete. In fact, the principle involved here is described in fair detail in the article on the Dirichlet multinomial distribution.

Бұйырылған шамадан тыс сергітумен Гиббс үлгі алу аппараты

Бұйрықты шамадан тыс релаксация қолданатын Гиббс үлгісі, кез келген қадамда берілген тақ сандағы үміткер мәндерді іріктеп, оларды және бір мәнді белгілі бір рет бойынша сұрыптайды. Егер s реттелген тізімдегі s-ші кіші мән болса, онда s-ші үлкен мән ретінде таңдалады. Толығырақ ақпарат алу үшін Neal (1995) еңбегіне жүгініңіз.

Басқа кеңейтулер

Гиббстің үлгі алуын әр түрлі жолдармен кеңейтуге болады. Мысалы, егер шарттық таралымынан үлгі алу қиын болса, сол айнымалылардан үлгі алу үшін бір реттік кесімді үлгі алу немесе Metropolis-Hastings алгоритмін қолдануға болады. Сондай-ақ, кездейсоқ айнымалы емес, бірақ олардың мәні басқа айнымалылардан анық есептелетін айнымалыларды да қосу мүмкін. Жалпыланған сызықтық модельдер, мысалы, логистикалық регрессия (немесе "максималды энтропия модельдері") осылайша енгізілуі мүмкін. (BUGS, мысалы, модельдерді осылай араластыруға мүмкіндік береді.)

Ақаулық режімдері

Гиббс сынамасын алудың екі түрі сәтсіздікке ұшырауы мүмкін. Біріншісі – жоғары ықтималдық жағдайларының аралдары бар, олардың арасында байланыс жоқ. Мысалы, 2 биттік векторлар үшін ықтималдық үлестірімін қарастырайық, онда (0,0) және (1,1) векторларының әрқайсысының ықтималдығы ½, ал қалған екі вектордың (0,1) және (1,0) ықтималдығы нөлге тең. Гиббс сынамасы екі жоғары ықтималдық векторларының бірінде тұрып қалады және екіншісіне ешқашан жете алмайды. Жалпы алғанда, жоғары өлшемді, нақты мәнді векторлар үшін, егер вектордың екі нақты элементі толық корреляцияда болса (немесе толық антикорреляцияда болса), бұл екі элемент тұрып қалады және Гиббс сынамасы оларды өзгерте алмайды. Екінші мәселе тіпті барлық жағдайлардың ықтималдығы нөлден жоғары болғанда және жоғары ықтималдығы бар жалғыз арал болғанда да пайда болуы мүмкін. Мысалы, 100 биттік векторлар үшін ықтималдық үлестірімін қарастырайық, онда барлық нөлдерден тұратын вектор ½ ықтималдығымен кездеседі, ал қалған барлық векторлар бірдей ықтимал, сондықтан олардың әрқайсысының ықтималдығы тең. Егер сіз нөлдік вектордың ықтималдығын бағалауды қаласаңыз, нақты үлестіруден 100 немесе 1000 үлгі алу жеткілікті болар еді. Бұл жауаптың ½-ге жақын болуы мүмкін. Бірақ дәл осындай нәтижеге жету үшін Гиббс сынамасынан одан да көп үлгі алу қажет болады. Бұндай есептеуді компьютер өмір бойында орындай алмайды. Бұл мәселе күйдіру кезеңінің ұзақтығына қарамастан туындайды. Себебі, нақты үлестіруде нөлдік вектордың жиілігі жартылай, ал осы оқиғалар нөлдік емес векторлармен кездейсоқ араласады. Тіпті кішкентай үлгіде де нөлдік және нөлдік емес векторлар кездеседі. Бірақ Гиббс сынамасы ұзақ уақыт бойы (қатарынан) тек нөлдік векторды қайтарады, содан кейін ұзақ уақыт бойы (қатарынан) тек нөлдік емес векторларды қайтарады. Осылайша, нақты үлестіруге жуықтасу өте баяу болады, көптеген қадамдарды қажет етеді; мұндай көп қадамды орындау есептеу тұрғысынан ақылға қонымды уақыт ішінде мүмкін емес. Мұндағы баяу жуықтасу өлшемділіктің қарғысының салдары ретінде қарастырылуы мүмкін. Мұндай мәселені 100 биттік вектордың барлық битін бірдей үлгілеу арқылы шешуге болады. (Бұл 100 биттік вектордың үлкенірек айнымалылар жиынтығының бөлігі екенін болжайды. Егер осы вектор ғана үлгіленетін болса, блокпен үлгілеу Гиббс сынамасын мүлдем жасамаумен тең болады, бұл гипотеза бойынша қиын болар еді.)

There are two ways that Gibbs sampling can fail. The first is when there are islands of high probability states, with no paths between them. For example, consider a probability distribution over 2 bit vectors, where the vectors (0,0) and (1,1) each have probability ½, but the other two vectors (0,1) and (1,0) have probability zero. Gibbs sampling will become trapped in one of the two high probability vectors, and will never reach the other one. More generally, for any distribution over high dimensional, real valued vectors, if two particular elements of the vector are perfectly correlated (or perfectly anti correlated), those two elements will become stuck, and Gibbs sampling will never be able to change them. The second problem can happen even when all states have nonzero probability and there is only a single island of high probability states. For example, consider a probability distribution over 100 bit vectors, where the all zeros vector occurs with probability ½, and all other vectors are equally probable, and so have a probability of each. If you want to estimate the probability of the zero vector, it would be sufficient to take 100 or 1000 samples from the true distribution. That would very likely give an answer very close to ½. But you would probably have to take more than samples from Gibbs sampling to get the same result. No computer could do this in a lifetime. This problem occurs no matter how long the burn in period is. This is because in the true distribution, the zero vector occurs half the time, and those occurrences are randomly mixed in with the nonzero vectors. Even a small sample will see both zero and nonzero vectors. But Gibbs sampling will alternate between returning only the zero vector for long periods (about in a row), then only nonzero vectors for long periods (about in a row). Thus convergence to the true distribution is extremely slow, requiring much more than steps; taking this many steps is not computationally feasible in a reasonable time period. The slow convergence here can be seen as a consequence of the curse of dimensionality. A problem like this can be solved by block sampling the entire 100 bit vector at once. (This assumes that the 100 bit vector is part of a larger set of variables. If this vector is the only thing being sampled, then block sampling is equivalent to not doing Gibbs sampling at all, which by hypothesis would be difficult.)

Бағдарламалық жасақтама

OpenBUGS (Гиббс үлгілеуі арқылы Байес қорытындысы) бағдарламалық жасақтамасы Марков тізбегі Монте-Карло әдісін қолдана отырып, күрделі статистикалық модельдерді Байес талдауына мүмкіндік береді. JAGS (Және бір Гиббс үлгілеуші) – Марков тізбегі Монте-Карло әдісін пайдалана отырып, Байес иерархиялық модельдерді талдауға арналған GPL бағдарламасы. Church – ықтималдық бағдарламалар түрінде берілген кез келген үлестірулер бойынша Гиббс қорытындысын жүргізуге арналған тегін бағдарлама. PyMC – жалпы ықтималдық графикалық модельдерді Байес тәсілімен оқытуға арналған ашық кодты Python кітапханасы. Turing – ықтималдық бағдарламалауды қолдана отырып, Байес қорытындысын жасауға арналған ашық бастапқы кодты Julia кітапханасы.