Программирование И.И. Техники в Elixir: Метод проб и ошибок (перевод)23.09.2016 08:18

The Generate and Test Algorithm


Перевод статьи Coding A.I. Techniques in Elixir: The Generate and Test Algorithm


В последнее время, я работал над проектом в области И.И. (искусственный интеллект). По моим ожиданиям, работа над этим проектом займет ещё значительное время. Цель состояла в том, чтобы написать проект 100% на языке Elixir, но прежде чем я смог принять это решение, мне нужно было удостовериться, что я смогу реализовать некоторые из самых популярных решений в области И.И. на Elixir. На протяжении нескольких дней я изучал некоторые из наиболее эффективных техник, которые применяют исследователи в области И.И. для решения проблем программными средствами.


В этой статье я сделаю краткое объяснение метода, называемого алгоритмом генерации и испытаний — Generate and test algorithm (он же проб и ошибок), а затем я буду использовать вариацию этого метода для решения простой задачи с использованием языка программирования Elixir.


В И.И. есть много областей, из которых наиболее известными на сегодняшний день являются машинное обучение, обработка естественного языка (natural language processing) и робототехника. Тем не менее, для меня моя любимая дисциплина в И.И. известна как автоматизированные рассуждения — Automated reasoning. Программа, которую я продемонстрирую попадет в эту область И.И.



Проблема


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


Решение


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


1. Сформировать возможное решение
2. Проверка того, что получено ожидаемое решение
3. Если решение верно, возвращаем его и завершаем работу, в противном случае повторяем шаги с 1 по 3

Имея в виду эту концепцию, давайте создадим умную программу, которая может ответить на вопрос: «Является ли результат х + у четным?». В этом упражнении мы будем заботиться только о четных суммах, так что, когда система обнаруживает, что результат подсчета суммы является четным числом, мы будем реагировать соответствующим образом подтвердив, что найден ожидаемый результат. Обычно, когда мы получаем истинный ответ, используя эту технику, мы должны были бы остановить всю обработку. Тем не менее, в нашем случае мы хотим только остановиться, когда все вопросы, подготовленные системой будут услышаны. И, наконец, на вопросы сумма чисел в которых является не четным числом, мы будем отвечать Нет.


Код


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


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


defmodule SumAndTest do
  @moduledoc """
  This script is designed to show the functionality of the AI Algorithm
  that is known as Generate and Test. It will produce the results to a
  addition question and answer whether or not the answer is even.
  """

  • Elixit организует код с помощью модулей. СЛАВА БОГУ, НИКАКИХ КЛАССОВ!!!


  • @moduledoc является макросом для добавления комментария, который позволяет дать краткое описание того, для чего предназначен данный модуль.

Мы должны ответить на вопрос: «Является ли результат х + у четным числом?». Так что давайте двигаться далее и создадим функцию, которая содержит этот вопрос.


  defp addition_question(first_numbaer, second_number) do
    "Is the result of #{first_numbaer} + #{second_number} even?"
  end

  • Мы определяем функцию addition_question с двумя аргументами


  • Интерполяция в строке в Elixir имеет тот же синтаксис, что и в Ruby

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


  defp say_answer(true) do
    "YES! Even result found."
  end

  defp say_answer(false) do
    "No."
  end

  • Когда передан аргумент true, мы говорим «да», когда false, мы просто говорим «нет»


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

Мы создали возможность отвечать да и нет. Но что будет инициировать этот ответ? Нам необходимо определить, является ли результат на суммы 2 чисел четным числом. Создадим соответствующую функцию.


  defp even?(number) when is_number(number) do
    if rem(number, 2) == 0, do: true, else: false
  end

Так же возможно переписать тело функции просто как rem(number, 2) == 0, что само по себе возвращает true или false (прим. пер.).


  • Elixir имеет возможность определить валидацию аргументов функции с помощью ключевого слова when. Если аргументы не удовлетворяют условию валидации, то данное определение функции считается не подходящим и возможно будет применено одно из ее следующих определений (прим. пер.)


  • В Elixir имеется аналог тернарного оператора в одну строку


  • rem() является функцией Elixir, принадлежащий к модулю Kernel (ядро). Она определяет остаток от деления нацело.

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


  defp generate(amount_of_questions) when is_number(amount_of_questions) do
    generate(0, amount_of_questions)
  end

  defp generate(accumulator, amount_of_questions) when amount_of_questions >= 1 do
    question = addition_question(Enum.random(1..100_000), Enum.random(1..100_000))
    build_list(question)
    generate(accumulator + 1, amount_of_questions - 1)
  end

  defp generate(total, 0) do
    IO.puts "#{total} addition questions generated."
    :ok
  end

  • Вы растеряны? Не нужно. В Elixir обычно не используются циклы. Функции являются вашим основным инструментом. В случае необходимости повторно выполнять действия используют рекурсию.


  • С помощью сопоставления аргументов (pattern matching) мы можем в методе generate принять необходимое количество вопросов и передать его в версию того же метода, но с двумя аргументами. Первый аргумент имеет значение 0, потому что это, где начальное значение количества уже сгенерированных вопросов.


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


  • Функция Enum.random принимает заданный диапазон и возвращает случайное число в пределах верхней и нижней границы этого диапазона. Это идеально подходит для нашей системы, мы не знаем, какие числа будут использованы. Это позволит отлично проверить правильность работы нашей системы!


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


  • Наконец в конце функции, мы вызываем снова функцию generate, на этот раз увеличивая аккумулятор (счетчик) на единицу, и отнимая единицу от общего количества вопросов, которые еще нужно сгенерировать.


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

Мы довольно близки к завершению. Но есть еще кое что важное. В функции generate/2 мы вызывали функцию build_list. Почему нам это нужно?


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


Мы создали эти вопросы, но нам нужен способ, чтобы сохранить их, так что система не потеряет их после того, как мы выйдем из функции. Вот где вступают агенты Elixir. Агенты в Elixir позволяют программе удерживать состояние. Это делает отслеживание изменений структуры данных с течением времени независимым. Использование агентов довольно просто, и они могут быть главной причиной, почему Джо Армстронг (создатель Erlang) говорит, что с Erlang и Elixir «Вам не нужна база данных!». Давайте создадим агента, который в начале будет содержать пустой список. Этот список будет хранить наши вопросы.


  defp start_list do
    Agent.start(fn() -> [] end, [name: __MODULE__])
  end

  • Мы видим создание агента с двумя аргументами. Первый — функция, которая возвращает пустой список. Второй аргумент представляет собой список ключ-значений (keyword list). Функция получает имя от текущего модуля.


  • (ПРИМЕЧАНИЕ) Всегда давайте имена своим агентам!

Здорово! Теперь, когда наш агент имеет возможность инициализации и может содержать состояние, модно двигаться далее и реализовать функцию build_list которая встречалась ранее.


  defp build_list(question) do
    Agent.update(__MODULE__, fn(list) -> [question | list] end)
  end

  • Функция принимает один аргумент — вопрос, и на самом деле build_list является оберткой функции Agent.update, которая принимает два аргумента. Первый аргумент является именем агента. Второй аргумент это функция, которая берет текущий список и добавляет текущий вопрос к новой версии списка.

Чтобы увидеть все вопросы, на которые системе необходимо ответить, нужно получить текущее состояние агента. Мы можем просто использовать функцию Agent.get/2. Назовем эту функцию questions.


  defp questions do
    Agent.get(__MODULE__, &(&1))
  end

  • Agent.get принимает два аргумента. Название текущего модуля, и короткую версию функции fn(x) -> x end.

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


1. Получить все подстроки содержащте по одному числу из строки вопроса.
2. Преобразовать подстроки в целые числа.
3. Подсчитать сумму.
4. Проверить четная ли сумма.
5. Ответить "Да" или "Нет".

Здесь мы будем использовать pipeline оператор (или оператор конвейера). Этот оператор представляет собой мышечную ткань языка программирования Elixir, и это делает алгоритмы обработки И.И. гораздо нагляднее, чем они в были бы в LISP.


  defp answer_to(question) do
    Regex.run(~r/(\d+) \+ (\d+)/, question, [capture: :all_but_first])
    |> Enum.map(&String.to_integer(&1))
    |> Enum.reduce(0, fn(n, acc) -> n + acc end)
    |> even?
    |> say_answer
  end

  • Оператор конвейера (pipeline) принимает результат вызова функции расположенный перед ним и использует его в качестве первого аргумента следующей функции.

Для работы с большими числами мы можем немного оптимизировать функцию answer_to/1 изменив регулярное выражение, чтобы выбирать из строки вопроса только последнюю цифру каждого числа (так как четность суммы не измениться)


  defp answer_to(question) do
    Regex.run(~r/\d*(\d) \+ \d*(\d)/, question, [capture: :all_but_first])
    |> Enum.map(&String.to_integer(&1))
    |> Enum.reduce(0, fn(n, acc) -> n + acc end)
    |> even?
    |> say_answer
  end

Или используя модуль Bitwise можем учитывать только последнюю цифру числа в двоичной системе (1 или 0). Оператор ^^^ вычисляет побитовую операцию XOR своих аргументов.


  use Bitwise

  defp answer_to(question) do
    Regex.run(~r/(\d+) \+ (\d+)/, question, [capture: :all_but_first])
    |> Enum.map(&String.to_integer(&1))
    |> Enum.reduce(0, fn(n, acc) -> acc ^^^ Bitwise.band(n, 1) end)
    |> even?
    |> say_answer
  end

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


  defp display_answer_for(question) do
    IO.puts(question)
    IO.puts(answer_to(question))
  end

  • IO является главным модулем для работы стандартного ввода/вывода для устройств.

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


1. Вызвать `start_list`, чтобы запустить агент.
2. Затем сгенерировать определенное количество вопросов. Давайте начнем с 20-ти.
3. Для каждого вопроса мы должны показать ответ на этот вопрос.

Вот как эта функция может выглядеть.


  def start do
    start_list
    generate(20)
    Enum.each(questions, &display_answer_for(&1))
  end

  • После того как агент запущен мы можем сообщить системе, чтобы сгенерировать 20 вопросов. Для каждого из этих вопросов, мы отображает вопрос и ответ на него.

Мы готовы! Что происходит, когда мы вызываем SumAndTest.start? Система производит 20 случайных вопросов с соответствующими ответами. Смотрите вывод ниже! 


$ iex
Erlang/OTP 18 [erts-7.3] [source] [64-bit] [smp:8:8] [async-threads:10] [hipe] [kernel-poll:false] [dtrace]

Interactive Elixir (1.3.1) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> c("sum_and_test.ex")
[SumAndTest]
iex(2)> SumAndTest.start
20 addition questions generated.
Is the result of 31956 + 95609 even?
No.
Is the result of 56902 + 37929 even?
No.
Is the result of 63154 + 23758 even?
YES! Even result found.
Is the result of 22268 + 66438 even?
YES! Even result found.
Is the result of 76068 + 36127 even?
No.
Is the result of 14158 + 84195 even?
No.
Is the result of 55174 + 13171 even?
No.
Is the result of 53028 + 68694 even?
YES! Even result found.
Is the result of 82027 + 39083 even?
YES! Even result found.
Is the result of 32349 + 70547 even?
YES! Even result found.
Is the result of 41416 + 37714 even?
YES! Even result found.
Is the result of 91326 + 32635 even?
No.
Is the result of 42663 + 21205 even?
YES! Even result found.
Is the result of 90054 + 71218 even?
YES! Even result found.
Is the result of 38305 + 69972 even?
No.
Is the result of 59014 + 3954 even?
YES! Even result found.
Is the result of 55096 + 34449 even?
No.
Is the result of 89363 + 16018 even?
No.
Is the result of 60760 + 12438 even?
YES! Even result found.
Is the result of 10044 + 47646 even?
YES! Even result found.
:ok

Вывод


Это, вероятно, самый простой из всех алгоритмов искусственного интеллекта. Его простота это то почему я решил написать об этом алгоритме в моей первой статье на «Automating the Future». Я бы рассматривал возможность использования метода проб и ошибок, если бы я имел дело с проблемой, в которой фигурируют только небольшое количество возможных исходов.


Автор: Quentin Thomas


исходный код

Комментарии (5)

  • 22 сентября 2016 в 22:21

    0

    ↑

    ↓

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

  • 22 сентября 2016 в 22:50

    +1

    ↑

    ↓

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

    • 23 сентября 2016 в 01:22

      0

      ↑

      ↓

      Возможно, статья является частью какой-то более крупной работы и решаемая в ней конкретная задача имеет смысл. Если так, то может стоит добавить ремарку о смысле происходящего? Да, это перевод, но можно сделать вставку от автора, что будем программировать. А самое главное — для чего. В самом начале, не поняв для чего все это делается, я ждал, чем же все это закончится, пытаясь понять, что происходит из кода. Но понимание алгоритма может быть затруднительным, если читатель не знаком с фунциональным подходом.
      При этом, как пример программирования Elixir, статья хорошая. Потому что на конкретном примере понять легче. Раскрыты многие темы: матчинг функций по параметрам, guards, циклы через рекурсию, агенты, pipeline. Вообще, конечно, вопросы есть по необходимости их применения. Но автор оригинального текста новичек. Так же хочу заметить, что, как мне кажется, автор ошибся с организацией приложения. Он сделал модуль, в котором все вместе, и который он запускает и в нем же все проверяет. А надо было сделать приложение, в нем модуль, который понимает строку такого вида и отвечает на эту строку. Проверку нужно было сделать через юнит тестирование.

    • 23 сентября 2016 в 03:31

      0

      ↑

      ↓

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

  • 22 сентября 2016 в 23:31

    0

    ↑

    ↓

    Сказочный перевод!

© Habrahabr.ru