science-review.ru
Введение. Опыт разработок в области ИИ, связанных с построением логических моделей различных предметных областей, приводит к однозначному выводу о специфичности их построения [1, 2, 3]. Поясним, что имеется в виду. Всякая сложная информационная система должна обладать адекватным теоретическим базисом, для обоснования приемов переработки информации. Так в качестве базиса информационных систем объектов управления используются конкретные теории: экономические, математические, физические и т.п., а базисом для разработки баз данных выступает реляционная алгебра. С другой стороны, построение логических моделей, связанных с формированием понятий (классов объектов) базируется на представлениях о формализме, с одной стороны, включающем логико-математические преобразования, а с другой, - основывающемся на результатах теоретического программирования. В результате получаем то, что называется логическими моделями.
Если логическая модель сложная и связана с порождением новых объектов в рамках определенной понятийной системы, то следует представлять и механизм, с помощью которого порождаются объекты - содержание этих понятий. Если такой механизм, по тем или иным причинам, отсутствует, например, из-за недостаточной проработки предметной области, то это выливается в неуправляемый перебор. Тогда модель громоздка и трудна для использования. Типичным примером являются модели, связанные с задачами на графах. Если не ограничить перебор условиями или стратегиями, то их решение весьма быстро исчерпывают все доступные ресурсы, т.к. основным приемом становится полный перебор.
С другой стороны, если в модели предполагается построение объектов - представителей понятий предметной области, то их не управляемое порождение, в большинстве случаев не приводит к решению задачи. Рассмотрим пример, который иллюстрирует, что получение непосредственных следствий недостаточно, и требуется совершить еще несколько логических преобразований для получения общей картины. Пусть отрезок AB пересекают два отрезка CD и EF, в точках соответственно G и H. Очевидно, что в этом случае появляются восемь углов, центральными вершинами которых являются G и H, а концевыми A, B, C, D, E, F. Однако, появление точек G и H на отрезке AB приводят к появлению пяти новых отрезков AF, AG, FG, BF, BG. Что влечет появление четырех новых углов: BFG, CFG, DGF, EGF. Следовательно, рассмотрение только непосредственных следствий из пересечения отрезков AB, CD и EF в виде появления двух точек G и H и первых восьми углов недостаточно. Надо вывести еще одно следствие в виде новых отрезков от пересечения, и новых четырех углов.
Подобное явление наводит на мысль о необходимости создания механизма управления порождением объектов - представителей понятий в логических моделях. Человек, в своих рассуждениях, управляет построением новых объектов, исходя из содержательных представлений о цели сформулированной задачи. Программа, решающая интеллектуальную задачу, не основывается на содержательных представлениях, поэтому в нее необходимо заложить знания, извлеченные из предметной области. Только тогда ее решения будут обладать полнотой. В противном случае возможна потеря решений из-за отсутствия в логических построениях некоторых объектов, присутствующих в предметной области.
Исходя из этого, мы рассмотрим основные приемы формирования понятий и предложим механизм, т.н. Супервизор, который позволит управлять этим процессом. В результате будут порождены все необходимые для решения объекты логической модели. Все рассуждения будут проиллюстрированы на примерах, взятых из разработанной автором системы «Живая математика», которая создана для поддержки решения математических задач школьного курса. Аналогичные идеи можно обнаружить в [4, 5].
1. Понятия. Так как основная цель логической модели предметной области состоит в моделировании преобразований над объектами, то, естественно, что такая модель опирается на конкретный понятийный базис. В каждой моделируемой предметной области используется множество C понятий, частично-упорядоченное отношением предок-потомок. Этот частичный порядок допускает циклы, когда понятие определяется через само себя, используя линейный порядок некоторого параметра. Такое определение предполагает использование в качестве понятия-предка с меньшим значением этого параметра. Это т.н. рекурсивное определение.
Каждое используемое понятие предметной области в модели представлено совокупностью объектов, являющихся представителями этого понятия. Так понятие точка имеет конкретные реализации в виде точек на чертеже с конкретными именами и координатами. То же относится к понятиям отрезок, треугольник, многочлен, квадратный трехчлен и т.д. Отрезок есть пара точек, обладающая дополнительными параметрами: длина, угол наклона и свободный член уравнения. В объектно-ориентированной программной реализации каждое понятие представляет собой класс с соответствующим содержанием. Тогда каждый представитель этого класса – конкретный представитель понятия. Это может быть фигура чертежа, алгебраическое или тригонометрическое выражение, график конкретной функции и т.п.
2. Операции над понятиями, определяющие свойства понятий (R: C® P), которые суть значения этих операций. Для их определения вводится множество функций с областью определения C. Например, длина отрезка, площадь треугольника, медиана треугольника, общий множитель многочлена, множество множителей полинома, конкретные преобразования тригонометрических объектов и пр. Если исследуется значение этих функций, то говорим о конкретных свойствах объектов, ими определяемых. Например, длина отрезка равна 5, синус угла равен 0,3 и т.п. Эти свойства используются для определения других понятий. Так медиана из угла A – это отрезок, проведенный из вершины A к противоположной стороне, который делит последнюю пополам.
3. Средства конструирования новых понятий (F: C ® C) используются для формирования новых понятий, но сами не принадлежат совокупности базисных понятий логической модели. Например, отрезок есть пара точек, треугольник – три попарно касающихся и не коллинеарных отрезка, многочлен – совокупность одночленов, синус угла – отношение длин определенных отрезков и пр. При реализации модели эти средства должны быть вынесены в отдельную программную часть, определенную над совокупностью базисных понятий. Таким образом, для преобразований совокупности F словарь C понятий выступает в роли области определения. Отметим, что без управления процессом образования новых понятий, этот процесс становится малоинформативным. Поэтому управление порождением новых объектов должно быть создано в полном согласовании с частичным порядком над множеством C, и требованием полноты – т.е. возможности порождения всех объектов понятий, которые следуют из условия задачи. Тем самым, определяется частичный порядок на понятиях, задаваемый отношением предок-потомок.
Необходимость предварительной проработки всего множества понятий с целью получения непротиворечивого частично-упорядоченного множества C следует из того, что при объектно-ориентированном программировании каждое понятие определяет класс объектов, и наличие противоречия в такой структуре недопустимо. Это приведет в ошибках модели. Исходя из этого, все понятия логической модели должны быть проанализированы и соответствующим образом упорядочены отношением предок-потомок.
4. Логическая система (L) доказательств свойств объектов представляет интерес, т.к. включает логические средства как прямого вывода, так и обратного. Поясним, что имеется в виду в данном случае. Например, доказательство равенства отрезка конкретному значению или равенства площадей треугольников требует логического построения из совокупности аксиом и известных теорем геометрии. Каждую теорему предметной области можно представить в виде логического следования: из набора посылок следует заключение. Тогда применение теоремы представляет собой проверку посылок и, в случае их истинности, присоединение к известным фактам заключения. Тем самым расширяется совокупность данных, которая выводится из исходной формулировки. То же относится к алгебраическим и тригонометрическим преобразованиям. Однако, в последних случаях используются правила переписывания, т.е. замены равного равным. Таким образом, прямой вывод – это движение от условия задачи к его заключению.
На этом основано построение т.н. неподвижной точки – прием построения модели, когда на каждом шаге выводятся новые данные, присоединяемые к уже известным. Рано или поздно происходит насыщение, т.е. выводимые данные уже не являются новыми и процесс поиска можно останавливать. Это состояние модели и называется неподвижной точкой. Именно оно описывает искомое состояние логической модели, которое следует из исходных данных.
Человек, как правило, не может использовать такой прием т.к. возникает большой объем данных, из которых к искомому заключению относится лишь небольшая часть. Компьютер может эффективно оперировать большими массивами информации, и поэтому для него метод неподвижной точки вполне приемлем. Более того, в большинстве случаев, это единственный способ автоматически найти решение.
Обратное движение наиболее наглядно видно на примере задач, в которых требуется совершить ограниченный перебор. Тогда решение задачи сводится к поиску и обоснованию гипотез, из которых выводится требуемое заключение. Например, в задаче: подобрать цифры a, b, c, чтобы выполнялось равенство abc = a! + b! + c! однозначно вывести эти значения из условия невозможно. Требуется выдвижение и проверка ряда гипотез, касающихся значений чисел a, b, c. К такому же классу решений можно отнести известные логические задачи, числовые ребусы и комбинаторные задачи.
Отметим, что логическая система не вводит новых объектов, а оперирует с ними для доказательства конкретных соотношений, сформулированных в виде логических выражений с использованием трех предыдущих словарей, а также логических правил. Прямой логический вывод может быть представлен: умозаключениями, формирующими древесную конструкцию построения заключения из посылок, линейной последовательностью преобразований при использовании переписывания или комбинацией этих средств. Обратный логический вывод, как правило, образует древесную конструкцию, причем от условия задачи мы движемся к гипотезам, из которых эта задача логически следует, до тех пор, пока не будут обнаружено полное множество утверждений, из которых следует заключение исходной задачи.
5. Необходимость Супевизора. Логическая модель строится по исследуемой предметной области, в которой выделяются определенные понятия, закладываемые в модель. При программированию, каждому понятию соответствует класс, члены которого суть представители соответствующего понятия. Если порядок на множестве C не имеет циклов, то порождение объектов модели простое: из базисных понятий переходим далее в соответствии с порядком. В таком случае, в первом приближении, можно считать, что нет необходимости в особом инструменте для порождения объектов. Но в общем случае частичный порядок на множестве C имеет циклы. Например, рассмотрим критерий равенства треугольников: равенство пары отрезков и прилегающих углов приводит к равенству треугольников, из которого следует равенство двух пар других соответствующих отрезков, являющихся сторонами треугольников. Здесь отношение на объектах приводит к порождению одноименного отношения на других однотипных объектах. Другой пример – это транзитивное замыкание отношения равенства или параллельности отрезков.
В общем случае, порождение некоторого объекта предметной области вызывает порождения других объектов, если соответствующие понятия находятся в отношении предок- потомок. И тут возникает естественный вопрос: на сколько необходимо разделять структуру описания понятий предметной области в виде классов от процедуры последовательного порождения объектов – представителей понятий. Как отмечалось, если частично-упорядоченное множество понятий предметной области простое, то выделять отдельно процедуру порождения не рационально. Она вполне может быть реализована, используя средства объектно-ориентированного программирования. Однако, если структура понятий предметной области достаточно сложная, то приходится выделять отдельную часть программы (т.н. Супервизор), чтобы реализовать последовательность порождения объектов с учетом частичного порядка на множестве понятий.
6. Конструкция Супервизора. Супервизором назовем ту часть программы построения логической модели, которая определяет последовательность построения объектов (представителей понятий) в зависимости от формулировки задачи и описания предметной области. Каждое понятие множества C определяет тип объектов, которые суть представители этого понятия. Если o есть объект, то type(o) есть то понятие, представителем которого является объект o. Так как все понятия предметной области частично упорядочены, то в супервизоре имеется таблица TC, представляющая этот порядок: каждая ее строка (ti, tj) представляет пару понятий, упорядоченных так: ti £ tj. Из этого следует, что когда порождается объект o, то Супервизор запускает порождение всех объектов типа tj, для которых выполняется отношение type(o) £ tj.
Однако, чтобы запустить процесс порождения объектов понятий-потомков, Супервизор должен получить сигнал, который формируется при порождении объектов - представителей понятий-предков. Эти сигналы формируются модулями, осуществляющими собственное порождение объектов – представителей понятий. Рассмотрим для примера работу произвольного модуля Mc, порождающего объекты, принадлежащие понятию c Î C. При порождении объекта o, который есть представитель понятия c, вырабатывается сигнал hc, однозначно определяющий порожденный объект o. После выполнения модуля Mc управление передается Супервизору, который получает на вход сигнал hc. Т.к. сигнал hc однозначно определяет тип type(o) объекта o, последний, используя таблицу TC, однозначно определяет все понятия, являющиеся потомками понятия type(o). Тем самым, решен вопрос о запуске соответствующих модулей для порождения новых объектов – представителей понятий.
Однако, если Супервизор будет реагировать на каждый вновь порожденный объект, то ресурсы, затрачиваемые на управление этим процессом, будут излишне большими, т.к. объектов много. Для исключения этого предлагается ввести дополнительный элемент, который есть надстройка над частично-упорядоченным множеством C и позволяет описать семантику модели в более содержательных терминах. Представим частично-упорядоченное множество C в виде ор-графа GC, узлы которого соответствуют понятиям из C, а дуги – отношению порядка £. Введет следующее определение.
Пусть D Í GC есть связный подграф, содержащий множество ND узлов и ED дуг. При этом InD есть множество дуг дополнения GC ¤ D, ведущих в D, и OutD – выходящих из D. Начала дуг множества InD определяют те понятия, которые суть предки понятий, соответствующих узлам подграфа D. Назовем их входными для D и полагаем, что эти понятия представлены объектами – их примерами. Последние пусть образуют множество O(InD). Аналогично, начала дуг из OutD определяют множество понятий, которые суть потомки понятий множества, определяемых множеством InD. Из вида частичного порядка и операционной семантики, определенной им, следует, что варьирование множества O(InD) объектов влечет изменение объектов O(OutD), определяемых началами дуг множества OutD. Введем такое определение.
Назовем неподвижной точкой подграфа D при фиксированном множестве O(InD) такую совокупность O(OutD) объектов, которая не может быть расширена при введенной операционной семантике, если не менять множество O(InD). В данном случае ничего не говорится о конечности или бесконечности множеств O(InD) и O(OutD), интерес представляет только не расширяемость множества O(OutD) при фиксированном O(InD). В качестве подграфа D может выступать и весь граф GC, который обладает пустым множеством In, а множество Out определяется условиями предметной области.
Справедлива
Теорема 1. Неподвижная точка, определяемая графом GC, влечет, что каждый подграф D Í GC обладает неподвижной точкой.
С другой стороны, справедлива
Теорема 2. Если каждый подграф D Í GC обладает неподвижной точкой, то и граф GC обладает неподвижной точкой.
Рассмотрим практические аспекты использования понятия неподвижной точки. Как уже было сказано, если управление поиском решения осуществляется в соответствии со стратегией, когда каждый объект по мере его порождения необходимо проверять на возможность порождения объектов-потомков, то это требует много ресурсов. Поэтому более рациональной представляется, когда выделяются фрагменты графа GC, обладающие содержательной семантикой, и для каждого из них строится неподвижная точка, определяемая входными понятиями. Например, равенство углов в геометрической задаче может быть получено в результате транзитивного замыкания, выполнения условий параллельности, коллинеарности или перпендикулярности соответствующих сторон и т.д. Тем самым, понятие равенства углов, которое вполне содержательное, выделяет фрагмент графа GC, для которого строится неподвижная точка. И ее построение может осуществляться одним модулем программы поиска решения.
Следовательно, функционирование Супервизора уже не сводится к попытке построения объекта-потомка каждый раз при порождении одного объекта-предка. Супервизор отвечает за порождением частичных неподвижных точек, определяемых содержательно значимыми фрагментами модели понятий предметной области.
7. Моделирование временных зависимостей. Но рассмотрим еще один аспект построения логических моделей, который связан с порядком порождения объектов-представителей понятий в соответствии с частичным порядком множества С. Нас интересует сложный частичный порядок, в котором имеются циклы, т.к. простая иерархия не вызывает особых трудностей при порождении объектов. Если оба понятия c0, c1 связаны отношением предок-потомок, т.е. в частичном порядке над множеством C встречается цикл, содержащий оба эти понятия, то в программной реализации модели объекты понятия c1 будут порождаться несколько раз по мере появления новых объектов-представителей понятия c0. Если не управлять этим процессом, то возникает ситуация, когда один и тот же объект-представитель понятия c1 будет порождаться несколько раз – по числу обращений к соответствующему модулю. Это не приводит к появлению новой информации в модели, но очень ресурсозатратно, т.к. часть объектов порождается несколько раз. Чтобы избежать такого нерационального использования ресурсов, в логическую модель вводится параметр абсолютное время, представляющее собой значение одной глобальной переменной, значение которой монотонно увеличивается независимо от выполнения программы построения модели. Тем самым абсолютное время моделирует обычное время. Его назначение состоит в фиксации времени появления объектов мидели и времени выполнения модулей, которые эти объекты порождают. Поясним это примером.
Если объект o порождается модулем M при наличии объектов o1, o2, …, om, то естественно допустить, что, хотя бы один из этих объектов o1, o2, …, om должен появиться после последнего применения модуля M, т.к. в противном случае произойдет повторное порождение объекта o. Последнее приводит к нерациональному использованию вычислительных ресурсов. Поэтому введение времени появления каждого объекта модели и времени срабатывания модулей для управления процессом порождения объектов, оправдано. Технически это реализуется сравнительно просто, что и позволяет достаточно эффективно управлять этим процессом.
В результате получаем, что в случае конечных моделей неподвижные точки будут получены практически при любом способе запуске модулей порождения объектов модели за конечное число шагов. В случае бесконечных моделей говорить о получении неподвижной точки не приходится в принципе, там приходится реализовывать более сложные стратегии построения модели.