Сложно ли сделать из мухи слона?

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


    Сальвадор Дали. Искушение св. Антония. 1946. (Фрагмент).
    Бельгийский Королевский музей изящных искусств (Брюссель).


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

    (О применении генетических алгоритмов в ИИ см. книгу: Д. Рутковская, М. Пилиньский, Л. Рутковский, Нейронные сети, генетические алгоритмы и нечеткие системы, М.: Горячая линия – Телеком, 2006).

    Однако ларчик открывается довольно просто. Пусть длина каждого из заданных слов $L$. Из словаря существительных выписываем все слова длиной $L$. Число найденных слов обозначим $N$. Эти слова будут метками вершин неориентированного графа. Каждую пару вершин, метки которых отличаются на одну букву, соединяем ребром. Для этого перебираем все пары вершин, сравнивая их метки – число пар $N(N –1)$, число побуквенных сравнений $LN(N –1)$. Далее решаем типовую задачу поиска кратчайшего пути между указанными вершинами графа.

    Словарь существительных взял с CD-ROM к книге Сергея Мельникова, Delphi и Turbo Pascal на занимательных примерах, СПб.: БХВ – Петербург, 2006 (к слову сказать, в этой книге можно найти много остроумных и простых решений подобных, казалось бы, сложных задач со словами):

    В словаре перечислены все имена существительные «Орфографического словаря»
    (106000 слов, 28-е издание, 1990 г.). [...] Набор текста осуществлён в 1996-98 годах игроками команды «Пузляры» (http://puzzle.ezakaz.ru) — Константином Кнопом, Яковом Зайдельманом, Валерием Тимониным, Виктором Кабановым, Дмитрием Филимоненковым.

    Получил:

    Число загруженных слов (число вершин графа): 1501
    Число ребер: 2402
    Решение: (8 слов) муха-мула-кула-кила-килт-киот-клот-клон-слон
    Затрачено времени: 4.59 сек.

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

    А вот некоторые другие метаграммы:

    муха-мура-бура-бора-кора-корн-коан-клан-улан-улар-удар-удав
    мышка-мошка-кошка-корка-горка
    шило-кило-коло-соло-сало-рало-рыло-мыло
    баран-барон-басон-басок-бачок-бочок-борок-порок-порог-ворог-ворот

    Над последним решением программа думала уже 25.21сек. Интересно, что граф оказывается несвязным. Так, например, не удалось найти решения для пешка – ферзь.

    Можно расширить задачу. Пусть программа находит самые длинные цепочки с заданным числом букв, то есть генерирует головоломки. Для решения этой задачи нужно принять длину ребра нашего графа равной единице и вычислить матрицу расстояний между вершинами. Это можно сделать, например, с помощью алгоритма Флойда-Уоршелла. Так, для слов в 11 букв получим:

    Число загруженных слов: 3391
    Число ребер: 223
    Максимальное расстояние: 9
    Пары на максимальном расстоянии: закатывание-запихивание, запихивание-наматывание, обсаживание-отматывание, отматывание-отсиживание
    Затрачено времени: 3821.45 сек.


    Найдем решение для пары запихивание – наматывание:

    Решение: (9 слов) запихивание-запахивание-запаривание-заваривание-заваливание-закаливание-накаливание-накалывание-накатывание-наматывание
    Затрачено времени: 62.12 сек.

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

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

    Подробнее
    Реклама
    Комментарии 29
    • +1
      А что это за язык? Ru++?
      • 0
        Где Вы нашли такой язык?
        • +2
          кула, кила, киот, клот, корн, коан, улар, коло, рало, басон, борок


          Это вы нашли.

          У меня их даже MSWORD подчеркивает как нерусские)

          • 0
            Гугл в помощь:

            борок
            басон
            рало
            и т.д.
            А Микрософту стоило бы лучше выучить язык, прежде чем чекеры для него писать.
            • 0
              Без гугла значит никак…
              • 0
                Не понял. Гугл — достижение прогресса, как огонь или колесо. Не нравится гугл — пользуйтесь яндексом. Или м.б. в пещеры вернуться? Забыть все науки и искусства, а просто охотиться с кирпичом на мамонта? — так ведь мамонты перевелись.
                А Даля надо знать…
                • +1
                  Мы в эту игру в детстве во дворе играли. За такие слова меня бы высмеяли и прогнали… А так да, Даль — наше все. У меня просьба, может вам интересно будет — решить эту задачу на живом языке. Интересно было бы сравнить с каноническим решением из «Наука и жизнь». Разговорный русский словарь есть в гугле))
                  • 0
                    Если бы я сказал на нашей улице «ИИ», то не высмеяли бы, как не смели смеяться, когда трубку от телевизора я, начитавшись детской энциклопедии, называл Кинескопом. Но не поняли бы. Однако Вы правы — результат работы программы зависит от словаря. Если Вас интересуют конкретные решения, то могу выслать Вам программу — хотите в исходном коде на Дельфи-7, хотите исполняемым файлом. Если не только Вас это заинтересует — выложу в открытый доступ.
                    • +1
                      Спасибо, но я не смогу воспользоваться вашим кодом или исполняемым файлом. Я в другом мире)

                      За кинескоп и меня не побьют. Но вот за «рало» схлопочу в морду, век воли не видать.
                      • 0
                        Детские коллективы не показатель. У детей могут быть разные не совпадающие знания. Нпр., помню как в 4ом классе на перемене повторил фразу, услышанную в научпоп. передаче по радио: всё состоит из атомов. Надо мной стали смеяться, но стоявший рядом семиклассник, брат одного из моих оппонентов, прекратил этот спор, авторитетно заявив, что я прав.

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

                          Кстати, это повышает общий кругозор двора.
                          • 0
                            Сейчас инет есть наверное в каждом дворе — в качестве инструмента верификации запросто можно использовать гугл. Раньше, когда не было сетки, в спорных случаях можно было пробежаться до районной или до школьной библиотеки.

                            Но никто не препятствует сделать компании свой словарь. Такое дело безусловно повысит общий кругозор двора. При этом в словаре могут оказаться слова, которые возникли только в этом дворе и никем кроме не используются.
                            • 0
                              Ошибка: не та ветка
                • +1
                  борок

                  Уменьшительно-ласкательный суффикс. Неспортивно.


                  С клотом тоже вопрос. Используется ли как самостоятельное слово, а не часть составного термина?

                  • +1
                    Вообще-то статья не о том. Алгоритм не оценивает словарь (Орфографический, 106000 слов, 28-е издание, 1990 г.). Думаю, что подобные претензии нужно адресовать составителям словаря. Выше я уже предложил выслать код, тогда Вы сами сможете получить желаемый результат.
                    • +1

                      Я имею в виду, что в эту игру играют по определённым правилам. Допустимы только существительные и только в стандартной форме. Именно поэтому применение в игре подобных приколов — читерство и законный повод получить по морде от соперника.

                      • 0
                        Я не спорю, замечу только, что игроки команды «Пузляры», видимо, сочли данное слово допустимым, раз оставили его в своем словаре. Думаю, что, прежде чем играть, надо договориться, какой словарь использовать.
          • +1
            Определение ИИ неверное. Вчера компьютер играл в Го хуже человека, а сегодня лучше — и что, характер задачи изменился? На самом деле, задачи ИИ — творческие, т.е. те, для решения которых недостаточно формальной логики.
            • 0
              Если я не в курсе последних достижений по Го, то, пожалуйста, поправьте меня, но, насколько мне известно, комп играет в Го хуже многих чемпионов. Такая пробуксовка наблюдается многие годы — вычислительные мощности многократно возрастают, а играть, доказывать теоремы, писать стихи как Пушкин, комп так и не выучился. Когда научится — вот тогда и можно будет пересмотреть определение.

              Про формальную логику. В ИИ (и не только там) используют и эвристические алгоритмы, где не только формальная логика.
              • 0
                Проблема Го решена в прошлом году: ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D0%B3%D0%BE

                Естественно, ИИ использует эвристики, как подпорку — именно потому, что не способен к творчеству
                • 0
                  Не увидел там утверждения, что проблема решена полностью. Про эвристики. Скорее человек использует их «как подпорку», когда не может найти строго доказуемого решения. Творчество — понятие эвристическое и во многом от вкуса зависит. Есть«творцы», которые холст экскрементами мажут и называют это творчеством, а разные именитые критики до хрипоты перманентно и инфинитно спорят, творчество это или не творчество.
                • –1
                  В мае 2017 года на саммите «Future of Go Summit» AlphaGo выиграла три партии из трёх в мини-матче с одним из сильнейших игроков в мире, лидером мирового рейтинга Эло Кэ Цзе[31]

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

                  P.S. теоремы доказывать компьютер еще в 80-х годах научился. Теорема о 4-х красках или основная теорема теории групп (http://www.ega-math.narod.ru/Nquant/Groups.htm).
                  • –2
                    Думаю, что успех программы в трех партиях не дает основания для вывода, что проблема решена. Нпр., в крестики и нолики 3х3 у программы выиграть невозможно. М.б. и здесь какой-то финт: программа сводит партию к комбинациям, когда становится возможным полный перебор. Интересно, что на следующих строчках указанной вики-статьи говорится о проблеме игры программы с программой.

                    Конечно, у ИИ есть скромные успехи, однако роботы в фонтанах топятся

                    Что касается задачи 4х красок, то ИИ здесь ни при чем. Было сделано утверждение, что достаточно перебрать всего ок. 2000 тысяч вариантов. Этот перебор был сделан на компьютере. Однако вникнуть во все детали ни один человек не в состоянии. Поэтому почти 30 лет ряд несогласных специалистов искали контрпример. Среди не признавших был такой известный математик, как Александр Гротендик, правда, в поисках контрпримера он не участвовал. До сих пор делаются попытки найти человеческое, а не машинное доказательство. См. нпр., В.В. Родионов, Методы четырехцветной раскраски вершин плоских графов, М.: URSS, 2005. Там довольно подробно изложена и история проблемы 4х красок. Т.о., задача 4-х красок это особый случай, а с другими теоремами, за исключением достаточно тривиальных и практически никому не нужных, комп справится пока не может.
                    • –1
                      Какая проблема не решена? Люди тоже топятся в фонтанах. Называйте вещи своими именами, непонятно, что вы хотите сказать.
                      • 0
                        Какая проблема не решена?


                        Я точно указал:

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


                        Читаем здесь эти строчки:

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

                        и т.д.

                        Люди тоже топятся в фонтанах.


                        Нормальные люди и подавляющее большинство ненормальных, склонных к суициду, в фонтанах не топятся. М.б. Вы считаете особым прогрессом ИИ имитацию личности на крайней стадии ее распада?
              • 0
                Хорошая статья, но тут говорится о сравнении, а сравнения я не нашел. Только с человеком. Если сравнивать скорость нахождения(пусть не оптимальных) решений этой задачи ИИ по скорости и данного алгоритма. Что-то мне подсказывает что достаточно хорошо обученный ИИ будет находить решения в разы быстрее так как ему не придется пролистывать весь словарь по нескольку раз. Возможно ли добавить в статью такие результаты тестирования?
                • +1
                  Мой алгоритм: муха-мула-кула-кила-килт-киот-клот-клон-слон 4.59 сек.
                  Генетический алгоритм: «муха» — «мура» — «фура» — «фора» — «кора» — «корн» — «коан» — «клан» — «клон» — «слон» 137 сек.

                  Но это очень грубое сравнение на разном железе. И это не главное. Я не оптимизировал программу, считая время в несколько секунд (и даже больше) вполне приемлемым. Главное, что мой алгоритм гарантирует нахождение кратчайшего решения, если оно существует в рамках выбранного словаря. А ИИ вряд ли сможет такое гарантировать. И м.б., что не достаточно хорошо обученный ИИ не сможет сделать из мухи слона.
                  • +1
                    Приятно что моя статья вдохновила на новые эксперименты. Но сравнение явно нечестное — моя итоговая на тот момент версия находила путь от мухи к слону менее чем за секунду. Наверняка решение на графах должно заметно быстрее работать, впрочем. Было бы очень интересно увидеть такое.

                    А в общем и целом мне действительно было интересно решить именно генетическим методом эту задачку, тем более мы сами именно таким методом её и решаем своей головой. По мне это самое классное и волшебное действо, — научить железный алгоритм, искусственный исполнительный мозг думать и действовать так, как думаешь и действуешь ты сам, решая задачу.
                    • 0
                      Большое спасибо за Вашу статью и за интересный комментарий. Вы совершенно правы — количественное сравнение слишком грубое, что я и отметил выше. На мой взгляд, тут важно качественное различие: интеллектуальный (естественный или искусственный) эвристический подход обычно не обладает строгой доказательной силой. Такова природа вещей — за все приходится платить, но никто при этом не считает нужным отказываться от ИИ подходов. Уж тем более я, написав недавно игрового бота с ИИ. Просто призываю читателей отдавать себе отчет не только в возможностях того или иного подхода, но и в его принципиальных ограничениях. Если бы мир был устроен проще и все бы задачи решались строго аналитически, то все бы так и решали, и приближенные методы были бы не нужны.

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

                      Что касается:

                      тем более мы сами именно таким методом её и решаем своей головой


                      Это очень интересный и, на мой взгляд, неоднозначный вопрос. Недавно в другом обсуждении вспомнил про Ботвинника, которому не удалось научить ЭВМ играть в шахматы своим методом. Не все методы ИИ в точности воспроизводят методы естественного интеллекта. Также повторюсь:

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

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