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

A. V. Lopatin, R. V. Avakumov

BUCKLING OF ORTHOTROPIC PLATES WITH TWO FREE EDGES LOADED WITH PURE IN-PLANE BENDING MOMENT

Buckling problem of orthotropic plates with two free and two simply-supported edges loaded with pure in-plane bending moment is solved in this paper. Finite difference method is used for problem solving.

Keywords: orthotropic plates, finite difference method.

© Лопатин А. В., Авакумов Р. В., 2009

УДК 519.682

К. В. Сафонов, Д. В. Личаргин

РАЗРАБОТКА ВЕКТОРИЗОВАННОЙ СЕМАНТИЧЕСКОЙ КЛАССИФИКАЦИИ НАД СЛОВАМИ И ПОНЯТИЯМИ ЕСТЕСТВЕННОГО ЯЗЫКА

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

Ключевые слова: генерация естественного языка, семантика естественного языка.

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

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

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

программистами, математиками, семасиологами, философами и многими другими [1; 2; 3; 4], при этом наиболее заметные результаты получены в области генерации грамматически осмысленных фраз и структур естественного языка, осуществляемой программами текстовых редакторов, электронными переводчиками и другими системами. Однако генерация семантически осмысленной речи остается менее разработанной темой, хотя многие системы на основе семантических сетей, речевого граффити, онтологий и других методов показывают неплохую эффективность в диалоге с пользователем на естественном языке. Наиболее популярный метод поддержки диалога с пользователем состоит в привлечении баз данных диалога на естественном языке между людьми, участниками форумов и т. п. Но здесь следует отметить все еще недостаточное развитие представления фраз и текстов естественного языка в виде функций и кластеров функций над многомерной семантической классификацией, притом что этот метод показывает свою высокую эффективность для генерации осмысленной речи [5; 6; 7].

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

На основе четырех элементарных частиц смысла -геносем {система (структура), классификация, локализация в пространстве, восприятие} - можно определять семы естественного языка:

- локализация в пространстве определяется как объект, где подсистемы всех уровней подобны. Так, например, треугольник между звездами галактики подобен любому пропорциональному треугольнику между домами на планете этой звездной системы;

- восприятие определяется как объект, где все подсистемы (воспринимаемое) подобны надсистемам (воспринимающим). Так, например, образы вазы в реальности, в световом потоке, на сетчатке глаза, в мозге и в сознании образуют пирамиду подобия информации;

- структура определяется как объект с разнородными системами и подсистемами. Так, например, структуры кузова и колес автомобиля - разнородны;

- классификация определяется как объект с подобием всех подсистем надсистемам. Так, например, ранетки содержат все свойства яблок, а яблоки - все свойства фруктов.

На основе четырех геносем можно определить 16 классов сем. Приведем пример такого вывода для класса сем «Основные семы»:

- существо - воспринимающее и локализованное в пространстве;

- предмет - невоспринимающее и локализованное в пространстве;

- сознание - воспринимающее и нелокализованное в пространстве;

- абстракция - невоспринимающее и нелокализо-ванное в пространстве,

- идея - воспринимаемое и нелокализующее;

- место - не обязательно воспринимаемое и локализующее;

- информация - воспринимаемое и локализующее;

- абстракция - не обязательно воспринимаемое и нелокализующее.

Выделим следующие основные классы атомов смысла - сем естественного языка:

1. Основные семы: существо, место, информация и др.

2. Семы вероятности: существующий, несуществующий, необходимый, возможный и производные от них.

3. Семы-предикаты: отношение-х, отношение-х-х, отношение-существо-х и др.

4. Семы-аргументы: субъект, объект, реципиент, инструмент и др.

5. Семы-локализации: часть, в, на, около и др.

6. Семы-отношения: включает, включается в, включает и включается в, частично включает, больше чем, меньше чем и др.

7. Семы-числа: цифры от 0 до 15.

8. Семы неопределенного количества: все, многие, некоторые, мало, никто и др.

9-12. Семы, характеризующие стилистику языка: позитивный - негативный, низкий - возвышенный и др.

13-16. Семы, характеризующие описание образов и форм: широкий - узкий, стабильный - нестабильный и др.

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

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

1. Первый уровень классификации понятий соответствует признаку О1 вектора О. Положим О1 = {нечто, отношение, сознание, идея, информация, место, предмет, существо}.

2. Второй уровень классификации понятий представлен признаком О2. Множество О2 значений признака классификации задается множеством правил порождающей грамматики: {£  Её, £  Ех, ё  живого, ё  неживого, х  которого живое, х  которого неживое, Е  часть (О/), Е  внутри (1п), Е  на поверхности (Оп), Е  около (А)}, где понятие около обозначает любое ненулевое расстояние между объектами.

3. Третий уровень классификации понятий определяется признаком О3, где О3 = {Х-у (сущность), Х-Х-у (сущность чего-то), отношение-Х-у (свойство), отноше-ние-Х-Х-у (связь), отношение-существо-Х-у (действие), отношение-существо-Х-Х-у (соединение), от-ношение-существо-существо-х-у (презентация), от-ношение-существо-существо-Х-Х-у (обмен)}, здесь Х - любая из основных сем, определенных на первом уровне классификации, а у - любая последовательность таких сем. Х выделяется как главная по смыслу сема. Знак минус используется в данном случае для обозначения конкатенации. В круглых скобках приведены смысловые пояснения.

4. Множество О4 значений признака О задается множеством правил порождающей грамматики {£  Р • Р2 х

хР3 • Р4 • Р5 • Р6 • Р7 • Р8, Р&количество, Р 1, Р2 g • устойчивость, Р2  1, Р3  g• позитивность, Р3 1, Р4  gспектр, Р4  1, Р5  g• информативность, Р5  1, Р6  gместоположение, Р6  1, Р7  gразмер, Р7  1, Р8  g искусственность, Р8  1}, где g - лингвистическое значение шкалы вида {минимальный, ...,малый,..., средний, ..., большой, ..., максимальный, 1}. Здесь 1 -пустой символ.

5. Множество О5 значений признака О задается множеством правил порождающей грамматики {£  х, х  (хЕх), х  хЕх, х  1 (существующее), х  0 (несуществующее), х  0 (возможное), х   (необходимое), Е  включает, Е  включается В, Е  включает и включается В, Е  частично включает, Е  больше чем, Е  меньше чем, Е  равно, Е  подобно, Е  становится, Е  происходит Из, Е  одновременно С, Е  неодновременно С, Е  имплицирует, Е следует Из, Е соответствует, Е связано С}.

Все последующие уровни классификации получаются путем рекурсивного повторения предложенных пяти уровней классификации. Индекс уровня вычисляется по формуле О1 = О где I принадлежит множеству це-

лых чисел.

Любому понятию или классу понятий естественного языка соответствует определенный вектор классификации. Например, группе слов {брать, давать, покупать, продавать, принимать, дарить, .} соответствует вектор вида [предмет \ \ отношение-существо-существо-Х]; группе слов {магазин, киоск, супермаркет, .} соответствует вектор вида [предмет \ в котором живое \Х ]

+ [предмет \ \ отношение-существо-существо-Х]; слову транспорт соответствует вектор [предмет \ в котором живое \X] + [место \ \ отношение-существо-Х].

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

Принцип генерации осмысленной речи на основе предложенной классификации протестирован на программном продукте «Электронный разговорник».

Теорема о неполноте формальной классификации. Для обоснования предложенной выше классификации введем определение условно-полной классификации и докажем теорему о неполноте семантической классификации.

Определение 1. Назовем систему представления семантики слов как точек векторного пространства условно-полной, если для произвольного элемента ає{а', а", а'", ...}, Ь є{Ь' , Ь", Ь'", ...}, ..., сє{с', с", с'и вектора v[a, Ь, ..., с] справедливо, что для любого понятия А, А ~а’ V а’' V а’' ' V ..., любого понятия В,В~Ь’ V Ь’' V Ь' ' ' V ... и любого понятия С, С~ Є V с" V Є'' V ...,где—знак соответствия.

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

Иными словами, для любой классификации А множества слов {а }, где любое ак~ у[ах, Ьу, ..., с2], смысл слова S(ak) содержит значение 8(ак).Ьп, такое что 0 (^(ак). Ьп~ S(v[аx, Ьу, ., с2])), т. е. 0 ^(ак) є S(v[ax, Ьу, ., с2])), где а = {а1, а2, а3, .}; Ь = {Ь1, Ь2, Ь3, .}; с = {с\ с2, с3, .}.

Приведем пример выхода поля значения за рамки значения, выделенного классификацией, в слове светлый ~ V[действие, ..., от поверхности, ..., интенсивное, .], 0 ^(светлый).лучистый ~ S(v[действие, ..., от поверхности, интенсивное, ...])). Следовательно, эмоциональ-

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

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

Лемма 1. Значение слова может иметь сколь угодно большую мощность.

Д о к а з а т е л ь с т в о. Под мощностью значения слова будем понимать мощность множества ^(ак).Е} для определенного слова ак. Пусть значение слова ак задано определением в виде семантической сети {Ь.(Ь.„Ь ,)}. Слово ак соотносится с объектом реальности, находящимся в системе отношений с внешними объектами, частями этой системы и восприятием этой системы. Поскольку отношение к внешним объектам реальности (расстояние, конкатенация, одновременность) определяют смысл {Ь(Ь.,,

Ь.,' )}, где Ь., ' - внешний объект, а реальность (например, множество точек пространства, количество литературных миров, время, подмножества множеств объектов и точек) принципиально бесконечна, то множество значений слова принципиально ничем не ограничено: {Ь, ,} = ¥ |-

ць , Ьг )}= ¥.

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

Лемма 2. Количество возможных слов с различной семантикой - бесконечно:

{Ь.(Ь.„ Ь.,,)} = ¥ у {Ь.} = ¥ у {Б(ак).Ь} = ¥, ввиду того, что слово ак может быть произвольным.

Д о к а з а т е л ь с т в о. Пусть классификация А задана вектором признаков v[a, Ь, ..., с], где ак~ v[ax, Ьу, ..., с2] и S(ak).Ьj - элемент значения слова ак; а = {а1, а2, а3, ...}, Ь = {Ь1, Ь2, Ь3, .}, с = {с1, с1, с3, .}. Пусть для любого ак справедливо, что V[ах, Ьу, ..., с2] ~ S(ak) и для любой координаты ёвектора v[a, Ь,...,с]: ё = {ё V0 ё} и {ё' V0 ё'} и ... Возьмем значение g = V0g' }П{^' V0g"} и ..., где

g Ф а,gФ Ь, ...,gФ с. В результате объединения векторов классификации v[a, Ь, ., с] и v' [§] получим вектор v'' [а, Ь, ..., с, g].

Очевидно, что в силу леммы 2 найдется такое S(a).Ь|f что S(a) є v'' [а, Ь, ., с, g]. Рассмотрим множество таких элементов значения Е = ^(а).Ьк}, I = {S(ak).Ьj}, I є Е. Эти множества различны, если g - не пусто ввиду того, что g Ф а, g Ф Ь, ..., g Ф с. Пусть У = Е - I.

Если может иметь место такая классификация v[a, Ь, ..., с], что множество У всегда пусто, тогда всегда либо S(g) = 0, либо S(g) є S(a) и S(Ь) и . и S(c).

Зададим слово а, такое что S(a) = S(v [а, Ь, ..., с]). Покажем, что всегда можно подобрать такие g, что У будет не пусто. В силу леммы 2 найдется слово а, такое что S(a) = =S(v[a, Ь, ., с, g]), и такое что его семантика будет отлична от семантики слова аВ противном случае {S(а{)} Ф ¥, где S(at) - любое значение слова-классификации, поскольку лемма 2 будет справедлива также для отдельно взятого множества слов-классификаций. Следоватально, множество У будет не пусто и полной классификации v[a, Ь, ..., с] не может существовать, что и требовалось доказать.

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

Данная теорема согласуется с теоремой Геделя о неполноте формальных систем.

Принципы генерации осмысленного естественного языка. Рассмотрим принципы порождения осмысленной речи на основе предложенной выше векторизованной классификации (см. рисунок).

Над данной семантической классификацией слов и понятий естественного языка формируются структуры разного уровня:

- на первом уровне находятся группы слов языка;

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

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

узнать/... + острый /пикантный /... + вкус /привкус /... + +...»;

- на четвертом уровне слова дробятся на подмножества этих шаблонов: «я/он/. + поел/перекусил/... + на улице/площади/... + Пирогова/Гвоздикова/...» или «я/ он + поел/перекусил/... + утром/вечером/...»;

- на пятом уровне эти фрагменты шаблонов объединяются в семантические шаблоны второго порядка: «Вкус пирога удивил меня утром» (шаблон класса отношение-атрибут _объекта-время), «Ресторан порадовал меня хрустящей корочкой» (шаблон класса отношение-мес-то-часть_объекта).

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

Пример семантических шаблонов генерации осмысленной речи приведен ниже:

The ... этот ... of the ... чего ... is ... является ... ,..-a/y-HTe(cb) the ... этот ... stuff предмет

taste вкус berry ягода sweet сладкий enjoy Hacna^gaTbca good хороший thing вещь

after-taste привкус strawberry клубника sour кислый feel HyBCTBOBaTb great великолепный object объект

smack привкус raspberry малина salty соленый savor CMaKOBaTb excellent отличный gem прелесть

flavor вкус gooseberry крыжовник bitter горький discuss Hacna^gaTbca wonderful чудесный must важная вещь

currant смородина pungent острый identify y3HaTb superior превосходный trifle мелочь

bilberry черника weak слабый notice 3aMeTHTb splendid великолепный process процесс

blackberry черная смородина strong сильный learn y3HaBaTb magnificent сказочный time время

cranberry клюква experience HcnbiTaTb surprising удивительный moment момент

sweet cherry черешня lovely красивый

cherry вишня worthy стоящий

grape виноград useful полезный

raisin изюм funny забавный

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

Библиографический список

1. Агамджанова, В. И. Контекстуальная избыточность лексического значения слова / В. И. Агамджанова. М. : Высш. шк., 1977.

Дерево семантической классификации

Узлы дерева - понятия в классификации

Функции истинности на подмножествах классификации

Таблицы генерации семантически осмысленной речи как подмножества классификации

Фразы естественного языка как функции на дереве семантической классификации

2. Апресян, Ю. Д. Идеи и методы современной структурной лингвистики / Ю. Д. Апресян. М. : Наука, 1966.

3. Вердиева, З. Н. Семантические поля в современном английском языке / З. Н. Вердиева. М. : Высш. шк., 1986.

4. Никитин, М. В. Лексическое значение слова / М. В. Никитин. М. : Высш. шк., 1983.

5. Личаргин, Д. В. Операции над семами слов естественного языка в машинном переводе / Д. В. Личаргин // Тр. конф. молодых ученых / Ин-т вычисл. моделирования Сиб. отд-ния Рос. акад. наук. Красноярск, 2003. С. 23-31.

6. Личаргин, Д. В. Устранение семантического шума как средство адекватного перевода / Д. В. Личаргин // Вопросы теории и практики перевода : тр. Всерос. конф. Пенза : Приволж. дом знаний, 2003. С. 90-92.

7. Личаргин, Д. В. Порождение фраз естественного языка в рамках задачи построения естественно-языкового интерфейса с программным обеспечением / Д. В. Личаргин // Проблемы информации региона (ПИР-2003) : материалы Восьмой Всерос. конф. / Краснояр. гос. техн. ун-т. Красноярск, 2003. Т. 2. С. 152-156.

K. V Safonov, D. V. Lichargin

ELABORATION OF A VECTOR BASED SEMANTIC CLASSIFICATION OVER THE WORDS AND NOTIONS OF THE NATURAL LANGUAGE

The problem of vector-based semantic classification over the words and notions of the natural language is discussed. A set of generative grammar rules for the generation of the semantic classification vector is offered. The examples of the classification application are given. A theorem ofoptionalformal classification incompleteness is presented. The principles of assigning of the meaning-bearing functions over the classification word groups are analyzed.

Keywords: natural language generation, natural language semantics.

© Сафонов К. В., Личаргин Д. В., 2009

УДК 519.688

П. В. Галушин, Е. С. Семенкин АСИМПТОТИЧЕСКИЙ ВЕРОЯТНОСТНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ*

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

Ключевые слова: вероятностный генетический алгоритм, мутация, селекция.

Вероятностный генетический алгоритм (ВГА) является попыткой создания алгоритма, имеющего схему, похожую на схему традиционного генетического алгоритма (ГА), и сохраняющего основные свойства генетических операторов, но сформулированного в терминах теории псевдобулевой оптимизации [1]. В вероятностном генетическом алгоритме, в отличие от традиционного ГА, явным образом вычисляются компоненты вектора вероятностей и отсутствует оператор скрещивания (вместо него используется оператор случайного выбора решения в соответствии с построенным распределением), однако сохранены генетические операторы мутации и селекции.

Целью проведенного авторами исследования была разработка модификации вероятностного генетического

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

Асимптотическая мутация. В ВГА мутация производится так же, как и в традиционном ГА, - путем случайного инвертирования генов хромосомы с заданной вероятностью (как правило, эта вероятность выбирается очень малой). Так как гены мутируют независимо, то мы можем ограничиться рассмотрением одного гена. Установленные ниже соотношения будут иметь место для каждого гена хромосомы.

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

* Работа выполнена при финансовой поддержке АВЦП «Развитие научного потенциала высшей школы» (НИР 2.1.1/2710) и Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» (НИР НК-136П/3).