Классификация вычислений

К настоящему времени выделено 5 классов вычислений:

1. аналоговые вычисления;

2. цифровые вычисления;

3. словесные вычисления;

4. реляционные вычисления;

5. смысловые вычисления;

Особенность аналоговых вычислений состоит в том, что аргументы являются непрерывными величинами. Исследуются аналоговые вычисления в вычислительной математике: дифференцирование, интегрирование и т.д.

Цифровые вычисления определяются тем, что аргументы дискретны. Они исследуются в дискретной математике.

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

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

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

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

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

Основные направления в развитии систем ИИ, подразделяются:

1. экспертные системы – 60% исследований;

2. естественные языковые системы – 25% исследований;

3. прочие направления: эволюционные, генетические алгоритмы, интеллектуальные технические системы, в том числе системы технического зрения, многозначные логики;

История развития ИИ.

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

Эвристика – это практически рациональная, но фактически не обоснованная модель. В 70-е годы 20-го века - развитие логического подхода в ИИ. Были разработаны: метод резолюций, заложенный в язык пролог, и обратный метод Маслова. Вместе с тем логический подход оказался ограниченным, так как в условиях задачи обязательно должны были присутствовать аксиомы из предметной области, а это не всегда возможно. С 80-го года развивается направление – экспертные системы. (Экспертная система – специализирующая программа, ориентированная на решение поисковых и ориентированных задач на основе заложенных знаний экспертов). Успех экспертных систем предопределён отказом от глобальных направлений жесткости ориентации на предметную область, вместе с тем, в рамках экспертных систем были получены новые модели знаний, в том числе фреймовая модель.

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

Важнейшими свойствами, присущими представлениям знаний в СППР [Еремеев А.П. Организация параллельных вычислений на основе моделей потока данных // Изв. РАН. Техн. кибернет., 1993, № 3, с. 212-225] являются внутренняя интерпретируемость, структурированность, связность, семантическая метрика, активность. Качественная диаграмма перехода от данных к знаниям представлена на рисунке 1.2. Перечисленные пять свойств информационных единиц - знаний - определяют ту грань, за которой данные превращаются в знания, а базы данных - в базы знаний. Совокупность средств, обеспечивающих работу с знаниями, образуют систему управления базой знаний (СУБЗ). В настоящее время не существует баз знаний, в которых в полной мере были реализованы внутренняя интерпретируемость, структуризация, связность, введена семантическая мера и обеспечена активность знаний.

Рисунок 1.3 - Диаграмма свойств информационных единиц «данные –знания»

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

Знания же всегда содержательны как на уровне представления, так и на уровне обработки и интерпретации. При переходе к знаниям в память ЭВМ вводится информация о некоторой схеме информационных единиц. При этом должны быть заданы специальные словари, в которых перечислены имеющиеся в памяти системы сведения об информационных единицах. В настоящее время СУБД обеспечивает реализацию внутренней интерпретируемости всех информационных единиц, хранимых в базе данных.

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

Связность. Между информационными единицами должна быть предусмотрена возможность установления свя­зей произвольного типа. Прежде всего, связи могут характеризовать от­ношения между информационными единицами. Семантика отношений может носить декларативный или продукционный характер. Например, две и более информационные единицы могут быть связаны отношением «одновременно», две информационные единицы — отношением «причи­на-следствие» или отношением «быть рядом». Приведенные отношения характеризуют декларативные знания. Если между двумя информацион­ными единицами установлено отношение «аргумент—функция», то оно характеризует процедурные знания, связанные с вычислением определен­ных функций. Существуют отношения структуризации, функциональные отношения, каузальные отношения и семантические отношения. С помо­щью первых задаются иерархии информационных единиц, вторые несут процедурную информацию, позволяющую находить (вычислять) одни информационные единицы через другие, третьи задают причинно-следственные связи, четвертые соответствуют всем остальным отношениям.

Между информационными единицами могут устанавливаться и иные связи, например, определяющие выбор информационных единиц из па­мяти или указывающие на то, что две информационные единицы несо­вместимы друг с другом в описании.

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

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

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

Независимо от реализации ЯПЗ должен отвечать следующим требованиям:

наличие простых и вместе с тем достаточно мощных средств представления сложно структурированных и взаимосвязанных объектов;

возможность отображения описаний объектов на разные виды памяти ЭВМ;

наличие гибких средств управления выводом, учитывающих необходимость структурирования правил работы решателя;

«прозрачность» системных механизмов для программиста, т. е. возможность их до определения и переопределения на уровне входного языка;

возможность эффективной реализации, как программной, так и аппаратной;

Конечно, перечисленные требования во многом противоречивы. Но лишь тогда, когда в рамках разумного компромисса учтены все эти требования, создаются удачные ЯПЗ.

Пусть требуется достигнуть минимум целевой функции;

Приведем систему ограничений к виду уравнений путем добавления новых переменных .

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

,

Формируем первое базисное решение на основе полученной системы:

-недопустимо

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

Возьмём, например, в качестве базисной переменной , тогда остальные переменные – свободные и равны 0;

, ,

, Æ ,

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

Выразим новую базисную переменную через свободную. Тогда

,

Получим для базисных переменных новое базисное решение Z₂=(2, 0, 0, 0, 0, 3). Таким образом, второе базисное решение является допустимым.

Вычислим значения целевой функции при базисных переменных . Для этого в запись функции Z вместо поставим её новое значение

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

Определим свободную переменную

,

,

,

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

Получим новый базис , свободные переменные .

Выразим новые базисные переменные через свободные. Для этого возьмём исходную систему уравнений, и второе уравнение увеличим вдвое

, вычтем из второго уравнения первое

На основании полученного значения для :

Базисное решение будет иметь вид:

.

Вычислим значение целевой:

Данное значение является минимальным, так как при свободных переменных все коэффициенты положительные.

Вернемся к базису и возьмём за новую базисную переменную

, Þ

, Þ

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

Значение базисных переменных через свободные рассчитаем

Рассчитаем для базиса значение целевой функции (ЦФ=25), это значение не является минимальным.

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

,

Для исходной системы уравнений возможно четыре варианта выбора первого базисного набора переменных. Набор позволит сразу получить допустимые решения.

Рассмотрим некоторые пути в дереве решений данной задачи.

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

ЛЕКЦИЯ 4