21 ноября 2019 года    
Четверг | 18:32    
Главная
 Новости
Базы данных
Безопасность PC
Всё о компьютерах
Графика и дизайн
Интернет-технологии
Мобильные устройства
Операционные системы
Программирование
Программы
Связь
Сети
 Документация
Статьи
Самоучители
 Общение
Форум







Разделы / Программирование / Другие

Алгоритмы искуственного интеллекта ( AI ).

A: (Sergey Anisimov anis@anis.kchepetsk.ru)

+--------------------------------------------+-------------------------------
| Алгоритмы искуственного интеллекта ( AI )  |
+============================================+

По статье Jang Hin Lang (jang@ecf.toronto.edu)

Я не верю, что возможно обсудить все принципы и методы создания AI (
механизмов самообучения ) в компьютерных программах. Поэтому Вашему
вниманию будут предложены лишь их часть, а вернее всего два алгоритма
создания AI в компьютерных программах.

+------------------+---------------------------------------------------------
| Алгоритм нейрона |
+==================+

Это наименее сложный из алгоритмов. Рассмотрим вначале схематичное
изображение нейрона:


Dendrite Дендрит           | ------------ |
(Ввод) ----------------- O |              |           Аксон - один
 . их может быть           | Тело нейрона | O ---------------
 . несколько               |  cell body   |        Axon (вывод)
(Ввод) ----------------- O |              |
                           |--------------|

Где O - synapse. Синапс служит для соединения контактов между собой и
исполнительными механизмами.

Синапс - это не физическое соединение, а временное химическое
соединение, которое может быть изменено. В нашем рассмотрении синапс
- это коэффициент назначенный к каждому вводу. Большое значение
коэффициента ввода означает, что данное соединение более важное чем
другое. Тело нейрона (ячейки) содержит в себе заранее
предопределенное значение - порог срабатывания. Выходной сигнал
сработает только тогда, когда на вход нейрона поступит значение
большое, чем порог срабатывания.

Определим механизм работы с нейроном, который позволит нам
моделировать AI ( самообучение ).

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

 - установите коэффициенты w и порог срабатывания t в
   нашем рассмотрении к неким произвольным значениям.

 - установите на каждый ввод x(0), x(1), x(2),...., x(n-1)
   ( прим. перев. Я здесь не понял - видимо надо дать на каждый ввод
   либо 1 либо 0 :( )

 - вычислите сработал ли вывод сравнив пороговое значение и сумму
   коээфициентов ввода


   n - 1
   -----
   \
    Сумма коэфф. = w (i) * x (i)
   /
   -----
   i = 0

 -  измените коэффициеты, для подтверждения правильных решений и
    устранения неверных.
    ( прим. перев. Я не понял как менять эти коэффициенты, на
    основании чего ? :( )

+--------------------------------------+-------------------------------------
| Алгоритм Кохенена, или алгоритм Сети |
+======================================+

Этот алгоритм, назван в честь профессора T. Kohonen с факультета
Информатики в Университете Helsinki, Финляндия. Вместо сравнения
входных коэффициентов к порогу срабатывания, ( как в случае с
алгоритмом нейрона ) Кохонен сравнил коэффициенты всех выходов, и
выбрал набор выходов имеющих коэффициенты, которые близко
соответствовали (согласовались) с коэффициентами входов.
Вот ссылка на его работу:

  Kaelbling, Leslie Pack
  Learning in Embedded Systems
  The MIT Press, Cambridge, Massachusetts
  (c) 1993
  ISBN 0-262-11174-8


Самоообучающаяся сеть состоит из матрицы выходов j, которые все
соединяются с каждым входом i.

     ----------------
      \  O    O    O \
        \              \
выхода j  \  O    O    O \
            \ 	           \
              \  O    O    O \
               ----------------


 Входа i O O

 ( прим. перев. Что обозначает данный рисунок я не понял :( )

Алгоритм позволяет определить выход-"победитель" - j*, который
точно подходит к ожидаемому выходу, как определенно входами i.
Изменение коэффициента j* и его окружения будет создавать желаемые
результаты.

 ( прим. перев. Вообще _ничего_ не понял :( )

Кохенен успешно реализовал эту методику для системы распознования
речи в середины восьмедисятых годов XX века. Вот его алгоритм:


1. Инициализация сети
 - определите матрицу w(ij) (0 <= i <= n-1) которая определяет
   коэффициенты от входа i во выход j. Установите
   минимальные значения коэффициентов n входов. Установите радиус
   окружения вокруг выхода j, N(j), к некоторому большому значению.

2. Установите входа
 - Установите входа x(0), x(1), x(2),...., x(n-1), где x(i) - ввод i.

3. Вычислите расстояние
 - Вычислите расстояние d(j) между входами i и каждым выходом j по
   формуле:


   n - 1
   -----
   \
    d(j) = (x(i) - w(ij))^2
   /
   -----
   i = 0

4. Выберите минимальное расстояние и обозначите выход j с
   минимумом d(j) - j*.

5. Обновите веса
 - обновите вес для узла j* и его окружения как определено
   размером границы N(j).


  w(ij) = w(ij) + M * (x(i) - w(ij))

   Коэффициент M используется чтобы управлять корректировкой
   коэффициентов выходов. Его значение должно устанавливаться в
   диапазоне [0.5, 1] и затем постепенно уменьшаться, по линейной
   функции от номера цикла обучения.

6. Если ожидаемое решение не было обнаружено,  повторите
   обучающийся цикл ( шаги 2-5 ).

7. Решение устанавливает S-сеть, которую можно использовать
   компьютеру против игрока.

   Например, сеть состоит из 16 выходов, 4 входов и размер окружения
   равен 4, алгоритм Кохенена может разработать стратегию действий
   всего за 216 ходов ( 9 * 4! ), что очень хорошо.

+-------------+-------------------------------------------------------------
| Примечание  |
+=============+

   А вот алгоритм выдранный из переписки.

   - cut -

Newsgroups: fido7.other.nice.sources
From: George Korablev <George.Korablev@p72.f207.n5020.z2.fidonet.org>
Date: Fri, 22 Nov 96 20:05:40 +0300
Subject: [News] Re: Самообучающиеся программы


    Сердечно приветствую,дорогой Alexey!

Wednesday November 20 1996.В 03:58, Alexey Efimov изрек из своих недр в адрес
George Korablev следующее:

 GK>> Да ты не рубишь разницу между обучающейся экспертной системой и
 GK>> обучающейся программой. Хотя игра м.б. построена по принципу
 GK>> экспертной системы и экспертная система по принципу игры. Могу
 GK>> поделиться мыслями - как построить экспертную системы (плагиат из
 GK>> одноименной книжки - валяется в библио-глобусе)

 AE>   Попpобуй... поделись.

Все-таки Sorry за плагиат, но раз уж просят...

Допустим есть система из двух объектов, имеющих по три свойства.
Например птица и самолет. Пусть "1" - это присутствие признака, а "0"
- наоборот.

            Крылья   Оперение  Шасси
Птица         1         1        0
Самолет       1         0        1

Заводим внутри программы массивы 2х3 и 1х3, изначально прописанные
нулями.  Массив 1х3 будет вектором наших вопросов.

Режим обучения/отгадывания:
Мы говорим системе: што есть  "крылья"+"шасси" (1,0,1). Система
при отгадывании выполняет следующую манипуляцию:

1. умножает вектор наших вопросов на все строки в массиве признаков
   поочереди.
2. Получаем два результата.
3. Выбираем максимальный. (это и есть ответ на наш вопрос)

Т.к. все были нули, программа говорит: "Птица?", вы отвечаете "Нет".
Далее происходит следующий алгоритм:
1. Если программа не угадала, то ваш вектор ответов вычитается из
строке массива соответствующему овтету, а к остальным прибавляется.
2. Если программа угадала, то ничего не происходит.

В нашем случае после первых наших вопросов имеем:
Птица   -1 0 -1
Самолет  1 0  1

Задаем след. вопрос: што есть "крылья"+"перья" (1,1,0)?
Программа:
Птица : -1+0+0 = -1
Самолет : 1+0+0 = 1
ответ: Самолет
Вы: неверно

Программа:
Птица   0  1 -1
Самолет 0 -1  1

После второго нашего заданного вопроса программа обучилась полностью.
На вопрос "што есть "перья" будет получен ответ "птица"
На вопрос "што есть "шасси" - "самолет"
На вопрос "што есть "крылья","крылья"+"перья"+"шасси",
"перья"+"шасси" программа получит одинаковые результаты при сравнении
макс. элементов.
На этот случай в алгоритм поиска максимальных элементов включается
след. кусок, который проверяет есть ли дубликаты у найденного
максимального значения. Если такие имеются, то программа должна
сказать "Похоже на..." и перечислить варианты ответов с одинаковыми
максимальными значениями.

P.S. При обучении программы следует завести счетчик максимального
количества вопросов и по его достижению прекращать какое либо
обучение (два одинаковых заданных вопроса на результаты работы
программы не влияют), в привед-й выше книге есть алгоритм по этому
поводу, но я его не помню.

P.P.S. Кстати можно использовать количественые значения признаков
типа "ноги" при вариантах ответов 1 :), 2, 3 :), 4 и т.д. тоже будет
работать и намного точнее.

P.P.P.S ;)
Приведенный пример экспуртной системы - одноуровневый. о можно на ее
основании построить N-мерную модель. Например каждый элемент плоского
массива - это результат по поискам максимальных элементов из других
массивов.

   - cut -

   ( прим. перев. IMHO это понятней. ;)) )

+------------------------+---------------------------------------------------
| Примечания переводчика |
+========================+

   Данный документ составлен Анисимовым С.Ю. 02/1997. г. К-Чепецк,
   Кировской обл. Россия. root@anis.velcom.vyatka.su

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

С наилучшими пожеланиями, для всех любителей программировать игры !
		  	Vale !
 Алгоритмы искуственного интеллекта ( AI ).
Лента новостей


2006 (c) Copyright Hardline.ru