Costas-Tyros_rus_MS

По очевидным причинам я также сменил название предиката на dSearch.

23.5.Эвристическийпоиск

Стратегии поиска, которые мы изучали до этого момента, никак не использовали основанных на доменах знаниях для выбора рассматриваемой ветки. Этот недостаток исправляется эвристической стратегией, которая оценивает цену перемещения от корня к цели через узел N до того, как перехо дить в N. Функция оценки задаётся следующей формулой:

используем эвристическую стратегию для того, чтобы найти путь между двумя городами на ниже приведённой карте.

Однако, до того, как начать, я хотел бы рассказать одну историю. Я люблю малоизвестные языки, и выучил довольно много из них. Например, я знаю древнеегипетский, греческий Гомера (Homeric

Greek), эсперанто, латынь, и т. д. Когда я был подростком, я даже выучил гуарани, второразрядный

язык, на котором говорят только в Парагвае, малонаселённой стране.

Парень (или девушка) перевел книгу за авторством В. Н. Пушкина (V. N. Pushkin) с русского на один из второразрядных языков, который я выучил. Названием книги было «Эвристика, наука о твор ческом мышлении» (Heuristics, the Science of Creative Thought). Когда я прочитал книгу Пушкина в пе реводе, я понял, насколько сложно найти хорошую эвристическую функцию и насколько более слож но перевести текст с одного языка на другой, особенно если ты не сильно разбираешься в затраги ваемой в тексте теме. Обработка естественного языка сложна не только для компьютеров, но и для людей в том числе. Например, доктор Пушкин пробовал объяснить правила игры в шахматы, для то го, чтобы использовать эту игру как тестовый стенд для искусственного интеллекта. В своём объясне

нии он сказал, что конь перемещается вдоль пути в форме буквы Г1. Переводчик привёл следующее переложение оригинала: Конь перемещается вдоль пути в форме перевёрнутой буквы L. После этого

долгого отступления, давайте вернёмся к эвристическому поиску. Города будут представлены свои ми координатами:

1 Конечно же, в этом месте у автора было пояснение: “where Г is a letter of the Russian alphabet” – «где Г – это буква русского алфавита», что в данном случае, вероятно, пояснять не надо.

151

xy("a", 2, 4). xy("b", 5, 6).

Двухместные факты описывают односторонние дороги, которые соединяют города:

op("a", "b" ). op("b", "m"). op("m", "f").

Вы узнали, что в эвристическом поиске очередь должна быть сортирована так, что наиболее многообещающие пути будут выставлены вперёд. Сортирующий алгоритм, который вы изучите, очень интересен, и изобретён Тони Хоаре. Каждый путь представлен нижеприведённой конструкци ей.

t(real, real, it)

где первый аргумент даёт значение эвристической функции F для узла; второй аргумент даёт значение . Сортирующий алгоритм имеет предикат сравнения как первый аргумент, и сдвигает многообещающие ветки в начало очереди.

search([T|Queue],S):

if goalReached(T) then S= T

else Extension= [E || toDaughter(T,E)], NewQueue= list::append(Queue,Extension), BestFirst= list::sortBy(cmp, NewQueue), search(BestFirst, S)

end if.

Законченная программа приведена ниже.

implement main /*heureka*/ domains

item=r(string, string). it= item*. node=t(real, real, it). tree=node*.

class facts

xy: (string, integer, integer). op: (string, string).

class predicates

getXY:(string, integer, integer) determ (i, o, o). cost: (string, string) > real.

hn: (string) > real.

not_in_circle: (string, it) determ (i,i). theGoal: (string) procedure (o). toDaughter: (node, node) nondeterm (i,o). init:(string) procedure (o). goalReached:(node) determ.

search: (tree, node) determ (i,o). prtSolution: (node) procedure (i). solve: () procedure.

cmp:(node, node) > core::compareResult. clauses

classInfo("main", "heureka 1.0").

cmp(t(A, _, _), t(B, _, _)) = core::greater() : A > B, !. cmp(t(A, _, _), t(B, _, _)) = core::equal() : A=B, !. cmp(_, _) = core::less().

152

then prtSolution(S)

else stdio::write("No solution") end if.

run(): console::init(), solve(). end implement main /*heureka*/

goal mainExe::run(main::run).

154

Глава 24: Нейросети

Испания не отличается своими научными достижениями. На самом деле, во Франции есть семьи со вдвое большим числом нобелевских лауреатов, чем во всей Испании. В Европе не много стран с меньшим количеством нобелевских лауреатов, чем в Испании; одна из них – это Сербия, но одним из сербов, не получивших нобелевскую премию, был Никола Тесла (Nicola Tesla), а страна, у которой есть Никола Тесла, не нуждается в нобелевских лауреатах. Несмотря на это, единственные два испан ских нобелевских лауреата находятся среди величайших учёных всех времён, вместе с Ньютоном и Архимедом. В этой главе вы узнаете об одном из них.

Испанский учёный дон Сантьяго Рамон и Кахаль (Don Santiago Ramón y Cajal) изу чал физиологию нервной системы и заключил, что она работает благодаря клеткам,

которые он назвал нейронами. В наши дни учёные считают, что нейрон принимает сигналы от других нейронов через связи, называемые синапсами (synapses). Между прочим, synapsis – это греческое слово, означающее связь. Обычно нейрон собирает

сигналы от остальных нейронов через сеть структур, называемых дендриты

(dendrites), что означает ветви дерева на греческом; если интенсивность входящих сигналов превос ходит определённый порог, нейрон запускается и посылает электрические раздражители через ствол, известный как аксон, который разделяется на древовидные дендриты, чьи синапсы активиру ют другие нейроны. Итак, подводя итоги… на конце каждого дендрита синапс преобразует деятель ность нейрона в электрические раздражители, которые возбуждают или затормаживают другой ней

рон.

В 1947 году Уоррен Маккаллох (Warren McCullogh) и Уолтер Питтс (Walter Pitts) предложили пер вую математическую модель нейрона. Их нейрон был бинарным устройством с фиксированным по рогом; он получал множество входных сигналов от возбуждающих синапсов, что ставило в соответст вие каждому входу определённый вес, являющийся положительным целым числом; тормозящие входные сигналы имели абсолютное право вето над любыми возбуждающими импульсами; на каж дом шаге обработки нейроны синхронно обновлялись, суммируя взвешенные возбуждающие входы и устанавливали выходное значение равное 1 тогда и только тогда, когда сумма была больше или равна пороговому значению и нейрон не принимал тормозящий импульс.

Следующим значительным продвижением в теории нейросетей был перцептрон, предложенный Франком Розенблаттом (Frank Rosenblatt) в статье 1958 года. Розенблатт был профессором Cornell

University, который является моим альма матер1. Однако, мне не посчастливилось быть знакомым с ним, так как он скончался за много лет до того, как я пришёл в этот университет.

Рисунок 24.1. Перцептрон с тремя входами.

1 Родным университетом, если кто не знает.

155

Перцептрон складывает входные сигналы, помноженные на вес (для каждого входного сигнала свой вес), и если результат больше поро гового значения, он [перцептрон – прим. пер.] производит ненулевой вы ходной сигнал. Этот метод был улучшен подачей взвешенной суммы в сигмоидную функцию, и принятием уже этого полученного значения как выходного сигнала перцептрона. Если вы начертите сигмоид, он примет форму греческой буквы ς, которая известна как конечная сигма (final sigma); отсюда и название сигмоид. Сигмоид определяется как

1

1

В Прологе это определение принимает следующий вид:

sigmoid(X)= 1.0/(1.0+math::exp( X)).

Рис. 24.1, приведённый выше, изображает перцептрон с тремя входами. Обозначим входы как x1, x2, и x3. В этом случае, выходным сигналом будет результат выражения

натренировать перцептрон на распознание входных образов. На самом деле, существует алгоритм, который модифицирует веса перцептрона так, что тот сможет различать два или больше образов. Например, перцептрон с двумя входами можно научить определять, когда логический вентиль «И» (and­gate) выдаcт 1, а когда 0.

Алгоритм обучения перцептрона должен иметь набор обучающих примеров. Предположим, что перцептрон изучает работу логического вентиля «И». Вот возможные примеры:

facts

eg:(unsigned, real, real, real). clauses

eg(0, 1, 1, 1). eg(1, 1, 0, 0). eg(2, 0, 1, 0). eg(3, 0, 0, 0).

У перцептрона имеется предсказывающая процедура, которая использует формулу ∑ для предсказания выходного значения по заданному набору входных. В Прологе предсказывающая процедура может быть закодирована так, как показано ниже.

predicted_out(E, V) : eg(E, I_1, I_2, _), getWgt(0, W_0), getWgt(1, W_1), getWgt(2, W_2),

X = W_0+W_1* I_1 + W_2* I_2, V= sigmoid(X).

Веса сохраняются в базе данных.

facts

weight:(unsigned, real). clauses

weight(0, 1.5). weight(1, 2.0). weight(2, 1.8).

156

Изначальные веса незначимы. Настоящие значения весов должны быть найдены обучающим ал горитмом. Процедура getWgt имеет очень простое определение:

getWgt(I, W) : weight(I, W), !. getWgt(_I, 0.0).

Вы можете спросить, зачем вообще нужно определять getWgt; было бы легче напрямую исполь зовать weight; проблема в том, что weight определяет nondeterm предикат, и нам требуется проце

дурный предикат для извлечения weight. Между прочим, ещё нужна и процедура для извлечения примеров:

egratia(Eg, I1, I2, Output) : eg(Eg, I1, I2, Output), !. egratia(Eg, I1, I2, Output) :

Ex = Eg rem 4,

eg(Ex, I1, I2, Output), !. egratia(_Eg, 1, 1, 0).

Алгоритм обучения основан на вычислении и исправлении ошибки, сделанной предсказываю щей функцией. Ошибка заданного примера вычисляется следующим предикатом:

evalError(Obj, E) : nn:predicted_out(Obj, VC), nn:egratia(Obj, _I1, _I2, V),

E= (VC V)*(VC V).

Нам нужна не ошибка текущего рассматриваемого примера, а сумма ошибок для каждого при мера. Общую ошибку можно вычислить так, как показано ниже.

errSum(Exs, _Partial_err, Total_err) : acc := 0.0, foreach Eg= list::getMember_nd(Exs) do

evalError(Eg, Err), acc := acc + Err end foreach,

Total_err= acc.

Схема вычислений foreach выбирает каждый пример из списка Exs, вычисляет соответствующую ошибку и прибавляет результат вычисления к накопителю acc, который хранится в глобальной пере менной.

class facts acc:real := 0.0.

Веса будут обновлены с помощью метода градиентного нисхождения таким образом, чтобы уменьшить ошибку до минимума.

updateWeight(DX, LC, Exs) : errSum(Exs, 0.0, Err0), PN= [tuple(I, W) || nn:getWgt_nd(I, W)], nn:setWeight([ tuple(P, NV) ||

tuple(P, V) = list::getMember_nd(PN), V1= V+DX,

nn:assertWgt(P, V1), errSum(Exs, 0.0, Nerr), nn:popweight(P, V1),

NV= V+LC*(Err0 Nerr)/DX]).

157

Градиентное нисхождение – это алгоритм оптимизации, который находит локальный минимум функции, совершая шаги, пропорциональные значению, противоположному к значению градиента функции в заданной точке. На каждом шаге метода градиентного нисхождения веса обновляются согласно следующей формуле:

можете представить это себе как ландшафт, с горами и долинами; позиция в этом ландшафте задаёт ся координатами и ; высота гор и глубина долин изображает ошибки. Обучающий алгоритм перемещает сеть с исходного положения в долину, то есть, в позицию, в которой ошибка достигает локального минимума.

Идеальная ситуация происходит, когда сеть достигает глобального минимума. Амери канцы, которые служат в контрразведке, любят говорить, что они лучшие из лучших. Это и есть то, что требуется в качестве решения любой задачи оптимизации: лучшее из лучших. Не смотря на это, градиентные методы чаще всего попадают в ловушку в локальном минимуме. Это происходит, потому что когда сеть дости гает минимума, не имеет значения, локальный это минимум или глобальный; его градиент становится близким нулю; на самом деле ал горитм узнает, что он достиг мининума, только потому, что градиент достигает значения, близкого нулю. Проблема в том, что этот кри

терий не говорит о том, глобальный это минимум или локальный. В словаре сказано, что градиент задаёт наклон дороги или железнодорожных путей. На вершине горы или на дне долины градиент равен нулю. Если использовать нивелир1 на вершине горы или на дне долины, никакого наклона за мечено не будет.

Алгоритм обучения нейросети корректирует веса нейрона до тех пор, пока ошибка не станет меньше некоторого малого значения; затем он останавливается.

train(DX, LC, Exs) : errSum(Exs, 0, Err0), if (Err0 < 0.1) then

stdio::write("Total Err: ", Err0), stdio::nl

else

updateWeight(DX, LC, Exs), train(DX, LC, Exs)

end if.

1 Инструмент для измерения степени наклона местности.

158

24.1.Описание нейрона

Нейрон, подобный показанному на рис. 24.2, может быть описан следующим уравнением:

0

Это уравнение прямой. Если использовать больше вхождений, получим прямые линии в высших

измерениях, но они всё равно останутся прямыми линиями. Давайте начертим логическую функцию, известную как логический вентиль «ИЛИ» (or­gate). У неё два входа, и .

Рисунок 24.2. Перцептрон с тремя входами.

Из рисунка вы можете увидеть, что одной прямой линии недоста точно для того, чтобы разделить значения вентиля «исключающее ИЛИ». Однако две прямые линии могут разделить значения, равные нулю, от значений, равных единице, как вы можете видеть на рисунке. Точно так же, один перцептрон не сможет научиться вычислять выходные значе ния этого вентиля, но сеть с большим количеством перцептронов, как, например, изображённая на рис. 24.3, уже может выполнить эту задачу. В следующих параграфах вы научитесь использовать объекты для реали зации многослойной нейросети в Прологе.

159

Рисунок 24.3. Нейросеть, способная научиться вычислять выходные значения логического вентиля «исключающее ИЛИ» (xor gate)

24.2.Реализациямногослойнойсети

•Создайте новый консольный проект

Project Name: neurons

UI Strategy: console

•Выберите корень дерева проекта. Выберите пункт File/New из меню задач VDE. Это от кроет диалоговое окно Create Project Item. Выберите Class на левой панели; создайте класс network, который может создавать объекты [галочка Creates Objects поставлена – прим. пер.]. Нажмите кнопку Create. Добавьте спецификацию класса к network.cl, network.i и network.pro.

class network : network %File: network.cl predicates

sigmoid:(real) > real. end class network

Добавьте интерфейс класса к network.i:

% Файл network.i interface network open core domains

example= e(real, real, real). examples= example*.

predicates

setWeight:(tuple{unsigned, real}*) procedure. predicted_out:(unsigned, real) procedure (i, o). egratia:(unsigned, real, real, real) procedure (i, o, o, o).

160