Методи нейромережевого розподіленого представлення та пошуку схожих символьних послідовностей в задачах класифікації на основі міркувань за прикладами

2. Розроблені, проаналізовані та реалізовані методи розподіленого представлення послідовностей, які за рахунок використання локально-чуттєвого хешування забезпечують малу ресурсоємність та сублінійний час пошуку приблизних найближчих послідовностей відносно розміру бази прикладів. Експериментальне дослідження якості пошуку на штучних даних показало достатність використання на практиці менших, ніж визначено аналітично, значень параметрів методу, що дозволяє зменшити ресурсоємність пошуку.

3. Запропонований метод нейромережевого розподіленого представлення послідовностей, який використовує рандомізацію векторних представлень і зв'язування елементів послідовності з їхніми позиціями, забезпечує уніфікацію формату представлення і можливість використання мір схожості векторних представлень для оцінки схожості послідовностей.

4. Розроблені методи пошуку схожих послідовностей за допомогою кластеризації за довжиною послідовностей та їх вирівнювання забезпечують пошук послідовностей різної довжини в реальних базах даних і розв'язання прикладних задач пошуку дублікатів і спаму на основі міркувань за прикладами за рахунок використання розподілених представлень і локально-чуттєвого хешування.

Ефективність і практична значимість розроблених методів підтверджені порівнянням отриманих результатів з відомими. Так, при пошуку дублікатів у базі РОМІП результат покращено на 20-40%, на базі Reuters-21578, - на рівні відомих. Перспективність застосування цих методів для виявлення спаму в великих поштових серверах показано на прикладі оцінки кількості спаму в колекціях електронних листів TREC Spam Track 2006 і 2005, де виявлено до 80% спаму при рівні неправильно класифікованих легальних повідомлень 5-10%.

5. Розроблені методи представлення і пошуку послідовностей забезпечують розв'язання прикладних задач класифікації ділянок ДНК і виявлення вторгнень, що підтверджує ефективність використання міркувань на основі прикладів для обробки послідовностей в реальних базах даних.

У задачі класифікації ділянок ДНК пошук екзонів з використанням підходу на основі міркувань за прикладами пришвидшено в 750 раз при збереженні якості на рівні відомих у цій області результатів. Розроблений метод пошуку послідовностей може застосовуватися при більш широкій області значень параметрів, ніж випливає з теоретичного аналізу, що експериментально показано на прикладі задачі пошуку некодуючих ділянок бета-глобіну при обробці коротких рядків. Запропонований метод є перспективним також для застосування в реальних системах виявлення вторгнень до комп'ютерних систем, що підтверджується результатом класифікації аудит-послідовностей, де отримано точність класифікації на рівні понад 90%.

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

ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНІ В ТАКИХ ПРАЦЯХ

1. Резник А. Нейросетевая идентификация пользователей компьютерных систем / А. Резник, Н. Куссуль, А. Соколов // Кибернетика и вычислительная техника. - 1999. - Вып. 123. - С. 70-79.

2. Соколов А. Обнаружение аномалий с помощью марковских цепей переменного порядка // Искусственный интеллект. - 2002. - №4. - С. 74-83.

3. Соколов А. Современные модели обнаружения аномалий в компьютерных системах // Управляющие системы и машины. - 2004. - №5. - С. 67-73.

4. Гриценко В. Концепция и архитектура программного нейрокомпьютера SNC / В. Гриценко, И. Мисуно, Д. Рачковский, А. Соколов // Управляющие системы и машины. - 2004. - №3. - С. 3-14.

5. Мисуно И. Поиск текстовой информации с помощью векторных представлений / И. Мисуно, Д. Рачковский, С. Слипченко, А. Соколов // Проблемы программирования - 2005 - №4 - С.50-67.

6. Мисуно И. Модульный программный нейрокомпьютер SNC: реализация и применение / И. Мисуно, Д. Рачковский, Е. Ревунова, А. Соколов // Управляющие системы и машины. - 2005. - №2. - С. 74-85.

7. Sokolov A. Approaches to sequence similarity representation / A. Sokolov, D. Rachkovkij // Int. Journal of Information Theories and Applications. - 2006. - V. 13, №3. - P. 272-278.

8. Соколов А. Векторные представления для эффективного сравнения и поиска похожих строк // Кибернетика и системный анализ. - 2007. - №4. - С. 18-38.

9. Sokolov A. Searching for Nearest Strings with Neural-like String Embedding // Int. Journal of Information Theories and Applications. -- 2007. -- V. 14. - №3. - P. 294-299.

10. Соколов А. Исследование ускоренного поиска близких текстовых последовательностей с помощью векторных представлений // Кибернетика и системный анализ. - 2008. - №4. - С. 32-47

11. Соколов А. Рандомизированное вложение расстояния редактирования в задачах поиска генов и обнаружения вторжений // Системные технологии. - 2008. Вып. 2 (55). - С. 126-139.

12. Misuno I. SNC: The software neurocomputer with modular architecture / I. Misuno, D. Rachkovskij, E. Revunova, A. Sokolov // Междунар. конф. "Проблемы нейрокибернетики". - Ростов-на-Дону, Россия, 2002 - Т. 2. - С. 109-113.

13. Sokolov A. On Handling Replay Attacks in Intrusion Detection Systems // Proc. of X-th Int. Conf. Knowledge-Dialogue-Solution. - Varna, Bulgaria, 2003. - P. 258-265.

14. Sokolov A. An adaptive detection of anomalies in user's behavior // Proc. of the Int. Joint Conf. on Neural Networks. - Portland, USA, 2003. V. 4. - P. 2443-2447.

15. Sokolov A. Some approaches to distributed encoding of sequences / A. Sokolov, D. Rachkovskij // Proc. of XI-th Int. Conf. Knowledge-Dialogue-Solution. - Varna, Bulgaria, 2005. - V. 2. - P. 522-528.

16. Мисуно И. Обработка текстовой информации с помощью векторных представлений / И. Мисуно, Д. Рачковский, С. Слипченко, А. Соколов // Международный семинар по индуктивному моделированию МСИМ-05 (IWIM-05). - Киев: 2005. - Т. 1 -C. 230-236.

17. Рачковский Д. Концепция и методы нейросетевого распределенного представления информации в задачах искусственного интеллекта / Д. Рачковский, И. Мисун, Е. Ревунова, А. Соколов // Междунар. конф. "Проблемы нейрокибернетики". - Ростов-на-Дону, Россия: 2005. - Т. 2. - C. 30-33.

18. Sokolov A. Nearest string by neural-like encoding // Proc. of the XII-th Int. Conf. Knowledge-Dialogue-Solution. - Varna, Bulgaria, 2006. - С. 101-106.

АНОТАЦІЯ

Соколов А. М. Методи нейромережевого розподіленого представлення та пошуку схожих символьних послідовностей в задачах класифікації на основі міркувань за прикладами. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.23 - системи та засоби штучного інтелекту. - Міжнародний науково-навчальний центр інформаційних технологій та систем НАН України і МОН України, Київ, 2008.

Дисертаційна робота присвячена розробці та дослідженню методів розподіленого представлення символьних послідовностей на основі розробленого q-грамного методу вкладення простору із класичною метрикою редагування в векторний простір з метрикою ?₁.

Розроблено детермінований q-грамний метод вкладення простору символьних послідовностей фіксованої довжини над скінченним алфавітом з класичною метрикою редагування в векторний простір з метрикою ?₁. Завдяки використанню підрядків змінної довжини поліпшено якість апроксимації відстані редагування порівняно з відомими методами, що продемонстровано аналітично шляхом застосування апарату графів де Брейна і чисельно на штучних даних.

На основі розробленого детермінованого методу запропоновано локально-чуттєву функцію для класичної відстані редагування, що продукує розподілене представлення послідовностей, яке забезпеченує малу ресурсоємність і можливість створення ефективної процедури пошуку приблизних найближчих послідовностей за сублінійний до розміру бази час - базової операції підходу на основі міркувань за прикладами. Чисельні експерименти показали можливість використання менших, ніж отриманих теоретично, значень параметрів процедури. Розроблені методи пошуку схожих послідовностей за допомогою кластеризації за довжиною послідовностей та вирівнювання довжини, що дало змогу виконувати пошук приблизних найближчих послідовностей різної довжини у реальних базах даних.

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

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

АННОТАЦИЯ

Соколов А. М. Методы нейросетевого распределенного представления и поиска сходных символьных последовательностей в задачах классификации на основе рассуждений по примерам. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.23 - системы и средства искусственного интеллекта. - Международный научно-учебный центр информационных технологий и систем НАН Украины и МОН Украины, Киев, 2008.

Диссертационная работа посвящена разработке и исследованию методов распределенного представления символьных последовательностей на основе разработанного q-граммного метода вложения пространства с классической метрикой редактирования в векторное пространство с метрикой ?₁.

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

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

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

Метод применен в ряде прикладных задач. В задаче поиска дубликатов в базе РОМИП результат улучшен на 20-40%, в базе Reuters-21578 - получены результаты на уровне известных. Показана перспективность использования разработанного метода поиска для обнаружения спама на основе рассуждений по примерам в крупных почтовых серверах. В базе электронных писем TREC Spam Track 2006 обнаружено до 80% спама при уровне неправильно классифицированных легальных сообщений 5-10%. В задаче классификации участков ДНК благодаря применению разработанного метода поиск экзонов ускорен в 750 раз при сохранении качества на уровне известных результатов работ, использующих подход на основе рассуждений по примерам. Разработанный метод поиска последовательностей может применяться в более широкой области значений параметров, чем следует из теоретического анализа, что экспериментально показано в задаче поиска некодирующих участков бета-глобина. Разработанный метод перспективен для применения в системах обнаружения вторжений, что подтверждается результатом классификации аудит-сессий пользователей компьютерных систем, где получена точность классификации на уровне более 90%.

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

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

ABSTRACT

Sokolov A. M. Neural-like distributed representations and similar sequences search for classification with case-based reasoning. - Manuscript.

Ph.D. thesis for acquiring scientific degree of Candidate of Technical Science on specialization 05.13.23 - Systems and Means of Artificial Intelligence. - International research and training center for informational technologies and systems, National Academy of Sciences of Ukraine and Ministry of Science and Education of Ukraine, Kyiv, 2008.

The dissertation is devoted to the development and investigation of methods for distributed representations of symbol sequences, based on the developed q-gram method of embedding sequence space endowed with classic edit metrics to the ?₁ vector space.

A deterministic q-gram method was developed, that embeds the space of symbol fixed length sequences over a finite alphabet endowed with classic edit metrics to the vector space with ?₁-metrics. The usage q-grams of different lengths has improved approximation quality compared to known methods. This was shown analytically by using de Bruin graphs for sequence representation.

Based on the developed deterministic method, a locality-sensitive hash-function was proposed for the classic edit distance. The function produces distributed representation of sequences, leading to a lower resource requirements and an effective approximate nearest sequence search procedure in sublinear time (on the number of sequences in the base). This search is a basic operation involved in cased-based reasoning approaches. Numeric experiments showed that it is possible to use lower than theoretically derived parameter values. Search methods for similar sequences of different length were also developed. This made possible the approximate sequence search in real-world datasets containing sequences of different length.

The method was applied to a number of real-world applications, where either results improving quality of the known ones were obtained or results that improve search time, while showing comparable performance. All methods were implemented in software that can be used in artificial intelligence systems.

Keywords: data representation, distributed vector representations of sequences, edit distance embedding, duplicates search, spam detection, gene search, intrusion detection, neural networks.

Размещено на Allbest.ru