AI-Complete - AI-complete

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

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

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

История

Этот термин был придуман Фаня Монталво по аналогии с NP-полной и NP-трудной в теории сложности , которая формально описывает наиболее известный класс сложных проблем. Ранее этот термин использовался в докторской диссертации Эрика Мюллера 1987 года и в жаргонном файле Эрика Раймонда 1991 года .

ИИ-полные проблемы

Предполагается, что проблемы, связанные с ИИ, включают:

Машинный перевод

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

Хрупкость программного обеспечения

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

Формализация

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

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

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

Полученные результаты

Сложность решения следующих задач с помощью машины Тьюринга с участием человека составляет:

  • Оптическое распознавание символов печатного текста:
  • Тест Тьюринга :
    • для разговора с предложением, где оракул запоминает историю разговора (постоянный оракул):
    • для беседы с предложением, в которой история беседы должна быть повторно передана:
    • для разговора с -предложением, где история разговоров должна быть повторно передана, и человеку требуется линейное время, чтобы прочитать запрос:
  • Игра ESP :
  • Маркировка изображений (на основе протокола Артура – ​​Мерлина ):
  • Классификация изображения : человек только: и меньше полагаться на человека: .

Смотрите также

использованная литература

  1. ^ Шапиро, Стюарт С. (1992). Искусственный интеллект в Стюарте С. Шапиро (ред.), Энциклопедия искусственного интеллекта (второе издание, стр. 54–57). Нью-Йорк: Джон Вили. (Раздел 4 посвящен «Задачи, выполняемые ИИ».)
  2. ^ Роман В. Ямпольский. Тест Тьюринга как определяющий признак AI-полноты. В области искусственного интеллекта, эволюционных вычислений и метаэвристики (AIECM) - по стопам Алана Тьюринга. Синь-Шэ Ян (Ред.). С. 3-17. (Глава 1). Спрингер, Лондон. 2013. http://cecs.louisville.edu/ry/TuringTestasaDefiningFeature04270003.pdf
  3. ^ Луис фон Ан, Мануэль Блюм, Николас Хоппер и Джон Лэнгфорд. CAPTCHA: Использование сложных проблем искусственного интеллекта для обеспечения безопасности. Архивировано 4 марта 2016 г. на Wayback Machine . В Proceedings of Eurocrypt, Vol. 2656 (2003), стр. 294-311.
  4. ^ Bergmair, Ричард (7 января 2006). "Стеганография естественного языка и" ИИ-полный "примитив безопасности". CiteSeerX  10.1.1.105.129 . Цитировать журнал требует |journal=( помощь ) (не опубликовано?)
  5. ^ Маллери, Джон С. (1988), «Размышление о внешней политике: найти соответствующую роль для Искусственно Intelligent Computers», Годового собрания Международной ассоциации исследований 1988 года. , Сент-Луис, Миссури.
  6. ^ Мюллер, Эрик Т. (1987, март). Мечтание и вычисления (технический отчет CSD-870017), докторская диссертация, Калифорнийский университет, Лос-Анджелес. («Мечтание - это еще однапроблема ИИ : если бы мы могли решить любую проблему искусственного интеллекта, мы могли бы решить все остальные», стр. 302)
  7. Перейти ↑ Raymond, Eric S. (1991, 22 марта). Файл жаргона версии 2.8.1 (определение «AI-complete» впервые добавлено в файл жаргона.)
  8. ^ Ide, N .; Веронис, Дж. (1998). «Введение в специальный выпуск по устранению неоднозначности слов: современное состояние» (PDF) . Компьютерная лингвистика . 24 (1): 2–40.
  9. ^ Ленат, Дуглас ; Гуха, Р.В. (1989), Построение больших систем , основанных на знаниях , Аддисон-Уэсли, стр. 1–5.
  10. ^ a b Дафна Шахаф и Эяль Амир (2007) К теории полноты ИИ . Здравый смысл 2007, 8-й Международный симпозиум по логической формализации здравого смысла .