Исскуственный интелект

ВВЕДЕНИЕ

Искусственным интеллектом, или ИИ (Artificial Intelligence - Аl), называют процесс создания машин, которые способны действовать таким образом, что будут восприниматься человеком как разумные. Это может быть повторение поведения человека или выполнение более простых задач, например, выживание в ди­намически меняющейся обстановке.

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

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

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

Проблема ИИ заключается в том, что технологии, которые исследуются в его рамках, становятся обычными сразу после их внедрения. Например, построение машины, которая смогла бы различать человеческую речь, когда-то считалось частью разработки ИИ. Теперь такие технологии, как нейронные сети и скрытые

модели Маркова, уже никого не удивляют и не рассматриваются как разработка ИИ. Родни Брукс описывает этот феномен как «эффект ИИ». После того как технология ИИ находит применение, она перестает быть техноло­гией ИИ, после своего создания эта техноло­гия перестает быть чудом и используется повсеместно.

Так как искусственный интеллект по-разному понимается разными людьми, было принято решение использовать другую классификацию. Сильный ИИ представляет собой программное обеспечение, благодаря которому компью­теры смогут думать так же, как люди. Помимо возможности думать, компьютер обретет и сознание разумного существа.

Слабый ИИ представляет собой широкий диапазон технологий ИИ. Эти функции могут добавляться в существующие системы и придавать им раз­личные «разумные» свойства. В данной контрольной работе описаны некоторые технологии Слабого ИИ, которые по мнению автора контрольной работы являются интересными и актуальными, так как объем контрольной работы не позволяет вместить все наиболее распространенные и известные алгоритмы и технологии ИИ.

2. Алгоритмы кластеризации

Алгоритм кластеризации - это метод, благодаря которо­му данные разделяются и объединяются в небольшие группы (кластеры) по прин­ципу аналогии. По тому же принципу осуществляется отделение несхожих данных, поэтому главной задачей при разбивке данных на кластеры является классифика­ция. Хотя классификация используется во многих случаях, ее основное предназна­чение - изучение данных в кластерах для выявления различий между ними. Более специфическое использование кластеров будет рассмотрено далее.

1. Биологическая мотивация

Алгоритмы кластеризации имеют биологическое происхождение, поскольку предоставляют возможность обучения посредством классификации. Человечес­кий мозг изучает новые понятия, сравнивая их с уже существующими знаниями. Мы классифицируем новое, пытаясь объединить его в одном кластере с чем-то, что нам уже известно (это является основой для понимания нового). Если новое понятие нельзя связать с тем, что мы уже знаем, нам приходится создавать новую структуру, чтобы понять явление, которое выходит за рамки существующей структуры. Впоследствии эта новая модель может стать основой для усвоения другой информации.

Объединяя новые понятия в кластеры с уже существующими знаниями, а так­же создавая новые кластеры для усвоения абсолютно новой информации мы ре­шаем проблему, которую Гроссберг назвал «дилеммой стабильности-гибкости». Вопрос состоит в том, как классифицировать новые данные и при этом не унич­тожать уже изученные. Алгоритм АRТ1 включает все необходимые элементы,

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

1.3 Алгоритм АRТ1

Алгоритм АRТ1 работает с объектами, которые называются векторами признаков. Вектор признаков является группой значений в двоичном коде, которые представляют определенный тип информации. Примером вектора признаков может служить выбор покупок. Каждый объект вектора при­знаков показывает, приобрел ли покупатель товар (если да, то значение равно 1, если нет - 0). Покупатель купил молоток и гаечный ключ.

Этот вектор признаков описывает покупательную способность путем иденти­фикации приобретенных покупателем предметов (о которых мы имеем информа­цию). Собираются векторы признаков покупателя, к которым затем применяется алгоритм АRТ1, чтобы разделить данные на кластеры. Идея состоит в том, что группа схожих данных о покупателе (содержащаяся в кластере) будет сообщать интересную информацию о схожих параметрах для группы покупателей.

1.4 АRТ1 в деталях

Мы начнем с группы векторов признаков (назовем эти примеры Е_1…K) и группы инициализированных векторов-прототипов (Р_1….N). Вектор-прото­тип является центром кластера. Количество векторов-прототипов, равное N. Являет­ся максимальным количеством кластеров, которое может поддерживаться. Параметр d показывает длину вектора. Мы инициализируем параметр внимательности (р или rho), равный небольшому значению между 0 и 1,0, а также бета-параметр (В), равный небольшому положительному целому числу. Эти параметры будут рассмотрены бо­лее подробно.

Vw – побитовый И вектор

||v|| - Значимость v (количество значимых элементов вектора)

N - Количество векторов-прототипов

P – Параметр внимательности (0 < р <= 1)

P – Вектор-прототип

E – Вектор признаков

d – Размер векторов(длина)

B – Бета-параметр

Изначально не существует ни одного вектора-прототипа, поэтому при выпол­нении алгоритма создается первый вектор-прототип из первого вектора признаков Затем проверяются на схожесть все последующие векторы признаков с вектором-прототипом. Цель проверки – выяснить, насколько схож вектор признаков и текущий вектор-прототип.

Р₀ =Е₀ (1.1)

Бета-параметр (Р), который используется в уравнении проверки на схо­жесть (уравнение 1.2), - это параметр «разрушения связи». Он выбирает прото­типы, в которых больше значений 1, при условии, что все значения 1 в векторе-прототипе также присутствуют в тестируемом векторе признаков.

||P_{i }E|| / (B+ ||P_i|| )> ||E|| / (B + d) (1.2)

Если тест на схожесть прошел успешно, выполняется следующий тест, чтобы проверить вектор признаков и вектор-прототип против параметра внимательнос­ти (уравнение 1.3). Задачей данного параметра является определение размера класса. Если значение параметра велико, образуются более крупные классы (кла­стеры с большим количеством данных). При уменьшении значения создаются кластеры с меньшим количеством данных. Если параметр внимательности задан Достаточно низким (< 0,1), для допуска векторы признаков должны соответство­вать вектору-прототипу.

||P_i  E|| / ||E|| < p (1.3)

Наконец, если пройден тест на внимательность, алгоритм добавляет текущий вектор признаков в текущий вектор-прототип (уравнение 1.4). Этот процесс пред­ставляет собой простое слияние вектора признаков и вектора-прототипа c помощью операции И. Если тест на внимательность (или тест на схожесть) не был пройден , проверяется следующий вектор-прототип. Если все векторы прототипы были проверены и при этом вектор признаков не был помещен в кластер, создается новый вектор-прототип из вектора признаков. Это приводит к форми­рованию нового кластера, так как рассматриваемый вектор признаков не соответ­ствует ни одному существующему кластеру.

Р_i = Р_i Е (1.4)

Теперь алгоритм проходит через все векторы признаков и сравнивает их со всеми векторами-прототипами.

Создать начальный Выражение 1.1

Вектор-прототип

Продолжить для

Каждого вектора

признаков

Выражение 3.2 Выражение 3.3

похож

ли вектор признаков да

на вектор прототип

нет

нет проходит тест

на внимательность?

Да

да

Еще прототипы ?

нет

Поместить вектор

Признаков в текущий Выражение 3.4

Вектор-прототип

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

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

1.5 Другие области применения

Алгоритм АRТ1 предоставляет возможность классификации данных в отдель­ные сегменты (кластеры). Классификация может быть полезна как средство иссле­дования классов (типов) кластеров. Кроме того, как видно по алгоритму персонализации, изучение членов отдельного кластера позволяет получить интересную информацию. Данный алгоритм можно использовать в следующих областях:

• статистике;

• распознавании образов;

• уменьшении диапазона поиска;

• биологии;

• поиске в сети internet;

• добыче данных .

1.6 Итоги

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

Пример алгоритма, представленный в этой главе, очень прост и работает с не­большим объемом данных. При персонализации в internet данные могут вклю­чать не только отображение содержания Web-страницы, но и время, которое было потрачено на ее просмотр. Тип и отображение данных зависят от алгоритма, кото­рый выполняет персонализацию. При правильной кодировке в векторах призна­ков алгоритм АRТ1 может работать с широким диапазоном данных, отображаю­щим многие аспекты поведения покупателя в сети internet.

Несмотря на то, что существует и опасная сторона применения алгоритмов персонализации, они могут быть очень эффективными инструментами при сборе самой разнообразной информации.

2. Алгоритм муравья

В этой главе рассматривается интересный алгоритм, основанный на применении нескольких агентов, с помощью которого можно решать самые разнообразные за­дачи. Алгоритмы муравья , или оптимизация по принципу мура­вьиной колонии (это название было придумано изобретателем алгоритма, Марко Дориго ), обладают специфическими свойствами, присущими му­равьям, и используют их для ориентации в физическом пространстве. Природа предлагает различные методики для оптимизации некоторых процессов. Алгоритмы муравья особенно интересны потому, что их можно использовать для решения не только статичных, но и динамических проблем, например, проблем маршрутизации в меняющихся сетях.

2.1 Естественная мотивация

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

Самое удивительное в данном процессе - это то, что муравьи умеют находить самый оптимальный путь между муравейником и внешними точками. Чем боль­ше муравьев используют один и тот же путь, тем выше концентрация ферментов на этом пути. Чем ближе внешняя точка к муравейнику, тем больше раз к ней пе­ремещались муравьи. Что касается более удаленной точки, то ее муравьи достига­ют реже, поэтому по дороге к ней они применяют более сильные ферменты. Чем выше концентрация ферментов на пути, тем предпочтительнее он для муравьев по сравнению с другими доступными. Так муравьиная «логика» позволяет выби­рать более короткий путь между конечными точками.

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

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

При прочих равных каждый муравей выберет свой путь. Первый муравей вы­бирает первый путь, а второй – второй путь. Так как второй путь в два раза короче первого, второй муравей достигнет цели за время Т₁. Первый муравей в этот мо­мент пройдет только половину пути.

Когда один муравей достигает пищи, он берет один из объектов и возвраща­ется к муравейнику по тому же пути. За время Т₂ второй муравей вернулся в му­равейник с пищей, а первый муравей достиг пищи.

Вспомните, что при перемещении каждого муравья на пути остается немного фермента. Для первого муравья за время Т₀-Т₂ путь был покрыт ферментом только один раз. В то же самое время второй муравей покрыл путь ферментом дважды. За время Т₄ первый муравей вернулся в муравейник, а второй муравей уже успел еще раз сходить к еде и вернуться. При этом концентрация фермента на втором пути будет в два раза выше, чем на первом. Поэтому первый муравей в следующий раз выберет второй путь, поскольку там концентрация фермента выше.

В этом и состоит базовая идея алгоритма муравья - оптимизация путем не­прямой связи между автономными агентами.

2.2 Алгоритм муравья

Подробно рассмотрим алгоритм муравья, чтобы понять, как он работает при Решении конкретной проблемы.

Предположим, что окружающая среда для муравьев представляет собой за­крытую двумерную сеть. Вспомните, что сеть - это группа узлов, соединенных по­средством граней. Каждая грань имеет вес, который мы обозначим как расстоя­ние между двумя узлами, соединенными ею. Граф двунаправленный, поэтому муравей может путешествовать по грани в любом направлении.

2

1

3

4

Граф с вершинами V = {1,2,3,4}

Грани Е = {{1,2},{1,4},{1,3},{2,3),{2.4),{3.4}}

2.3 Муравей

Муравей - это программный агент, который является членом большой коло­нии и используется для решения какой-либо проблемы. Муравей снабжается на­бором простых правил, которые позволяют ему выбирать путь в графе. Он под­держивает список табу, то есть список узлов, которые он уже посетил. Таким образом, муравей должен проходить через каждый узел только один раз. Путь между двумя узлами графа, по которому муравей посетил каждый узел толь­ко один раз, называется путем Гамильтона, по имени матема­тика сэра Уильяма Гамильтона.

Узлы в списке «текущего путешествия» располагаются в том порядке, в кото­ром муравей посещал их. Позже список используется для определения протяжен­ности пути между узлами.

Настоящий муравей во время перемещения по пути будет оставлять за собой фермент. В алгоритме муравья агент оставляет фермент на гранях сети после за­вершения путешествия.

2.4 Начальная популяция

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

2.5 Движение муравья

Движение муравья основывается на одном и очень простом вероятностном уравнении. Если муравей еще не закончил путь, то есть не посетил все узлы сети, для определения следующей грани пути используется уравнение :

(2.1)

Здесь - интенсивность фермента на грани между узлами r и u, -Функция, которая представляет измерение обратного расстояния для грани, a -вес фермента, а - коэффициент эвристики. Параметры a и  определяют отно­сительную значимость двух параметров, а также их влияние на уравнение. Вспом­ните, что муравей путешествует только по узлам, которые еще не были посещены (как указано списком табу). Поэтому вероятность рассчитывается только для граней, которые ведут к еще не посещенным узлам. Переменная k представляет гра­ни, которые еще не были посещены.

2.6 Путешествие муравья

Пройденный муравьем путь отображается, когда муравей посетит все узлы диа­граммы. Обратите внимание, что циклы запрещены, поскольку в алгоритм включен список табу. После завершения длина пути может быть подсчитана - она равна сумме всех граней, по которым путешествовал муравей. Уравнение показывает количество фермента, который был оставлен на каждой грани пути для муравья k. Переменная Q, является константой.

(2.2)

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

(2.3)

Обратите внимание, что данное уравнение применяется ко всему пути, при этом каждая грань помечается ферментом пропорционально длине пути. Поэтому следует дождаться, пока муравей закончит путешествие и только потом обновить уровни фермента, в противном случае истинная длина пути останется неизвест­ной. Константа р - значение между 0 и 1.

2.7 Испарение фермента

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

(2.4)

Поэтому для испарения фермента используется обратный коэффициент об­новления пути.

2.8 Повторный запуск

После того как путь муравья завершен, грани обновлены в соответствии с дли­ной пути и произошло испарение фермента на всех гранях, алгоритм запускается повторно. Список табу очищается, и длина пути обнуляется. Муравьям разреша­ется перемещаться по сети, основывая выбор грани на уравнении 2.1

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

2.9 Области применения

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

При решении задачи распределения ресурсов необходимо задать группу ресурсов n для ряда адресатов m и при этом минимизировать расходы на перераспределение (то есть функция должна най­ти наилучший способ распределения ресурсов). Обнаружено, что алгоритм му­равья дает решения такого же качества, как и другие, более стандартные спо­собы.

Намного сложнее проблема распределения работы. В этой задаче группа машин М и заданий J (состоящих из после­довательности действий, осуществляемых на машинах) должны быть распреде­лены таким образом, чтобы все задания выполнялись за минимальное время. Хотя решения, найденные с помощью алгоритма муравья, не являются оптимальными, применение алгоритма для данной проблемы показывает, что с его помощью мож­но решать аналогичные задачи.

Алгоритм муравья применяется для решения других задач, например, про­кладки маршрутов для автомобилей, расчета цветов для графиков и маршрутиза­ции в сетях. Более подробно способы использования алгоритма муравья описыва­ются в книге Марко Дориго «Алгоритмы муравья для абстрактной оптимизации»

2.10 Итоги

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

ЗАКЛЮЧЕНИЕ

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

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

Представим человеческий мозг. Нам еще предстоит понять, какие структуры мозга отвечают за то, что мы называем разумом или сознанием. Процесс работы миллионов нейронов каким-то образом создает разум на глобальном уровне. Про­стой процесс действия нейрона на микро уровне способствует формированию го­раздо более сложного процесса на макро уровне.

ИИ начинал свое развитие на уровне «сверху вниз», причем разработки в об­ласти его связей были минимальны. После того как Марвин Мински и Сеймур Паперт опубликовали книгу «Перцептроны», исследования в области нейронных сетей были почти полностью прекращены. Однако разработчики быстро поняли, что проблемы, описанные в данной книге, легко поддаются решению. Как счита­ют сегодня, методика «снизу вверх» связана с будущим ИИ. Главный вопрос в области ИИ формулируется так: можем ли мы создать ИИ, который будет ко­пировать человеческий разум, или мы опишем наши задачи и позволим ИИ на основе их решения обрести разум. Результаты изучения в этих сферах показыва­ют, что нам следует руководствоваться методом «снизу вверх».

Алан Тьюринг первым предложил идею «Машины-ребенка», принцип кото­рой состоит в том, что разумная машина не станет разумной в одно мгновение, а будет постепенно учиться, как это делают дети. Стремление к обучению будет запрограммировано, но знания машины будут улучшаться с течением времени.

Другие исследователи предположили, что верный подход к проблеме - это изучение и построение искусственных животных. Сможем ли мы, к примеру, со­здать искусственное насекомое, которое сможет повторять поведение настоящего насекомого и учиться так же, как оно? Эта задача, разумеется, намного проще, чем создание разума, подобного человеческому, но, очевидно, ее решение поможет нам при построении искусственного разума.

Свое логическое развитие идея создания искусственных насекомых, живот-ных и людей нашла при построении роботов. Эта задача требует инноваций в сфере развития и проектирования микродатчиков и приводов, а также программных структур, способствующих неограниченному обучению системы.

ИСПОЛЬЗУЕМАЯ ЛИТЕРАТУРА

1. Джонс М.Т. Программирование искусственного интеллекта в

приложениях / Пер. с англ. Осипов А.И. - Москва 2004

1. Журнал «Мир ПК».- №3.- 2002.