авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 3 | 4 || 6 |

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В. ЛОМОНОСОВА Факультет вычислительной математики и кибернетики ...»

-- [ Страница 5 ] --

Итак, пусть выполняются описанные ограничения, нало женные на вид объектов контекста. Применение принципа до минирования по характерности к таблице кандидатов в фор мальные понятия глобального контекста, полученной методом альтернативного конструирования [4], заключается в возмож Сборник статей молодых ученых факультета ВМК МГУ, № 10, Применение шкал характерности признаков в АФП Таблица 2. Формальный контекст общего вида лает мяукает мычит собака корова кошка рыба Таблица 3. Формальный контекст, удовлетворяющий условию лает мяукает мычит безмолвствует собака корова кошка рыба ности исключения ложных понятий, доминируемых по харак терности теми понятиями, которые, как установлено, не явля ются формальными понятиями глобального контекста. Прин цип доминирования также позволяет оптимизировать выбор следующей пары локальных контекстов для принципа альтер нативного конструирования: на каждой следующей итерации следует выбирать локальный контекст, признаки которого име ют наименьшую характерность. Такой выбор позволяет доби ваться максимального сокращения псевдопонятий из списка кандидатов в формальные понятия глобального контекста.

Проиллюстрируем сказанное на примере:

Пример 7. Для простоты рассуждений в качестве приме ра будем рассматривать глобальный контекст, удовлетворя ющий условию 1. Будем также считать, что все объекты контекста принадлежат одному классу, то есть имеют од Сборник статей молодых ученых факультета ВМК МГУ, № 10, 244 Д. Е. Стельмашенко ни и те же шкалы характерности. Пусть неизвестный гло бальный контекст задает все возможные наборы успешных оценок, позволяющих студенту поступить в ВУЗ. Известны шкалы характерности признаков объектов предметной обла сти. Они имеют следующий вид:

Пять Четыре Три АВС Будем восстанавливать глобальный контекст методом альтернативного конструирования. Пусть два локальных контекста заданы путем перечисления их объектов. Призна ки этих контекстов соответствуют оценкам абитуриентов на экзаменах:

D1, N1 =((пять, А), (пять, В), (три, А), (пять, С), (четыре, А), (четыре, В)) D2, N2 = (5, 4, 3) В силу выполнения условия 1, можно работать не с фор мальными понятиями этих контекстов, а напрямую с их объектами, и результатом работы метода альтернативного конструирования в таком случае будет список объектов гло бального контекста. Итак, согласно принципу альтернатив ного конструирования, построим множество R1, элемента ми которого являются все возможные варианты объединения объектов контекстов D1, N1 и D2, N2 :

R1 =(Пять, А, 5), (Четыре, А, 5), (Три, А, 5), (Пять, А, 4), (Четыре, А, 4), (Три, А, 4), (Пять, В, 5), (Четыре, В, 5), (Три, В, 5), (Пять, А, 3), (Четыре, А, 3), (Три, А, 3), (Пять, С, 5), (Четыре, С, 5), (Три, С, 5), (Пять, В, 4), (Четыре, В, 4), (Три, В, 4).

Рассмотрим теперь вторую пару известных локальных контекстов. Выбирать ее надо таким образом, чтобы при знаки одного из локальных контекстов имели наименьшую ха рактерность. В данном случае все признаки имеют одинако вое распределение характерностей, а потому выбор локальных Сборник статей молодых ученых факультета ВМК МГУ, № 10, Применение шкал характерности признаков в АФП контекстов не играет существенной роли. В качестве второй пары локальных контекстов возьмем контексты D3, N3 =(пять, четыре, три) D4, N4 = ((5, A), (4, A), (5, B), (3, A), (5, C), (4, B) В таком случае множество R2 имеет следующий вид:

R2 =((Пять, А, 5), (Пять, В, 5), (Три, А, 5), (Пять, С, 5), (Четыре, А, 5), (Четыре, В, 5), (Пять, А, 4), (Пять, В, 4), (Три, А, 4), (Пять, С, 4), (Четыре, А, 4), (Четыре, В, 4), (Пять, А, 3), (Пять, В, 3), (Три, А, 3), (Пять, С, 3), (Четыре, А, 3), (Четыре, В, 3)) Согласно принципу альтернативного конструирования, элементы, не входящие в множество R1 R2 являются псев допонятиями и подлежат исключению. Одним из таких эле ментов является псевдопонятие (Пять, С, 4). Однако, в си лу принципа доминирования по характерности, также мож но исключить и псевдопонятие (Пять, С, 3), поскольку все его признаки менее характерны признаков уже исключенно го псевдопонятия. Таким образом, принцип доминирования по характерности позволяет на каждом шаге алгоритма альтернативного конструирования исключать большее число псевдопонятий.

6 Автоматизированное построение шкал характерности признаков В принципе доминирования по характерности [1, 2] предпо лагалось, что шкалы характерности это заранее известные данные, полученные от эксперта. Однако, построение шкал ха рактерности это сложная задача, решение которой не всегда очевидно. Более того, не всегда эксперту удается заметить су ществующие в предметной области закономерности распреде ления признаков между классами объектов. Автоматизирован ное построение этих шкал решает данную проблему и позволя ет выявить все существующие закономерности распределения Сборник статей молодых ученых факультета ВМК МГУ, № 10, 246 Д. Е. Стельмашенко признаков по объектам различных классов.

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

Условие 2. Глобальный контекст должен быть полным.

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

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

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

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

Обозначим множество достоверных формальных понятий гло бального контекста как R+, а множество всех исключенных Сборник статей молодых ученых факультета ВМК МГУ, № 10, Применение шкал характерности признаков в АФП псевдопонятий как R.

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

На втором шаге алгоритма из множества R исключаются элементы, которые полностью содержатся в других элементах множества R и длина1 которых не превышает минимальной длины объектов глобального контекста. В случае, когда объ екты контекста удовлетворяют условию 1, на этом шаге алго ритма в множестве R остаются только псевдопонятия макси мальной длины, равной длине объектов контекста.

На третьем шаге алгоритма из множества R+ удаляются все элементы, входящие в другие элементы этого множества.

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

На каждой итерации оставшиеся в множествах R+ и R элементы сравниваются друг с другом. В процессе этого срав Под длиной элемента или объекта в данном случае понимается коли чество входящих в него признаков.

Сборник статей молодых ученых факультета ВМК МГУ, № 10, 248 Д. Е. Стельмашенко нения находятся те элементы, которые отличаются друг от дру га на один признак и принадлежат при этом к разным классам, то есть один к множеству R+, а другой к множеству R. Те признаки, в которых различаются эти два элемента, наносятся на шкалу характерности по следующему правилу: более харак терным считается признак, присущий элементу из множества R+, а менее характерным элементу из R.

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

В первом случае неоднозначность разрешается путем пере бора всех возможных вариантов распределения признаков по группам. Как правило, распределение признаков по группам известно, однако, если оно неочевидно, то возможных вари антов таких распределений для контекстов больших размеров не так уж и много в силу условия несовместимости признаков одной группы внутри объекта. Существует ряд известных ал горитмов определения возможности совместимости признаков внутри одной группы [8, 9].

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

Сборник статей молодых ученых факультета ВМК МГУ, № 10, Применение шкал характерности признаков в АФП В том случае, если по окончании работы алгоритма для всех уровней решетки формальных понятий шкалы так и не будут найдены, считается, что для данного глобального кон текста шкал характерности признаков не существует.

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

Это означает, что какие-то шкалы могут быть общими для всех объектов контекста, а другие соответствовать какому-то конкретному классу объектов.

Для внесения ясности в рассуждения, проиллюстрируем ра боту описанного метода на примере:

Пример 8. Находясь в условиях примера 7, будем полагать, что для объектов глобального контекста выполняется усло вие 1, а также будем считать, что разбиение признаков кон текста по группам известно. Пусть глобальный контекст был восстановлен при помощи методов альтернативного кон струирования и тестирования и пусть множество его фор мальных понятий имеет следующий вид:

D C = R+ = ((В), (Пять), (5), (4), (Четыре), (А), (В, Пять), (А, Четыре), (В, 5), (А, 4), (Пять, 5), (А, 5), (Пять, 4) (А, Пять) (Четыре, 5) (В, Пять, 5) (А, Четыре, 4) (В, Пять, 4) (А, Четыре, 5) (С, Пять, 5) (А, Три, 5) (В, Четы ре, 5) (А, Пять, 3) (А, Пять, 5) (А, Пять, 4).

Множество R, полученное в ходе восстановления гло бального контекста, также известно. Оно имеет следующий вид:

R = (A, 3), (C, 5), (B, 4), (Четыре, В), (Четыре, 4), (Три, 5), (Пять, С), (С), (3), (Три), (Три, А, 4), (С, Пять, 4), (С, 5, Четыре), (3, А, Четыре), (В, 5, Три), (В, пять, 3), (Четыре, В, 4), (Три, А, 3), (3, Пять, С), (С, 5, Три), (Пять, С, 4), (5, С, Четыре), (5, Три, В), (А, Три, 4), (четыре, В, 3).

Начнем построение шкал характерности с шага 1 описан ного алгоритма, то есть из множества R удалим все эле Сборник статей молодых ученых факультета ВМК МГУ, № 10, 250 Д. Е. Стельмашенко менты, содержащиеся хотя бы в одном элементе множества R+. Таким образом множество R приобретет следующий вид:

R = (Три, А, 4), (С, Пять, 4), (С, 5, Четыре), (3, А, Четыре), (В, 5, Три), (В, пять, 3), (Четыре, В, 4), (Три, А, 3), (3, Пять, С), (С, 5, Три), (Пять, С, 4), (5, С, Четыре), (5, Три, В), (А, Три, 4), (четыре, В, 3).

Далее, согласно второму шагу алгоритма, из множества R следует удалить те элементы, которые содержатся в других элементах множества R (в силу того, что для гло бального контекста выполнено условие 1). В нашем примере таких элементов не оказалось, поэтому переходим к третье му шагу алгоритма.

На третьем шаге делаем то же самое с множеством R+.

Получаем:

R+ =(В, Пять, 5) (А, Четыре, 4) (В, Пять, 4) (А, Четы ре, 5) (С, Пять, 5) (А, Три, 5) (В, Четыре, 5) (А, Пять, 3) (А, Пять, 5) (А, Пять, 4).

Теперь, согласно четвертому шагу алгоритма, сравниваем попарно все элементы множеств R+ и R, отличающиеся на один признак, и составляем соответствующие шкалы харак терности. Например, сравним объект (Три, А, 4) класса R с объектом (Четыре, А, 4) класса R+ и построим шкалу ха рактерности, согласно которой признак Три является менее характерным чем признак Четыре. Сравним теперь объект (Четыре, В, 4) класса R и объект (Пять, В, 4) класса R+.

Получаем, что признак Пять более характерен чем признак Четыре. Таким образом, согласно принципу транзитивности, получаем шкалу характерности следующего вида: 5 4 3.

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

Сборник статей молодых ученых факультета ВМК МГУ, № 10, Применение шкал характерности признаков в АФП 7 Заключение В настоящей работе была рассмотрена возможность приме нения принципа доминирования по характерности в задаче сов мещения формальных контекстов. Показано, что данный прин цип позволяет ускорить процесс исключения псевдопонятий и тем самым получить список формальных понятий глобально го контекста быстрее. Предложен метод автоматизированного построения шкал характерности признаков, который позволяет не привлекать экспертов и находить не всегда очевидные зако номерности распределения признаков по классам объектов.

Список литературы [1] Ларичев О. И., Мечитов А. И., Мошкович Е. М., Фу ремс Е. М., Выявление экспертных знаний. // М.: Наука 1989.

[2] Ларичев О. И. Теория и методы принятия решений, а так же Хроника событий в Волшебных Странах: Учебник. // М.: Логос 2000.

[3] Ganter B., Wille R. Formal Concept Analysis: Mathematical Foundations. // Springer 1999.

[4] Соловьев С. Ю., Стельмашенко Д. Е. Подходы к исследо ванию формальных контекстов. // Информационные про цессы 2011 том 11, №2 С. 277–290.

[5] Стельмашенко Д. Е. Свойства формальных контекстов.

// Информационные процессы 2011 том 1, № С. 86–89.

[6] Valtchev P., Missaoui R., Lebrun P. A partition-based approach towards constructing Galois (concept) lattices. // Discrete Mathematics 2002 vol. 256, no.3. P. 801– 829.

Сборник статей молодых ученых факультета ВМК МГУ, № 10, 252 Д. Е. Стельмашенко [7] Стельмашенко Д. Е. Алгоритм восстановления глобально го контекста. // Сборник статей молодых ученых факуль тета ВМК МГУ 2012 выпуск 9, C.191–209.

[8] Cole R., Eklund P. Browsing Semi-structured Web Texts Using Formal Concept Analysis. // ICCS 2001 P. 319–332.

[9] Scheirer W., Kumar N., Ricanek K., Boult T., Belhumeur P.

Fusing with Context: a Bayesian Approach to Combining Descriptive Attributes. // Proceedings of the IEEE International Joint Conference on Biometrics (IJCB) 2011.

Сборник статей молодых ученых факультета ВМК МГУ, № 10, Сборник статей молодых ученых факультета ВМК МГУ, № 10, 2013 УДК 004.832. Об одном способе организации библиотеки моделей программ © 2013 г. Н. Н. Фастовец nnf-cmc@cs.msu.su Кафедра алгоритмических языков 1 Введение В настоящее время развитие автоматизации во многих об ластях человеческой деятельности, включая научные исследо вания, требует увеличения затрат на разработку программно го обеспечения [1]. Помимо этого, с одной стороны возрастают требования к надежности используемых программ, а с другой возникает потребность в использовании языков более высоко го уровня, удобных для использования людьми, занятыми в разработке узко специализированного (в первую очередь на учного) программного обеспечения, но не являющимися про фессиональными программистами [2]. Возможным ответом на данные требования может быть развитие средств автоматиче ского синтеза программ, то есть разработка методов автомати ческого построения исполняемой программы по заданной фор мальной спецификации, то есть формальному описанию тре бований к синтезируемой программе. Существует ряд методов решения данной задачи [1], однако, в силу имеющихся на дан ном этапе их развития ограничений, они не получили широко го распространения в практической разработке программного обеспечения.

Возможным направлением дальнейших исследований в об ласти автоматического синтеза является применение рассуж дений на основе прецедентов [3,4]: решение поставленной зада чи строится путем адаптации известного решения другой за дачи, по некоторому отношению похожей на поставленную.

254 Н. Н. Фастовец Использование данного подхода в автоматическом синтезе поз воляет избежать необходимости построения новой программы целиком, ограничившись только модификацией уже существу ющей. Однако данный подход требует определить метод вы бора из библиотеки известных решений такой программы, для которой потребуется наименьшее количество подобных изме нений. Помимо этого, требуется также найти способ органи зации библиотеки программ, позволяющий повысить эффек тивность поиска подобной программы. Существует ряд мето дов [5,6], рассматривающих вопрос автоматической коррекции программ, то есть приведения заданной программы в соот ветствие с указанной спецификацией. Такие методы потенци ально могут быть использованы в качестве средств адаптации выбранного решения, однако остается открытым вопрос осу ществления поиска в библиотеке и выбора исходной програм мы.

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

В данной работе мы рассматриваем возможный метод оцен ки неполного соответствия выбранной программы заданной формальной спецификации, а также связанный с данным ме тодом способ организации библиотеки программ, позволяющий на каждом шаге поиска наиболее подходящей программы со кращать пространство поиска за счет использования иерар хии прецедентов, основанной на выполнении логического сле дования между элементами прецедентов. Мы будем ориенти Сборник статей молодых ученых факультета ВМК МГУ, № 10, Организация библиотеки моделей программ роваться на программы, реализующие алгоритмы, вычисляю щие некоторое возвращаемое значение от своих входных пара метров. Поскольку такие вычисления как правило оформля ются как подпрограммы (функции или методы) в коде основ ной программы, то рассматривать мы будем именно такие под программы. В рамках данной работы мы будем рассматривать подмножество программ языка Паскаль (Pascal) [8]. Мы будем рассматривать подпрограммы (функции), написанные на язы ке Паскаль, принимающие в качестве аргументов параметры, передаваемые по значению, и возвращающие вычисленное зна чение через присваивание оного переменной, одноименной рас сматриваемой функции. Ввиду ограничений, налагаемых ис пользуемыми методами символьного исполнения, мы не будем касаться вопроса обработки рекурсивных вызовов, циклов, а также составных (сложных) типов данных и массивов, оставив оный для дальнейшей работы.

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

2 Используемые методы 2.1 Рассуждения на основе прецедентов Рассуждения на основе прецедентов [3] представляют собой общий подход к решению интеллектуальных задач, состоящий в попытке использования человеческой модели принятия ре шений. Прецедент это фрагмент опыта системы, описа ние решения некоторой проблемной ситуации, которое может быть использовано при решении новой задачи. В ходе рассуж Сборник статей молодых ученых факультета ВМК МГУ, № 10, 256 Н. Н. Фастовец дений на основе прецедентов циклически выполняются следу ющие действия:

1. Извлечение из памяти наиболее похожего прецедента или набора прецедентов, 2. Использование информации из выбранного прецедента (или набора прецедентов) для решения задачи, 3. Проверка соответствия полученного решения поставлен ным требованиям, 4. Запоминание задачи и полученного решения для возмож ного использования в дальнейшем.

В различных практических системах и конкретных методах данный цикл может применяться не полностью [4]. Однако ис пользование данного подхода при решении задач требует ре шения ряда вопросов:

• Определение отношения похожести прецедентов (для выполнения первого шага).

• Выбор способа организации библиотеки прецедентов, обеспечивающего эффективный поиск наиболее подходя щего для адаптации известного решения.

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

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

Сборник статей молодых ученых факультета ВМК МГУ, № 10, Организация библиотеки моделей программ 2.2 Автоматическая коррекция программ Методы автоматической коррекции программ, то есть вне сения в программу модификаций, приводящих оную в соответ ствие с заданной спецификацией, представляют значительный интерес как средство выполнения этапа адаптации выбранно го известного решения. Коррекция программ включает в себя поиск фрагментов программы, вносящих отклонение от требу емого поведения, и модификацию их с целью устранения таких отклонений. Существуют и развиваются методы коррекции, ориентированные на различные типы программ, предполагаю щие также разные способы синтеза новых правильных фраг ментов. Например, метод, предложенный в работе [5], предпо лагает использование символьного исполнения для выявления операторов присваивания вида LHS RHS, выражение в пра вой части которых приводит к отклонению значения перемен ной LHS от требуемого спецификацией. Для построения кор ректной правой части применяется перебор ряда шаблонных выражений над переменными программы и проверка получа емого результата на соответствие спецификация. Иной подход изложен в работе [6], предметом рассмотрения которой являют ся программы, представленные в виде систем переписывания термов [11]. Спецификации таких программ также задаются в форме наборов правил переписывания термов. Коррекция в таком случае заключается в удалении из программы тех пра вил, которые вызывают построение отличающихся от допуска емых спецификацией термов, и применении средств индуктив ного синтеза для добавления в корректируемую систему новых правил.

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

Сборник статей молодых ученых факультета ВМК МГУ, № 10, 258 Н. Н. Фастовец 2.3 Символьное исполнение Символьное исполнение [12, 13] представляет собой подход к анализу поведения программы, в основе которого лежит вы полнение рассматриваемой программы с использованием сим вольных входных значений вместо конкретных значений вход ных параметров. При этом значения переменных, использу емых программой, представляются как выражения над сим вольными входными значениями (символьными выражения ми).

Определение 1. Состояние выполняемой программы в ходе символьного выполнения (символьное состояние) определяет ся набором (P C;

E;

i), где • P C условие пути (path condition), представляющее со бой не содержащее кванторов булевозначное выражение над символьными входными значениями.

•E структура, описывающая значения переменных программы через символьные выражения.

• i счетчик команд, указывающий на оператор програм мы, который предстоит выполнить для перехода в сле дующее состояние.

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

Начальное состояние выполняемой программы, принимаю щей на вход N значений, описывается структурой вида (true;

x1 = 1,..., xN = N, x(N +1) =,..., xH = ;

1), Сборник статей молодых ученых факультета ВМК МГУ, № 10, Организация библиотеки моделей программ где условие пути тождественно истине;

переменным x1,..., xN, представляющим входные параметры, со поставлены символьные входные значения, а остальным переменным x(N +1),..., xH программы сопоставлен символ, представляющий неопределенное значение;

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

Построение следующего состояния при выполнении оператора производиться следующим образом.

Пусть текущее состояние выполнения описывается струк турой (P C;

x1 = 1,..., xH = H ;

opi ), • Если счетчик opi указывает на оператор присваивания xk RHS, где xk одна из переменных программы, а некоторое выражение, то следующее состояние RHS будет описываться структурой (P C;

x1 = 1,..., xk = RHS,..., xH = H ;

opi+1 ), где RHS выражение, получаемое из RHS заменой всех вхождений переменных на символьные выражения, сопо ставленные им в текущем состоянии.

• Если opi указывает на оператор условного ветвления, за данный в полной форме if C then opj else opk, то по следующими являются два новых состояния, имеющие вид (P C C ;

E;

opj ) и (P C ¬C ;

E;

opk ), где C полу чаемое из условия заменой всех вхождений переменных на символьные выражения, сопоставленные им в теку щем состоянии (сивол E применим для сокращения запи си конструкции x1 = 1,..., xH = H ).

• Если opi указывает на оператор условного ветвления, за данный в сокращенной форме if C then opj, то, как и в предыдущем случае, мы получим два последующих со стояния вида (P C C ;

E;

opj ) и (P C ¬C ;

E;

op(i+1) ), где C выражение, получаемое из условия C заменой всех вхождений переменных на символьные врыажения, Сборник статей молодых ученых факультета ВМК МГУ, № 10, 260 Н. Н. Фастовец представляющие их значения, E для сокращения записи представляет структуру x1 = 1,..., xH = H, а op(i+1) указывает на следующий за условным ветвлением опера тор программы.

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

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

1 function sdiv(a, b: integer): integer 2 begin 3 if(b = 0) then 4 sdiv:= Err 5 else 6 sdiv := a div b;

7 end;

Начальное состояние описывается выражением (true;

a = A, b = B, sdiv = ;

3).

Обработка оператора условного ветвления на строке 3 со здаст два новых символьных состояния выполняемой програм мы:

(1) (B = 0;

a = A, b = B, sdiv = ;

4) (2) (¬(B = 0);

a = A, b = B, sdiv = ;

6) При этом процесс символьного исполнения разделяется и про изводиться независимо для каждого из полученных состояний.

Далее, последующим для состояния (1) после выполнения опе ратора на строке 4 станет состояние (B = 0;

a = A, b = B, sdiv = Err;

7), Сборник статей молодых ученых факультета ВМК МГУ, № 10, Организация библиотеки моделей программ а для состояния (2) после выполнения оператора присваивания на строке 6 последующим станет (¬(B = 0);

a = A, b = B, sdiv = A div B;

7).

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

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

2.4 Построение описаний программ Применение символьного исполнения к императивной про грамме P, вычисляющей некоторое значение, позволяет по строить символьное описание [15] поведения анализируемой программы. Такое описание представляет собой множество вариантов поведения программы, сопоставляющих некоторо му подмножеству наборов входных значений анализируемой программы функцию, вычисляемую данной программой. Ес ли в процессе символьного исполнения, находясь в состоянии (P C;

x1 = e1,..., xH = eH ;

opi ) мы обнаруживаем, что счетчик opi указывает на оператор остановки программы (либо выхо да из подпрограммы), то мы можем сформировать очередной вариант поведения программы:

Определение 2. Вариант поведения программы пара сим вольных выражений (pc;

f ), где Сборник статей молодых ученых факультета ВМК МГУ, № 10, 262 Н. Н. Фастовец • pc ограничение входных значений. Не содержащее кванторов булевозначное выражение над константа ми и символьными входными значениями, совпадающее с условием пути символьного состояния, в котором производится завершение обработки соответствующей ветви символьного исполнения;

•f результат вычисления. Символьное выражение, описывающее значение, содержащееся в выходной пе ременной программы (подпрограммы) при выполнении ограничения входных значений.

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

Определение 3. Символьное описание программы множе ство Summ(P ) = {(pc1 ;

f1 ),..., (pcN ;

fN )} вариантов поведе ния программы P, в котором ограничения на значения вход ных параметров, содержащиеся в каждом варианте, являют ся несовместными, то есть для любых i, j, 1 i, j N, i = j выражение pci pcj является несовместным.

Таким образом, символьное описание позволяет предста вить рассматриваемую программу как множество вариантов Сборник статей молодых ученых факультета ВМК МГУ, № 10, Организация библиотеки моделей программ поведения, соответствующих различным непересекающимся подмножествам множества наборов входных значений про граммы. В дальнейшем мы будем говорить об описаниях про граммы, подразумевая под таковыми именно символьные опи сания, соответствующие приведенному определению.

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

1 function amax(x, y: integer): integer 2 begin 3 if(x 0) then 4 x := -1*x;

5 if(y 0) then 6 y := -1*y;

7 if(x y) then amax := x else amax := y 8 end;

Начальное состояние выполнения описывается конструкцией (true;

x = 1, y = 2, amax = ;

3). Обработка первого услов ного ветвления на строке 3 создаст два возможных новых состояния выполнения: (1 0;

x = 1, y = 2, amax = ;

4) и (¬(1 0);

x = 1, y = 2, amax = ;

5). После вы полнения оператора присваивания x:= -1*x на строке в ветви с условием пути 1 0, мы получим новое состояние (1 0;

x = 1, y = 2, amax = ;

5). Теперь каждая из полу ченных ветвей теперь должна обработать оператор ветвления на строке 5. При этом его условие будет через конъюнк цию добавлено к условию пути соответствующей ветви. Таким образом мы получим четыре новых состояния (1 0 2 0;

x = 1 1, y = 2, amax = ;

6), (1 0 ¬(2 0);

x = 1 1, y = 2, amax = ;

7), Сборник статей молодых ученых факультета ВМК МГУ, № 10, 264 Н. Н. Фастовец (¬(1 0) 2 0;

x = 1, y = 2, amax = ;

6), (¬(1 0) ¬(2 0);

x = 1, y = 2, amax = ;

7).

После обработки оператора присваивания y:= -1*y на строке 6 мы дополним соответствующие ветви выполнения и по лучим новый набор состояний:

(1 0 2 0;

x = 1 1, y = 1 2, amax = ;

7), (1 0 ¬(2 0);

x = 1 1, y = 2, amax = ;

7), (¬(1 0) 2 0;

x = 1, y = 1 2, amax = ;

7), (¬(1 0) ¬(2 0);

x = 1, y = 2, amax = ;

7).

Далее, из каждого полученного состояния мы должны перейти к обработке ветвления, указанного в строке 7. Для кратко сти перечислим только те случаи, когда значение входного па раметра x, то есть alpha1, не меньше нуля. Тогда мы получим следующие состояния:

(¬(1 0) 2 0 1 1 2 ;

x = 1, y = 1 2, amax = 1 ;

8), (¬(1 0) 2 0 ¬(1 1 2 );

x = 1, y = 1 2, amax = 1 2 ;

8), (¬(1 0) ¬(2 0) 1 2 ;

x = 1, y = 2, amax = 1 ;

8), (¬(1 0) ¬(2 0) ¬(1 2 );

x = 1, y = 2, amax = 2 ;

8).

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

Сборник статей молодых ученых факультета ВМК МГУ, № 10, Организация библиотеки моделей программ 3 Организация библиотеки прецедентов Рассматривая задачу поиска программы, наиболее соответ ствующей заданной спецификации, мы сталкиваемся с рядом сложностей. Во-первых, большинство методов верификации, то есть проверки соответствия программы p спецификации S, да ют только бинарную оценку: обладает анализируемая програм ма указанным свойством или нет. В случае же использования рассуждений на основе прецедентов мы предполагаем, что ни одна из программ, содержащихся в библиотеке, не отвечает спе цификации новой задачи и нам требуется выбрать программу, которая в наибольшей степени соответствует S, или менее всего отклоняется от нее. Во-вторых, чтобы избежать необхо димости проверки всех прецедентов в доступной библиотеке, при построении оной нам требуется использовать некоторое от ношение порядка (или частичного порядка) на множестве эле ментов библиотеки, позволяющее из связи пары элементов по данному отношению и наличия оценки соответствия одного из них заданной спецификации, сделать вывод о соответствии ли бо нарушении оной вторым элементом. В качестве основы для решения этих проблем, мы предлагаем использовать описания программ, получаемые с помощью символьного исполнения.

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

Далее, мы можем представить нашу библиотеку прецеден тов как дерево H, каждая вершина vi которого помечена вы ражением pc(vi ) над символами алфавита входных символь ных значений, а также множеством программ progs(vi ), для которых существует вариант поведения, условие пути в кото ром совпадает с pc(vi ). Направленная дуга (vi, vj ) содержит ся в дереве H в том случае, если имеет место импликация Сборник статей молодых ученых факультета ВМК МГУ, № 10, 266 Н. Н. Фастовец pc(vj ) pc(vi ). Последнее условие позволяет сокращать про странство поиска при выборе наиболее подходящей програм мы, так как из несовместимости с заданной спецификацией ва риантов поведения, имеющих условием пути выражение pc(vk ), можно сделать вывод о несовместимости с ней же вариантов поведения, условия пути которых представлены вершинами, лежащими в поддереве vk.

1. Двигаясь от корня дерева к его листьям, составляем спи сок V вершин vi1,..., vik, соответствующие которым условия пути совместимы с заданной спецификацией S.

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

2. Теперь мы составим множество программ, хотя бы один вариант поведения которых содержит условие пути, со поставленное вершине, попавшей в список V, то есть со ставим объединение C = progs(vj ).

vj V 3. Если множество C пусто, то система должна сообщить об отсутствии подходящего для адаптации прецедента. В противном случае, для каждой программы pi C мы определяем количество Ni ее вариантов поведения, усло вие пути которых помечает вершину, попавшую в V, по сле чего мы можем вычислить оценку неполного соответ ствия pi заданной спецификации S как N Sim(pi, S) =.

Summ(pi ) Результатом поиска является та программа, для которой указанная оценка является наибольшей.

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

Сборник статей молодых ученых факультета ВМК МГУ, № 10, Организация библиотеки моделей программ 3.1 Спецификации программ Для формального описания требований к синтезируемой программе мы будем использовать спецификации, заданные через так называемые специфицирующие теоремы.

Определение 4. Специфицирующая теорема или специфи кация выражение логики первого порядка, не содержащее свободных переменных, имеющее вид x1.D1,..., xN.DN y.DO R[x1,..., xN, y], где x1,..., xN переменные, представляющие значения входных параметров, принадлежащие множествам (доме нам) D1,..., DN соответственно, а y выходная перемен ная, то есть переменная, содержащая возвращаемое значе ние, принадлежащее домену DO.

В дальнейшем, для краткости, кванторную приставку x1.D1,..., xN.DN y.DO в спецификации мы будем обо значать символом Q, если она не будет указана явно.

Определение 5. Будем говорить, что программа P, вычис ляющая значение функции f (x1,..., xN ), отвечает специ фикации Q R[x1,..., xN, y] в том случае, если для любых значений входных параметров x1,..., xN выполняется от ношение R[x1,..., xN, f (x1,..., xN )].

В качестве примера спецификации, заданной указанным об разом, можно рассмотреть выражение x.Z y.Z z.Z (x y z = x) (y x z = y), выступающее спецификацией функции максимума, выбираю щей наибольшее из пары переданных ей значений.

Сборник статей молодых ученых факультета ВМК МГУ, № 10, 268 Н. Н. Фастовец 3.2 Проверка вариантов поведения Описанная ранее программа amax(x,y) выбора наибольше го по абсолютному значению числа не соответствует специфи кации функции максимума x.Z y.Z z.Z (x y z = x) (y x z = y), так как может возвращать значение, не равное ни одному из своих аргументов. Однако, если оба аргумента программы яв ляются неотрицательными числами, возвращаемое значение будет соответствовать требованию, выраженному в специфи кации. То есть, мы можем сказать, что хотя указанная про грамма в целом не соответствует заданной спецификации, но при наличии некоторых дополнительных ограничений требуе мое отношение между входными параметрами и возвращаемым значением будет выполняться. И такие дополнительные огра ничения удобно получать из вариантов поведения программы, перечисленных в ее описании. Например, в частично приведен ном в разделе 2.4 описании программы amax(x,y) содержатся варианты поведения (¬(1 0) ¬(2 0) 1 2 ;

x = 1, y = 2, amax = 1 ), (¬(1 0) ¬(2 0) ¬(1 2 );

x = 1, y = 2, amax = 2 ), в которых указанное в спецификации отношение выполняется:

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

Говоря строго, вариант поведения (pc, e) Summ(P ) неко торой программы P отвечает спецификации QR в том случае, если при подстановке = {1 /x1,..., N /xN, y/e} является Сборник статей молодых ученых факультета ВМК МГУ, № 10, Организация библиотеки моделей программ истинной формула x1,..., xN pc R, то есть при лю бых значениях входных параметров из выполнения над ними условия pc следует, что возвращаемое значение программы, вы числяемое функцией, представленной выражением e, отвечает входным параметрам по отношению R. Однако при поиске под ходящего прецедента мы будем опираться на иерархию условий пути и оценку их соответствия спецификации, так как для них может быть определено выполнение логического следования, а вычисляемая функция будет корректироваться позже, на эта пе адаптации. Поэтому, а также с целью снижения вычисли тельной сложности оценки, мы на каждом шаге поиска будем проверять совместность условия пути, которым помечена рас крываемая вершина, и спецификации. Иначе говоря, мы хотим узнать, может ли описываемое условием пути состояние до стигаться в программе, отвечающей заданной спецификации.

Для этого нам потребуется определить выполнимость форму лы pcx Rx, где x = {1 /x1,..., N /xN }, для чего можно воспользоваться методом резолюции.

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

Пусть задано множество возможных состояний светофора:

Color = {Red, Y ellow, Green, LArrow, RArrow, error}.

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

prev.Color dt.Z nxt.Color prev =Red dt = 10 nxt = Green Сборник статей молодых ученых факультета ВМК МГУ, № 10, 270 Н. Н. Фастовец prev =Green dt = 10 nxt = Y ellow prev =Y ellow dt = 3 nxt = Red, В дальнейшем мы будем обозначать данное выражение– спецификацию как T raf f icLight.

Рассмотрим две имеющиеся функции, выполняющие подоб ные действия:

function stateA(s:Color, t: integer): Color begin if(s = Green) then if(t = 10) then stateA := Yellow else stateA := s else if(s = Yellow) then if(t = 3) then stateA := Red else stateA := s else if(s = Red) then if(t = 8) then stateA := Green else stateA := s end;

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

Summ(stateA) = {((S = Green) T = 10;

Y ellow), ((S = Green) ¬(T = 10);

S), (¬(S = Green) S = Y ellow T = 3;

Red), (¬(S = Green) S = Y ellow ¬(T = 3);

S), (¬(S = Green) ¬(S = Y ellow) S = Red T = 8;

Green), (¬(S = Green) ¬(S = Y ellow) S = Red ¬(T = 8);

S), Сборник статей молодых ученых факультета ВМК МГУ, № 10, Организация библиотеки моделей программ (¬(S = Green) ¬(S = Y ellow) ¬(S = Red);

error)}, и функцию function stateB(s: Color, t: integer): Color begin if(s = Green) then if(t = 10) then stateB := Yellow else stateB := s else if(s = Yellow) then if(t = 3) then stateB := Red else stateB := s else if(s = Red) then if(t = 10) then stateB := RArrow else stateB := s else if(s = RArrow) then if(t = 5) then stateB := Green else stateB := s end;

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

Summ(stateB) = {((S = Red) T = 10;

Y ellow), ((S = Red) ¬(T = 10);

S), (¬(S = Red) S = Y ellow T = 3;

Red), (¬(S = Red) S = Y ellow ¬(T = 3);

S), (¬(S = Red)¬(S = Y ellow)S = Green T = 10;

RArrow), (¬(S = Red) ¬(S = Y ellow) S = Green ¬(T = 10);

S), (¬(S = Red) ¬(S = Y ellow) Сборник статей молодых ученых факультета ВМК МГУ, № 10, 272 Н. Н. Фастовец ¬(S = Green) S = RArrowT = 5;

Green), (¬(S = Red) ¬(S = Y ellow) ¬(S = Green) S = RArrow ¬(T = 5);

S), (¬(S = Red) ¬(S = Y ellow) ¬(S = Green) ¬(S = RArrow);

error} Сопоставляя варианты поведения приведенных программ легко увидеть, для программы stateA некоторые варианты оказываются несовместимыми со спецификацией. Например, вариант поведения (¬(S = Green) ¬(S = Y ellow) (S = Red) (T = 8);

Green) при формировании проверяемой на выполнимость формулы pcx Rx, где x = {S/prev, T /dt} дает нам невыполнимое выражение prev.Color dt.Z nxt.Color (¬(prev = Green)¬(prev = Y ellow)(prev = Red) (dt = 8)) prev =Red dt = 10 nxt = Green prev =Green dt = 10 nxt = Y ellow prev =Y ellow dt = 3 nxt = Red.

Также несовместимыми со спецификацией оказываются вари анты поведения (¬(S = Green)¬(S = Y ellow) (S = Red) ¬(T = 8);

S), (¬(S = Green)¬(S = Y ellow) ¬(S = Red);

error) Таким образом, получаем для программы stateA оценку непол ного соответствия Sim(stateA, T raf f icLight) = 4.

Аналогичным образом проверяя варианты поведе ния программы stateB получим, что для нее окажут ся несовместными со спецификацией также три вари анта из девяти, то есть будет иметь место соотноше ние Sim(stateB, T raf f icLight) 9. Получаем, что = Сборник статей молодых ученых факультета ВМК МГУ, № 10, Организация библиотеки моделей программ Sim(stateB, T raf f icLight) Sim(stateA, T raf f icLight), то есть в качестве наиболее подходящего прецедента для адаптации следует выбрать программу stateB. Результа том адаптации станет отвечающая заданной спецификации программа function stateRes(s, t: integer): integer begin if(s = Green) then if(t = 10) then stateB := Yellow else stateRes := s else if(s = Yellow) then if(t = 3) then stateB := Red else stateRes := s else if(s = Red) then if(t = 10) then stateB := Green else stateRes := s end;

которая получена из stateB заменой константы Arrow на кон станту Green и удалением оператора условного ветвления if(s = Arrow) then if(t = 5) then stateB := Green else stateB := s Однако следует учитывать, что при реализации в конкретной системе, результат адаптации будет зависеть от применяемого метода коррекции.

4 Альтернативные методы В данной работе был предложен способ организации биб лиотеки известных программ и оценка неполного соответствия моделей программ заданной спецификации, предназначенный для использования при автоматическом синтезе новых про грамм с применением рассуждений на основе прецедентов. В Сборник статей молодых ученых факультета ВМК МГУ, № 10, 274 Н. Н. Фастовец то же время, эффективность данного варианта применения рассуждений на основе прецедентов в синтезе программ суще ственно зависит от используемого метода адаптации известных решений, то есть метода коррекции программ.

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


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

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

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

Указанные методы синтеза могут применяться в ходе кор рекции известной программы, приводящей последнюю в соот ветствие с заданной спецификацией. Так, например, описанный в работе [6] способ коррекции предполагает использование ин дутивного синтеза для построения добавляемых в корректиру Сборник статей молодых ученых факультета ВМК МГУ, № 10, Организация библиотеки моделей программ емую программу правил.

5 Заключение Значительным преимуществом использования рассужде ний на основе прецедентов в синтезе программ является воз можность получения требуемой программы за счет модифи кации уже существующей, что предполагает снижение коли чества операций, необходимых для получения решения. В то же время, применение данного подхода при синтезе программ требует использования такой организации библиотеки преце дентов и методов поиска в ней, которые позволили бы прово дить оценку степени соответствия содержащихся в библиотеке программ заданной пользователем спецификации. Последнее предполагает проведение верификации каждой известной про граммы по отношению к указанной спецификации, что пред ставляется крайне сложной задачей. Помимо этого, дополни тельную сложность создает ожидаемое отсутствие в библио теке прецедентов известной программы, отвечающей заданной спецификации, и необходимость выбора той программы, кото рая требует наименьшего количества модификаций и, как след ствие, необходимость определения оценки неполного соответ ствия проверяемой программы указанным требованиям. Воз можным решением указанных задач является анализ извест ных программ средствами символьного исполнения, позволя ющий представить модель программы как множество ее вари антов поведения, каждый из которых удовлетворяет, либо не удовлетворяет заданной спецификации. Исследование совме стимости отдельных вариантов поведения программы со специ фикацией позволяет построить оценку неполного соответствия спецификации всей программы. Применение средств построе ния иерархии прецедентов, либо отдельных их элементов, поз воляет, в свою очередь, повысить эффективность поиска наибо лее подходящего прецедента за счет последовательного сокра Сборник статей молодых ученых факультета ВМК МГУ, № 10, 276 Н. Н. Фастовец щения пространства поиска путем отсечения заведомо менее подходящих групп известных программ.

Список литературы [1] Kreitz C. Program Synthesis. // Automated Deduction A Basis for Applications Vol. 3 Applications. Dordrecht:

Kluwer. — 1998. — P. 105–134.

[2] Wilson G., Arulia D. A., et al. Best Practices for Scientic Computing. Preprint. [no. 1210.0530]. ArXiv e-prints. — 2012. — 6 p.

[3] Aamodt A., Plaza E. Case-Based Reasoning: Foundational Issues, Methodological Variations, and System Approaches.

// AI Communications. Vol. 7. № 1, — 1994. — P. 39–59.

[4] Варшавский П. Р., Еремеев А. П. Поиск решения на основе структурной аналогии для интеллектуальных систем под держки принятия решений. // Известия Российской ака демии наук. Теория и системы управления. № 1, 2005.

с. 97–109.

[5] Konighofer R., Bloem R. Automated Error Localization and Correction for Imperative Programs. // Proceedings of the International Conference on Formal Methods in Computer– Aided Design (FMCAD 11). Austin, TX, USA : FMCAD Inc, —2011, —p. 91–100.

[6] Alpuente M., Ballis D., Correa F., Falaschi M. An Integrated Framework for the Diagnosis and Correction of Rule–Based Programs. // Theoretical Computer Science Vol. 411. № 47.

— 2010. — P. 4055–4101.

[7] Korukhova Y., Fastovets N. A Case–Based Reasoning Ap proach to Program Synthesis. // Proceedings of the Interna tional Conference on Knowledge Engineering and Ontology Сборник статей молодых ученых факультета ВМК МГУ, № 10, Организация библиотеки моделей программ Development (KEOD 2010). SciTePress : Portugal. — 2010, — P. 335– [8] Йенсен К., Вирт Н. Паскаль. Руководство для пользова теля и описание языка. // М. : Финансы и статистика.

1982. С. [9] Paulo Gomes, Francisco C. Pereira, Paulo P, Nuno Seco, Paulo Carreiro, Jose Luis Ferreira, Carlos Bento. Us ing CBR for Automation of Software Design Patterns. // Proceedings of the 6th European Conference on Advances in Case–Based Reasoning (ECCBR ’02). London, UK :

Springer–Verlag, 2002.

[10] Ulrich J. W, Robert M. Program Synthesis By Analogy. // Proceedings of the 1977 symposium on Articial intelligence and programming languages. Vol. 12 № 8. New York, NY, USA : ACM. —1977, — p. — 22–28.

[11] Klop J. W. Term Rewriting Systems. // Handbook of logic in computer science. Vol. 2. Oxford University Press, Inc :

New York, NY, USA. — 1992. — P. 1–116.

[12] King J. C. Symbolic execution and program testing. // Com munications of the ACM. Vol. 19 № 7. ACM New York : New York, NY, USA. — 1976. —p. 385–394.

[13] Pasareanu C. S., Visser W.. A survey of new trends in sym bolic execution for software testing and analysis. // Inter national Journal on Software Tools for Technology Transfer (STTT) - Special Section on HVC 07 archive. Vol. 11 № 4, — 2009. — P. 339–353.

[14] Obdrzalek J., Trtik M.. Ecient Loop Navigation for Sym bolic Execution. // Proceedings of the 9th international con ference on Automated technology for verication and analysis (ATVA’11). Berlin, Germany : Springer–Verlag, — 2011, — P. 453– Сборник статей молодых ученых факультета ВМК МГУ, № 10, 278 Н. Н. Фастовец [15] Person S. J., Dwyer M. B., Elbaum S., Pasareanu C. S. Dif ferential symbolic execution. // Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of soft ware engineering (SIGSOFT ’08/FSE-16). New York, NY, USA : ACM, — 2008, — P. 226– [16] Manna Z., Waldinger R. Fundamentals of Deductive Pro gram Synthesis. // IEEE Transactions on software engineer ing. 18. № 8. — 1992. — P. 674– Сборник статей молодых ученых факультета ВМК МГУ, № 10, Сборник статей молодых ученых факультета ВМК МГУ, № 10, 2013 УДК 004. Анализ и применение признаков оценочных слов для формирования словаря оценочной лексики © 2013 г. И. И. Четвёркин ilia2010@yandex.ru Кафедра алгоритмических языков 1 Введение В связи с бурным развитием сети Интернет, возможность доступа к нему получает всё большее количество пользовате лей. На сегодняшний день существует большое количество ре сурсов, где люди могут оставлять собственное мнение по пово ду какого-либо объекта. В таких отзывах содержится полезная информация, например, какой из набора продуктов лучший.

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

Оценочные слова это слова, которые несут в себе неко торую эмоциональную оценку, например хороший или пло хой. Эта оценка может быть положительной или отрицатель ной. Нас будут интересовать любые слова, выражающие субъ ективное отношение.

Как уже было замечено выше, важным фактором каче ственного извлечения оценочных суждений о той или иной 280 И. И. Четвёркин сущности является знание оценочных слов и выражений, кото рые используются в данной области. Дело в том, что невозмож но заранее собрать список оценочных слов и выражений, кото рые будут применимы для всех предметных областей, посколь ку некоторые оценочные выражения употребляются только в конкретных предметных областях, другие являются оценочны ми в одной области и не являются оценочными в другой [14].

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

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

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


Сборник статей молодых ученых факультета ВМК МГУ, № 10, Анализ и применение признаков оценочных слов 2 Методы автоматического извлечения оценочных слов Словари оценочных слов играют важную роль в большин стве задач анализа мнений [4], включающих в себя поиск и извлечение мнений, автоматические ответы на субъективные вопросы, оценочное аннотирование и т. д. Хотя методы машин ного обучения с учителем показали свою эффективность в за даче классификации отзывов по тональности [14], авторы в [3] демонстрируют, что включение характеристик на основе оце ночной лексики существенно улучшает качество классифика ции.

Существует два глобальных подхода к автоматическому из влечению оценочной лексики: на основе словарей и на основе текстовых коллекций.

Первый подход основан на информации из различных сло варей и тезаурусов. Одним из наиболее распространенных ме тодов является итеративное формирование словаря оценочных выражений на основе тезауруса WordNet или других семанти ческих ресурсов. Основной принцип в данном методе заключа ется в том, что синонимы и антонимы оценочного слова также являются оценочными. Таким образом, из начального множе ства слов может быть получено новое, более полное множество оценочных слов [8, 13]. В [5] для конструирования оценочного словаря используются толкования слов. Основная идея заклю чается в том, что слова с одинаковой оценочной ориентацией имеют схожие толкования.

Второй подход основан на поиске закономерностей, правил и шаблонов в текстовых коллекциях [10, 12]. В [15] авторы те стируют качество оценочного словаря, полученного по огром ному массиву текстовой информации, собранному с четырех миллиардов Веб страниц. Авторы формируют граф совмест ной встречаемости слов и используют алгоритм распростра нения меток на нем. Полученный словарь позволил получить Сборник статей молодых ученых факультета ВМК МГУ, № 10, 282 И. И. Четвёркин более высокое качество работы в нескольких задачах обработ ки мнений по сравнению с уже существующими словарями на английском языке. Кроме того, данный ресурс содержит боль шое количество сленговых, вульгарных и других несловарных слов.

В литературе также встречаются некоторые работы, кото рые комбинируют вышеописанные два подхода [4].

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

Во-первых, для исследования было собрано 28, 773 отзы ва о фильмах различного жанра с рекомендательного портала www.imhonet.ru. Каждому отзыву соответствовала оценка ав тора по десятибалльной шкале. Эта коллекция является основ ной для работы, назовем её коллекцией мнений.

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

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

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

Сборник статей молодых ученых факультета ВМК МГУ, № 10, Анализ и применение признаков оценочных слов Кроме того, было высказано предположение, что можно вы делить некоторые части корпуса мнений, в которых концентра ция оценочных слов больше, а именно: предложения, заканчи вающиеся на ! или... ;

короткие предложения не более чем из 7 слов;

короткие отзывы, состоящие из одного предло жения;

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

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

• Частотные характеристики: частота слова во всей коллекции и подокументная частота;

частота слов с боль шой буквы;

признак Странность ;

признак TFIDF;

• Характеристики на основе оценки пользователя:

отклонение от средней оценки;

дисперсия оценки слова;

вероятность встретить заданное слово с каждой из оце нок;

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

Всего для каждого слова вычисляется 33 признака.

На основе данного признакового описания обучались раз личные алгоритмы классификации (LogitBoost, RandomForest, Logistic Regression) и применялись для разделения слов на оце ночные и неоценочные. Наилучший результат показала комби нация различных алгоритмов с точностью Precision@1000 = =81.5 %. Более подробное описание представленной модели оценочных слов можно найти в [2].

Для определения наиболее значимых признаков были вы числены метрика точности по каждому из них. Наилучшие ре зультаты показал признак Странность, вычисленный с по мощью пары корпусов малый-описаний. Точность данного Сборник статей молодых ученых факультета ВМК МГУ, № 10, 284 И. И. Четвёркин признака составила P recision@1000 = 49.1 %, и превосходит точность, полученную с помощью других признаков более чем на 10 %.

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

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

Для вычисления признака, необходимо иметь два корпуса, один с высокой концентрацией оценочных слов, другой контрастный. Идея в том, что слова, которые несут оценки, будут странными в контексте контрастного корпуса [1].

s (w) W eirdness = g (w) где s (w) вероятность встретить слово в коллекции с вы сокой концентрацией оценочных слов;

g (w) вероятность встретить слово в контрастной коллекции.

На первом этапе будут исследованы параметры распреде ления слов в коллекциях текстов на основе закона Ципфа– Мандельброта. Во второй части будет исследован признак Странность и введено его распределение. На последнем Сборник статей молодых ученых факультета ВМК МГУ, № 10, Анализ и применение признаков оценочных слов этапе будет введено определение взаимной информации и ее связь с дивергенцией Кульбака–Лейблера. На основании дан ных определений будет доказана теорема о монотонности ди вергенции Кульбака–Лейблера в зависимости от параметров распределения слов в коллекции. Полученные теоретические выводы будут проверены на практике на текстовых коллекци ях, описанных в разделе 4.1 Распределения слов в коллекциях текстов Большинство работ в области лексической статистики ос нованы на модели случайного выбора с возвращением. В дан ной модели полагается существование популяции типов слов w1,... wS с вероятностями появления 1,... S. S называет ся размером популяции и может быть равено бесконечности (S = ) в случае счетного числа типов. Значения вероятно стей i являются параметрами данной модели и должны удо влетворять равенству:

(1) 1 + · · · + S = Для удобства будем полагать, что 1 S. Это ··· го всегда можно добиться простым переприсваиванием индек сов. Случайный выбор слова из заданной популяции будет описываться случайной величиной X : {1,..., S}. Если X = k, значит случайно выбран тип wk и распределение за дается P (X = k) = k для k = {1,..., S}. Случайная выборка размера N соответствует N -кратному, независимому повторе нию данного эксперимента, X = (X1,,..., XN ).

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

Поэтому в литературе [6] предлагается переформулировать за данную модель популяции в терминах с меньшим значением параметров: после того, как эти параметры оценены, гипоте тическое распределение параметров i может быть вычислено.

Сборник статей молодых ученых факультета ВМК МГУ, № 10, 286 И. И. Четвёркин Такого рода модели популяции обычно обозначаются термином LNRE1.

Часто предполагается [7], что вероятность появления слов также является случайной величиной с заданным абсолют но непрерывным распределением и функцией плотности ве роятности p(). Для того, чтобы формально определить дан ную функцию, введем несколько вспомогательных функций.

Структурное распределение типов:

S (2) G() = I i i= Функция распределения для случайной величины :

S (3) F () = i I i i= Согласно [6], большинство LNRE моделей приближают G() с помощью некоторой непрерывной функции g() такой, что:

(4) G() = g() d и аналогично:

(5) F () = g() d = p() d Из выражения (1) следует условие нормировки для p():

(6) g() d = p() d = 0 Large number of rare events или большое количество редких событий Сборник статей молодых ученых факультета ВМК МГУ, № 10, Анализ и применение признаков оценочных слов Уже давно известно, что распределение вероятностей слов, оце ненных по случайному тексту, поразительно похоже на закон Ципфа [11]. Формально случайный текст понимается как по следовательность символов, порожденных марковским процес сом, с границами слов, обозначенными символом пробел. Бы ло показано, что в достаточно общих предположениях, такая сегментированная последовательность символов эквивалентна случайно выборке слов, порожденной с помощью модели, опи санной в начале раздела. А также, что вероятности типов слов удовлетворяют закону Ципфа–Мандельброта:

C (7) i =, i {1,..., S} (i + b)a где C это нормировочная константа, а a 1 и b 0 константы, зависящие от коллекции.

Для вывода аналитического представления функций (2) (5), заметим, что в соответствии с моделью Ципфа– Мандельброта, зависимость G() от может быть выражена следующим образом [6]:

Ca (8) G() = b a для = i. Дифференцирование по выражения (8) дает сле дующий вид функции g():

C 1, 0 B (9) g() = 0, [0, B] / где 0 1 и связан с параметрами в модели Ципфа– Мандельброта как = a. B 0 параметр ограничиваю щий значения, которые может принимать величина [0, B].

Нормировочную константу C можно найти из условия (6):

C= B Сборник статей молодых ученых факультета ВМК МГУ, № 10, 288 И. И. Четвёркин Таким образом, плотность распределения p() задается следу ющим образом:

,0 B B 1 (10) p() = 0, [0, B] / 4.2 Распределение случайной величины признака и его некоторые особенности Введем новую случайную величину, соответствующую при знаку Странность. Данная случайная величина принимает значения равные частному значений вероятностей слов в двух разных коллекциях (выборках) Z : { s }, где s и g обозна g чают коллекции. Случайная величина Z является непрерывной и может принимать значения на R+.

Найдем распределение случайной величины Z в предпо ложении, что случайные величины s и g являются незави симыми и имеют плотности распределения, заданные выра жением (10) с различными параметрами для каждой коллек ции. Согласно определению функции распределения: FZ (z) = P {s /g z}.

Если представить s и g как координаты на плоскости, тогда FZ (z) равна вероятности того, что точка (s, g ) попа дет в область, координаты которой удовлетворяют неравенству s /g z, где s [0, Bs ] и g [0, Bg ]. Исходя из геометри ческой интерпретацией, для нахождения функции распределе ния FZ (z) необходимо рассмотреть два случая: для z Bs /Bg и для z Bs /Bg.

Рассмотрим случай для z Bs /Bg :

Bg zg FZ (z) = p(s, g ) ds dg = 0 Сборник статей молодых ученых факультета ВМК МГУ, № 10, Анализ и применение признаков оценочных слов Bg zg Bg Cs Cg g (g z)1s g g g s s ds dg = dg = Cs Cg 1 s 0 0 Cs Cg z 1s 1 g Bg 1s z 1s Bg s g = (1 s )(2 s g ) 2 g s Bs (11) Продифференцировав (11) находим, что (1 g )(1 s ) Bg 1s z s, z p(z) = Bs /Bg 2 g s Bs Рассмотрим случай для z Bs /Bg :

Bs /z zg Bg Bs FZ (z) = p(s, g ) ds dg + p(s, g ) ds dg = 0 0 Bs /z 1 g Bs Bs 1g 1g z g 1 + 1 z g 1 (12) = 2 s g Bg Bg Продифференцировав (12) находим, что (1 g )(1 s ) Bs 1g z g 2, z Bs /Bg p(z) = 2 g s Bg Таким образом плотность распределения случайной вели чины Z полностью определена.

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

Сборник статей молодых ученых факультета ВМК МГУ, № 10, 290 И. И. Четвёркин Для оценки полезности признака будет использоваться вза статистическая функция, отражаю имная информация I щая количество информации содержащееся в одной случай ной величине относительно другой. В качестве случайных ве личин мы будем рассматривать признак Странность Z и слу чайную величину, соответствующую классу T (оценочное или неоценочное) для заданного слова.

+ p(z, t) I(Z, T ) = p(z, t) · log dz = p(z) · p(t) t{0,1} + p(z | t = 1) p(z | t = 1)p(t = 1) log dz+ p(z) + p(z | t = 0) + p(z | t = 0)(1 p(t = 1)) log dz = p(z) = p(t = 1)DKL (p(z | t = 1) || p(z))+ + p(t = 0)DKL (p(z | t = 0) || p(z)) где DKL (p(z | t) || p(z)) дивергенция Кульбака–Лейблера, пока зывающая удаленность одного распределения от другого. Ис ходя из выражения взаимной информации через дивергенции Кульбака–Лейблера, возрастание значения дивергенции при водит к росту взаимной информации и, как следствие, к росту полезности признака Странность.

Дальнейшее изложение в данном разделе будет направле но на исследование значений параметров распределений слов, которые ведут к увеличению значений расстояний Кульбака– Лейблера. С учётом данных определений в предыдущих разде лах, рассмотрим поведение функции Кульбака–Лейблера при t = 1. Все вычисления и выводы будут верны и для случая t = 0. Предположим, что для распределение p(z | t = 1), z R+ подчиняется тем же законам, что и p(z), z R+ только с дру Сборник статей молодых ученых факультета ВМК МГУ, № 10, Анализ и применение признаков оценочных слов гими значениями параметров s1, Bs1. Также, будем полагать, что для всех коллекций выполнено неравенство s s1, по скольку в противном случае концентрация оценочных слов для высоких значений признака Странность будет минимальной.

Тогда имеет место следующая теорема:

Теорема 1. Функция DKL (p(x | t = 1) || p(x)) является моно тонно убывающей от параметра s1.

Доказательство. Для уменьшения объема выкладок обозна (1g )(1 ) чим константой H выражение 2g s s. Константа H1 бу дет обозначать аналогичное выражение в котором все вхож дения s заменены на s1. Дополнительно, предположим, что Bs = Bs1, что позволит существенно упростить преобразова ния, но часто имеет место на практике. Преобразуем интеграл:

+ p(z | t = 1) p(z | t = 1) log dz = p(z) Bs /Bg Bg H 1 Bg s s 1s z s s1 dz+ z s1 log = H Bs H Bs + Bs H 1g z g 2 log + dz = H Bg H Bs /Bg 1 s1 1 g H1 H 1 Bg s s = log + log + 2 s1 g 2 s1 g H H Bs Bs /Bg Bg 1s z s1 log z s s1 dz = + H Bs H1 (s s1 )(1 g ) Bg = log + log 2 s1 g H Bs Bg (1 s1 ) log + Bs H1 (s s1 ) = ) (1 s Сборник статей молодых ученых факультета ВМК МГУ, № 10, 292 И. И. Четвёркин 1 g H1 s s = log = 1 s1 2 s1 g H 1 s1 2 s g s s1 1 g (13) = log 2 s1 g 1 s 1 s1 2 s1 g Найдем частную производную от функции f (s1, s, g ), за данной выражением (13) по переменной s1 :

(g 1)(g + 2s1 3)(s1 s ) f (s1 ) (14) = (s1 1)2 (2 s1 g ) s Из выражения (14) видно, что при s1 s функция явля ется строго убывающей по s1. Теорема доказана.

Аналогичным образом можно показать, что функция f (s1, s, g ) является монотонно возрастающей от парамет ра s.

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

С помощью пакета zipfR в статистической среде R были найдены реальные значения для s1, s, g для всех коллек ций. Для коллекции отзывов пользователей о фильмах s1 = = 0.570, s = 0.582, для малой коллекции s1 = 0.625, s = = 0.661 и для коллекции описаний g = 0.408.

Можно заметить, что в данном случае не удается приме нить предложенный критерий для данной пары коллекций, т.к. пары параметров являются несравнимыми. В этом слу чае с помощью выражения (13) для дивергенции Кульбака– Лейблера можно вычислить точные значения и сравнить их.

Так, для коллекции отзывов DKL = 3 · 104, для малой кол лекции DKL = 6·103. Из найденных значений, можно сделать вывод, что малый корпус позволяет лучше дискриминировать оценочные слова, чем коллекция отзывов, что подтверждается Сборник статей молодых ученых факультета ВМК МГУ, № 10, Анализ и применение признаков оценочных слов показателями качества отдельных признаков, которые можно найти в работе [2].

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

5 Заключение В данной работе описан метод извлечения оценочных слов для заданной предметной области. При построении модели проведен анализ наиболее важного признака Странность и установлена теоретическая зависимость взаимной информации между признаком и меткой класса от параметров распределе ния слов в используемых коллекциях. Дополнительно, в явном виде было выведено выражение для вычисления дивергенции Кульбака–Лейблера, от которой зависит значение взаимной ин формации и которое может быть применено для оценки каче ства используемых коллекций.

Благодарности. Работа частично поддержана грантом РФФИ N11–07–00588-а.

Список литературы [1] Ahmad K., Gillam L., Tostevin L. University of Surrey par ticipation in Trec8: Weirdness indexing for logical document extrapolation and retrieval (wilder) // The Eighth Text RE trieval Conference (TREC-8). — 1999.

[2] Chetviorkin I. I., Loukachevitch N. V. Extraction of Russian Sentiment Lexicon for Product Meta–Domain // Proceed Сборник статей молодых ученых факультета ВМК МГУ, № 10, 294 И. И. Четвёркин ings of COLING 2012: Technical Papers. — 2012. P. 593— 610.

[3] Choi Y., Cardie C. Adapting a polarity lexicon using integer linear programming for domain-specic sentiment classica tion // Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing — 2009. — Vol.2.

P. 590–598.

[4] Ding X., Liu B., Yu P. S. A holistic lexicon-based approach to opinion mining // Proceedings of the international con ference on Web search and web data mining. — 2008. — P.

231–240.

[5] Esuli A., Sebastiani F. Determining the semantic orienta tion of terms through gloss classication // Proceedings of the 14th ACM international conference on Information and knowledge management. — 2005. — P. 617–624.

[6] Evert S. A simple LNRE model for random character se quences // Proceedings of the 7`mes Journes Interna e e tionales d’Analyse Statistique des Donnes Textuelles. — e 2004. — P. 411—422, Louvain-la-Neuve, Belgium.



Pages:     | 1 |   ...   | 3 | 4 || 6 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.