Търсене на държавно пространство
В зависимост от това какъв метод за представяне на знания сме избрали – декларативен или продукционен – ние определяме начина на прилагане на знанието. С производствената система всичко е съвсем просто: ние директно интерпретираме продуктите.
Ако сме избрали декларативно представяне на знанието, тогава всичко е малко по-сложно. За да направим това, трябва да приложимтърсене в пространството на състоянието. Факт е, че структурираното представяне на знания е организирано йерархично. И ако се опитаме да приложим йерархично описание на входните данни, то на всяко негово ниво ще получим възможни варианти за интерпретация на данните – хипотези.
За да се избере ефективно една или повече от най-добрите хипотези, избягвайки комбинаторна експлозия, се използват алгоритми за търсене в пространството на състоянията.
Пространството на състоянието възниква, когато решението на проблема е разделено на отделни стъпки. Тук се разграничава началното състояние, когато все още не сме избрали хипотеза, както и крайното състояние, когато сме намерили хипотеза, която е възможно решение на нашия проблем. В процеса на търсене на тази хипотеза има операции на преход към следващото състояние. В същото време не е трудно да се забележи, че пространственото състояние има експоненциална сложност в зависимост от числените стъпки. Ако се заемете да прекосите цялото пространство на състоянието, това ще отнеме експоненциално време.
За да се избегне този проблем, се прилагат различни алгоритми за търсене. Те се делят на два вида - изчерпателно търсене и евристично търсене. Както вече стана ясно, изчерпателното търсене в по-голямата част от случаите не е подходящо (освен ако не решаваме много малък проблем), но има известна образователна стойност. Затова първо ще го разгледаме и ако сте запознати с него, можете веднага да преминете към евристичния тип.
Търсене по изчерпателно изброяване
Има следните видове изчерпателно търсене: първо търсене в ширина, първо търсене в дълбочина и итеративно дълбоко търсене. По време на търсене в ширина ние предприемаме всяка възможна стъпка в пространственото състояние на първоначалното състояние и получаваме нов набор от състояния. По-нататък, от всяко състояние на този набор, ние отново предприемаме всички възможни стъпки, получаваме следващия набор от състояния и така нататък - докато намерим решение. Графично търсенето в ширина може да бъде представено като движение на фронта в пространството на състоянието.
Първото търсене в дълбочина означава, че правим една крачка от първоначалното състояние, след което правим още една крачка от новото състояние и т.н., докато достигнем крайното състояние или състояние, от което не могат да се правят повече стъпки. В този случай ние се връщаме рекурсивно назад и отново предприемаме стъпки от състоянието, в което сме се върнали, докато намерим решение. Лесно е да се види, че такова търсене в широчината има експоненциална сложност както във времето, така и в паметта. Търсенето първо в дълбочина има експоненциална времева сложност. Разбира се, може да имаме късмет и да намерим решение веднага, но на практика това е малко вероятно.
Итеративното задълбочаващо се търсене е оптимизация за търсене в дълбочина и в ширина, която гарантирано намира най-близкото решение до първоначалното състояние, като същевременно избягва експоненциалната сложност. Как се реализира този алгоритъм? Търсим в дълбочина с ограничение на дълбочината на константата N. Намерихме решение - добро. Не го намерихме - повтаряме търсенето първо в дълбочина с константата N + 1 и така нататък, докато бъде намерено. Този алгоритъм, макар и лесен за изпълнение, е подходящ само за най-простите проблеми.
Евристично търсене
Най-често практическите проблеми се решават с помощта на евристикаТърсене. Евристичното търсене се основава на функцията за оценка на състоянието. За разлика от изчерпателните алгоритми за търсене, евристичното търсене ви позволява да класирате пространствените състояния въз основа на тяхната „перспектива“. Евристичното търсене претърсва пространството на състоянието по по-целенасочен начин от изчерпателните алгоритми за търсене. Важно е, че в много задачи оценката на състоянието е най-добрата оценка за пътя за достигане на даденото състояние от първоначалното. Ако такава оценка е възможна в нашия проблем, тогава алгоритмите за евристично търсене са значително опростени.
Основният клас евристични алгоритми за търсене е търсене от най-доброто състояние. Той включва три основни алгоритъма: Greedy Search, Beam Search и A*. Тяхната обща идея се основава на поддържане на набора от постигнати състояния по време на търсенето и избор на едно или няколко най-добри състояния на всяка стъпка.
Най-простият от тях еалчно търсене. Ако се приложи към проблема за намиране на най-добрия път в графика, това ще даде добре познатия алгоритъм на Дейкстра. Алчното търсене, избирайки състоянието, от което ще продължи търсенето, търси състоянието с най-добра оценка на пътя от първоначалното до даденото. Затова се нарича "алчен" - защото "грабва" най-доброто състояние в момента, без да мисли за последствията. Естествено, подобно на много алчни алгоритми, тази стратегия не води до оптимално решение. Крайните състояния често се достигат по начин, който е твърде дълъг и неоптимален. В допълнение, алчното търсене трябва постоянно да поддържа набори от всички достигнати състояния, които могат да бъдат твърде много, причинявайки прекомерна консумация на памет.
Търсенето с лъч има своите предимства и недостатъци. Основният му недостатък е, че за разлика от greedy, ray search не гарантира намиране на крайното състояние с най-добро качество, тъй като най-доброто състояние може да изпадне от него по време на движението на фронта. На практика това може да се пребори чрез регулиране на предната ширина. Колкото по-тясна е предната част, толкова по-бързо работи алгоритъмът, но толкова по-често допуска грешки. Колкото по-широка е предната част, толкова по-добре работи алгоритъмът, но по-дълго. Това е едно от важните му предимства – възможността за лесно балансиране между скорост и качество. Търсенето с лъч е много популярно в академичните среди, особено сред китайските учени. Той е лесен за изпълнение и работи доста добре.
Идеята на алгоритъма A* е, че на всяка стъпка избираме не най-доброто, а най-обещаващото състояние в момента. Състоянието, през което е най-вероятно да премине пътят към най-доброто крайно състояние.
За оценка на текущото състояние в алгоритъма A* се добавя евристична оценка отдолу за остатъка от пътя до крайното състояние. Ако евристичната оценка отдолу е достатъчно добра, тогава A* работи ефективно и бързо намира най-доброто състояние. В този случай A* ще бъде полином на броя на стъпките, а не експоненциален. A* е наистина добър алгоритъм, в работата си го използвам много по-често от търсенето с лъчи.
В третия пост от тази поредица ще говорим за методите за получаване на знания, използвани при създаването на изкуствен интелект, както и за машинното обучение - по-специално за тези методи, които се използват във FineReader.