Үлгіні тану алгоритмі: Rete алгоритмі

Кіріспе

Үлгілерді сәйкестендіру алгоритмі

Rete алгоритмі (REEtee, RAYtee, сирек кездесетін REET, rehTAY) – ережелерге негізделген жүйелерді іске асыруға арналған үлгілерді сәйкестендіру алгоритмі. Алгоритм білім базасындағы көптеген нысандарға немесе фактілерге көптеген ережелерді немесе үлгілерді тиімді қолдану үшін жасалған. Ол жүйенің дерек қорындағы және фактілеріндегі мәліметтерге сүйене отырып, қандай ережелерді орындау керектігін анықтау үшін қолданылады. Rete алгоритмін Карнеги Меллон университетінің Чарльз Л. Форги әзірледі, алғаш рет 1974 жылы ғылыми еңбек ретінде жарияланды, кейін 1979 жылы Ph.D. диссертациясында және 1982 жылғы мақаласында толықтырылды.

Шолу

Наивті сараптамалық жүйенің іске асырылуы әрбір ережені білім базасындағы белгілі фактілермен тексеріп, қажет болған жағдайда осы ережені орындай алады, содан кейін келесі ережеге өтеді (және аяқталғаннан кейін бірінші ережеге қайта оралады). Бірақ орташа көлемдегі ережелер мен фактілерден тұратын білім базалары үшін мұндай қарапайым тәсіл тым баяу болады. Rete алгоритмі тиімдірек іске асыру үшін негіз құрайды. Rete негізделген сараптамалық жүйе түйіндер желісін құрастырады, онда әрбір түйін (тамыр түйінінен басқа) ереженің сол жағындағы (шарт бөлігінде) кездесетін үлгіге сәйкес келеді. Тамыр түйінінен жапырақ түйініне дейінгі жол ереженің толық сол жақ бөлігін анықтайды. Әрбір түйіннің осы үлгіге сәйкес келетін фактілердің жады бар. Бұл құрылым, по сути, жалпыланған трие болып табылады. Жаңа фактілер расталатын немесе өзгертілген кезде, олар желі бойынша таралады, сол факті осы үлгіге сәйкес келгенде түйіндерге белгілер қойылады. Егер факт немесе фактілердің комбинациясы белгілі бір ережеге қатысты барлық үлгілерді қанағаттандырса, жапырақ түйініне жетеді және тиісті ереже орындалады. Rete алғаш рет OPS5 өндірістік жүйе тілінің негізгі қозғалтқышы ретінде қолданылды, ол Digital Equipment Corporation үшін R1 сияқты алғашқы жүйелерді құру үшін пайдаланылды. Rete көптеген танымал ережелік қозғалтқыштар мен сараптамалық жүйе қабықшаларының негізіне айналды, оның ішінде CLIPS, Jess, Drools, IBM Operational Decision Management, BizTalk Rules Engine және Soar. "Rete" сөзі латын тілінде "желі" немесе "тарақ" деген мағынаны білдіреді. Қазіргі итальян тілінде бұл сөз "желі" мағынасында қолданылады. Чарльз Форги "Rete" терминін анатомияда қан тамырлары мен жүйке талшықтарының желісін сипаттау үшін қолданғандықтан қабылдағанын айтқан. Rete алгоритмі жылдамдықты арттыру үшін жадты құрбан етуге бағытталған. Көп жағдайда қарапайым іске асырулармен салыстырғанда жылдамдық бірнеше есе артады (Rete өнімділігі теориялық тұрғыдан жүйедегі ережелер санына тәуелді емес болғандықтан). Дегенмен, өте үлкен сараптамалық жүйелерде бастапқы Rete алгоритмі жад пен серверді пайдалану мәселелеріне тап болады. Басқа алгоритмдер, жаңа және Rete негізделген, аз жадты қажет ететін (мысалы, Rete* немесе Collection Oriented Match) әзірленді.

A naive implementation of an expert system might check each rule against known facts in a knowledge base, firing that rule if necessary, then moving on to the next rule (and looping back to the first rule when finished). For even moderate sized rules and facts knowledge bases, this naive approach performs far too slowly. The Rete algorithm provides the basis for a more efficient implementation. A Rete based expert system builds a network of nodes, where each node (except the root) corresponds to a pattern occurring in the left hand side (the condition part) of a rule. The path from the root node to a leaf node defines a complete rule left hand side. Each node has a memory of facts that satisfy that pattern. This structure is essentially a generalized trie. As new facts are asserted or modified, they propagate along the network, causing nodes to be annotated when that fact matches that pattern. When a fact or combination of facts causes all of the patterns for a given rule to be satisfied, a leaf node is reached and the corresponding rule is triggered. Rete was first used as the core engine of the OPS5 production system language, which was used to build early systems including R1 for Digital Equipment Corporation. Rete has become the basis for many popular rule engines and expert system shells, including CLIPS, Jess, Drools, IBM Operational Decision Management, BizTalk Rules Engine, and Soar. The word 'Rete' is Latin for 'net' or 'comb'. The same word is used in modern Italian to mean 'network'. Charles Forgy has reportedly stated that he adopted the term 'Rete' because of its use in anatomy to describe a network of blood vessels and nerve fibers. The Rete algorithm is designed to sacrifice memory for increased speed. In most cases, the speed increase over naïve implementations is several orders of magnitude (because Rete performance is theoretically independent of the number of rules in the system). In very large expert systems, however, the original Rete algorithm tends to run into memory and server consumption problems. Other algorithms, both novel and Rete based, have since been designed that require less memory (e. g. Rete* or Collection Oriented Match).

Сипаттама

Rete алгоритмі өрнекті сәйкестендіру өндіріс жүйесінде ("ережелер") өнімдерге ("фактілер") сәйкес келетін деректердің топтамасын ("мәліметтер") сәйкестендіруге жауапты функционалдылықтың іске асырылуын жалпыланған логикалық сипаттайды (ережелер қозғалтқышының санаты). Өндіріс бір немесе бірнеше шарттардан және шарттарға сәйкес келетін әрбір толық фактілер жиынтығы үшін орындалуы мүмкін әрекеттер жиынтығынан тұрады. Шарттар фактілердің атрибуттарын, соның ішінде фактілер түрін анықтайтын/анықтамашыларды тексереді. Rete алгоритмі келесідей негізгі сипаттамаларды көрсетеді: ол түйіндерді ортақтастыру арқылы кейбір артықшылықты азайтады немесе жояды. Ол әртүрлі фактілер түрлерін біріктіру кезінде ішінара сәйкестіктерді сақтайды. Бұл өз кезегінде өндіріс жүйесіне өндіріс жүйесінің жұмыс жадына әр өзгеріс енгізілген сайын барлық фактілерді толық қайта бағалаудан аулақ болуға мүмкіндік береді. Оның орнына, өндіріс жүйесі тек жұмыс жадындағы өзгерістерді (дельталарды) бағалауы керек. Бұл жұмыс жадынан деректерді қайтарып алғанда жад элементтерін тиімді жоюға мүмкіндік береді. Rete алгоритмі өрнекті сәйкестендіру қозғалтқыштарында сәйкестендіру функционалдығын іске асыру үшін кеңінен қолданылады, ол алдыңғы тізбектеу мен қорытынды шығаруды қолдау үшін сәйкестікті шешу акті циклын пайдаланады. Ол көптеген-көп сәйкестіктерді қамтамасыз етеді, бұл іздеу желісінде көптеген немесе барлық мүмкін шешімдерді табу қажет болған кезде маңызды ерекшелік. Retes – жоғары деңгейдегі ережелерді көрсететін бағытталған ациклді графиктер. Олар әдетте орындалу кезінде жад объектілерінің желісін пайдалану арқылы бейнеленеді. Бұл желілер ереже шарттарын (үлгілерді) фактілерге (реляциялық деректер жиынтығына) сәйкес келеді. Rete желілері реляциялық сұраныс процессорларының бір түрі ретінде әрекет етеді, олар деректердің кездейсоқ саны бойынша проекцияларды, таңдауларды және шартты түрде қосылуларды орындайды. Өндірістер (ережелер) әдетте талдаушылар мен әзірлеушілер жоғары деңгейдегі ережелер тілін қолдана отырып анықтайды. Олар ереже жиынтығына жиналады, содан кейін, көбінесе орындалу кезінде орындалатын Rete-ге аударылады. Фактілер жұмыс жадына "қосылғанда", қозғалтқыш әрбір факт үшін жұмыс жады элементтерін (WME) жасайды. Фактілер – жиынтықтар, сондықтан олар деректердің кездейсоқ санын қамтуы мүмкін. Әрбір WME-де бүкіл жиынтық болуы мүмкін немесе әр факт WME-дің жиынтығымен бейнеленуі мүмкін, онда әр WME-де белгіленген ұзындығы бар жиынтық болады. Бұл жағдайда, жиынтықтар әдетте үштік (3 жиынтық) болып табылады. Әрбір WME Rete желісіне бір түбір тораптан кіреді. Түбір түйіні әр WME-ді өзінің бала түйіндеріне жібереді, содан кейін әр WME желі арқылы таралуы мүмкін, мүмкін ол терминал түйініне жеткенше аралық естеліктерде сақталуы мүмкін.

The Rete algorithm provides a generalized logical description of an implementation of functionality responsible for matching data tuples ("facts") against productions ("rules") in a pattern matching production system (a category of rule engine). A production consists of one or more conditions and a set of actions that may be undertaken for each complete set of facts that match the conditions. Conditions test fact attributes, including fact type specifiers/identifiers. The Rete algorithm exhibits the following major characteristics:

It reduces or eliminates certain types of redundancy through the use of node sharing. It stores partial matches when performing joins between different fact types. This, in turn, allows production systems to avoid complete re evaluation of all facts each time changes are made to the production system's working memory. Instead, the production system needs only to evaluate the changes (deltas) to working memory. It allows for efficient removal of memory elements when facts are retracted from working memory. The Rete algorithm is widely used to implement matching functionality within pattern matching engines that exploit a match resolve act cycle to support forward chaining and inferencing. It provides a means for many–many matching, an important feature when many or all possible solutions in a search network must be found. Retes are directed acyclic graphs that represent higher level rule sets. They are generally represented at run time using a network of in memory objects. These networks match rule conditions (patterns) to facts (relational data tuples). Rete networks act as a type of relational query processor, performing projections, selections and joins conditionally on arbitrary numbers of data tuples. Productions (rules) are typically captured and defined by analysts and developers using some high level rules language. They are collected into rule sets that are then translated, often at run time, into an executable Rete. When facts are "asserted" to working memory, the engine creates working memory elements (WMEs) for each fact. Facts are tuples, and may therefore contain an arbitrary number of data items. Each WME may hold an entire tuple, or, alternatively, each fact may be represented by a set of WMEs where each WME contains a fixed length tuple. In this case, tuples are typically triplets (3 tuples). Each WME enters the Rete network at a single root node. The root node passes each WME on to its child nodes, and each WME may then be propagated through the network, possibly being stored in intermediate memories, until it arrives at a terminal node.

Альфа желісі

Торап графигінің "сол" (альфа) жағы тұрақты мәндермен WME атрибуттарын салыстыратын қарапайым шарттық тестілерге негізделген жеке WME-лерді іріктеуге жауапты дискриминациялық желі құрайды. Дискриминациялық желідегі тораптар бір WME-нің екі немесе одан көп атрибуттарын салыстыратын тестілерді де орындай алады. Егер WME бір тораппен көрсетілген шарттарға сәтті сәйкес келсе, ол келесі торапқа жіберіледі. Көптеген жүйелерде түбірлік тораптың тікелей бағынышты тораптары әр WME-нің объекті идентификаторын немесе факт түрін тексеру үшін қолданылады. Сондықтан, бір объекті түрін көрсететін барлық WME-лер әдетте дискриминациялық желінің белгілі бір тармағындағы тораптар арқылы өтеді. Дискриминациялық желідегі альфа-тораптардың әр тармағы (сонымен қатар 1 кіріс торабы деп аталады) альфа-жад деп аталатын жадта аяқталады. Бұл жадтар белгілі бір торап тармағындағы әрбір тораптың әрбір шартына сәйкес келетін WME жиынтықтарын сақтайды. Егер WME тармақтағы кем дегенде бір шартты орындамаса, ол тиісті альфа-жадта сақталмайды. Альфа-торап тармақтары шарттардың қайталануын азайту үшін бөлінуі мүмкін.

Бета желісі

Графиктің "оң" (бета) жағы негізінен әртүрлі WME арасындағы қосылыстарды жүзеге асырады. Бұл міндетті емес, және қажет болған жағдайда ғана қосылады. Ол 2 кіріс түйінінен тұрады, мұнда әр түйіннің "сол" және "оң" кірісі бар. Әрбір бета түйіні өзінің шығысын бета жадына жібереді. Rete сипаттамаларында бета желісі ішіндегі токендердің өтуі жиі айтылады. Алайда, осы мақалада біз деректер таратуды токендер емес, WME тізімдері арқылы сипаттаймыз, әртүрлі іске асыру мүмкіндіктерін және токендердің мақсаты мен қолданылуын ескере отырып. Кез келген WME тізімі бета желісінен өтетін кезде, оған жаңа WME қосылуы мүмкін, ал тізім бета жадында сақталуы мүмкін. Бета жадындағы WME тізімі берілген өндіріс шарттарына ішінара сәйкес келеді. Бета түйіндерінің тармағының соңына жеткен WME тізімдері бір өндіріс үшін толық сәйкес келеді және терминалды түйіндерге жіберіледі. Бұл түйіндер кейде p түйіндері деп аталады, мұнда "p" өндіріс дегенді білдіреді. Әрбір терминалды түйін бір өндірісті білдіреді, ал әрбір терминалды түйінге келетін WME тізімі осы өндірістің шарттарына сәйкес келетін WME-лердің толық жиынтығын білдіреді. Әрбір WME тізімі үшін өндіріс түйіні "күн тәртібінде" жаңа өндіріс мысалын "белсенділендіреді". Күн тәртібі әдетте басымдық кезек ретінде іске асырылады. Бета түйіндері әдетте бета жадында сақталған WME тізімдері мен альфа жадында сақталған жеке WME арасында қосылыстарды жасайды. Әрбір бета түйіні екі кіріс жадымен байланысты. Альфа жады WM-ді сақтайды және жаңа WME сақталған сайын бета түйінінде "оң" белсенділендіруді орындайды. Бета жады WME тізімдерін сақтайды және жаңа WME тізімі сақталған сайын бета түйінінде "сол" белсенділендіруді орындайды. Қосылу түйіні оң жақтан белсендірілген кезде, ол кіріс альфа жадынан жаңа сақталған WME-нің бір немесе бірнеше атрибуттарын кіріс бета жадындағы әрбір WME тізіміндегі тиісті WME атрибуттарымен салыстырады. Қосылу түйіні сол жақтан белсендірілген кезде, ол бета жадында жаңа сақталған бір WME тізімін қарап шығып, берілген WME-лердің нақты атрибуттық мәндерін алады. Ол осы мәндерді альфа жадындағы әрбір WME атрибутының мәндерімен салыстырады. Әрбір бета түйіні WME тізімдерін шығарады, олар бета жадында сақталады немесе тікелей терминалды түйінге жіберіледі. WME тізімдері бета жадында сақталады, егер қозғалтқыш келесі бета түйіндерінде қосымша сол жақтан белсенділендіруді орындаса. Логикалық тұрғыдан алғанда, бета түйіндерінің тармағының басындағы бета түйіні ерекше жағдай, өйткені ол желідегі жоғарырақ бета жадынан ешқандай кіріс алмайды. Әртүрлі қозғалтқыштар бұл мәселені әртүрлі жолмен шешеді. Кейбір қозғалтқыштар альфа жадынан бета түйіндерінің сол жақ кірісіне қосылу үшін арнайы адаптер түйіндерін пайдаланады. Басқа қозғалтқыштар бета түйіндеріне екі альфа жадынан тікелей кіріс алуға мүмкіндік береді, біреуін "сол" кіріс ретінде, екіншісін "оң" кіріс ретінде қарастырады. Екі жағдайда да "басты" бета түйіндері екі альфа жадынан кіріс алады. Түйіннің артықшылықтарын жою үшін кез келген альфа немесе бета жады бірнеше бета түйінін белсендіру үшін пайдаланылуы мүмкін. Бета желісінде қосылу түйіндерінен басқа қосымша түйін түрлері болуы мүмкін, олардың кейбіреулері төменде сипатталған. Егер Rete-де бета желісі болмаса, альфа түйіндері бір WME-ні қамтитын токендерді тікелей p түйіндеріне жібереді. Бұл жағдайда WME-ні альфа жадында сақтаудың қажеті болмауы мүмкін.

The "right" (beta) side of the graph chiefly performs joins between different WMEs. It is optional, and is only included if required. It consists of 2 input nodes where each node has a "left" and a "right" input. Each beta node sends its output to a beta memory. In descriptions of Rete, it is common to refer to token passing within the beta network. In this article, however, we will describe data propagation in terms of WME lists, rather than tokens, in recognition of different implementation options and the underlying purpose and use of tokens. As any one WME list passes through the beta network, new WMEs may be added to it, and the list may be stored in beta memories. A WME list in a beta memory represents a partial match for the conditions in a given production. WME lists that reach the end of a branch of beta nodes represent a complete match for a single production, and are passed to terminal nodes. These nodes are sometimes called p nodes, where "p" stands for production. Each terminal node represents a single production, and each WME list that arrives at a terminal node represents a complete set of matching WMEs for the conditions in that production. For each WME list it receives, a production node will "activate" a new production instance on the "agenda". Agendas are typically implemented as prioritised queues. Beta nodes typically perform joins between WME lists stored in beta memories and individual WMEs stored in alpha memories. Each beta node is associated with two input memories. An alpha memory holds WM and performs "right" activations on the beta node each time it stores a new WME. A beta memory holds WME lists and performs "left" activations on the beta node each time it stores a new WME list. When a join node is right activated, it compares one or more attributes of the newly stored WME from its input alpha memory against given attributes of specific WMEs in each WME list contained in the input beta memory. When a join node is left activated it traverses a single newly stored WME list in the beta memory, retrieving specific attribute values of given WMEs. It compares these values with attribute values of each WME in the alpha memory. Each beta node outputs WME lists that are either stored in a beta memory or sent directly to a terminal node. WME lists are stored in beta memories whenever the engine will perform additional left activations on subsequent beta nodes. Logically, a beta node at the head of a branch of beta nodes is a special case because it takes no input from any beta memory higher in the network. Different engines handle this issue in different ways. Some engines use specialised adapter nodes to connect alpha memories to the left input of beta nodes. Other engines allow beta nodes to take input directly from two alpha memories, treating one as a "left" input and the other as a "right" input. In both cases, "head" beta nodes take their input from two alpha memories. In order to eliminate node redundancies, any one alpha or beta memory may be used to perform activations on multiple beta nodes. As well as join nodes, the beta network may contain additional node types, some of which are described below. If a Rete contains no beta network, alpha nodes feed tokens, each containing a single WME, directly to p nodes. In this case, there may be no need to store WMEs in alpha memories.

Дау-жанжалдарды шешу

Кез келген сәйкестікті шешу циклы барысында, қозғалтқыш жұмыс жадына бекітілген фактілерге сәйкес келетін барлық мүмкін нұсқаларды табады. Ағымдағы барлық сәйкестіктер анықталғаннан және тиісті өндіріс инстанциялары күн тәртібіне қосылғаннан кейін, қозғалтқыш осы өндіріс инстанцияларының "орындалу" ретін анықтайды. Бұл қақтығысты шешу деп аталады, ал белсендірілген өндіріс инстанцияларының тізімі – қақтығыс жиыны деп аталады. Рет ережелердің маңыздылығына (ұсынылымдыққа), ережелердің тізбегіне, әрбір инстанциядағы фактілердің жұмыс жадына қосылған уақытына, әр өндірістің күрделілігіне немесе басқа да өлшемдерге сүйене отырып белгіленуі мүмкін. Көптеген қозғалтқыштар ереже жасаушыларға әртүрлі қақтығысты шешу стратегияларын таңдауға немесе бірнеше стратегияны тізбектеуге мүмкіндік береді. Қақтығысты шешу Rete алгоритмінің құрамы ретінде анықталмаған, бірақ осы алгоритммен бірге қолданылады. Кейбір мамандандырылған өндіріс жүйелері қақтығысты шешуді жүзеге асырмайды.

Өндірісті орындау

Конфликттерді шешкеннен кейін, қозғалтқыш енді бірінші өндіріс инстанциясын "қосып", өндіріске қатысты әрекеттер тізімін орындайды. Әрекеттер өндіріс инстанциясының WME тізіміндегі деректерге әсер етеді. Дәстүрлі түрде, қозғалтқыш барлық өндіріс инстанциялары орындалғанша әрбір өндіріс инстанциясын ретімен орындауды жалғастырады. Әрбір өндіріс инстанциясы кез келген сәйкестікті шешу циклында бір рет ғана орындалады. Бұл қасиет рефракция деп аталады. Дегенмен, өндіріс инстанцияларын орындау тізбегі жұмыс жадына өзгерістер енгізу арқылы кез келген сәтте тоқтатылуы мүмкін. Ереже әрекеттерінде қозғалтқыштың жұмыс жадынан WME-ді қосу немесе алып тастау туралы нұсқаулар болуы мүмкін. Кез келген өндіріс инстанциясы мұндай бір немесе бірнеше өзгерістерді орындаған сайын, қозғалтқыш дереу жаңа сәйкестікті шешу әрекет циклына кіреді. Бұл жұмыс жадындағы WME-ді "жаңартуды" да қамтиды. Жаңарту WME-ді алып тастап, содан кейін қайтадан қосу арқылы жүзеге асырылады. Қозғалтқыш өзгертілген деректерді сәйкестендіреді, бұл өз кезегінде күнтізбенің өндіріс инстанциялары тізіміне өзгерістер енгізуі мүмкін. Осылайша, кез келген нақты өндіріс инстанциясы үшін әрекеттер орындалғаннан кейін, бұрын белсендірілген инстанциялар күнтізбенің тізімінен алынып тасталуы мүмкін, ал жаңа инстанциялар белсендірілуі мүмкін. Жаңа сәйкестікті шешу әрекетінің бөлігі ретінде қозғалтқыш күнтізбенің қақтығыстарын шешеді, содан кейін ағымдағы бірінші инстанцияны орындайды. Қозғалтқыш өндіріс инстанцияларын орындауды және күнтізбенің бос қалғанша жаңа сәйкестікті шешу циклдарына кіруді жалғастырады. Осы сәтте ереже қозғалтқышы жұмысын аяқтаған деп есептеледі және тоқтатылады. Кейбір қозғалтқыштар алдыңғы циклда орындалған кейбір өндіріс инстанциялары жаңа циклда қайта орындалмауына мүмкіндік беретін, тіпті олар күнтізбенің тізімінде болса да, кеңейтілген рефракция стратегияларын қолдайды. Қозғалтқыш күнтізбенің ешқашан бос күйге жетпейтін, сонымен қатар аяқталмайтын циклдерге түсуі мүмкін. Осы себепті көптеген қозғалтқыштар өндіріс әрекеттері тізімінен шақырылатын "тоқтату" командаларын қолдайды. Олар сондай-ақ автоматты циклді анықтау мүмкіндігін де ұсынады, онда аяқталмайтын циклдер белгілі бір қайталану санынан кейін автоматты түрде тоқтатылады. Кейбір қозғалтқыштар күн тәртібі бос болған кезде тоқтамай, керісінше, жаңа фактілер сырттан енгізілгенше күту күйіне өтетін модельді қолдайды. Конфликттерді шешуге қатысты, белсендірілген өндіріс инстанцияларын орындау Rete алгоритмінің ерекшелігі емес. Алайда, бұл Rete желілерін пайдаланатын қозғалтқыштардың маңызды ерекшелігі болып табылады. Rete желілері ұсынатын кейбір оңтайландырулар қозғалтқыш бірнеше сәйкестікті шешу циклдарын орындайтын жағдайларда ғана тиімді.

Having performed conflict resolution, the engine now "fires" the first production instance, executing a list of actions associated with the production. The actions act on the data represented by the production instance's WME list. By default, the engine will continue to fire each production instance in order until all production instances have been fired. Each production instance will fire only once, at most, during any one match resolve act cycle. This characteristic is termed refraction. However, the sequence of production instance firings may be interrupted at any stage by performing changes to the working memory. Rule actions can contain instructions to assert or retract WMEs from the working memory of the engine. Each time any single production instance performs one or more such changes, the engine immediately enters a new match resolve act cycle. This includes "updates" to WMEs currently in the working memory. Updates are represented by retracting and then re asserting the WME. The engine undertakes matching of the changed data which, in turn, may result in changes to the list of production instances on the agenda. Hence, after the actions for any one specific production instance have been executed, previously activated instances may have been de activated and removed from the agenda, and new instances may have been activated. As part of the new match resolve act cycle, the engine performs conflict resolution on the agenda and then executes the current first instance. The engine continues to fire production instances, and to enter new match resolve act cycles, until no further production instances exist on the agenda. At this point the rule engine is deemed to have completed its work, and halts. Some engines support advanced refraction strategies in which certain production instances executed in a previous cycle are not re executed in the new cycle, even though they may still exist on the agenda. It is possible for the engine to enter into never ending loops in which the agenda never reaches the empty state. For this reason, most engines support explicit "halt" verbs that can be invoked from production action lists. They may also provide automatic loop detection in which never ending loops are automatically halted after a given number of iterations. Some engines support a model in which, instead of halting when the agenda is empty, the engine enters a wait state until new facts are asserted externally. As for conflict resolution, the firing of activated production instances is not a feature of the Rete algorithm. However, it is a central feature of engines that use Rete networks. Some of the optimisations offered by Rete networks are only useful in scenarios where the engine performs multiple match resolve act cycles.

Экзистенциалдық және әмбебап сандық өлшеулер

Шартты сынақтар көбінесе жеке топтамаларда таңдаулар мен қосылуларды орындау үшін қолданылады. Дегенмен, қосымша бета түйін түрлерін іске асыру арқылы Rete желілері сандық есептеулерді орындауға мүмкіндік алады. Экзистенциалдық сандық анықтау жұмыс жадында кем дегенде бір сәйкес WME жиынтығының бар екенін тексеруді қамтиды. Универсалды сандық анықтау жұмыс жадындағы WME-лердің барлық жиынтығы белгілі бір шартты қанағаттандыратынын тексеруді қамтиды. Универсалды сандық өлшеудің бір түрі WME жиынтығынан алынған WME-лердің белгілі бір саны белгілі бір критерийлерге сәйкес келе ме екенін тексеруі мүмкін. Бұл нақты санға немесе сәйкес келулердің ең кем санына тексеруге байланысты болуы мүмкін. Сандық есептеу барлық Rete жүйелерінде де жүзеге асырылмайды және қолдау көрсетілген жағдайларда бірнеше нұсқасы бар. Экзистенциалдық сандық өлшеудің теріске шығару ретінде белгілі бір түрі кеңінен, бірақ әрқашан емес, қолдау табады және маңызды құжаттарда сипатталған. Экзистенциалдық теріске шығарылған шарттар мен конъюнкциялар сәйкес WME немесе WME жиынтықтарының жоқ екенін тексеру үшін арнайы бета түйіндерін пайдалануды қамтиды. Бұл түйіндер WME тізімдерін тек сәйкес келу болмаған жағдайда ғана таратады. Теріске шығарудың нақты жүзеге асырылуы әртүрлі болуы мүмкін. Бір тәсіл бойынша түйін сол жақ кірісінен алатын әрбір WME тізімі үшін қарапайым санауды сақтайды. Санау оң жақ кірісінен алынған WME-лермен табылған сәйкесулердің санын көрсетеді. Түйін тек санауы нөлге тең WME тізімдерін таратады. Басқа тәсіл бойынша түйін сол жақ кірісінен алынған әрбір WME тізімі үшін қосымша жадты сақтайды. Бұл жад бета-жадтың бір түрі болып табылады және оң жақ кірісінен алынған WME-лермен сәйкес келетін WME тізімдерін сақтайды. Егер WME тізімінде жадында WME тізімдері болмаса, ол желіде таратылады. Бұл тәсілде теріске шығару түйіндері әдетте қосымша бета-жадта олардың нәтижесін сақтаудың орнына тікелей бета түйіндерін белсендіреді. Теріске шығару түйіндері «теріске шығару сәтсіздік ретінде» жұмыс істейді. Жұмыс жадына өзгерістер енгізілген кезде бұрын ешқандай WME-ге сәйкес келмеген WME тізімі жаңадан қосылған WME-ге сәйкес болуы мүмкін. Бұл жағдайда таратылған WME тізімі және оның барлық көшірмелері желідегі төменгі бета-жадтардан алынып тасталуы керек. Жоғарыда сипатталған екінші тәсіл WME тізімдерін тиімді түрде жою механизмдерін қолдау үшін жиі қолданылады. WME тізімдері алынып тасталған кезде, кез келген сәйкес өндіріс инстанциялары белсенділігін жоғалтады және күнтізбенің тізімінен алынып тасталады. Экзистенциалдық сандық есептеу екі теріске шығару бета түйінін біріктіру арқылы жүзеге асырылуы мүмкін. Бұл қос теріске шығару семантикасын білдіреді (мысалы, «Егер сәйкес WME болмаса, онда…»). Бұл көптеген өндірістік жүйелер қолданатын әдеттегі тәсіл.

Conditional tests are most commonly used to perform selections and joins on individual tuples. However, by implementing additional beta node types, it is possible for Rete networks to perform quantifications. Existential quantification involves testing for the existence of at least one set of matching WMEs in working memory. Universal quantification involves testing that an entire set of WMEs in working memory meets a given condition. A variation of universal quantification might test that a given number of WMEs, drawn from a set of WMEs, meets given criteria. This might be in terms of testing for either an exact number or a minimum number of matches. Quantification is not universally implemented in Rete engines, and, where it is supported, several variations exist. A variant of existential quantification referred to as negation is widely, though not universally, supported, and is described in seminal documents. Existentially negated conditions and conjunctions involve the use of specialised beta nodes that test for non existence of matching WMEs or sets of WMEs. These nodes propagate WME lists only when no match is found. The exact implementation of negation varies. In one approach, the node maintains a simple count on each WME list it receives from its left input. The count specifies the number of matches found with WMEs received from the right input. The node only propagates WME lists whose count is zero. In another approach, the node maintains an additional memory on each WME list received from the left input. These memories are a form of beta memory, and store WME lists for each match with WMEs received on the right input. If a WME list does not have any WME lists in its memory, it is propagated down the network. In this approach, negation nodes generally activate further beta nodes directly, rather than storing their output in an additional beta memory. Negation nodes provide a form of 'negation as failure'. When changes are made to working memory, a WME list that previously matched no WMEs may now match newly asserted WMEs. In this case, the propagated WME list and all its extended copies need to be retracted from beta memories further down the network. The second approach described above is often used to support efficient mechanisms for removal of WME lists. When WME lists are removed, any corresponding production instances are de activated and removed from the agenda. Existential quantification can be performed by combining two negation beta nodes. This represents the semantics of double negation (e. g., "If NOT NOT any matching WMEs, then "). This is a common approach taken by several production systems.

Жады индекстеу

Rete алгоритмі жұмыс жадының индекстеуіне ешқандай нақты тәсілді міндеттемейді. Дегенмен, қазіргі заманғы өндіріс жүйелерінің көпшілігі индекстеу механизмдерін қамтамасыз етеді. Кейбір жағдайларда тек бета-жадтар индекстеледі, ал басқаларында альфа және бета-жадтардың екеуі де индекстеуге қолданылады. Жақсы индекстеу стратегиясы – өндіріс жүйесінің жалпы тиімділігін анықтаудағы маңызды фактор, әсіресе жоғары комбинаторлық үлгілерді сәйкестендіруге (яғни, бета-қосылу түйіндерін қарқынды пайдалануға) әкелетін ережелер жиынтығын орындау кезінде, немесе кейбір өңдеуіштер үшін, көптеген сәйкестік шешімдерін анықтау циклдарында WME-лерді көптеп жоюды орындау кезінде. Жадтар көбінесе хэш-кестелердің комбинацияларын пайдаланып іске асырылады, ал хэш-мәндер жадтардың толық мазмұнына емес, WME тізімдері мен WME-лердің ішінен шартты қосылуларды жасау үшін қолданылады. Бұл, өз кезегінде, Rete желісінің жүзеге асыратын бағалаулар санын айтарлықтай азайтады.

ЖМЕ мен ЖМЕ тізімдерін жою

WME жұмыс жадынан алынған кезде, ол сақталған барлық альфа жадтан жойылуы керек. Соған қоса, WME-ні қамтитын WME тізімдері бета жадтан алынып тасталуы керек, ал осы WME тізімдері үшін белсенді өндіріс мысалдары күн тәртібінен деактивацияланып, алынып тасталуы керек. Іске асырудың бірнеше нұсқасы бар, оның ішінде ағаш негізіндегі және қайта сәйкестендіру негізіндегі жою. Кейбір жағдайларда жоюды оңтайландыру үшін жадты индекстеу қолданылуы мүмкін.

Орындау шарттары

Ереже жиынтығында өнімдерді анықтағанда, шарттарды «ИЛИ» (OR) операторы арқылы топтастыру жиі кездеседі. Көптеген өндіріс жүйелерінде бұл, бірнеше «ИЛИ» (OR) арқылы біріктірілген үлгіні қамтитын бір өнімді, бірнеше өнім ретінде қарастыру арқылы іске асырылады. Соның нәтижесінде құрылған Rete желісі терминалдық түйіндер жиынтығын қамтиды, олар бірлесіп жеке өнімдерді көрсетеді. Бұл тәсіл «ИЛИ» (OR) шарттарының қысқа тұйықталуына мүмкіндік бермейді. Сонымен қатар, кейбір жағдайларда, бірдей WME жиынтығы бірнеше ішкі өнімдерге сәйкес келгенде, күн тәртібінде өнімнің қайталама нұсқалары іске қосылуы мүмкін. Кейбір жүйелер осы мәселені шешу үшін күн тәртібіндегі қайталауды болдырмау механизмін ұсынады.

Диаграмма

Келесі диаграмма Rete негізгі топологиясын көрсетеді және әртүрлі түйін түрлері мен жадтар арасындағы байланыстарды көрсетеді. Көптеген жүзеге асырулар тупльдік жұмыс жады элементтерінің алғашқы іріктеуін жүзеге асыру үшін типтік түйіндерді пайдаланады. Типтік түйіндерді арнайы іріктеу түйіндері деп қарастыруға болады. Олар әртүрлі тупльдік қатынас түрлерін ажыратады. Диаграммада жоққа шығарылған конъюнкция түйіндері сияқты арнайы түйін түрлерінің қолданылуы көрсетілмеген. Кейбір жүйелер функционалдылықты кеңейту және оңтайландыруды максималдау үшін бірнеше түйін мамандануларын іске асырады. Диаграмма Rete-тің логикалық көрінісін ұсынады. Жүзеге асырулар физикалық ерекшеліктері бойынша өзгеше болуы мүмкін. Атап айтқанда, диаграммада бета түйін тармақтарының басында оң жақтан белсендіруді қамтамасыз ететін фиктивті кірістер көрсетілген. Жүйелер альфа жадтарына тікелей оң белсендіруді жүзеге асыруға мүмкіндік беретін адаптерлер сияқты басқа да тәсілдерді іске асыруы мүмкін. Диаграммада түйіндерді бөлісудің барлық мүмкіндіктері көрсетілмеген. Rete алгоритмінің толыққанды және егжей-тегжейлі сипаттамасы үшін Роберт Дуренбостың "Ірі оқу жүйелері үшін өндіріс сәйкестендіруі" кітабының 2-тарауына қараңыз (төмендегі сілтемені қараңыз).

Альфа желісі

Мүмкін болатын нұсқа – дискриминациялық желіде әрбір аралық түйін үшін қосымша жадтар енгізу. Бұл Rete жүйесінің күрделігін арттырады, бірақ ережелерді Rete жүйесіне динамикалық түрде қосу немесе жою қажет болғанда тиімді болуы мүмкін, бұл дискриминациялық желінің топологиясын динамикалық түрде өзгертуді жеңілдетеді. Дооренбос басқаша іске асыру жолын сипаттаған. Онда дискриминациялық желі жадтар жиынтығымен және индекспен алмастырылады. Индекс хэш-кесте арқылы іске асырылуы мүмкін. Әрбір жад бір шартты үлгіге сәйкес келетін WME-лерді сақтайды, ал индекс жадтарды олардың үлгілері бойынша анықтау үшін қолданылады. Бұл тәсіл WME-лер тұрақты ұзындықтағы түйіндерді білдіргенде және әрбір түйіндің ұзындығы қысқа болғанда ғана (мысалы, 3 түйінден) қолданылуы тиімді. Сонымен қатар, бұл әдіс тек тұрақты мәндермен теңдікті тексеретін шартты үлгілерге ғана қолданылады. WME Rete жүйесіне енгенде, индекс WME атрибуттарына сәйкес келетін жадтар жиынтығын табу үшін қолданылады, содан кейін WME осы жадтардың әрқайсысына тікелей қосылады. Бұл іске асыруда өзі 1 кіріс түйіндері жоқ. Дегенмен, теңсіздік сынақтарын жүзеге асыру үшін Rete қосымша 1 кіріс түйін желілерін қамтуы мүмкін, WME-лер жадқа орналастырылмас бұрын олар арқылы өтеді. Әйтпесе, теңсіздік сынақтарын төменде сипатталған бета желіде жүргізуге болады.

Бета желісі

Токендердің тізімдерін құру, онда әр токен бір WME-ні сақтайды – бұл жиі қолданылатын нұсқа. Бұл жағдайда, жартылай сәйкестік үшін WME тізімдері токендердің тізбегі арқылы көрсетіледі. Бұл тәсіл артықшылықты болуы мүмкін, себебі ол WME тізімдерін бір токеннен екіншісіне көшіру қажеттілігін жояды. Оның орнына, бета-түйінге жартылай сәйкестік тізіміне қосылуы тиіс WME-ні сақтау үшін жаңа токенді құру және осы токенді кіріс бета-жадында сақталған басты токенге тіркеу жеткілікті. Жаңа токен енді токен тізбегінің басы болып табылады және шығыс бета-жадында сақталады. Бета-түйіндер токендерді өңдейді. Токен – жад ішіндегі сақтау бірлігі, сондай-ақ жадтар мен түйіндер арасындағы ақпарат алмасу бірлігі. Көптеген жағдайларда, токендер альфа-жадтарда пайда болады, онда олар жеке WME-лерді сақтау үшін қолданылады. Бұл токендер кейін бета-желісіне жіберіледі. Әр бета-түйін өз жұмысын орындайды және нәтижесінде жартылай сәйкестікті білдіретін WME тізімін сақтау үшін жаңа токендерді құруы мүмкін. Бұл кеңейтілген токендер бета-жадтарда сақталады және келесі бета-түйіндерге жіберіледі. Мұндай жағдайда, бета-түйіндер әдетте бета-желі арқылы WME тізімдерін беру үшін, әр алынған токеннен жаңа токендерге WME тізімдерін көшіріп, содан кейін біріктіру немесе басқа операциялар нәтижесінде тізімдерге қосымша WME-лерді қосады. Жаңа токендер шығыс жадында сақталады.

Түрлі қарастырулар

Rete алгоритмімен анықталмағанымен, кейбір қозғалтқыштар шындықты сақтауды жақсырақ бақылауға мүмкіндік беретін кеңейтілген мүмкіндіктерді ұсынады. Мысалы, егер бір өндіріс үшін сәйкестік табылса, онда жаңа ЖМЭ-лер құрылып, олар өз кезегінде басқа өндірістің шарттарына сай келуі мүмкін. Егер жұмыс жадына енгізілген өзгерістер бірінші сәйкестіктің жарамсыз болуына себеп болса, онда екінші сәйкестік те жарамсыз болуы мүмкін. Rete алгоритмі логикалық шындық тәуелділіктерін автоматты түрде анықтап, басқару механизмін анықтамайды. Дегенмен, кейбір қозғалтқыштар шындық тәуелділіктерін автоматты түрде сақтауға мүмкіндік беретін қосымша мүмкіндіктерді қолдайды. Мұндай жағдайда, бір ЖМЭ-нің жойылуы логикалық шындық тұжырымдамаларын сақтау үшін басқа ЖМЭ-лердің автоматты түрде жойылуына әкелуі мүмкін. Rete алгоритмі негіздеменің қандай да бір тәсілін анықтамайды. Негіздеме – бұл сарапшы және шешімдерді қабылдау жүйелерінде жиі қолданылатын механизм, онда ең қарапайым жағдайда жүйе соңғы қорытындыға жету үшін қолданылған ішкі шешімдердің барлығын көрсетеді. Мысалы, сарапшы жүйесі жануардың ірі, сұр түсті, үлкен құлақтары, сүйегі және тістері бар екенін көрсете отырып, оның піл екендігін негіздеуі мүмкін. Кейбір қозғалтқыштар Rete алгоритмін іске асырумен қатар негіздеме жүйесін де ұсынады. Бұл мақалада Rete алгоритмінің барлық мүмкін нұсқалары мен кеңейтімдері толық сипатталмайды. Басқа да қарастырылатын мәселелер мен инновациялар бар. Мысалы, қозғалтқыштар Rete желісінде белгілі бір дерек түрлеріне және дерек көздеріне, мысалы, бағдарламалық объектілерге, XML деректеріне немесе реляциялық деректер кестелеріне үлгіні сәйкестендіру ережесін қолдану үшін арнайы қолдау көрсете алады. Тағы бір мысал – көптеген қозғалтқыштар Rete желісіне кіретін әрбір ЖМЭ үшін уақыт белгілерін қосымша түрде ұсынады және осы уақыт белгілерін конфликтілерді шешу стратегияларымен бірге қолдануы мүмкін. Қозғалтқыштар қозғалтқышқа және оның жұмыс жадына бағдарламалық түрде қол жеткізуге мүмкіндік беретін тәсілдерде айқын айырмашылықтарға ие және негізгі Rete моделін параллель және таратылған өңдеу нысандарын қолдау үшін кеңейте алады.

Although not defined by the Rete algorithm, some engines provide extended functionality to support greater control of truth maintenance. For example, when a match is found for one production, this may result in the assertion of new WMEs which, in turn, match the conditions for another production. If a subsequent change to working memory causes the first match to become invalid, it may be that this implies that the second match is also invalid. The Rete algorithm does not define any mechanism to define and handle these logical truth dependencies automatically. Some engines, however, support additional functionality in which truth dependencies can be automatically maintained. In this case, the retraction of one WME may lead to the automatic retraction of additional WMEs in order to maintain logical truth assertions. The Rete algorithm does not define any approach to justification. Justification refers to mechanisms commonly required in expert and decision systems in which, at its simplest, the system reports each of the inner decisions used to reach some final conclusion. For example, an expert system might justify a conclusion that an animal is an elephant by reporting that it is large, grey, has big ears, a trunk and tusks. Some engines provide built in justification systems in conjunction with their implementation of the Rete algorithm. This article does not provide an exhaustive description of every possible variation or extension of the Rete algorithm. Other considerations and innovations exist. For example, engines may provide specialised support within the Rete network in order to apply pattern matching rule processing to specific data types and sources such as programmatic objects, XML data or relational data tables. Another example concerns additional time stamping facilities provided by many engines for each WME entering a Rete network, and the use of these time stamps in conjunction with conflict resolution strategies. Engines exhibit significant variation in the way they allow programmatic access to the engine and its working memory, and may extend the basic Rete model to support forms of parallel and distributed processing.

Рет II

1980 жылдары Чарльз Форги Rete алгоритмінің мұрагері – Rete II-ні жасады. Бастапқы Rete-ден (ашық қолданыс) айырмашылығы, бұл алгоритм жарияланбады. Rete II күрделі проблемалар үшін (бірнеше есе артық) жақсы нәтижелер көрсетеді және ресми түрде CLIPS/R2, C/++ және 1998 жылы OPSJ (Java-дағы іске асырылым) бағдарламаларында қолданылды. KnowledgeBased Systems Corporation жүргізген сынақтар бойынша Rete II күрделі проблемаларда 100-ден 1000 есеге дейін өнімділікті арттырады. Rete II екі негізгі жақсартумен сипатталады: Rete желісінің жалпы өнімділігіне қатысты нақты оңтайландырулар (үлкен деректер жиынтықтарымен жұмыс істегенде өнімділікті арттыру үшін хэштелген жадты пайдалануды қоса алғанда) және Rete желісімен біріктірілген кері тізбектеу алгоритмін енгізу. Кері тізбектеу алгоритмі ғана Rete мен Rete II арасындағы көрсеткіштердегі ең үлкен өзгерістерді түсіндіре алады. Rete II FICO компаниясының (бұрын Fair Isaac деп аталған) Advisor коммерциялық өнімінде іске асырылған, сондай-ақ Jess (кем дегенде 5.0 нұсқасынан бастап) Rete желісімен біріктірілген коммерциялық кері тізбектеу алгоритмін қосады, бірақ толық сипаттамасы жарияланбағандықтан, ол Rete II-ні толыққанды іске асырды деу қиын.

Рет-III

2000-шы жылдардың басында Чарльз Форги FICO инженерлерімен бірлесіп Rete III қозғалтқышын жасады. Rete III алгоритмі, Rete NT емес, Rete II-нің FICO тауарлық белгісі болып табылады және FICO Advisor қозғалтқышының құрамында іске асырылған. Бұл, негізінен, Advisor қозғалтқышына қолжетімділік беретін API-мен жабдықталған Rete II қозғалтқышы, себебі Advisor қозғалтқышы басқа FICO өнімдеріне де қолжетімділікке ие.

Rete-NT

2010 жылы Форги Rete алгоритмінің жаңа буынын жасады. InfoWorld жүргізген сынақта алгоритм бастапқы Rete алгоритмінен 500 есе жылдам, ал оның алдыңғы нұсқасы Rete II-ден 10 есе жылдам деп есептелді. Бұл алгоритм қазір Sparkling Logic компаниясына лицензияланды, Форги инвестор және стратегиялық кеңесші ретінде қосылған компанияның SMARTS өнімінің логикалық қорытындылау механизмі болып табылады.

Қайта-қайта

Rete бірінші реттік логиканы (негізінен, егер-әйтпесе операторларын) қолдауға бағытталғандықтан, Rete OO белгісіздікті қолдайтын ережелерге негізделген жүйені ұсынуды мақсат етеді (шешім қабылдау үшін қажетті ақпарат жетіспесе немесе қате болса). Автордың ұсынысына сәйкес, "егер Қауіп болса, дабыл қағылады" ережесі "Қауіптің ықтималдығын ескере отырып, дабыл қағудың белгілі бір ықтималдығы болады" немесе тіпті "Қауіп қаншалықты жоғары болса, дабыл соншалықты қаттырақ естілуі керек" сияқты жақсартуларға ие болуы мүмкін. Осы мақсатта, ол Rete алгоритмін іске асыратын Drools тілін ықтималдық логиканы, мысалы, тұманды логика мен Байес желілерін қолдайтындай кеңейтеді.