Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Символдар тізбектерін модельдеуге арналған грамматикалық теория, табиғи тілдердің құрылымын түсіну мақсатындағы есептеу лингвистикасы саласындағы зерттеулерден туындады.
Grammar theory to model symbol strings originated from work in computational linguistics aiming to understand the structure of natural languages.
Жасырын Марков модельдерімен байланыс
PCFG модельдері жасырын Марков модельдері тұрақты грамматиканы кеңейткендей, контекстсіз грамматиканы да кеңейтеді. Inside Outside алгоритмі – Forward Backward алгоритмінің аналогы. Ол белгілі бір PCFG негізінде берілген тізбекке сәйкес келетін барлық туындылардың жалпы ықтималдығын есептейді. Бұл PCFG-нің тізбекті жасау ықтималдығымен тең, және тізбектің берілген грамматикамен қаншалықты үйлесімді екенін көрсетеді. Inside Outside алгоритмі РНК жағдайында оқу тізбектерінен алынған бастапқы жиіліктерді бағалау үшін модельді параметрлеуде қолданылады. CYK алгоритмінің динамикалық бағдарламалау түрлері PCFG моделі үшін РНК тізбегінің Витерби талдауын анықтайды. Бұл талдау – берілген PCFG бойынша тізбектің ең мүмкін туындысы.
PCFGs models extend context free grammars the same way as hidden Markov models extend regular grammars. The Inside Outside algorithm is an analogue of the Forward Backward algorithm. It computes the total probability of all derivations that are consistent with a given sequence, based on some PCFG. This is equivalent to the probability of the PCFG generating the sequence, and is intuitively a measure of how consistent the sequence is with the given grammar. The Inside Outside algorithm is used in model parametrization to estimate prior frequencies observed from training sequences in the case of RNAs. Dynamic programming variants of the CYK algorithm find the Viterbi parse of a RNA sequence for a PCFG model. This parse is the most likely derivation of the sequence by the given PCFG.
Грамматикалық құрылым
Контекстсіз грамматикалар табиғи тілдерді модельдеу әрекеттерінен шабыттанған ережелер жиынтығы ретінде ұсынылады. (немесе қосындысы) ағаштағы барлық ереже салмақтарының. Әрбір ереже салмағы, егер ереже ағашта қолданылса, сол кезде ғана қосылады. WCFG-ның ерекше жағдайы – PCFG, онда салмақтар (лог) ықтималдықтары болып табылады. CYK алгоритмінің кеңейтілген түрі, берілген WCFG үшін тізбектің "ең жеңіл" (ең аз салмақты) туындысын табу үшін қолданылуы мүмкін. Егер ағаш салмағы ереже салмақтарының көбейтіндісі болса, WCFG және PCFG бірдей ықтималдық үлестірілімдерін білдіре алады. Осының салдарынан, формалды тіл теориясының белоктарды талдаудағы көптеген қолданымдары жергілікті өзара әрекеттесулерге негізделген қарапайым функционалдық үлгілерді модельдеуге арналған төменгі экспрессивті қуатты грамматикаларды жасаумен шектелген. Белок құрылымдары көбінесе ұялы және қиылысқан қатынастарды қоса алғанда, жоғары реттік тәуелділіктерді көрсетеді, сондықтан олар кез келген CFG-ның мүмкіндіктерін асып түседі.
Context free grammars are represented as a set of rules inspired from attempts to model natural languages. (or sum ) of all rule weights in the tree. Each rule weight is included as often as the rule is used in the tree. A special case of WCFGs are PCFGs, where the weights are (logarithms of ) probabilities. An extended version of the CYK algorithm can be used to find the "lightest" (least weight) derivation of a string given some WCFG. When the tree weight is the product of the rule weights, WCFGs and PCFGs can express the same set of probability distributions. As a consequence, most applications of formal language theory to protein analysis have been mainly restricted to the production of grammars of lower expressive power to model simple functional patterns based on local interactions. Since protein structures commonly display higher order dependencies including nested and crossing relationships, they clearly exceed the capabilities of any CFG.