AI-полный

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

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

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

История

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

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

В мае 2022 года DeepMind опубликовала работу, в которой они обучили одну модель выполнять несколько дел одновременно. Модель под названием Gato может «играть в Atari, использовать изображения подписей, общаться в чате, складывать блоки с помощью настоящей руки робота и многое другое, принимая, исходя из контекста, решение о том, выводить ли текст, крутящие моменты суставов, нажатия кнопок или другие токены». Точно так же некоторые задачи, которые когда-то считались решаемыми с помощью ИИ, например машинный перевод, являются одними из возможностей больших языковых моделей .

Проблемы с искусственным интеллектом

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

• ИИ Экспертная оценка (комплексное понимание естественного языка , автоматизированное рассуждение , автоматизированное доказательство теорем , формализованная логическая экспертная система )
• Проблемы Бонгарда
• Компьютерное зрение (и подзадачи, такие как распознавание объектов )
• Понимание естественного языка (и подзадачи, такие как интеллектуальный анализ текста , машинный перевод , и устранение смысловой неоднозначности слов )
• Автономное вождение
• Работа с непредвиденными обстоятельствами при решении любой реальной проблемы, будь то навигация , планирование или даже рассуждения , выполняемые экспертными системами .

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

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

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

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

Сложность выполнения алгоритма с помощью машины Тьюринга с участием человека определяется парой $\langle \Phi _{H},\Phi _{M}\rangle$, где первый элемент представляет сложность части человека, а второй элемент — сложность части машины.

Результаты

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

• Оптическое распознавание символов печатного текста: $\langle O(1),poly(n)\rangle$
• Тест Тьюринга :
  • для $n$-предложение разговора, в котором оракул запоминает историю разговора (постоянный оракул): $\langle O(n),O(n)\rangle$
  • для $n$-предложение разговора, в котором история разговора должна быть передана повторно: $\langle O(n),O(n^{2})\rangle$
  • для $n$- разговор с предложением, в котором история разговора должна быть передана повторно, и человеку требуется линейное время, чтобы прочитать запрос: $\langle O(n^{2}),O(n^{2})\rangle$
• Игра ESP : $\langle O(n),O(n)\rangle$
• Маркировка изображений (на основе протокола Артура-Мерлина ): $\langle O(n),O(n)\rangle$
• Классификация изображений : только человек: $\langle O(n),O(n)\rangle$, и с меньшей зависимостью от человека: $\langle O(\log n),O(n\log n)\rangle$.

Исследования

Роман Ямопольский предполагает, что проблема $C$ является AI-полным, если он имеет два свойства:

• Он находится в наборе задач ИИ (решаемых Human Oracle).
• Любую проблему ИИ можно превратить в $C$ по некоторому алгоритму с полиномиальным временем.

С другой стороны, проблема $H$ является AI-Hard тогда и только тогда, когда существует проблема AI-Complete $C$ это полиномиальное время, сводимое по Тьюрингу к $H$. Как следствие, это также приводит к существованию задач AI-Easy , которые можно решить за полиномиальное время с помощью детерминированной машины Тьюринга с оракулом для некоторой проблемы.

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

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

Для Кви-Бинторо и Велеса, Решение проблем, связанных с искусственным интеллектом, будет иметь серьезные последствия для общества.

См. также

• ASR-полный
• Список нерешенных проблем информатики
• Синтетический интеллект
• Практикопоэз