Машинное обучение алгоритмам

    Машинное обучение как оно есть сейчас


    В популярных методах машинного обучения программа не выучивает алгоритм. Классификатор, нейронная сеть или, для большей очевидности, методы регрессии выучивают в лучшем случае функцию (в математическом, а не программистском смысле): имея входные данные, выдать выходные данные. Это может быть в лучшем случае единственным шагом алгоритма и не понятно, как масштабировать такое решение на целый алгоритм вместо одного шага. Без возможности выучивать алгоритмы, эти методы далеки от AGI (общего искусственного интеллекта — Artificial General Intelligence). На пути к AGI неплохо бы найти способ, чтобы программы выучивали алгоритмы с ветвлением, циклами и подпрограммами. Далее следует научить программы понимать другие программы. Далее понимать и улучшать саму себя. Не настаиваю что именно этим путём люди пройдут к AGI, но это моё скромное виденье.

    Программа как прикладной искусственный интеллект


    В отличие от других методов машинного обучения, в своё свободное время я сделал интерактивную систему, которая задаёт пользователю вопросы и после каждого ответа выдаёт список возможных целей — что может прийтись пользователю по вкусу, будь то новая игра, фильм, книга, товар или услуга. Смысл нового поисковика в том, что пользователь может не иметь представления о том, что именно он(а) ищет, поэтому не может сформировать ключевых слов чтобы вбить в существующие поисковики. А вот ответить на вопросы программы может, и всегда есть вариант «не знаю/затрудняюсь ответить».

    Реализация и конкуренты


    Пример как это работает можно увидеть у других, кто сделал что-то похожее: Akinator. Не будем о том что идея пришла мне раньше чем появился Akinator. Добрался реализовать только недавно, и в отличие от Акинатора выложил в open source — открытый исходный код ProbQA здесь. Не известно, на каком именно алгоритме работает Акинатор. Мой же алгоритм на C++ любой может увидеть сам, а чтоб легче читался код расскажу немного далее. Используется матрица N на K на M, где N — количество вопросов, K — количество ответов, M — количество целей. Программа ведёт статистику, сколько раз пользователи выбрали j-ю цель как искомую для набора вопросов и ответов. Далее по допущению независимости определяется обратное: вероятность j-й цели при наборе вопросов и ответов, включающем все предыдущие и каждый незаданный вопрос как кандидат быть следующим. Каждому вопросу присваивается вес, исходя из функции приоритета, которая зависит от энтропии новых (т.е. после нового вопроса) вероятностей целей и от Эвклидового расстояния между старыми и новыми вероятностями целей. Далее «наилучший» вопрос выбирается взвешенно-случайным образом.

    Реализован только back-end на C++. Жду когда кто-нибудь напишет front-end web-приложения. Сам по такому не специализируюсь.

    Программа изучает алгоритмы


    Так получается, что программа ProbQA (Probabilistic Question Asking) в отличие от других методов машинного обучения, по сути способна выучивать алгоритмы. Она показала хорошие результаты в изучении алгоритма двоичного поиска (дихотомии), смотрите картинку ниже. Мы можем говорить, что она выучивает алгоритмы, потому что с её знаниями программа делает следующее: взаимодействие с пользователем в нескольких шагах, ведущее к конечным целям. Программа запрашивает ввод, далее в зависимости от ввода ветвится и спрашивает пользователя о чём-то ещё.

    image

    На картинке выше приведена кривая изучения программой алгоритма дихотомии. По оси X количество заданных программой и отвеченных пользователем вопросов, по оси Y процент правильно угаданных целей двоичного поиска для 256 следующих одна за одной попыток. Тестирование всегда проводится на новых данных: мы загадываем случайное число от 0 до 999, и даём программе угадать его путём задавания вопросов и получения ответов от пользователя (в данном случае, пользователь — тестирующая программа, которая знает загаданное число). Далее, если ProbQA угадала правильно, или же провалилась (задала более 100 вопросов), мы её учим, раскрывая выбранное тестирующей программой число.

    Как мы видим из картинки, обучение ProbQA до 100% точности занимает количество вопросов и ответов, примерно равное размеру матрицы. В нашем случае матрица состоит из 1000 вопросов умноженное на 5 вариантов ответа умноженное на 1000 целей. Каждый i-й вопрос из этих 1000 имеет вид «Как загаданное число сравнимо с числом i?». Варианты ответа: 0 — «Загаданное число намного меньше чем i», 1 — «Загаданное число чуть меньше i», 2 — «Загаданное число равно i», 3- «Загаданное число чуть больше i», 4 — «Загаданное число намного больше i».

    Теперь интересует такой вопрос: какая длина цепочки вопросов, приводящей к правильной цели? На картинке ниже мы можем видеть что сначала (во время тренировки) программа задаёт много вопросов, но когда программа уже выучила алгоритм, средняя длина цепочки падает где-то до 7 вопросов.

    image

    Результат можно считать хорошим, учитывая что написанный человеком алгоритм двоичного поиска задаёт ln(1000)/ln(4) = 5 вопросов. Оставшиеся 2 вопроса нужны программе чтобы продолжать учиться, а не выкладываться по полной, не узнавая ничего нового. Это контролируется упомянутой выше функцией приоритетов и тем, что выбирается не «самый-самый» дифференцирующий вопрос, а взвешенно-случайный.

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

    Долгосрочная перспектива


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

    1. Artificial Super-Neuron
    2. New programming

    Если будут желающие, могу написать отдельную статью на основе тех двух.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 6

      +2
      Далее следует научить программы понимать другие программы.

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

        +1

        Рекуррентные нейросети полны по Тьюрингу, вот, например, подробности: https://stats.stackexchange.com/questions/220907/meaning-and-proof-of-rnn-can-approximate-any-algorithm.

          +3
          Вы неявно (на самом деле вполне явно) закодировали алгоритм двоичного поиска, который «учится» быть двоичным поиском.
            –2
            Казалось бы — для побочного хобби-проекта — вполне неплохо. Я когда-то квадратичные/кубические функции нейросетями аппроксимировал. Вполне расширяющий сознание опыт, особенно если на промежуточные результаты (по эпохам) глазами смотреть.
            0
            Сделал только что применение для этого движка: probqa.com. Сайт служит как система рекомендации игр для пользователей, которые слабо представляют, во что они следующее хотели бы поиграть. Не зная ключевых слов для поиска и описаний тысяч существующих игр, пользователь всё ещё может отвечать на вопросы путём кликанья на один из 5 вариантов ответа, и на каждом шаге получать список наиболее вероятных для него игр, исходя из ранее полученных программой ответов.
              0
              Насколько я понял, алгоритм кодируется чем-то типа матрицы переходов. Скрытая марковская модель, или что-то довольно похожее.
              Не могли бы вы чуть подробнее рассказать о том, как ваша модель реализует алгоритм в смысле машины Тьюринга?
              Ну, то есть, допустим, я задал в качестве обучающей выборку несколько пар массивов вида:
              [5, 2, 1, 7] -> [1, 2, 5, 7], а в результате должен сформироваться алгоритм сортировки. Промежуточные итерации в качестве входных данных не подаются (или подаются, но изредка и описывают хорошо, если 1% всех шагов)
              Ну или на входе коэффициенты квадратного уравнения, а на выходе его корни, а посередине формируется алгоритм решения.
              Можно привести такие примеры? Я некоторое время работал над подобными задачами и упёрся в комбинаторный взрыв, но, может, вы придумали что-то лучше

              Only users with full accounts can post comments. Log in, please.