Кривцов В.Е., Бачурин А.И. (сост.), Дружинина В.А., Волкова И.А., Котова О.П., Себова Л.В. (ред.) и др. Труды 53-й научной конференции МФТИ: Современные проблемы фундаментальных и прикладных наук. Часть IX. Инновации и высокие технологии

Подождите немного. Документ загружается.

Секция концептуального анализа и проектирования 81

УДК 159.922

А.В. Черноухов

,В.М.Капустян

2,3,1

aleksandr.chernoukhov@phystech.edu, kapuvic@mail.ru

Московский физико-технический институт

(государственный университет)

Негосударственное исследовательское учреждение

«Институт информационных технологий»

Национальный исследовательский университет

Московский государственный строительный университет

Концептуальный анализ техник А.В. Курпатова

психотерапевтического сопровождения процесса

развития личности на этапе первой закрытой

модели

На сегодняшний день разные психотерапевтические школы име-

ют собственные теории личности, собственный язык описания и объ-

яснения проблем, собственные методы «лечения». Психотерапевты

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

данного больного и так и не прийти к какому-либо общему мнению.

Всё вышесказанное затрудняет, а порой и делает невозможным, объ-

единение опыта и знаний всех этих школ в некую общую систему,

позволившую бы психотерапии стать более эффективной. А необхо-

димость эффективной психотерапии очевидна.

Таким образом, становится понятно, что необходим некий общий

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

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

Первым шагом к достижению этой цели стало создание А.В. Кур-

патовым «Системной поведенческой психотерапии». Однако, по сло-

вам самого Курпатова, «Системная поведенческая психотерапия» —

это именно терапевтическая технология, позволяющая оказывать по-

мощь при различных психических расстройствах. Но не все психоло-

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

жит процесс развития личности. Он сопровождается личностными

кризисами, но их нельзя назвать «болезнью».

Ясно, что психотерапевтическое сопровождение процесса разви-

тия личности (ПСПРЛ) не вписывается в схему системной поведен-

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

82 53-я научная конференция МФТИ ФИВТ

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

как именно терапевтические техники психотерапии, так и нетерапев-

тические.

«Общий язык» — это понятийная схема. Таким образом, для его

создания требуется концептуализация (построение понятийной схе-

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

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

щей понятие ПСПРЛ на этапе первой закрытой модели (ПЗМ). Пер-

вая закрытая модель — это первый этап развития личности по Кур-

патову.

Для достижения поставленной цели в работе строится концепту-

альная схема, выражающая понятие «Процесс развития личности на

этапе ПЗМ», на основе которой выводится понятие «Психотерапевти-

ческое сопровождение процесса развития личности на этапе ПЗМ».

Полученные результаты являются основой для дальнейшей кон-

цептуализации ПСПРЛ, а затем и всей психотерапии. Выведенное

понятие «ПСПРЛ» позволяет понять, каким образом этот процесс

должен происходить, что необходимо для развития методов ПСПРЛ.

Литература

1. Курпатов А.В., Алёхин А.Н. Философия психологии. Новая

методология, 2 изд. — М.: ЗАО «ОЛМА Медиа Групп», 2006.

2. Курпатов А.В., Алёхин А.Н. Развитие личности. Психология

и психотерапия. — М.: ЗАО «ОЛМА Медиа Групп», 2007.

3. Курпатов А.В., Алёхин А.Н. Индивидуальные отношения. Тео-

рия и практика эмпатии. — М.: ЗАО «ОЛМА Медиа Групп», 2007.

Секция оценки эффективности

инвестиционных проектов

УДК 519.856

А.В. Докучаев

docuhaevrud@gmail.com

Самарский государственный технический университет

Дополнительное инвестирование сетевого проекта

методом динамического программирования

Поставлена задача эффективного инвестирования дополнительно-

го ограниченного ресурса для сокращения критического времени вы-

полнения сетевого проекта при неоднородном изменении дуг орграфа

проекта.

На основании списка предшествования работ проекта составля-

ются списки непосредственного предшествования. При необходимо-

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

построения графа проекта.

Далее методом динамического программирования решается зада-

ча оптимизации инвестирования дополнительного ресурса. Итераци-

онная процедура расчета продолжается до полного расходования до-

полнительного ресурса либо до наступления накладываемых на па-

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

84 53-я научная конференция МФТИ ФИВТ

УДК 37.022

П.Н. Степанов

petr.stepanov@gmail.com

Московский физико-технический институт

(государственный университет)

Особенности инвестиционных проектов

в дистанционном обучении

Инвестиционные проекты в дистанционном обучении имеют свои

характерные особенности [1], при этом одной из неформализуемых

особенностей дистанционного обучения является схожесть распреде-

ления инвестиций в дистанционном обучении с равномерным рас-

пределением: инвестиции проектов, реализующих на первый взгляд

«один и тот же» конечный продукт, могут лежать в достаточно ши-

роких пределах.

Целью исследования стало выяснение вопроса «почему это так и

от чего может зависеть объем инвестиций в тот или иной проект».

В качестве объекта исследования выступили электронные учебни-

ки — элементы дистанционного обучения, предназначенные для мак-

симально эффективной самостоятельной работы с материалом.

Рассматриваемые электронные учебники отличались формой из-

ложения материала, методическим подходом, характером разработки

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

В результате была показана эффективность создания курсов при

помощи т.н. редакторов электронных курсов [2]. Cформирована клас-

сификация программ-редакторов электронных курсов по целям того

или иного курса. Эффективность инвестиций в «похожие» проекты

(дано также и определение «похожести» в работе) оценивается при

помощи существующих методов оценки эффективности инвестицион-

ных проектов [3].

В рамках исследования был предложен способ дополнения учеб-

ных пособий, предназначенных для самостоятельной работы, кон-

текстно-зависимыми формами обратной связи с преподавателями,

т.н. тьюторами, которые при этом смогут удаленно давать консуль-

тации по запросу учащегося.

Сделан частный вывод о возможности создания электронных кур-

сов и степени применимости проекта по созданию данных курсов для

Секция оценки эффективности инвестиционных проектов 85

обучения студентов МФТИ в рамках одного из предметов учебного

плана на основе модульно-компетентностного подхода [4] с примене-

нием существующих редакторов электронных курсов от компаний

Adobe, Articulate и WebSoft, а также без применения таковых, ис-

ключительно с помощью плагина-надстройки к программе Microsoft

PowerPoint.

Литература

1. Хортон У., Хортон К. Электронное обучение: инструменты и

технологии. — М.: КУДИЦ-ОБРАЗ, 2005.

2. Исследование рынка технологий дистанционного обучения в

СНГ. Инструменты для разработки электронных курсов. Т. 4. —

Smart education, 2010.

3. Виленский, П.Л., Лившиц В.Н., Смоляк С.А. Оценка эффек-

тивности инвестиционных проектов. Теория и практика. — М.: Дело,

2008.

4. Труды 52-й научной конференции МФТИ «Современные про-

блемы фундаментальных и прикладных наук». Часть IX. Инновации

и высокие технологии. — М.: МФТИ, 2009.

Секция распознавания изображений

и обработки текста

УДК 004.052.32

А.В. Бузмаков

1,2

, В.М. Сапроненко

abuzmakov@gmail.com

Московский физико-технический институт

(государственный университет)

Компания «ABBYY»

Оценка схожести документа на выходе системы

распознавания символов и внутреннего

представления этого документа

Современная система распознавания символов состоит как мини-

мум из следующих этапов: считывание изображения, анализ изобра-

жения, выделение и распознавание символов, синтезирование доку-

мента, экспорт в требуемый формат. По исполнению первых 4 этапов

система получает документ в собственном формате. Для использо-

вания результатов системы пользователями необходимо произвести

экспорт документа — преобразование собственного формата в один

из общепринятых, таких, как docx, pdf. На этом этапе могут проис-

ходить различные ошибки. Задача — оценить качество выполнения

этого последнего этапа.

Вводится понятие блока, для картинки это прямоугольник картин-

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

качественной части текста, такой, как колонка или область колонти-

тула.

Ошибки могут наблюдаться на уровне отдельного символа (по-

теря форматирования, изменение видимости, изменение координаты

символа), на уровне слов (ранний или поздний переносы слова, раз-

рыв слова переносом), на уровне одного блока (существенное изме-

нение размеров, пропажа блока), на уровне нескольких блоков (визу-

альный порядок блоков, пропажа или появление наложения блоков)

Секция распознавания изображений и обработки текста 87

и документный уровень (другое кол-во страниц, колонтитулы или

сноски легли на неправильные страницы).

Для нахождения блоковых ошибок для каждой пары блоков на

исходном и конечном документе вычисляется набор метрик, на осно-

вании которых принимается решение о наличии или отсутствии той

или иной ошибки. В набор метрик входят: горизонтальные и верти-

кальные расстояния; один блок находится левее / выше / ниже /

правее другого, а также этого же отношении, но для охватывающих

прямоугольников блоков; расположение одного блока вертикально,

горизонтально или по обеим осям внутри другого блока; пересечение

блоков.

Для нахождения ошибок визуального порядка заводится набор

правил вида «наличие флага X в исходных метриках влечет необ-

ходимость флага Y конечных». При нарушении какого-либо из этих

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

блоков.

На основании найденных ошибок для каждой исходной страницы

вычисляется частота появления ошибки, средняя и максимальная се-

рьезность. А также такие же величины на документ целиком.

На основании полученных ошибок появляется возможность оце-

нивать эффективность правок в последнем этапе системы распозна-

вания символов, а также выбирать приоритеты исправления тех или

иных ошибок.

88 53-я научная конференция МФТИ ФИВТ

УДК 519.6

С.В. Голубев

Sergey_G@abbyy.com

Московский физико-технический институт

(государственный университет)

Компания «ABBYY»

Распознавание структурированных документов

с обучением на примерах

С повсеместным внедрением информационных технологий и си-

стем электронного документооборота серьезной проблемой становит-

ся преобразование информации с бумажных носителей в электрон-

ную форму. При этом имеется большой класс документов, имеющих

достаточно сложную логическую и графическую структуру, для кото-

рых сплошное распознавание текста методами оптического распозна-

вания символов не позволяет корректно извлечь информацию. Среди

методов извлечения информации из таких документов получили ме-

тоды, основанные на структурном распознавании образов [1, 2].

К этой группе методов относится технология распознавания

структурированных документов ABBYY FlexiLayout. В этой систе-

ме используется специализированная модель документа (структурное

описание), позволяющая достичь большей гибкости по сравнению с

простыми графовыми моделями [3]. Заметную сложность в примене-

нии данной системы представляет необходимость построения модели

документа вручную для каждого типа документа. Для решения этой

проблемы выглядит целесообразным применить методы машинного

обучения.

Предлагается система распознавания документов на основе ма-

шинного обучения, включающая следующие элементы:

1. Модуль распознавания, в качестве которого используется систе-

ма ABBYY FlexiLayout.

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

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

метрических отношений, в котором вершины соответствуют эле-

ментам структуры, а ребра задают относительные расстояния

между элементами.

Секция распознавания изображений и обработки текста 89

3. Модуль обучения, строящий обобщенную графовую модель на

основе примеров.

4. Модуль преобразования графовой модели в структурное описа-

ние FlexiLayout.

В рамках работы была проведена проверка точности распознавания

методом скользящего контроля. При этом была подтверждена при-

менимость системы для распознавания документов с полужесткой

структурой, при этом после обучения на 5--10 изображениях система

достигает точности 90--95% (процент ошибочно локализованных дан-

ных составляет 5--10%). Также система может использоваться для

распознавания форм с гибкой структурой, однако в этом случае тре-

буется больший размер обучающей выборки и доработка структурно-

го описания вручную.

Литература

1. Farrow G.S.D. [et al.]. Model Matching in Intelligent Document

Understanding // Proc. of ICDAR’95. — 1995.

2. Hirayama Y. Analyzing Form Images by Using

Line–Shared–Adjacent Cell Relations // Proc. of IAPR’96. — 1996.

3. Зуев К.А. Система идентификации структуры печатных доку-

ментов: дисс. ... канд. тех. наук. — М.: МГУЛ, 1999.

90 53-я научная конференция МФТИ ФИВТ

УДК 004.822

К.А. Грищенков

kirillgrish@gmail.com

Московский физико-технический институт

(государственный университет)

ООО «Аби Продакшн»

Семантический поиск на основе системы

полнотекстового поиска

Семантический поиск призван увеличить релевантность резуль-

татов поиска путем понимания намерений пользователя и значения

ключевых слов в контексте поискового запроса.

В настоящий момент в большинстве традиционных поисковых

систем используется релевантная модель оценки соответствия про-

индексированного документа поисковому запросу. Такая модель не

справляется с решением задач поиска омонимов (как лексических,

так и грамматических), синонимов, многозначных слов. Это вызва-

но тем, что релевантная модель основывается на лингвистическом

подходе, в то время как вышеперечисленные языковые сущности не

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

Для решения задачи преодоления вышеописанных недостатков

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

рования слов и последующего поиска по тегам.

Лежащая в основе система полнотекстового поиска используется

для создания индекса некоторого корпуса текстов и поиска по этому

корпусу текстов. Под корпусом текстов понимается некоторая сово-

купность документов, из которых может быть получен текст.

Система имеет морфологическую поддержку для нескольких язы-

ков и позволяет выполнять поиск различных форм слова, если слово

относится к одному из таких языков. Система позволяет искать не

только сами слова, но также и произвольные атрибуты, связанные со

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

Для получения атрибутов используется семантический анализ

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

каждой из которых задаются параметры разбора предложений. Для

каждого предложения результатом анализа является лучшее дерево

составляющих или в случае разбора с сохранением альтернатив —

несколько альтернативных деревьев. Из такого дерева для каждой

Секция распознавания изображений и обработки текста 91

составляющей получаются ее поверхностная позиция, глубинная по-

зиция в родительской составляющей, лексический класс ядра и грам-

матическое значение, кодируются идентификатором из базы данных

и записываются в атрибуты.

Язык запросов основан на XML. Пользовательский запрос

Object_Situation: механизм «механизм:

MECHANISM_AS_METHOD» < Inanimate Plural Noun >

означающий, что ищется слово «механизм», в отношении «Ситу-

ационный объект», относящееся к лексическому классу «механизм:

MECHANISM_AS_METHOD», с грамматическим значением «неоду-

шевленное существительное во множественном числе» трансформи-

руется в XML:

< Request >

< ... >

< Attribute > SE 4476 </Attribute >

< Attribute > CL 2781070 </Attribute >

< Attribute > GR 100001000 </Attribute >

< Attribute > GR 100001029 </Attribute >

< Attribute > GR 100000540 </Attribute >

</Request >

Поиск по этому запросу отметит слово «механизм» в предложе-

нии «В Израиле и Америке все еще есть механизмы для того, что-

бы интегрировать новых мигрантов.», но не отметит в предложении

«Привести механизм лебёдки в действие.»

В текущем виде система семантического поиска используется

лингвистами для отладки статистики классов, позиций полученной

по результатам семантического разбора базы параллельных текстов,

а также уточнения семантических описаний объектов в иерархии.

Литература

1. Manning Ch. D., Raghavan P., Schьtze H. Introduction to

Information Retrieval. — Cambridge University Press, 2008.

2. Кормен Т ., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы:

построение и анализ — Introduction to Algorithms / под ред. И.В.

Красикова. — М.: Вильямс, 2005. — 1296 с.

92 53-я научная конференция МФТИ ФИВТ

УДК 004.93

К.С. Гудков

goudkovs@ultranet.ru

Государственный научно-исследовательский институт

авиационных систем

Извлечение графических фрагментов

отсканированных документов

Задача перевода бумажной документации в электронный вид ра-

но или поздно встаёт перед любым предприятием. Одной из её подза-

дач является извлечение графических фрагментов отсканированных

документов. Сравниваются три подхода к её решению:

• Использование Open OCR CuneiForm [http://openocr.org/] и

COM-сервера Puma.

• Использование бинаризации с учётом разницы в RGB-компонен-

тах, поиска и обрамления контуров.

• Использование дилатации, эрозии, поиска и обрамления конту-

ров.

Для второго и третьего метода поиск и обрамление контуров осу-

ществляются при помощи библиотеки Intel OpenCV [1].

При использовании Open OCR CuneiForm по исходному отскани-

рованному документу создаётся RTF-файл, содержащий требуемые

графические компоненты, которые затем извлекаются и конвертиру-

ются в требуемый формат. Среди недостатков этого метода можно

указать высокую чувствительность к DPI при сканировании и невоз-

можность предоставить пользователю интерфейс по изменению гра-

ниц найденных графических фрагментов.

Второй метод — это преобразование цветного изображения к

чёрно-белому изображению в зависимости от разницы между RGB-

компонентами и поиск контуров на бинаризованном изображении.

Среди недостатков второго метода можно указать чувствительность

к выбору порога, сложности нахождения изображений, близких к гра-

дациям серого, и невозможность применения метода к отсканирован-

ным документам, содержащим фрагменты рукописного текста.

Секция распознавания изображений и обработки текста 93

Третий метод — это применение к исходному изображению морфо-

логических трансформаций [2], в частности, последовательное приме-

нение операторов дилатации и эрозии, и поиск контуров на бинари-

зованном изображении.

В работе проводится сравнительный анализ алгоритмов, предна-

значенных для извлечения графических фрагментов отсканирован-

ных изображений. Каждый из алгоритмов был реализован в виде

программы в среде программирования Delphi. Наилучшие результа-

ты были показаны при помощи третьего метода.

Литература

1. Bradsky G., Kaebler A. Learning OpenCV Computer Vision with

the OpenCV Library. — O’Reilly Media, Inc., 2008.

2. Serra J. Image Analysis and Mathematical Morphology. —

Academic Press, Inc., 1982.

УДК 81’322.4, 004.891.2

Е.В. Захожая

1,2

,В.И.Протасов

3,2

elena.zakhozhaya@gmail.com, protonus@yandex.ru

Московский физико-технический институт

(государственный университет)

Институт физико-технической информатики

Московский государственный горный университет

Применение генетических алгоритмов

для получения связного машинного перевода

текста

В докладе исследуется принципиальная возможность построения

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

горитмов [1]. Метод генетического консилиума [2] позволяет объеди-

нить различные подходы к машинному переводу [3] и вовлечь в про-

цесс перевода пользователя, и тем самым использовать неформали-

зованные знания человека для значительного улучшения точности и

связности перевода [4]. Существенным достоинством предложенного

метода является то, что пользователю достаточно знать лишь один

язык из двух, участвующих в переводе. К минусам метода можно

94 53-я научная конференция МФТИ ФИВТ

отнести его трудоемкость. В результате была показана принципиаль-

ная работоспособность метода, разработан детальный алгоритм и на

основе экспериментов выявлены общие закономерности.

В ходе работы текст переводится несколькими различными элек-

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

некоторой обработки и фильтровки каждый из полученных резуль-

татов переводится в обратном направлении. Процесс повторяется; ко-

личество итераций, через которое достигается результат, зависит от

сложности текста и направления перевода, а также желаемой точно-

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

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

имеем в наличии текст на знакомом пользователю языке, у пользо-

вателя есть возможность проследить, как выглядят тексты, получен-

ные разными электронными переводчиками. Пользователь выбирает

тот вариант перевода, который, по его мнению, наиболее удачен на

данной итерации, либо составляет их комбинацию. (Наиболее удач-

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

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

переводе с незнакомого.) Второй способ отсеивания слабых вариан-

тов проводится на этапе, на котором мы имеем варианты на незна-

комом пользователю языке. Отсеивание производится машиной на

основании сравнения варианта с исходным текстом, поэтому такое

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

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

правильное использование временных форм глагола. Как показали

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

менее точные и оставить в рассмотрении наиболее точные варианты

перевода.

Конец определяется пользователем: когда варианты, предостав-

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

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

тролирует точность перевода.

Гибридная система объединяет работу различных электронных

агентов, независимо от алгоритмов их работы, что позволяет учиты-

вать все возможные результаты, и в итоге получать их наилучшую

возможную комбинацию. Вовлечение человека дает возможность оце-

нивать комбинации с той точки зрения, с которой их видит конечный

потребитель перевода, а использование метода генетического конси-

лиума в основе системы обеспечивает тот факт, что полученная ком-

бинация является наилучшей.

Секция распознавания изображений и обработки текста 95

Литература

1. Турчин В.Ф. Феномен науки: кибернетический подход к эволю-

ции. — М.: ЭТС, 2000. — 368 с.

2. Протасов В.И. Конструирование метасистемных переходов в

интеллектуальных системах. — М.: Изд.-во Института физико-техни-

ческой информатики, 2009. — 186 с.

3. Сокирко А. Будущее машинного перевода // Компьютерра. —

2002. — № 21.

4. Федоров А.В. Основы общей теории перевода (лингвистические

проблемы). — СПб.: Филологический факультет СПбГУ; М.: «Фило-

логия–Три», 2002. — 416 с.

УДК 004.93

Л.А. Ицкович

,С.О.Кузнецов

2,3

Lev_I@abbyy.com, skuznetsov@hse.ru

Компания «ABBYY»

Государственный университет — Высшая школа экономики

Московский физико-технический институт

(государственный университет)

Методы машинного обучения в задаче

распознавания символов

Цель данной работы — определить, какие из известных призна-

ковых классификаторов и в какой степени подходят для решения

задачи распознавания символов. Рассмотрены метод ближайшего со-

седа [1], наивный байесовский классификатор [1], дерево решений [2],

классификатор на основе решёток формальных понятий [3], метод

опорных векторов [1].

В качестве базовой рассматривается схема печатного анализатора,

принятая в ABBYY OCR Technologies. Исходя из её устройства, фор-

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

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

распознанных символов; способность генерировать несколько вари-

антов распознавания (гипотез); способность оценивать уверенность

гипотез; высокое практическое быстродействие.

96 53-я научная конференция МФТИ ФИВТ

Рассматривается вопрос, возможно ли модифицировать извест-

ные признаковые классификаторы таким образом, чтобы они удовле-

творяли перечисленным требованиям. В частности, для генерации

списка гипотез и оценки их уверенностей с помощью дерева реше-

ний предлагается использовать различные варианты пост-фаззифи-

кации дерева решений [4] или комбинирование гипотез, полученных

от нескольких деревьев решений — случайного леса [5].

С использованием базы изображений и их омнифонтовых призна-

ков, принятых в ABBYY OCR Technologies, проведено сравнение ко-

личественных характеристик рассматриваемых алгоритмов. По каче-

ству распознавания (рис. 1) лучшим признан алгоритм на основе слу-

чайного леса. По способности правильно оценивать уверенности гипо-

тез (рис. 2) при малых разрешённых длинах списка гипотез лучшим

оказывается наивный байесовский классификатор, при больших —

алгоритм на основе случайного леса.

Литература

1. Hastie T., Tibshirani R., Friedman J. The elements of statistical

learning. — New York: Springer–Verlag, 2001. — 745 p.

2. Mitchell T.M. Machine Learning. — New York: McGraw-Hill,

1997. — 414 p.

3. Ицкович Л.А., Колотиенко С.С., Кузнецов С.О. Распознавание

символов с помощью решёток формальных понятий и сравнительный

анализ метода с другими алгоритмами распознавания символов //

Труды 51-й научной конференции МФТИ «Современные проблемы

прикладных и фундаментальных наук». — 2008. — Т. 9. — С. 121--123.

4. Chiang I.-J., Hsu J.Y.-J. Fuzzy classiﬁcation trees for data analysis

// Fuzzy Sets and Systems. — 2002. — V. 130. — P. 87--99.

5. Breiman L. Random forests // Machine Learning. — 2001. — V. 45,

N. 1. — P. 5--32.

Секция распознавания изображений и обработки текста 97

Рис. 1. Зависимость процента случаев, когда правильная гипотеза

попала в список, от длины списка гипотез

Рис. 2. Параметрическая зависимость: процент случаев, когда пра-

вильная гипотеза попала в список (при данной уверенности отсе-

чения), от средней длины списка гипотез (при данной уверенности

отсечения)

98 53-я научная конференция МФТИ ФИВТ

УДК 004.054

А.А. Незнанов

1,2

,М.В.Кривошеев

2,3

aneznanov@hse.ru, internalprogramerror@gmail.com

Государственный университет — Высшая школа экономики

Московский физико-технический институт

(государственный университет)

ООО «Аби Продакшн»

Методологии, методики и инструменты

юзабилити-тестирования

Начало развития области «юзабилити» как науки было положе-

но в 1960 году, когда Д.Р. Ликлидер постулировал концепцию «че-

ловеко-компьютерного симбиоза», которую в дальнейшем стали на-

зывать человеко-машинным интерфейсом. Юзабилити-исследования

особенно бурно начинают развиваться с начала 90-х годов с вовле-

чением подавляющего большинства активного населения в общение

с компьютерными системами [1]. С тех пор непрерывно повышается

актуальность проблемы получения оценок качества интерфейса ма-

шины с пользователем — юзабилити-тестирования.

Как оценки, так и само качество — понятия в достаточной степени

субъективные, поэтому принято считать, что одна из основных задач

юзабилити-тестирования — измерение субъективной удовлетворённо-

сти пользователя.

Даже среди специалистов существуют разные определения юзаби-

лити. Международный стандарт ISO9241-11 определяет юзабилити

как «степень, с которой продукт может быть использован определён-

ными пользователями при определённом контексте использования

для достижения определённых целей с должной эффективностью,

продуктивностью и удовлетворённостью». При этом относительная

важность всех трёх аспектов определяется упомянутым контекстом.

Начав с классических экспертных оценок: интервью, анкетирова-

ния и тестов, юзабилити-тестирование оформилось в развитую техно-

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

мализованной области гуманитарных исследований. И лишь в послед-

ние годы в данной области начали реально использоваться инстру-

ментальные средства объективного контроля, позволяющие следить

за биотоками мозга, движениями зрачков и другими параметрами ис-

Секция распознавания изображений и обработки текста 99

пытуемого, а также обрабатывать эту информацию с помощью разви-

тых средств анализа данных, в том числе с использованием элементов

искусственного интеллекта.

В данной работе:

• Приведены некоторые меры юзабилити, оценена возможность

объективной оценки и возможность её автоматического получе-

ния с учётом формализованных моделей пользователей.

• Описаны несколько методик оценивания юзабилити, их досто-

инства и недостатки.

• Исследованы современные инструментальные средства, способ-

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

жению его стоимости и повышению объективности, а следова-

тельно, и качества.

Литература

1. Woodson W.E., Tillman P., Tillman B. Human Factors Design

Handbook. — McGraw-Hill Professional, 1992. — 1056 p.

2. Купер А. Психбольница в руках пациентов или почему высокие

технологии сводят нас с ума и как восстановить душевное равнове-

сие. — СПб.: Символ–Плюс, 2005. — 336 с.

3. Головач В.В. Дизайн пользовательского интерфейса

.Искус-

ство мыть слона. — 2010. — 94 с.

100 53-я научная конференция МФТИ ФИВТ

УДК 519.175.1

А.А. Незнанов

1,2

, А.Ю. Кожевников

2,3

aneznanov@hse.ru, alex-kozh@yandex.ru

Государственный университет — Высшая школа экономики

Московский физико-технический институт

(государственный университет)

ООО «Аби Продакшн»

Исследование современных алгоритмов решения

задач различения графов общего вида

Задача установления изоморфности двух графов имеет важное

значение в таких областях, как машинное зрение [5], анализ изобра-

жений [6], обработка данных. Однако это сложная задача, находяща-

яся на границе классов P иNP.

Применяются два основных подхода к проблеме изоморфизма: на-

хождение канонического представления (канкода) графа и построе-

ние явного изоморфного отображения. Первый подход имеет боль-

ший практический интерес, так как позволяет создавать индексируе-

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

более эффективных алгоритмов канонизации графа был предложен

Бренданом Мак–Кеем в 1981 году [1] и реализован им в постоянно

обновляемой открытой библиотеке nauty [2]. Для подавляющего боль-

шинства семейств графов стандартные реализации этого алгоритма

являются полиномиальными, но для некоторых семейств производи-

тельность резко деградирует. Существуют специально сконструиро-

ванные семейства (например, [4]), иллюстрирующие экспоненциаль-

ность.

Вторым рассматриваемым в докладе алгоритмом (GIA) является

полиномиальный алгоритм, представленный в работе [3]. Он также

разработан для построения канкода специального вида, однако ис-

пользует кардинально отличный от [1] подход на основе «полных»

инвариантов. В работе показано, что предложенная система инвари-

антов не является полной и приведены контрпримеры к решению

задачи установления изоморфности. Также рассмотрены вопросы вы-

числительной сложности и приводятся результаты объёмных вычис-

лительных экспериментов.

В данной работе: