Программирование для гуманитариев

Грамматика

Разбить на страницы
Показывать лекцию целиком

"ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ, раздел информатики, включающий разработку методов моделирования и воспроизведения с помощью ЭВМ отдельных функций творческой деятельности человека, решение проблемы представления знаний в ЭВМ и построение баз знаний, создание экспертных систем, разработку т. н. интеллектуальных роботов"

Цель лекции:

  • Дать читателю представление о дисциплине: "искусственный интеллект";
  • Ознакомить его с понятиями: "логический вывод", "продукция", "правила подстановки";
  • Ознакомить читателя с основными положениями формальной грамматики, понятиями: "однозначная грамматика" и "синтаксическое дерево";
  • Научить его пользоваться регулярными выражениями;
  • Дать базовые знания для последующего изучения языков логического программирования.
    •

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

    9.1. Введение

    К символьным операциям относят:

  • Операцию ввода-вывода строк;
  • Конкатенацию (объединение) строк;
  • Поиск по шаблону;
  • Замену в тексте строки по заданному образцу;
  • Грамматический, синтаксический и др. разбор текста;
  • Прямой вывод;
  • Обратный вывод;
  • Построение "деревьев вывода";
  • Семантический анализ текста;
  • Построение фреймов и семантических сетей;
  • Синтез "связной речи";
  • И многое другое.
    •

    Эти задачи гораздо сложнее, чем численные расчёты на ЭВМ. К тому же научно они менее разработаны, чем численные методы. Но именно за символьными вычислениями - будущее отрасли высоких технологий.

    Символьные операции могут применяться, например:

  • При подготовке и рассылке электронной корреспонденции;
  • При поиске во всемирной сети;
  • При наборе и вёрстке текста;
  • При проверке орфографии и стиля документа;
  • При переводе текста с языка на язык (имеются в виду как "человеческие", так и "машинные" языки);
  • При осуществлении "теста Тьюринга";
  • В датамайнинге;
  • При автоматической коррекции текста и перевода его из формата в формат;
  • При разработке языков программирования и написании их трансляторов и компиляторов для них;
  • и т.д.
    •

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

    9.2. Построение деревьев вывода

    Для начала рассмотрим игру "Животные", приведённую в [64]. Вот диалог работы с этой программой:

    [Пример 01]

  • "Это кот?" - "Нет".
  • "Сдаюсь, кто это?" - "кит".
  • "Чем отличается кот от кит?" - "плавает в море".
  • "Сыграем ещё?" - "Да".
  • "Он плавает в море?" - "Нет".
  • "Это кот?" - "Нет".
  • "Сдаюсь, кто это?" - "студент".
  • "Чем отличается кот от студент?" - "ходит на лекцию".
  • "Сыграем ещё?" - "Да".
  • "Он плавает в море?" - "Нет".
  • "Он ходит на лекцию?" - "Да".
  • "Это студент?" - "Нет".
  • "Сдаюсь, кто это?" - "профессор".
  • "Чем отличается студент от профессор?" - "читает лекции".
  • …
    •

    Этот диалог формирует следующее дерево (см. рисунок 9.1):

    (рис 9.1) Дерево вывода примера 01

    В этом дереве имеется "корень" - название игры ("животные"). От него исходят так называемые "бинарные ветви" - ветви, которым соответствуют ответы: "Да" или "Нет". Это дерево является моделью, полностью описывающее состояние игры: "Животные". С помощью этого дерева можно ответить на вопросы:

  • Сколько необходимо задать вопросов, чтобы получить ответ: "студент"?
  • Кто является "соседней ветвью" ответа: "студент"?
  • Присутствует ли ответ: "студент" - в дереве вывода?
  • Много ли не заполненных ветвей дерева (обозначенных: "Кто это")?
    •

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

    Вот другой пример дерева вывода, вид которого представлен на рисунке 9.2. Рассмотрим грамматический разбор английского предложения: "The big elephant will eat pineapples tomorrow". ("Большой слон будет есть ананасы завтра").

    (рис 9.2) Синтаксическое дерево при разборе английского предложения

    Как известно читателям, изучавшим английский язык, структура английского предложения является жёсткой и имеет следующий вид:

    <Подлежащее><Сказуемое>[<Прямое дополнение>][<Обстоятельство>]

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

    В принципе, в этом предложении можно менять существительные и глаголы - это не должно влиять на правильность разбора предложения. Например, правильными также будут следующие предложения:

  • An old man ate an apple yesterday.
  • A small elephant is eating a ball now!
    •

    Однако второе предложение бессмысленно (кому-то оно может показаться даже непристойным). Это объясняется тем, что мы не рассматривали "осмысленность" предложения при выводе. Автор должен отметить, что задачи искусственного интеллекта понимания смысла текста и "осмысленного" генерирования предложений не решены уже более 50 лет (время появления первых ЭВМ с современной архитектурой). В основном из-за того, что до сих пор нет ответа на вопрос: "Что такое смысл"? Но это уже отступление от темы.

    Итак, мы рассмотрели два дерева вывода, выяснили, насколько это "дерево" полезно при разборе и построении предложений, открыли новые возможности символьных вычислений. Однако построение всех деревьев вывода и анализ их человеком обычно очень трудная, если не сказать, "неподъёмная" задача. Нельзя ли оптимизировать выполнение этих задач? Можно! Об этом - в следующем подразделе.

    9.3. Прямой и обратный вывод

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

    [Пример 02]

    /* Массиву строковых переменных names присвоены значения (язык Си плюс-плюс) */

names[0] = "Галя"; names[1] = "Нина"; names[2] = "Петя";

/* То же определение на языке Turbo Prolog */

names("Галя"); names("Нина"); names("Петя");

/* Определение массивов строковых переменных article (все возможные английские артикли) (C++) */

article[0] = ""; article[1] = "the"; article[2] = "a"; article[3] = "an";

    Правила же определяются следующим образом:

    [Пример 03]

    /* Пример на C++ */

if( names[i] == "Галя" ) woman.name = names[i];

/* Пример на Turbo Prolog */

woman( N ) if N == "Галя" оr N == "Нина", name(N);

    Выводом же будет автоматическое доказательство некоторого предположения, определённого как истинность одного из правил. Это правило называют "целью" вывода (по-английски: "goal"). При выборе цели возможно нахождение одного, нескольких или ни одного решения - списка значений переменных, участвующих в выводе.

    Примечание. Множество решений - это, практически, множество предложений заданной грамматики, полученных в результате доказательства цели вывода. Определение грамматики см. раздел 2 лекции 10.

    Когда написаны все факты и правила, необходимо написать алгоритм вывода. Он может быть одним из следующих:

  • Вывод на основе системы продукций (или "нейронной сети");
  • Вывод на основе правил (стандартный алгоритм вывода по прямой цепочке рассуждений);
  • Вывод на основе правил (стандартный алгоритм вывода по обратной цепочке рассуждений).
    •

    Рассмотрим их поподробнее.

    9.3.1. Система продукций (и "нейронные сети")

    Вывод на основе системы продукций следующий:

  • Определяются и вводятся "факты", на основе которых делается вывод;
  • Описываются промежуточные переменные вывода и цель вывода;
  • Составляется набор правил (продукций), последовательно задающие значения промежуточным переменным;

    Внимание! Порядок записи продукций имеет значение.

  • В процессе написания продукций в текст вставляются операторы вывода значений переменных, когда это необходимо;
  • В процессе работы системы продукций с реализацией "нечёткой логики" (по-другому: "нейронной сети") каждой продукции соответствует "коэффициент уверенности", который отражает степень доверия к этой продукции. Он вычисляется на основе коэффициентов уверенности доказанных фактов, правил, и коэффициента уверенности самой продукции.
    •

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

    Преимущества системы продукций и нейронных сетей:

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

    Недостатки этих систем:

  • Они не подходят для кодирования "стандартным алгоритмом вывода". Программист должен реализовывать "с нуля" алгоритм нейронной сети или системы продукций.
  • Невозможность предсказать поведение работающей программы;
  • Сложность отладки. Для отладки необходимо при прогоне тестов менять только один параметр. Это делает отладку длительной по времени.
  • Система продукций - это "чёрный ящик", не дающий пользователю объяснений о ходе своих рассуждений.
    •  Примечание. Информацию о коэффициентах уверенности, их расчёту и применении смотри, например, в [57].

    9.3.2. Вывод на правилах (прямая цепочка рассуждений)

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

    Наглядно результат прямого вывода по дереву вывода, приведённого на рисунке 9.2, показан на рисунке 9.3.

    (рис 9.3) Восходящий разбор английского предложения

    Достоинства алгоритма восходящего разбора:

  • Наличие стандартного алгоритма вывода;
  • Возможность предсказать результат на любом этапе разработки программы;
  • Простота отладки правил (но не алгоритма вывода!);
  • Средняя сложность реализации в "процедурных" языках и языках логического программирования (Пролог).
    •

    Недостатки алгоритма:

  • Сложность реализации в алгоритме коэффициентов уверенности;
  • Время выполнения вывода растёт экспоненциально с ростом числа правил;
  • ("Неустранимый" недостаток данной цепочки рассуждений). При организации прямой цепочки рассуждений на каждом шаге терминальному символу ставится в соответствие нетерминальный символ ("основа"). Как найти эту основу и то, к чему она должна приводиться? Именно этот недостаток, требующий "подбора методом проб и ошибок", и является основанием для недостатка 2;
  • Следствием недостатка №3 является то, что "в системе с реальным числом правил имеется столь много подразумеваемых (скрытых) фактов, что, будучи обнаружены, они затмят те несколько фактов, которые действительно представляют интерес и являются полезными".
    •

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

    9.3.3. Вывод на правилах (обратная цепочка рассуждений)

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

    Ситуация меняется, когда мы рассматриваем дерево вывода на рисунке 9.2. В этом случае у нас имеется единственный "корень" дерева (обозначенный нами как <предложение>) и множество "листьев" - фактов. Естественно, перебор всех возможных "фактов" и "отсев" ненужных комбинаций займёт много времени (см. недостаток №3 прямой цепочки рассуждений). В то же время "доказательство" корневой части можно оптимизировать таким образом, чтобы исключить из рассмотрения заведомо "неправильные" цепочки рассуждений.

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

    Механизм обратного вывода встроен в язык логического программирования ПРОЛОГ. Именно на нём будут написаны примеры в этом подразделе.

    Достоинства нисходящего разбора:

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

    Недостатки обратного вывода:

  • Сложность реализации стандартного алгоритма в "процедурных" языках;
  • Время выполнения программы растёт экспоненциально с ростом числа правил;
  • ("Неустранимый" недостаток данной цепочки рассуждений). При организации обратной цепочки рассуждений могут встретиться правила с альтернативами, меняющие направление разбора. Как узнать, какую альтернативу следует использовать при выводе? Именно этот недостаток, требующий "подбора методом проб и ошибок", и является основанием для недостатка 2;
  • (Следствие недостатка №3) Данный алгоритм плохо обрабатывает леворекурсивные грамматики.
    •

    9.4. Разбор символьных выражений

    Однако довольно часто грамматический разбор некоторого символьного текста (им может быть предложение, текстовая форма, и т.д.) предваряется "лексическим анализатором", или "сканером лексем" (смотри [41]). Рассмотрим лексический анализатор поподробнее.

    Сканер лексем

    Часто грамматический разбор текста намного упрощается, если его предварительно обработать программой, в просторечии называемой сканером (не путать с аппаратным устройством для ввода изображений!). Его назначение:

  • Пропуск ненужных ("заполняющих") символов;
  • Определение и "выделение" ключевых слов;
  • Выявление чисел, констант, идентификаторов и т.п., не имеющих "жёсткого" написания, как "ключевые слова", но несущие смысловое значение.
    •

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

    Кроме того, существует так называемые "интеллектуальные сканеры", способные не только выделять из текста лексемы, но также "классифицировать лексемы" по определённым признакам. Например, в примере 06 и приложении II (app2002) представлен такой сканер, реализованный на языке Си и позволяющий выделять из текста не просто цифры, но и числа определённых типов, в том числе и в "научной" нотации. Там же представлен другой сканер, используемый в программе "Частотный словарь". Грамматику сканера чисел мы рассмотрим в лекции 10.

    Подпрограммы для поиска и замены лексем

    В архиве strfind.zip и в приложении III представлен набор (библиотека) подпрограмм для поиска и замены символов, найденных в символьной строке, другими символами. Эту библиотеку автор использовал при написании программ: "Частотный словарь", "SSI_Exchange", "Преобразование формата Лексикона в pre-HTML (txr2rtx)" и других.

    Подпрограммы написаны на языке Си и оптимизированы под компиляторы Borland C/C++ и GNU C. Имеется также версия с использованием библиотеки Windows API. Библиотека распространяется под лицензией GNU GPL на условиях Copyleft. Текст документации распространяется по CC - лицензии на условиях ByName и Copyleft. Для их коммерческого использования необходимо получить разрешение у автора по e-mail. Текст программы и документация находятся в архиве и продублирована в Приложении II.

    Более подробно о функциях работы с текстовыми строками смотри в приложении к лекции 6 данного курса и указанной к ней дополнительной литературе.

    9.5. Резюме

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

    В следующей лекции Вы познакомитесь с основами формальных грамматик - базовыми элементами алгоритмов регулярных выражений и искусственного интеллекта. Она является наиболее сложной в данном курсе, но Вы её должны обязательно рассмотреть, понять и использовать в своей работе.

    9.6. Глоссарий

    Термин (рус.) Термин (англ.) Толкование
    творческая деятельность creative activity Деятельность человека по созданию литературного произведения, музыки, научных работ, моделей, бизнес-идей и другой оригинальной, не имеющей аналогов информации.
    представление знаний knowledge representation Запись трудно формализуемых, опытных и "интуитивно" добытых от эксперта данных, позволяющая "воспроизводить рассуждения эксперта" в экспертной системе некоторой области человеческих знаний. "Добычей" и составлением экспертных систем занимается инженер по знаниям
    база знаний knowledge base Представление знаний в виде набора правил, фактов, записей в иерархических и реляционных базах данных, используемых в дальнейшем при создании экспертных систем.
    экспертная система expert system Программа, созданная инженером по знаниям, способная самостоятельно, на основе собранных исходных данных, в диалоговом режиме моделировать "рассуждения эксперта" и объяснять выданные ею решения.
    интеллектуальный робот intellectual robot Автомат, способный без участия человека "обучаться новым навыкам работы". Обычно эти роботы имеют средства ориентации в пространстве, способные воспринимать ранее успешно осуществлённые программы, в некоторых случаях - распознавать человеческие жесты и речь.
    логический вывод logical deduce В информатике - вывод на основе введённых в компьютер правил (аналог силлогизмов) и добытых фактов, на основе которых компьютер или проверяет истинность утверждений, или позволяет находить все значения переменных, не противоречащих ранее записанным фактам и правилам. При этом если ранее введённые правила и факты образуют базу знаний, то логический вывод на их основе означает вывод по текущей базе знаний.
    правила подстановки rule of substitutions Правила, по которым "нетерминальный символ" в грамматике или внутренняя переменная при логическом выводе заменяется "правильным" (допустимым) его значением.
    дерево вывода tree of a reduce "Развёртка" грамматического разбора некоторого предложения, нахождения всех терминальных символов и "верных" значений внутренних переменных вывода в графическую схему с одним "корнем" - целью вывода и множеством "листов" - решений. Основное преимущество деревьев вывода - их наглядность и простота целостного восприятия (гештальт).
    синтез текста text synthesis Создание "связанного текста на человеческом языке" интеллектуальным роботом. Отметим, что эта проблема имеет непосредственное отношение к "тесту Тьюринга" и не решена до сих пор.
    ввод-вывод input-output Операция "общения" двух автоматов или автомата и человека по удобным для них интерфейсам и протоколам. Обычно в ЭВМ рассматривается операция ввода с клавиатуры и вывода на дисплей.
    разбор текста analysis of a text Разбиение текста на "человеческом" языке на стилистические, синтаксические, грамматические, морфологические и другие части, необходимые для его анализа (в т.ч. и на ЭВМ).
    электронная корреспонденция electronic correspondence Входящая и исходящая информация, передаваемая по "компьютерной" электронной почте.
    проверка орфографии spelling check Проверка компьютером правильности написания слов набранного текста, на предмет соответствия его орфографии, управления и "благозвучности" какому-либо "человеческому" языку.
    проверка стиля examination of a style Проверка компьютером правильности употребления отдельных слов и "смысловых конструкций", разбиения текста на предложения и абзацы на соответствие заданному стилю изложения.
    ассоциативное (множество) associative set Множества A, B и C называются ассоциативными, если выполняется равенство: (AB)C = A(BC).
    коммутативное (множество) commutative set Множества A и B называют коммутативными, если выполняется равенство: AB = BA.
    конкатенация catenation Операция "бесшовного" соединения двух строк друг с другом. Имеет различное обозначение. Операция конкатенации ассоциативна, но не коммутативна.
    шаблон template См. регулярные выражения, метасимвол.
    метасимвол meta symbol Символ, имеющий специальное значение в регулярных выражениях. Например, символ '*' означает "ноль или более повторений", символ '+' - "одно или более повторений". Сочетание символов и метасимволов определяет шаблон поиска. При поиске метасимволы играют роль нетерминальных символов.
    регулярное выражение regular expression Символьная строка, содержащая метасимволы, используемая для операций поиска и замены текста в текстовом файле или в текстовой строке.
    поиск 1 find 1 Операция нахождения подстроки в строке текста по заданному образцу. Замена текста не производится. Подстрока-образец может представлять собой регулярное выражение.
    замена replace Операция поиска подстроки в строке, с заменой найденного образца заранее определённым фрагментом текста. Подстрока может представлять собой регулярное выражение.
    синтаксический разбор 1 syntax parsing 1 Построение синтаксического дерева по тексту.
    синтаксический разбор 2 syntax parsing 2 Алгоритм, позволяющий определить, является ли исходный текст порождением одной из грамматик.
    грамматический разбор 1 grammar parsing 1 (в узком смысле) Алгоритм, позволяющий определить, является ли данное предложение предложением определённого языка (например, английского), и какие части речи входят в него.
    вывод 1 reduce 1, deduce 1 Процесс сопоставления исходного текста цели вывода путём применения правил формальной грамматики.
    цель (вывода) goal Одно из правил (или нетерминальный символ), которому ищется соответствие в тексте. Целью может быть необязательно начальный символ грамматики
    прямой вывод direct deduce Логический вывод, осуществляемый от терминального символа к цели вывода. Алгоритм прямого вывода строится либо на системе продукций, либо по прямой цепочке рассуждений
    обратный вывод reverse deduce Логический вывод, доказывающий, существует ли для данной цели вывода цепочка правил, с помощью которой строится исходный текст.
    семантический анализ semantic analysis Сопоставление успешно разобранному синтаксическому дереву "смысловых" значений. Значением может быть понимание текста в "человеческом" понимании, программа на ЭВМ и др.
    семантическая сеть semantic net Условное построение, позволяющее создать "связи" между узлами сети с целью логического вывода, нахождения определённых значений для узлов сети, ответов на вопросы, задаваемых ЭВМ и т.п.
    фрейм 1 frame 1 Расширение семантической сети. Фреймы содержат в себе "основные отношения" реального мира, на основе которого строятся "представление знаний" об этом мире. Недостающие элементы - описания фреймов определяются через цепочку сообщений между фреймами. По мнению американского учёного Минского, сознание человека также основано на фреймах.
    ИИ AI См. искусственный интеллект.
    искусственный интеллект artificial intelligence Совокупность алгоритмов, реализующих действия, ранее выполняемые только человеком. Искусственным интеллектом также называется часть информатики, алгебры и т.п., изучающая эти алгоритмы.
    тест Тьюринга Turing's test Тест, по которому определяется "интеллектуальность" приложения. Он состоит в том, что эксперту предлагается общаться на определённую тему с человеком, затем с программой. Если эксперту не удалось найти разницу в "общении", значит, тест пройден. По состоянию на 01.06.2008 тест Тьюринга не прошла ни одна программа.
    датамайнинг datamining Процесс извлечения и обработки данных из различных источников, чтобы создать документы для принятия решения.
    коррекция текста text correction Исправление найденных в тексте синтаксических, орфографических, стилистических и других ошибок.
    бинарные ветви binary chain Две ветви дерева вывода, выбор которых аналогичен ответам на вопрос: "Да" или "Нет".
    обход (дерева вывода) round (of a reduced tree) Порядок, в котором программа производит обход дерева вывода (нахождения фактов). От этого порядка зависит эффективность алгоритма вывода.
    подлежащее subject Член предложения, обозначающий лицо, которое совершает действие. Обычно это группа существительного.
    группа существительного group of a noun В английском языке это собственное или нарицательное существительное, местоимение, вместе с предшествующим артиклем и определением.
    прямое дополнение direct object Член предложения, обозначающий объект, над которым осуществляются действия подлежащим. Обычно это группа существительного.
    сказуемое predicate Член предложения, обозначающий действие, которое подлежащее осуществляет над дополнением. Обычно выражается глаголом.
    основной глагол main verb Слово в языке, означающее какое-либо действие. В предложении основной глагол несёт смысловую нагрузку.
    вспомогательный глагол auxiliary verb Глагол, который "объясняет" и "дополняет" смысл основного глагола.
    артикль article Член английского (и не только!) предложения, указывающий, что данное словосочетание является группой существительного (а не иной частью речи). Обычно артикль распространён в языках, в которых отсутствуют специфические окончания слов (как в славянских языках).
    определение attribute Член группы существительного, дополняющий смысл существительного в словосочетании.
    существительное noun Слово, обозначающее на языке лицо или предмет.
    местоимение pronoun Слово, заменяющее в предложении ранее упомянутое существительное, прилагательное или числительное.
    наречие adverb Слово, дополняющее смысл, образ действия, выраженного сказуемым.
    понимание смысла comprehension of a sense Алгоритм искусственного интеллекта, с помощью которого из текста на "человеческом" языке выделяются ключевые понятия, которые потом заносятся в базу знаний (базу данных) в ЭВМ, и на основе которых генерируются ответы на вопросы, заданные человеком ЭВМ. Отметим, что сгенерированные ответ не обязательно должны проходить "тест Тьюринга" - достаточно использовать диалоговые окна-формы.
    факт fact Значение переменной или терма, принимающего участие в логическом выводе. Это значение может быть только терминальным символом. Пример факта; name("Галя").
    правило 1 rule 1 Конструкция, ставящая в соответствие некоторым нетерминальным символам значения фактов. Правило имеет вид: "Если <факт> и <факт> то <нетерминальная переменная> = <значение>", или "дед(B, C) if отец(B, A) and отец(A, C)".
    продукция production Аналог правила (1) в искусственном интеллекте, но термин используется в контексте "условие", а не "функция";
    автоматическое доказательство предположения automatic proof of the supposition Алгоритм искусственного интеллекта, позволяющий на основе принципов формальной логики, используя записанные в ЭВМ правила и факты, определять (доказывать) истинность или ложность суждения - "цели" вывода.
    решение decision Список значений переменных, полученных при доказательстве цели вывода.
    алгоритм вывода reduction algorithm Стандартный алгоритм для логического вывода, не зависящий от вида количества и значения правил (1) и фактов. Это - антагонист алгоритма системы продукций и нейронных сетей. Примечание: существуют стандартные алгоритмы отдельно для прямого и обратного вывода.
    система продукций system of productions Алгоритм логического вывода, результат которого зависит от количества и порядка расположения продукций. От алгоритма нейронных сетей он отличается безусловным характером правил.
    промежуточные переменные вывода intermediate variables of deduce Переменные в языке программирования (например, ПРОЛОГ), используемые внутри правил вывода и не участвующие в записи фактов или генерации результатов вывода. Промежуточные переменные называются по-другому "внутренними переменными вывода".
    набор (система) продукций collection (set, system) of the productions Некоторое множество операторов условия, ветвления или множественного выбора, с помощью которых моделируется логический вывод из нескольких возможных альтернатив. При этом собственно алгоритм вывода не используется, а правильность работы этой системы настраивают путём перестановки операторов и изменения их приоритета.
    нейронные сети neural net Система продукций, правила которых носят некоторую случайную, "вероятностную" составляющую, определяемую коэффициентом уверенности.
    коэффициент уверенности (КУ) coefficient of a sure Численное значение, которое приблизительно отражает вероятностную составляющую логического вывода. Коэффициент уверенности меняется от "-1" (отрицание события, полученного в результате вывода) до "1" (безусловное наступление события в результате вывода). Значение "0" соответствует неопределённости события, полученного при выводе.
    реализация "с нуля" (алгоритма) realization from zero (of the algorithm) Реализация уникального алгоритма, в котором нет (или не используется) стандартные "заготовки" типа фрагмента кода программы, библиотеки, запрограммированные ранее алгоритмы. Алгоритмы нейронных сетей и системы продукций необходимо всегда программировать с нуля.
    настройка нейронной сети test of neural net Процесс изменения порядка следования правил и изменения коэффициентов уверенности в нейронной сети с целью выдачи "адекватных результатов" работы приложений. Это - самый сложный этап тестирования программы - нейронной сети.
    отладка debugging Процесс нахождения ошибок в программе (синтаксических, логических, "отказов"). В логической парадигме под отладкой также понимают настройку продукций и правил таким образом, чтобы система выдавала правильные результаты.
    прямая цепочка рассуждений direct chain of reasoning Алгоритм построения "дерева вывода" начиная с фактов, постепенно раскрывая и доказывая новые предположения и приведения цепочки рассуждений к "единому" корню. Эту цепочку нужно использовать, когда исходных фактов много, а количество "ветвей" (правил) относительно мало.
    обратная цепочка рассуждений reverse chain of reasoning Алгоритм построения "дерева вывода" начиная с "цели вывода" (корня), поочерёдно опускаясь до фактов и выясняя, истина ли данная цель. Эта цепочка рассуждений является универсальной, и её алгоритм содержится в реализации языка ПРОЛОГ.
    нисходящий вывод reversed reduce Логический вывод, использующий обратную цепочку рассуждений.
    ПРОЛОГ PROLOG Расшифровывается как "PROgramming in LOGic" (программирование логики). Язык логического программирования, реализующий встроенный алгоритм обратного вывода. Для написания программы на нём необходимо задать только факты и правила.
    система объяснения машинного вывода explanation system (of a computer deduce) Введение в правила, используемые в алгоритмах логического вывода, кода, позволяющего "отслеживать" порядок их применения и выдавать его пользователю на "человеческом языке", с возможностью объяснения их применений. В основном эта система используется в экспертных системах.
    лексический анализатор lexical analyzer Программный модуль, реализующий проверку и выделение "ключевых слов" (лексем) в тексте, предваряющий его полный грамматический разбор. Лексический анализатор обычно программируют на "процедурных" языках, и реализуют на основе автоматных грамматик.
    сканер лексем lexeme scanner См. лексический анализатор.
    заполняющие символы filling characters Символы в языке, не несущие смысловой нагрузки и предназначены, во-первых, для разделения лексем, а во-вторых, для "графического оформления" текста. Обычно к заполняющим символам относят все пробельные символы.
    ключевые слова 1 keywords 1 В языке программирования символы и слова, обозначающие операции, операторы языка, объявления и модификаторы, а также имена некоторых "библиотечных функций". После обработки ключевых слов сканером лексем для их обозначения и последующего разбора им присваиваются уникальные идентификаторы.
    интеллектуальный сканер intellectual lexical analyzer Сканер, способный, кроме простого разбора лексем, также определять типы лексем, а также выделять сложные лексемы, такие как числа в научном формате. Хотя эти сканеры также реализуются на процедурных языках, они часто строятся на основе КС-грамматик.
    Страницы:

    "ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ, раздел информатики, включающий разработку методов моделирования и воспроизведения с помощью ЭВМ отдельных функций творческой деятельности человека, решение проблемы представления знаний в ЭВМ и построение баз знаний, создание экспертных систем, разработку т. н. интеллектуальных роботов"

    Цель лекции:

  • Дать читателю представление о дисциплине: "искусственный интеллект";
  • Ознакомить его с понятиями: "логический вывод", "продукция", "правила подстановки";
  • Ознакомить читателя с основными положениями формальной грамматики, понятиями: "однозначная грамматика" и "синтаксическое дерево";
  • Научить его пользоваться регулярными выражениями;
  • Дать базовые знания для последующего изучения языков логического программирования.
    •

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

    9.1. Введение

    К символьным операциям относят:

  • Операцию ввода-вывода строк;
  • Конкатенацию (объединение) строк;
  • Поиск по шаблону;
  • Замену в тексте строки по заданному образцу;
  • Грамматический, синтаксический и др. разбор текста;
  • Прямой вывод;
  • Обратный вывод;
  • Построение "деревьев вывода";
  • Семантический анализ текста;
  • Построение фреймов и семантических сетей;
  • Синтез "связной речи";
  • И многое другое.
    •

    Эти задачи гораздо сложнее, чем численные расчёты на ЭВМ. К тому же научно они менее разработаны, чем численные методы. Но именно за символьными вычислениями - будущее отрасли высоких технологий.

    Символьные операции могут применяться, например:

  • При подготовке и рассылке электронной корреспонденции;
  • При поиске во всемирной сети;
  • При наборе и вёрстке текста;
  • При проверке орфографии и стиля документа;
  • При переводе текста с языка на язык (имеются в виду как "человеческие", так и "машинные" языки);
  • При осуществлении "теста Тьюринга";
  • В датамайнинге;
  • При автоматической коррекции текста и перевода его из формата в формат;
  • При разработке языков программирования и написании их трансляторов и компиляторов для них;
  • и т.д.
    •

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

    9.2. Построение деревьев вывода

    Для начала рассмотрим игру "Животные", приведённую в [64]. Вот диалог работы с этой программой:

    [Пример 01]

  • "Это кот?" - "Нет".
  • "Сдаюсь, кто это?" - "кит".
  • "Чем отличается кот от кит?" - "плавает в море".
  • "Сыграем ещё?" - "Да".
  • "Он плавает в море?" - "Нет".
  • "Это кот?" - "Нет".
  • "Сдаюсь, кто это?" - "студент".
  • "Чем отличается кот от студент?" - "ходит на лекцию".
  • "Сыграем ещё?" - "Да".
  • "Он плавает в море?" - "Нет".
  • "Он ходит на лекцию?" - "Да".
  • "Это студент?" - "Нет".
  • "Сдаюсь, кто это?" - "профессор".
  • "Чем отличается студент от профессор?" - "читает лекции".
  • …
    •

    Этот диалог формирует следующее дерево (см. рисунок 9.1):

    (рис 9.1) Дерево вывода примера 01

    В этом дереве имеется "корень" - название игры ("животные"). От него исходят так называемые "бинарные ветви" - ветви, которым соответствуют ответы: "Да" или "Нет". Это дерево является моделью, полностью описывающее состояние игры: "Животные". С помощью этого дерева можно ответить на вопросы:

  • Сколько необходимо задать вопросов, чтобы получить ответ: "студент"?
  • Кто является "соседней ветвью" ответа: "студент"?
  • Присутствует ли ответ: "студент" - в дереве вывода?
  • Много ли не заполненных ветвей дерева (обозначенных: "Кто это")?
    •

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

    Вот другой пример дерева вывода, вид которого представлен на рисунке 9.2. Рассмотрим грамматический разбор английского предложения: "The big elephant will eat pineapples tomorrow". ("Большой слон будет есть ананасы завтра").

    (рис 9.2) Синтаксическое дерево при разборе английского предложения

    Как известно читателям, изучавшим английский язык, структура английского предложения является жёсткой и имеет следующий вид:

    <Подлежащее><Сказуемое>[<Прямое дополнение>][<Обстоятельство>]

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

    В принципе, в этом предложении можно менять существительные и глаголы - это не должно влиять на правильность разбора предложения. Например, правильными также будут следующие предложения:

  • An old man ate an apple yesterday.
  • A small elephant is eating a ball now!
    •

    Однако второе предложение бессмысленно (кому-то оно может показаться даже непристойным). Это объясняется тем, что мы не рассматривали "осмысленность" предложения при выводе. Автор должен отметить, что задачи искусственного интеллекта понимания смысла текста и "осмысленного" генерирования предложений не решены уже более 50 лет (время появления первых ЭВМ с современной архитектурой). В основном из-за того, что до сих пор нет ответа на вопрос: "Что такое смысл"? Но это уже отступление от темы.

    Итак, мы рассмотрели два дерева вывода, выяснили, насколько это "дерево" полезно при разборе и построении предложений, открыли новые возможности символьных вычислений. Однако построение всех деревьев вывода и анализ их человеком обычно очень трудная, если не сказать, "неподъёмная" задача. Нельзя ли оптимизировать выполнение этих задач? Можно! Об этом - в следующем подразделе.

    9.3. Прямой и обратный вывод

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

    [Пример 02]

    /* Массиву строковых переменных names присвоены значения (язык Си плюс-плюс) */

names[0] = "Галя"; names[1] = "Нина"; names[2] = "Петя";

/* То же определение на языке Turbo Prolog */

names("Галя"); names("Нина"); names("Петя");

/* Определение массивов строковых переменных article (все возможные английские артикли) (C++) */

article[0] = ""; article[1] = "the"; article[2] = "a"; article[3] = "an";

    Правила же определяются следующим образом:

    [Пример 03]

    /* Пример на C++ */

if( names[i] == "Галя" ) woman.name = names[i];

/* Пример на Turbo Prolog */

woman( N ) if N == "Галя" оr N == "Нина", name(N);

    Выводом же будет автоматическое доказательство некоторого предположения, определённого как истинность одного из правил. Это правило называют "целью" вывода (по-английски: "goal"). При выборе цели возможно нахождение одного, нескольких или ни одного решения - списка значений переменных, участвующих в выводе.

    Примечание. Множество решений - это, практически, множество предложений заданной грамматики, полученных в результате доказательства цели вывода. Определение грамматики см. раздел 2 лекции 10.

    Когда написаны все факты и правила, необходимо написать алгоритм вывода. Он может быть одним из следующих:

  • Вывод на основе системы продукций (или "нейронной сети");
  • Вывод на основе правил (стандартный алгоритм вывода по прямой цепочке рассуждений);
  • Вывод на основе правил (стандартный алгоритм вывода по обратной цепочке рассуждений).
    •

    Рассмотрим их поподробнее.

    9.3.1. Система продукций (и "нейронные сети")

    Вывод на основе системы продукций следующий:

  • Определяются и вводятся "факты", на основе которых делается вывод;
  • Описываются промежуточные переменные вывода и цель вывода;
  • Составляется набор правил (продукций), последовательно задающие значения промежуточным переменным;

    Внимание! Порядок записи продукций имеет значение.

  • В процессе написания продукций в текст вставляются операторы вывода значений переменных, когда это необходимо;
  • В процессе работы системы продукций с реализацией "нечёткой логики" (по-другому: "нейронной сети") каждой продукции соответствует "коэффициент уверенности", который отражает степень доверия к этой продукции. Он вычисляется на основе коэффициентов уверенности доказанных фактов, правил, и коэффициента уверенности самой продукции.
    •

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

    Преимущества системы продукций и нейронных сетей:

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

    Недостатки этих систем:

  • Они не подходят для кодирования "стандартным алгоритмом вывода". Программист должен реализовывать "с нуля" алгоритм нейронной сети или системы продукций.
  • Невозможность предсказать поведение работающей программы;
  • Сложность отладки. Для отладки необходимо при прогоне тестов менять только один параметр. Это делает отладку длительной по времени.
  • Система продукций - это "чёрный ящик", не дающий пользователю объяснений о ходе своих рассуждений.
    •  Примечание. Информацию о коэффициентах уверенности, их расчёту и применении смотри, например, в [57].

    9.3.2. Вывод на правилах (прямая цепочка рассуждений)

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

    Наглядно результат прямого вывода по дереву вывода, приведённого на рисунке 9.2, показан на рисунке 9.3.

    (рис 9.3) Восходящий разбор английского предложения

    Достоинства алгоритма восходящего разбора:

  • Наличие стандартного алгоритма вывода;
  • Возможность предсказать результат на любом этапе разработки программы;
  • Простота отладки правил (но не алгоритма вывода!);
  • Средняя сложность реализации в "процедурных" языках и языках логического программирования (Пролог).
    •

    Недостатки алгоритма:

  • Сложность реализации в алгоритме коэффициентов уверенности;
  • Время выполнения вывода растёт экспоненциально с ростом числа правил;
  • ("Неустранимый" недостаток данной цепочки рассуждений). При организации прямой цепочки рассуждений на каждом шаге терминальному символу ставится в соответствие нетерминальный символ ("основа"). Как найти эту основу и то, к чему она должна приводиться? Именно этот недостаток, требующий "подбора методом проб и ошибок", и является основанием для недостатка 2;
  • Следствием недостатка №3 является то, что "в системе с реальным числом правил имеется столь много подразумеваемых (скрытых) фактов, что, будучи обнаружены, они затмят те несколько фактов, которые действительно представляют интерес и являются полезными".
    •

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

    9.3.3. Вывод на правилах (обратная цепочка рассуждений)

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

    Ситуация меняется, когда мы рассматриваем дерево вывода на рисунке 9.2. В этом случае у нас имеется единственный "корень" дерева (обозначенный нами как <предложение>) и множество "листьев" - фактов. Естественно, перебор всех возможных "фактов" и "отсев" ненужных комбинаций займёт много времени (см. недостаток №3 прямой цепочки рассуждений). В то же время "доказательство" корневой части можно оптимизировать таким образом, чтобы исключить из рассмотрения заведомо "неправильные" цепочки рассуждений.

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

    Механизм обратного вывода встроен в язык логического программирования ПРОЛОГ. Именно на нём будут написаны примеры в этом подразделе.

    Достоинства нисходящего разбора:

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

    Недостатки обратного вывода:

  • Сложность реализации стандартного алгоритма в "процедурных" языках;
  • Время выполнения программы растёт экспоненциально с ростом числа правил;
  • ("Неустранимый" недостаток данной цепочки рассуждений). При организации обратной цепочки рассуждений могут встретиться правила с альтернативами, меняющие направление разбора. Как узнать, какую альтернативу следует использовать при выводе? Именно этот недостаток, требующий "подбора методом проб и ошибок", и является основанием для недостатка 2;
  • (Следствие недостатка №3) Данный алгоритм плохо обрабатывает леворекурсивные грамматики.
    •

    9.4. Разбор символьных выражений

    Однако довольно часто грамматический разбор некоторого символьного текста (им может быть предложение, текстовая форма, и т.д.) предваряется "лексическим анализатором", или "сканером лексем" (смотри [41]). Рассмотрим лексический анализатор поподробнее.

    Сканер лексем

    Часто грамматический разбор текста намного упрощается, если его предварительно обработать программой, в просторечии называемой сканером (не путать с аппаратным устройством для ввода изображений!). Его назначение:

  • Пропуск ненужных ("заполняющих") символов;
  • Определение и "выделение" ключевых слов;
  • Выявление чисел, констант, идентификаторов и т.п., не имеющих "жёсткого" написания, как "ключевые слова", но несущие смысловое значение.
    •

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

    Кроме того, существует так называемые "интеллектуальные сканеры", способные не только выделять из текста лексемы, но также "классифицировать лексемы" по определённым признакам. Например, в примере 06 и приложении II (app2002) представлен такой сканер, реализованный на языке Си и позволяющий выделять из текста не просто цифры, но и числа определённых типов, в том числе и в "научной" нотации. Там же представлен другой сканер, используемый в программе "Частотный словарь". Грамматику сканера чисел мы рассмотрим в лекции 10.

    Подпрограммы для поиска и замены лексем

    В архиве strfind.zip и в приложении III представлен набор (библиотека) подпрограмм для поиска и замены символов, найденных в символьной строке, другими символами. Эту библиотеку автор использовал при написании программ: "Частотный словарь", "SSI_Exchange", "Преобразование формата Лексикона в pre-HTML (txr2rtx)" и других.

    Подпрограммы написаны на языке Си и оптимизированы под компиляторы Borland C/C++ и GNU C. Имеется также версия с использованием библиотеки Windows API. Библиотека распространяется под лицензией GNU GPL на условиях Copyleft. Текст документации распространяется по CC - лицензии на условиях ByName и Copyleft. Для их коммерческого использования необходимо получить разрешение у автора по e-mail. Текст программы и документация находятся в архиве и продублирована в Приложении II.

    Более подробно о функциях работы с текстовыми строками смотри в приложении к лекции 6 данного курса и указанной к ней дополнительной литературе.

    9.5. Резюме

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

    В следующей лекции Вы познакомитесь с основами формальных грамматик - базовыми элементами алгоритмов регулярных выражений и искусственного интеллекта. Она является наиболее сложной в данном курсе, но Вы её должны обязательно рассмотреть, понять и использовать в своей работе.

    9.6. Глоссарий

    Термин (рус.) Термин (англ.) Толкование
    творческая деятельность creative activity Деятельность человека по созданию литературного произведения, музыки, научных работ, моделей, бизнес-идей и другой оригинальной, не имеющей аналогов информации.
    представление знаний knowledge representation Запись трудно формализуемых, опытных и "интуитивно" добытых от эксперта данных, позволяющая "воспроизводить рассуждения эксперта" в экспертной системе некоторой области человеческих знаний. "Добычей" и составлением экспертных систем занимается инженер по знаниям
    база знаний knowledge base Представление знаний в виде набора правил, фактов, записей в иерархических и реляционных базах данных, используемых в дальнейшем при создании экспертных систем.
    экспертная система expert system Программа, созданная инженером по знаниям, способная самостоятельно, на основе собранных исходных данных, в диалоговом режиме моделировать "рассуждения эксперта" и объяснять выданные ею решения.
    интеллектуальный робот intellectual robot Автомат, способный без участия человека "обучаться новым навыкам работы". Обычно эти роботы имеют средства ориентации в пространстве, способные воспринимать ранее успешно осуществлённые программы, в некоторых случаях - распознавать человеческие жесты и речь.
    логический вывод logical deduce В информатике - вывод на основе введённых в компьютер правил (аналог силлогизмов) и добытых фактов, на основе которых компьютер или проверяет истинность утверждений, или позволяет находить все значения переменных, не противоречащих ранее записанным фактам и правилам. При этом если ранее введённые правила и факты образуют базу знаний, то логический вывод на их основе означает вывод по текущей базе знаний.
    правила подстановки rule of substitutions Правила, по которым "нетерминальный символ" в грамматике или внутренняя переменная при логическом выводе заменяется "правильным" (допустимым) его значением.
    дерево вывода tree of a reduce "Развёртка" грамматического разбора некоторого предложения, нахождения всех терминальных символов и "верных" значений внутренних переменных вывода в графическую схему с одним "корнем" - целью вывода и множеством "листов" - решений. Основное преимущество деревьев вывода - их наглядность и простота целостного восприятия (гештальт).
    синтез текста text synthesis Создание "связанного текста на человеческом языке" интеллектуальным роботом. Отметим, что эта проблема имеет непосредственное отношение к "тесту Тьюринга" и не решена до сих пор.
    ввод-вывод input-output Операция "общения" двух автоматов или автомата и человека по удобным для них интерфейсам и протоколам. Обычно в ЭВМ рассматривается операция ввода с клавиатуры и вывода на дисплей.
    разбор текста analysis of a text Разбиение текста на "человеческом" языке на стилистические, синтаксические, грамматические, морфологические и другие части, необходимые для его анализа (в т.ч. и на ЭВМ).
    электронная корреспонденция electronic correspondence Входящая и исходящая информация, передаваемая по "компьютерной" электронной почте.
    проверка орфографии spelling check Проверка компьютером правильности написания слов набранного текста, на предмет соответствия его орфографии, управления и "благозвучности" какому-либо "человеческому" языку.
    проверка стиля examination of a style Проверка компьютером правильности употребления отдельных слов и "смысловых конструкций", разбиения текста на предложения и абзацы на соответствие заданному стилю изложения.
    ассоциативное (множество) associative set Множества A, B и C называются ассоциативными, если выполняется равенство: (AB)C = A(BC).
    коммутативное (множество) commutative set Множества A и B называют коммутативными, если выполняется равенство: AB = BA.
    конкатенация catenation Операция "бесшовного" соединения двух строк друг с другом. Имеет различное обозначение. Операция конкатенации ассоциативна, но не коммутативна.
    шаблон template См. регулярные выражения, метасимвол.
    метасимвол meta symbol Символ, имеющий специальное значение в регулярных выражениях. Например, символ '*' означает "ноль или более повторений", символ '+' - "одно или более повторений". Сочетание символов и метасимволов определяет шаблон поиска. При поиске метасимволы играют роль нетерминальных символов.
    регулярное выражение regular expression Символьная строка, содержащая метасимволы, используемая для операций поиска и замены текста в текстовом файле или в текстовой строке.
    поиск 1 find 1 Операция нахождения подстроки в строке текста по заданному образцу. Замена текста не производится. Подстрока-образец может представлять собой регулярное выражение.
    замена replace Операция поиска подстроки в строке, с заменой найденного образца заранее определённым фрагментом текста. Подстрока может представлять собой регулярное выражение.
    синтаксический разбор 1 syntax parsing 1 Построение синтаксического дерева по тексту.
    синтаксический разбор 2 syntax parsing 2 Алгоритм, позволяющий определить, является ли исходный текст порождением одной из грамматик.
    грамматический разбор 1 grammar parsing 1 (в узком смысле) Алгоритм, позволяющий определить, является ли данное предложение предложением определённого языка (например, английского), и какие части речи входят в него.
    вывод 1 reduce 1, deduce 1 Процесс сопоставления исходного текста цели вывода путём применения правил формальной грамматики.
    цель (вывода) goal Одно из правил (или нетерминальный символ), которому ищется соответствие в тексте. Целью может быть необязательно начальный символ грамматики
    прямой вывод direct deduce Логический вывод, осуществляемый от терминального символа к цели вывода. Алгоритм прямого вывода строится либо на системе продукций, либо по прямой цепочке рассуждений
    обратный вывод reverse deduce Логический вывод, доказывающий, существует ли для данной цели вывода цепочка правил, с помощью которой строится исходный текст.
    семантический анализ semantic analysis Сопоставление успешно разобранному синтаксическому дереву "смысловых" значений. Значением может быть понимание текста в "человеческом" понимании, программа на ЭВМ и др.
    семантическая сеть semantic net Условное построение, позволяющее создать "связи" между узлами сети с целью логического вывода, нахождения определённых значений для узлов сети, ответов на вопросы, задаваемых ЭВМ и т.п.
    фрейм 1 frame 1 Расширение семантической сети. Фреймы содержат в себе "основные отношения" реального мира, на основе которого строятся "представление знаний" об этом мире. Недостающие элементы - описания фреймов определяются через цепочку сообщений между фреймами. По мнению американского учёного Минского, сознание человека также основано на фреймах.
    ИИ AI См. искусственный интеллект.
    искусственный интеллект artificial intelligence Совокупность алгоритмов, реализующих действия, ранее выполняемые только человеком. Искусственным интеллектом также называется часть информатики, алгебры и т.п., изучающая эти алгоритмы.
    тест Тьюринга Turing's test Тест, по которому определяется "интеллектуальность" приложения. Он состоит в том, что эксперту предлагается общаться на определённую тему с человеком, затем с программой. Если эксперту не удалось найти разницу в "общении", значит, тест пройден. По состоянию на 01.06.2008 тест Тьюринга не прошла ни одна программа.
    датамайнинг datamining Процесс извлечения и обработки данных из различных источников, чтобы создать документы для принятия решения.
    коррекция текста text correction Исправление найденных в тексте синтаксических, орфографических, стилистических и других ошибок.
    бинарные ветви binary chain Две ветви дерева вывода, выбор которых аналогичен ответам на вопрос: "Да" или "Нет".
    обход (дерева вывода) round (of a reduced tree) Порядок, в котором программа производит обход дерева вывода (нахождения фактов). От этого порядка зависит эффективность алгоритма вывода.
    подлежащее subject Член предложения, обозначающий лицо, которое совершает действие. Обычно это группа существительного.
    группа существительного group of a noun В английском языке это собственное или нарицательное существительное, местоимение, вместе с предшествующим артиклем и определением.
    прямое дополнение direct object Член предложения, обозначающий объект, над которым осуществляются действия подлежащим. Обычно это группа существительного.
    сказуемое predicate Член предложения, обозначающий действие, которое подлежащее осуществляет над дополнением. Обычно выражается глаголом.
    основной глагол main verb Слово в языке, означающее какое-либо действие. В предложении основной глагол несёт смысловую нагрузку.
    вспомогательный глагол auxiliary verb Глагол, который "объясняет" и "дополняет" смысл основного глагола.
    артикль article Член английского (и не только!) предложения, указывающий, что данное словосочетание является группой существительного (а не иной частью речи). Обычно артикль распространён в языках, в которых отсутствуют специфические окончания слов (как в славянских языках).
    определение attribute Член группы существительного, дополняющий смысл существительного в словосочетании.
    существительное noun Слово, обозначающее на языке лицо или предмет.
    местоимение pronoun Слово, заменяющее в предложении ранее упомянутое существительное, прилагательное или числительное.
    наречие adverb Слово, дополняющее смысл, образ действия, выраженного сказуемым.
    понимание смысла comprehension of a sense Алгоритм искусственного интеллекта, с помощью которого из текста на "человеческом" языке выделяются ключевые понятия, которые потом заносятся в базу знаний (базу данных) в ЭВМ, и на основе которых генерируются ответы на вопросы, заданные человеком ЭВМ. Отметим, что сгенерированные ответ не обязательно должны проходить "тест Тьюринга" - достаточно использовать диалоговые окна-формы.
    факт fact Значение переменной или терма, принимающего участие в логическом выводе. Это значение может быть только терминальным символом. Пример факта; name("Галя").
    правило 1 rule 1 Конструкция, ставящая в соответствие некоторым нетерминальным символам значения фактов. Правило имеет вид: "Если <факт> и <факт> то <нетерминальная переменная> = <значение>", или "дед(B, C) if отец(B, A) and отец(A, C)".
    продукция production Аналог правила (1) в искусственном интеллекте, но термин используется в контексте "условие", а не "функция";
    автоматическое доказательство предположения automatic proof of the supposition Алгоритм искусственного интеллекта, позволяющий на основе принципов формальной логики, используя записанные в ЭВМ правила и факты, определять (доказывать) истинность или ложность суждения - "цели" вывода.
    решение decision Список значений переменных, полученных при доказательстве цели вывода.
    алгоритм вывода reduction algorithm Стандартный алгоритм для логического вывода, не зависящий от вида количества и значения правил (1) и фактов. Это - антагонист алгоритма системы продукций и нейронных сетей. Примечание: существуют стандартные алгоритмы отдельно для прямого и обратного вывода.
    система продукций system of productions Алгоритм логического вывода, результат которого зависит от количества и порядка расположения продукций. От алгоритма нейронных сетей он отличается безусловным характером правил.
    промежуточные переменные вывода intermediate variables of deduce Переменные в языке программирования (например, ПРОЛОГ), используемые внутри правил вывода и не участвующие в записи фактов или генерации результатов вывода. Промежуточные переменные называются по-другому "внутренними переменными вывода".
    набор (система) продукций collection (set, system) of the productions Некоторое множество операторов условия, ветвления или множественного выбора, с помощью которых моделируется логический вывод из нескольких возможных альтернатив. При этом собственно алгоритм вывода не используется, а правильность работы этой системы настраивают путём перестановки операторов и изменения их приоритета.
    нейронные сети neural net Система продукций, правила которых носят некоторую случайную, "вероятностную" составляющую, определяемую коэффициентом уверенности.
    коэффициент уверенности (КУ) coefficient of a sure Численное значение, которое приблизительно отражает вероятностную составляющую логического вывода. Коэффициент уверенности меняется от "-1" (отрицание события, полученного в результате вывода) до "1" (безусловное наступление события в результате вывода). Значение "0" соответствует неопределённости события, полученного при выводе.
    реализация "с нуля" (алгоритма) realization from zero (of the algorithm) Реализация уникального алгоритма, в котором нет (или не используется) стандартные "заготовки" типа фрагмента кода программы, библиотеки, запрограммированные ранее алгоритмы. Алгоритмы нейронных сетей и системы продукций необходимо всегда программировать с нуля.
    настройка нейронной сети test of neural net Процесс изменения порядка следования правил и изменения коэффициентов уверенности в нейронной сети с целью выдачи "адекватных результатов" работы приложений. Это - самый сложный этап тестирования программы - нейронной сети.
    отладка debugging Процесс нахождения ошибок в программе (синтаксических, логических, "отказов"). В логической парадигме под отладкой также понимают настройку продукций и правил таким образом, чтобы система выдавала правильные результаты.
    прямая цепочка рассуждений direct chain of reasoning Алгоритм построения "дерева вывода" начиная с фактов, постепенно раскрывая и доказывая новые предположения и приведения цепочки рассуждений к "единому" корню. Эту цепочку нужно использовать, когда исходных фактов много, а количество "ветвей" (правил) относительно мало.
    обратная цепочка рассуждений reverse chain of reasoning Алгоритм построения "дерева вывода" начиная с "цели вывода" (корня), поочерёдно опускаясь до фактов и выясняя, истина ли данная цель. Эта цепочка рассуждений является универсальной, и её алгоритм содержится в реализации языка ПРОЛОГ.
    нисходящий вывод reversed reduce Логический вывод, использующий обратную цепочку рассуждений.
    ПРОЛОГ PROLOG Расшифровывается как "PROgramming in LOGic" (программирование логики). Язык логического программирования, реализующий встроенный алгоритм обратного вывода. Для написания программы на нём необходимо задать только факты и правила.
    система объяснения машинного вывода explanation system (of a computer deduce) Введение в правила, используемые в алгоритмах логического вывода, кода, позволяющего "отслеживать" порядок их применения и выдавать его пользователю на "человеческом языке", с возможностью объяснения их применений. В основном эта система используется в экспертных системах.
    лексический анализатор lexical analyzer Программный модуль, реализующий проверку и выделение "ключевых слов" (лексем) в тексте, предваряющий его полный грамматический разбор. Лексический анализатор обычно программируют на "процедурных" языках, и реализуют на основе автоматных грамматик.
    сканер лексем lexeme scanner См. лексический анализатор.
    заполняющие символы filling characters Символы в языке, не несущие смысловой нагрузки и предназначены, во-первых, для разделения лексем, а во-вторых, для "графического оформления" текста. Обычно к заполняющим символам относят все пробельные символы.
    ключевые слова 1 keywords 1 В языке программирования символы и слова, обозначающие операции, операторы языка, объявления и модификаторы, а также имена некоторых "библиотечных функций". После обработки ключевых слов сканером лексем для их обозначения и последующего разбора им присваиваются уникальные идентификаторы.
    интеллектуальный сканер intellectual lexical analyzer Сканер, способный, кроме простого разбора лексем, также определять типы лексем, а также выделять сложные лексемы, такие как числа в научном формате. Хотя эти сканеры также реализуются на процедурных языках, они часто строятся на основе КС-грамматик.
    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^