національна академія наук україни

інститут ПРОБЛЕМ математичних машин і систем

МІСУНО Іван Семенович

УДК 004.8 : 004.032.26

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

05.13.23 – Системи та засоби штучного інтелекту

Автореферат

дисертації на здобуття наукового ступеня
кандидата технічних наук

Київ – 2006

Дисертацією є рукопис.

Робота виконана у Міжнародному науково-навчальному центрі інформаційних технологій та систем НАН і МОН України.

Науковий керівник: кандидат технічних наук
Рачковський Дмитро Андрійович,
Міжнародний науково-навчальний центр
інформаційних технологій та систем НАН і МОН України,
старший науковий співробітник

Офіційні опоненти: доктор технічних наук, професор
Гладун Віктор Полікарпович,
Інститут кібернетики ім. В.М. Глушкова НАН України,
в.о. завідувача відділу

доктор технічних наук, професор
Замаруєва Ірина Вікторівна,
Військовий інститут Київського національного університету ім. Тараса Шевченка,
професор

Провідна установа: Державний науково-дослідний інститут інформаційної інфраструктури Державного департаменту з питань зв'язку та інформатизації України та Національної академії наук України, відділ високопродуктивних обчислювальних систем, м. Львів

Захист відбудеться “_25_” _жовтня____ 2006 року о _14_ годині на засіданні спеціалізованої вченої ради Д 26.204.01 в Інституті проблем математичних машин і систем НАН України за адресою: 03187, м. Київ-187, проспект Академіка Глушкова, 42.

З дисертацією можна ознайомитись у бібліотеці Інституту проблем математичних машин і систем НАН України за адресою: 03187, Київ-187, проспект Академіка Глушкова, 42.

Автореферат розісланий “_19_” __вересня__ 2006 року.

Вчений секретар

спеціалізованої вченої ради, к.т.н. Ходак В.І.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

Для розв’язання задач пошуку і класифікації ключовою проблемою є вибір адекватних форм і ефективних методів представлення і обробки інформації. Найбільш перспективними в цьому плані є векторні представлення, які дозволяють використовувати ефективні методи обробки – лінійні моделі, асоціативну пам'ять, знаходження схожості скалярним добутком та ін. Векторні представлення широко використовуються в нейромережевому підході (М.М. Амосов, О.І. Галушкін, В.П. Гладун, В.Л. Дунін-Барковський, О.М. Касаткін, Л.М. Касаткіна, Б.В. Крижановський, В.Г. Редько, О.М. Різник, З.Л. Рабінович, І.О. Рибак, О.О. Фролов, J.T.F.B.D.та ін.) і, зокрема, в нейромережевих розподілених представленнях (Е.М. Куссуль, Д.А. Рачковський, P.T.J.та ін.). Перспективність векторних представлень і методів обумовлена також тим, що вони можуть бути природним чином інтегровані в більш розвинені концепції і системи штучного інтелекту (ШІ), зокрема, у системи обробки структурованої інформації.

Зростання обсягу і складності інформації, що обробляється, вимагає підвищення швидкодії і точності рішення задач пошуку і класифікації. Обчислювальна ефективність обробки векторних представлень текстів і зображень у значній мірі залежить від розмірності таких представлень. Це обумовлює важливість задачі зменшення розмірності векторів (D.D.J.M.Y.та ін.), зокрема, шляхом відбору інформативних ознак або використання розподілених представлень. Інша актуальна задача – це підвищення якості самих методів класифікації багатовимірних векторних представлень (Y.J. Platt, R.E.A.J.V.Е.М. Куссуль).

Перспективним шляхом інтелектуалізації сучасних систем обробки текстової інформації є використання семантики. Поширені методи повнотекстового пошуку (С.S.G.H-P.та в Інтернет (R.Yates, S.A.L.здійснюють пошук безпосередньо за словами запиту або вимагають використання дорогих лінгвістичних ресурсів – тезауруси, онтології, що конструюються людьми (C.G.N.І.В. Замаруєва, С. Ніренбург, В. Раскін). Тому актуальним є розвиток методів автоматичного формування відповідних векторних представлень (S.S.T.S.

Важливим аспектом подальшого розвитку систем і технологій ШІ є уніфікація методів і алгоритмів обробки інформації, засобів їх реалізації у прикладних системах та створення універсальних і спеціалізованих інструментально-технологічних засобів розробки інтелектуальних ІТ (наприклад, MathLab, NeuralWare, MNN-CAD та ін.).

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

Зв’язок роботи з науковими програмами, планами, темами.
Робота виконувалася у відповідності з планами наукових досліджень відділу Міжнародного науково-навчального центру інформаційних технологій і систем в таких науково-дослідних роботах: “Розробка та дослідження нейромережевих методів моделювання когнітивних процесів № ДР U002685 (2001-2003); “Дослідження та розроблення нових інтелектуальних інформаційних технологій на основі використання високоефективних нейромережевих методів та алгоритмів” № ДР U002070 (2002-2006); “Розробка та дослідження нейромережевих інформаційних технологій роботи з базами знань” № ДР 0104U003191 (2004-2006); “Створити засоби автоматичної обробки інформації із застосуванням міркувань за аналогіями” № ДР U008280 (2003-2006); “Створити дослідні зразки нейрокомп’ютерів нових поколінь” № ДР U006718; за Державною науково-технічною програмою “Образний комп'ютер”: “Технологія, методи, алгоритми визначення міри семантичного зв’язку слів” № ДР U005512 (2002); “Розробити комп’ютерну технологію цілеспрямованої обробки текстової і аудіоінформації” № ДР U005770 (2003); “Розробити інтелектуальні інформаційні технології розпізнавання та ідентифікації аудіо-відеоінформації на основі нейромережевих технологій” № ДР U008324 (2004).

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

Відповідно до мети в роботі поставлені такі задачі:

- розробити методи добору інформативних ознак для векторних представлень даних;

- розробити методи підвищення якості класифікації даних, які мають векторне представлення;

- розробити методи формування векторних представлень текстової інформації, що враховують її семантичну близькість;

- розробити методи обчислювально ефективної обробки багатовимірних розріджених векторних представлень;

- експериментально дослідити ефективність і якість розроблених методів у задачах пошуку і класифікації візуальної і текстової інформації;

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

Об’єкт дослідження – комп'ютерні системи пошуку і класифікації текстової і візуальної інформації.

Предмет дослідження – представлення й обробка інформації: векторні представлення текстової і візуальної інформації, методи й алгоритми пошуку і класифікації, штучні нейронні мережі, нейрокомп’ютери.

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

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

- вдосконалено методи добору бінарних інформативних ознак шляхом розробки процедур ранжирування, що відрізняються застосуванням нового критерію надмірності та відомих критеріїв інформативності, а також можливістю добору ознак у процесі їхнього формування;

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

- вдосконалено і систематично досліджено методи нейромережевого класифікатора LIRA шляхом введення процедур добору ознак, об'єднання множинних результатів класифікації, введення відмови від класифікації, а також модифікації правил навчання;

- вперше розроблено методи автоматичного формування розподілених векторних представлень текстової інформації з дискретними елементами, що враховують її семантичну близькість, шляхом використання текстів навчальної бази як контекстів під час формування контекстних векторів;

- вдосконалено методи пошуку і класифікації текстів із урахуванням семантичної близькості, що відрізняються використанням контекстних векторів з дискретними елементами;

- з метою підвищення обчислювальної ефективності вдосконалено методи виділення ознак, класифікації, пошуку, обчислення взаємної інформації завдяки уніфікованому застосуванню методу індексування під час оперування розрідженими векторними представленнями;

- розроблені нові засоби підтримки інтелектуальних інформаційних технологій, спрямованих на класифікацію і пошук текстової інформації, що відрізняються використанням оригінальних методів формування й оперування векторними представленнями інформації;

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

Практичне значення одержаних результатів. На основі розроблених методів створені програмні засоби для реалізації ІТ класифікації і пошуку:

- програмний нейрокомп’ютер SNC – інструментальний засіб розробки і реалізації нейромережевих інформаційних технологій;

- CommonLіb – об’єктно-орієнтована бібліотека класів на С++, що реалізує ефективне оперування розрідженими розподіленими векторними представленнями в прикладних системах;

- Classifier Toolbox – програмні модулі класифікації зображень і текстів, а також програмні інтерфейси, що підтримують самостійне застосування модулів та розширення набору класифікаторів у SNC;

- Feature Toolbox – програмні модулі, що реалізують розроблені методи добору інформативних ознак і орієнтовані на використання в задачах, рішення яких пов'язано з оперуванням багатовимірними векторними бінарними ознаковими представленнями;

- Semantіc Toolbox – програмні модулі інтелектуальної обробки текстової інформації з елементами врахування семантики;

- TextSearch, TextClassifier – макети систем пошуку і класифікації текстів.

Створене програмне забезпечення використовується в наукових і практичних цілях, що підтверджується відповідними актами: Міністерства промислової політики України (від 26.10.2005 р.); НДІ нейрокібернетики Ростовського державного університету (від 29.09.2005 р.); ТОВ “Інтермедіа комунікації” (від 21.02.2006 р.).

Особистий внесок здобувача. У роботах, написаних у співавторстві й опублікованих у профільних виданнях, внесок здобувача полягає в наступному. [1, ] – проектування системної архітектури і реалізація ядра, обчислювальних блоків, засобів проведення серійних експериментів програмного нейрокомп’ютера SNC; проведення досліджень задач класифікації й обробки даних. [3, 5] – методи формування й розробка систем розподілених представлень текстової інформації за контекстами документів; методи і системи пошуку текстів за такими представленнями, експериментальні дослідження. [4] – методи добору ознак за критеріями інформативності та дублювання, об’єднання множинних результатів класифікації, модифікації персептроноподібного класифікатора; дослідження на базі MNIST. [7, 9] – реалізація методів розподіленого кодування інформації (числової, текстової, зображень), розробка модифікованого класифікатора-персептрона, проведення та обробка результатів експериментів. [8] – розробка засобів представлення і розгортання епізодів-аналогів за допомогою XML-мови описування, розробка системи ефективного пошуку представлень епізодів. [10, 11] – розробка і реалізація ефективних методів обчислення перекриття розподілених представлень.

Апробація результатів дисертації. Результати дисертаційного дослідження були повідомлені на XІІІ, XІV Міжнародних конференціях з нейрокібернетики (Ростов-на-Дону, 2002, 2005); X-th Іnt. Conf. “Knowledge-Dіalogue-Solutіon” KDS_(Bulgarіa, 2003); V Всеросійській науково-технічній конференції “Нейроінформатика-2003” (Москва); Міжнародному семінарі з індуктивного моделювання МСІМ-05 (Київ, 2005); постійно діючому семінарі “Проблеми нейрокомп’ютерів і нейромереж” (Київ, ІПММС та МННЦІТтаС, 2001-2006); у школі-семінарі “Про проблеми образного мислення” (Жукін, 2005).

Публікації. Основні результати дисертації викладені у 17 друкованих працях, у тому числі 11 – у фахових виданнях, рекомендованих ВАК України для спеціальності 05.13.23, з них 1 одноосібна та 6 тез доповідей на наукових конференціях.

Структура дисертації. Дисертація складається із вступу, п’яти розділів, висновків, списку використаних джерел із 148 найменувань, 2 додатків. Обсяг дисертації становить 148 сторінок основного тексту, включаючи 33 рисунка і 4 таблиці.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

У першому розділі дано огляд сучасного стану робіт в області пошуку і класифікації текстової і візуальної інформації.

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

Поряд із задачами класифікації із зростанням обсягів інформації, що доступна в електронній формі, все більше значення набувають задачі пошуку. Сучасні методи пошуку текстової інформації засновані на моделях векторних просторів VSM. У цих моделях компоненти текстів, такі, як слова, словосполучення, фрагменти текстів або цілі документи, представлені багатовимірними векторами. Елементами векторів є значення деякої функції від частоти спільного знаходження компонентів текстів і їхніх контекстів. Ступінь подібності між компонентами текстів визначається величиною подібності між їхніми векторами, наприклад, скалярним добутком. Однак традиційні моделі векторних просторів не враховують семантичну близькість текстової інформації. Це стосується і задач класифікації текстової інформації. Для врахування семантичної близькості використовують методи, засновані на узагальненій моделі векторних просторів GVSM, а також розкладання за сингулярним значенням LSA, які є обчислювально складними при великих розмірностях простору ознак, типових для великих текстових масивів.

Таким чином, підвищення ефективності розв’язання задач пошуку і класифікації текстів і зображень потребує розвитку методів пошуку і класифікації інформації, що представлена у векторному форматі, створення уніфікованих засобів програмно-алгоритмічної підтримки і розробки нових та вдосконалення існуючих ІТ у напрямку підвищення обчислювальної ефективності, точності та привнесення якісно нових можливостей, що здатні забезпечити більш високий рівень інтелектуальної обробки інформації. Задачі пошуку і класифікації є типовими для ШІ, і створення нових методів та засобів їх вирішення є важливим не тільки в практичному плані, але і дозволить розширити теоретичну базу ШІ. Це обумовлює актуальність спрямованості дисертаційної роботи на підвищення ефективності рішення задач пошуку і класифікації на основі векторних представлень.

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

Для скорочення розмірності векторних просторів з метою підвищення обчислювальної ефективності методів класифікації розроблено методи добору ознак, що використовують критерії інформативності і дублювання на основі взаємної інформації Шеннона. Ознаки розглядаються як незалежні (чи попарно залежні) для того, щоб уникнути експонентного росту числа членів під час обчислення взаємної інформації. Взаємна інформація між бінарною ознакою f і класами з множини С дорівнює

. | ()

Критерій дублювання ознаки f відносно множини ознак G

RE(f,G) = maxgG MI(f, g) / MI(g, g), | ()

де MI(f, g) – взаємна інформація двох бінарних ознак.

Нехай F{k} – шукана множина ознак потужністю k, Q1 – відношення числа переглянутих ознак до числа відібраних, – поріг до величини . Добір множини ознак виконується такою процедурою (а також її варіантами):

1. З початкової множини ознак F{Qk} береться qk (1?q?Q) ознак з максимальною величиною , і ці ознаки включаються у проміжну множину F{qk}:

F0{qk} = ; Fi{qk} = { f = } Fi–1{qk}, i=1,…, qk; F{qk} = Fqk {qk}.

2. Відібрані ознаки нумеруються: ознаці призначається номер vRE(f) за зростанням міри дублювання RE(f, F{qk}) і номер vMI(f) за зменшенням взаємної інформації MI(f,C). Рангом ознаки f є величина vRE(f)+vMI(f):

vRE(f) = | {gF{qk} : RE(g, G)<RE(f, G) } |;    vMI(f) = | {gF{qk} : MI(g, G)>MI(f, G) } |.

3. До складу множини F{M} включається Mk ознак с максимальним рангом в F{qk}:

F0{M}=; Fi{M}={ f = } Fi–1{M}, i=1,…, M; F{M} = FM{M}.

4. Шукана множина F{k} є F{M}, доповнена інформативними ознаками із F{qk} з малою величиною дублювання RE(f, F{k})< відносно F{k}:

F0{k}*=F{M}; F0{k}=F{M}; Fi{k}*={ f = } Fi–1{k}*;

Fi{k} = { f : gFi{k}* RE(f, Fi–1{k})< }, i=1,…,(qk–M); F{k} = Fi*{k} : | Fi*{k} | = k.

Дублювання нових ознак оцінюється відносно малої множини вже відібраних ознак F{k}. Завдяки цьому обчислювальна складність процедури залишається низькою при рості розміру початкової множини ознак, що дозволяє працювати з необмеженими початковими множинами, наприклад, з “комбінаторними” ознаками LIRA, RSC. Варіанти процедур добору ознак відрізняються способом ранжирування ознак за критеріями і , застосуванням порогу до мінімальної величини інформативності, критерієм останову.

Розроблено узагальнення правила навчання багатокласового персептрона з одним шаром зв’язків, що навчаються. Нехай активація вихідного нейрона класа с визначається як yc xc+bc, де wc – ваги зв’язків c-го нейрона; x – вхідний вектор; bc – поріг. Результатом класифікації є індекс c* нейрона з максимальною активацією: c*с yc. Якщо c*ctrue, ваги зв’язків змінюються таким чином:

, i=1,N, | ()

де yc-true=yc-true(1_T), 0<T<1 – величина “захисної смуги”; ctrue – індекс нейрона правильного класу; >0 – інкремент, а f()>0 – декремент ваги зв’язку, що модифікується (наприклад, f() /|c|, де |c| – число класів, для яких yc > yc-true).

З даного правила при T=0 одержуємо правило персептрона з навчанням на кілька класів одночасно. При модифікації ваг одного класу c*  ctrue і при f()= одержуємо відоме правило персептрона з захисною смугою, а при T=0 – правило навчання звичайного персептрона. Для багатокласових задач правило , на відміну від звичайного персептрона, модифікує границі декількох класів одночасно, що, у сполученні із захисною смугою, дозволяє підвищити узагальнюючу здатність. На відміну від методу опорних векторів, дозволяє природно вирішувати багатокласові задачі і має лінійну обчислювальну складність щодо довжини навчальної вибірки L.

Об'єднання множинних результатів класифікації і пошуку дозволяє підвищити їхню якість при незалежності або розбіжності окремих результатів.

Нехай Z – кількість поєднуваних результатів. Позначимо Rz z-й вихідний вектор розмірністю |C|. Підсумковий результат (класифікації або пошуку) може бути визначений такими способами:

(i) Максимум суми індивідуальних результатів ;

(ii) Голосування , де , | ()

де countZ(сz) – кількість “голосів” за клас с від усіх Z результатів.

Для кожного Rz визначимо числовий критерій корисності z, наприклад:

(A) величину активації класу-переможця ; (B) відношення рівнів активації ; (C) суму активацій всіх класів . | ()

Тут с** позначає клас, що одержав друге після с* значення . Тоді результат класифікації визначається серед Rz, для яких

(a) ; (b) n найбільших z; (с) n найбільших z серед . | ()

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

Ряд методів і алгоритмів обробки векторних представлень (оцінка ймовірностей в –, добування ознак, пошук, класифікація та ін.) вимагають обчислення L скалярних добутків вхідного вектора a і набору L векторів (матриця W): b=Wa (розмірність a дорівнює N, b – L). Ефективне виконання таких операцій над розрідженими векторами (з малою часткою p ненульових елементів) може бути реалізоване за допомогою індексування. Для цього формується структура даних, що складається з N векторів vn (n=1,N) перемінної розмірності і у vn записуються номера тих з L векторів набору, у яких елемент вектора з номером n ненульовий. Середнє число таких векторів Lp і, відповідно, розмірність структури даних O(N Lp). Тоді b обчислюється так: для кожного з ~Np векторів, що відповідають ненульовим елементам a, додаються значення an у ті елементи L-мірного b, номера яких зазначені в рядку: b[vn[j]]+a[n], n=1,N, j=0,jmax_n. Обчислювальна складність множення Wa складає O(NLp2), що для p<<1 набагато менше складності “прямого” множення O(NL). Ефективна реалізація векторно-матричних операцій з використанням даної процедури реалізована в програмних засобах розділу 5.

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

Модифікація персептроноподібного класифікатора досліджувалася на штучних і реальних числових векторних даних з лінійно нероздільними областями класів: DGEN, задачі Leonard-Kramer і базі ELENA ([2, 7]), де бінарні ознаки виділялися кодуванням гіперпрямокутними рецептивними полями RSC [9], а також при класифікації зображень рукописних цифр бази MNIST [4] (рис. ), де для виділення бінарних ознак використано метод LIRA. Отримані бінарні розріджені вектори використовувалися для навчання одношарового персептрона.

Результати експериментів показали, що при класифікації даних DGEN, Leonard-Kramer і MNIST персептрон із правилом навчання показує кращі результати в широкому діапазоні параметрів (табл. , стовпець “Пр.0” – персептрон із захисною смугою і навчанням одного класу, стовпець “Пр.1” – з навчанням декількох класів; усереднення по 5...25 реалізаціям ознак).

Методи добору інформативних ознак досліджувалися при класифікації зображень бази MNIST і текстів бази Reuters-21578. На MNIST ефект від застосування добору ознак найбільше вагомий при малих N і Q<100. При збільшенні Q ефект від застосування добору зменшується, і при Q?100 спостерігається погіршення результатів, пов'язане з появою значного числа ознак, що дублюються (з великим значенням RE, рис. ). При доборі ознак із урахуванням дублювання при збільшенні порога (див. розділ 2) середня помилка класифікації зменшувалася (табл. 2).

Застосування добору ознак без урахування можливого дублювання дозволило значно скоротити розмірність даних (з N=50000 до N=1000) при збереженні високих результатів класифікації MNIST на рівні 2,7–2,9% помилок. Добір ознак з урахуванням дублювання дозволив додатково зменшити відсоток помилок у середньому на 0,6%. Час навчання класифікатора зменшився при цьому з ~5 хвилин до 5 секунд, а добір ознак зайняв 75 секунд.

При дослідженні методів добору ознак у задачі класифікації текстів бази Reuters-21578 тексти були представлені як бінарні вектори, де елементами є індикатори наявності слів. Число ознак після попередньої обробки (див. розділ 5) складало N=33500, після добору – варіювалося від 10 до 10000. Класифікація проведена методами: kNN, опорних векторів (МОВ) і одношаровим персептроном, а результат оцінювався по точці перелому характеристики точність-повнота.

При доборі ознак результати класифікації залишаються високими, незважаючи на значне скорочення розмірності векторів (рис. 3). Для МОВ точність класифікації на 90 класах погіршилася з 0,879 при N=1000 до 0,864 при N=100; на 10 класах, відповідно, з 0,923 до 0,903. Результати методу kNN при N=100 склали 0,819 і різко погіршилися при збільшенні числа ознак (до 0,713 при N=300), що пов'язано зі збільшенням частки малоінформативних ознак.

Рис. 3. Точність класифікації Reuters-21578, добір ознак, 90 класів

Добір ознак з урахуванням дублювання при кількості ознак N=500 дозволив поліпшити результат класифікації з 0,916 до 0,937 (табл. 3).

Таким чином, розроблені методи добору ознак з урахуванням дублювання дозволили поліпшити результати класифікації текстів для персептрона і kNN та зберегти високі результати для МОВ при значному скороченні витрат пам'яті й часу навчання і класифікації.

Об'єднання множинних результатів класифікації досліджувалося на базі MNIST. Генерувалося 5 реалізацій випадкових ознак LIRA (N=512000), за допомогою яких кодувалася збільшена в 25 разів навчальна і тестова вибірки та проводилося навчання 5 персептронів. Результат класифікації визначався голосуванням по (iа також по “кращих” претендентах із сортуванням по (A-C). Хоча розходження в індивідуальних результатах класифікаторів були малі, при виборі класифікаторів по (с) було отримане зниження відсотка помилок у середньому з 0,72% до 0,60%. Таким чином, об'єднання результатів дозволило поліпшити підсумковий результат класифікації. Значення вираження (a-c) використовувалося як критерій “впевненості” для прийняття рішення про відмову від класифікації (при його малому значенні). При числі відмов 0,5% точність класифікації зросла з 99,31% до 99,54%, при 1% – до 99,63%, при 3% – до 99,86%, при 10% – до 100%.

Усі досліджені методи класифікації зображень і текстів, а також методи добору ознак програмно реалізовані (розділ 5).

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

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

Формування контекстних векторів слів виконується шляхом множення матриці слова-тексти A [WL] на матрицю R [LN], у рядках якої знаходяться індексні вектори текстів rj розмірністю N<<L, для яких m<<N елементів з випадково обраними номерами встановлено в ненульове значення (+1, або {+1,–1}):

S = AR. | ()

В результаті матриця S [WN] буде містити в рядках si контекстні вектори слів розмірністю N. Контекстні вектори текстів, що враховують семантичну подібність слів, що входять в них, формуються так:

D = ATS. | ()

Матриця D [LN] містить у рядках dj контекстні вектори текстів. Для одержання векторів із дискретними елементами до них застосовуються поелементні порогові операції:

di* = { 1 при di > ; інакше 0 }– бінаризація (bin);

di* = { 1 при di > + 0; –1 при di < – 0; інакше 0 } – тернаризація (tern), | (9)

де – величина порога, що впливає на кількість ненульових елементів у векторах.

В експериментах елементи матриці A фільтрувалися log(1+tfij idfj) (позначено lt); контекстні вектори слів і текстів нормувалися до довжини 1 по l2. На відміну від класичних методів VSM, завдяки наявності подібності між контекстними векторами різних слів, контекстні вектори текстів можуть бути подібні, навіть якщо в них не містяться однакові слова. Це дозволяє використовувати такі представлення для пошуку і класифікації текстів з урахуванням семантичної близькості. На відміну від методу GVSM, розподілені векторні представлення дозволяють скоротити розмірність і значно підвищити обчислювальну ефективність їхнього формування.

Ефективність класифікації текстів, що представлені контекстними векторами з дискретними елементами, досліджувалася на прикладі бази Reuters-21578, де отримано точність класифікації 0,910 (табл. 4), що відповідає якості класифікації за допомогою традиційних представлень (розділ 3). Об'єднання або перетин результатів класифікації з використанням контекстних векторів та традиційних методів дозволяє підвищувати їх повноту або точність.

Пошук інформації в базі текстів полягає у ранжируванні текстів бази за ступенем релевантності запиту. Ефективність пошуку з використанням контекстних векторів (Context) досліджувалася на прикладі трьох стандартних баз: Medlars, Time, Cranfield [5] (табл. 5).

Таким чином, найкращі результати пошуку VSM і GVSM забезпечуються при lt-фільтрації частотної матриці A. Застосування контекстних векторів із дискретними елементами (bin, tern) при класифікації і пошуку текстової інформації дає результати до 20% вище, ніж традиційний метод VSM. При цьому результати близькі до GVSM і контекстних представлень з дійсними елементами (l2), але дискретні вектори забезпечують підвищення ефективності їх обробки.

Проведено оцінку обчислювальної ефективності розроблених методів формування векторних представлень текстової інформації і методів пошуку. Обчислювальна складність пошуку для контекстних векторів з дійсними елементами CtxReal і дискретними елементами CtxDiscr у порівнянні з GVSM на різних етапах обробки приведена в табл. . Оцінювалася обчислювальна складність етапів: попередня обробка – формування по базі текстів матриці пошуку (виконується одноразово); формування вектора запиту; безпосередньо пошук – обчислення міри подібності запиту з кожним із текстів бази. Вибір k текстів бази з максимальною подібністю виконувався частковим сортуванням цього вектора за O(L k) операцій. Розмірності матриць дані в квадратних дужках.

Тут p1=||t||0/W – середня частка слів словника в текстах; p=||s||0/N=||dj||0/N – розрідженість контекстних векторів слів і текстів; q – кількість слів в запиті.

При звичайному пошуку обчислювальна складність етапів попередньої обробки і пошуку у великих базах текстів L>>N найвища для методу GVSM. Для контекстних векторів CtxReal складність етапу попередньої обробки менше, ніж у GVSM при N<L, а застосування дискретних векторів CtxDiscr і ефективної процедури множення матриць (розділ 2) дозволяє прискорити попередню обробку і пошук (до 100..10000 разів при p~0.1–0.01) у порівнянні з CtxReal.

При оптимізованому пошуку на етапі попередньої обробки обчислюється матриця подібностей усіх слів словника з кожним текстом бази. Завдяки цьому етап пошуку для всіх трьох методів складається в підсумовуванні рядків матриці подібностей, відповідних словам запиту. Для контекстних векторів CtxReal складність етапу попередньої обробки менше, ніж для GVSM при N<Wp1, для CtxDiscr – при Np2<W. Наприклад, для бази TASA (37600 текстів, 78000 слів) на попередню обробку GVSM необхідно ~5 годин (комп'ютер P4 2.8 ГГц), CtxReal – 2,5 години, а для CtxDisc – ~0,5 години. Етап пошуку для CtxReal ефективніше, ніж при звичайному пошуку при q<N, для CtxDiscr – при q<Np2.

Таким чином, при типових значеннях W, L, N оптимізований пошук із застосуванням дискретних контекстних векторів CtxDiscr забезпечує найкращу продуктивність.

П’ятий розділ присвячено питанням розробки програмних засобів для інформаційних технологій класифікації і пошуку.

Для обробки даних у форматі розріджених векторних представлень створено ієрархію програмних модулів Toolbox (рис. 4):

- CommonLib – уніфіковане оперування розрідженими векторними представленнями;

- Classifier Toolbox – класифікація векторної інформації;

- Feature Toolbox – ранжирування і добір ознак;

- Semantic– формування контекстних векторів текстової інформації.

Рис. 4. Ієрархія програмних
модулів Toolbox

На базі Toolbox створені програмний нейрокомп’ютер SNC, макети систем контекстного пошуку текстів TextSearch і класифікації TextClassifier.

Програмний нейрокомп'ютер SNC (рис. 5) призначений для розробки і дослідження нових алгоритмів і нейромережевих технологій обробки інформації, а також для створення прикладних систем класифікації і пошуку. В основу системної архітектури SNC покладено такі принципи: уніфікація представлення й обробки інформації, модульність архітектури, візуальне конфігурування.

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

Загальний вигляд програмної архітектури SNC представлений на рис. 6.

Рис. 5. Програмний нейрокомп’ютер SNC |

Рис. 6. Програмна архітектура SNC

Він складається з таких основних модулів:–

– центральний об'єкт системної архітектури SNC. Через його інтерфейси, реалізовані в ньому класи і методи виконуються: створення і конфігурування блоків обробки і зв'язків, перевірка цілісності і несуперечності зв'язків між блоками, збереження проекту, виконання проекту і запис експериментальних даних у БД;–

– засоби клієнтської частини, за допомогою яких здійснюється взаємодія користувача з SNC у режимі САПР;– 

Блоки обробки даних – основні обчислювальні блоки SNC: попередньої обробки, кодування, фільтрації і класифікації даних;–

– класи взаємодії з базою даних, за допомогою яких виконується збереження і обробка експериментальних результатів;– 

Utility – класи бібліотек, що реалізують ефективні операції з векторними представленнями та інші операції.

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

Рис. 7. Макет системи пошуку текстів

Рис. 8. Макет системи класифікації
текстів

TextSearch – макет системи пошуку текстів на основі контекстних векторних представлень текстової інформації, який реалізовано під керуванням веб-сервера Microsoft IIS (рис. 7).

TextClassifier – макет системи класифікації текстів, реалізований як комплект модулів для виділення інформативних ознак, формування векторів текстової інформації на основі векторних моделей і методів контекстних векторів та класифікації (рис. ).

При створенні макетів використані алгоритми і методи, реалізовані в Classifier Toolbox і Semantic Toolbox. Відомості щодо актів впровадження наведено в розділі “Практична значимість”.

ВИСНОВКИ

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

За результатами проведеного дослідження зроблено такі висновки:

1. Розроблені методи добору бінарних інформативних ознак дозволяють зменшувати розмірність векторних представлень під час класифікації векторних даних. Методи, реалізовані програмними засобами Feature Toolbox, забезпечують зниження обчислювальних витрат при збереженні якості в задачах класифікації, що підтверджено на реальних даних. Так, для зображень бази MNІST при скороченні числа ознак у 10-50 разів отримана точність класифікації більше 97% і збільшена швидкість класифікації більше ніж у 10 разів; для текстів бази Reuter-21578 при скороченні розмірності текстових векторів у 20-100 разів отримано результат 0,903–0,937, близький до кращих світових (0,92).

2. Розроблено методи, що забезпечують підвищення якості класифікації даних, які мають векторне представлення, шляхом удосконалення навчання, об'єднання множинних результатів класифікації, застосування добору найбільш надійних результатів і відмови від класифікації. Методи реалізовано програмними засобами Classifier Toolbox та в нейрокомп’ютері SNC і експериментально досліджені. На базі MNIST об'єднання множинних результатів класифікації і застосування відбору найбільш надійних результатів дало зменшення помилки класифікації з 0,72% до 0,60%, а застосування відмови від класифікації дозволило додатково знизити рівень помилок.

3. Розроблено методи формування розподілених представлень текстової інформації з урахуванням її семантичної близькості, що відрізняються застосуванням контекстних векторів з дискретними елементами. Методи реалізовано програмними засобами Semantіc Toolbox і використано у макеті програмної системи контекстного пошуку текстів TextSearch, реалізованої в веб-серверній архітектурі. Показано поліпшення результатів пошуку на стандартних базах текстів Medlars, Cranfіeld, Tіme до 20% за 11-точковою усередненою характеристикою порівняно з VSM-пошуком. При класифікації бази Reuter-21578 за допомогою Semantic Toolbox та Classifier Toolbox отримано результати до 0,918, що відповідає рівневі кращих результатів традиційних методів.

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

5. Створений програмний нейрокомп’ютер SNC є ефективним інструментальним засобом розробки нейромережевих інтелектуальних ІТ. Ефективність забезпечується архітектурою SNC, яка підтримує візуальне конфігурування проектованих алгоритмів у вигляді блок-схем, дозволяє створювати гнучко конфігуровані проекти для дослідницьких і прикладних цілей, розширювати клас вирішуваних задач шляхом включення нових функціональних модулів.

6. Розроблено нові програмні засоби для створення і реалізації інтелектуальних ІТ класифікації та пошуку, що використовують оригінальні методи формування й оперування векторними представленнями інформації (CommonLіb, Feature Toolbox, Classifier Toolbox, Semantіc Toolbox), та макети, що демонструють їх ефективність (TextSearch, TextClassifier).

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

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

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

3. Мисуно И.С., Рачковский Д.А., Слипченко С.В. Векторные и распределенные представления, отражающие меру семантической связи слов // Математичні машини і системи. - 2005. - № 3. - С. 50-67.

4. Мисуно И.С., Рачковский Д.А., Слипченко С.В. Экспериментальное исследование классификации рукописных цифр // Системные технологии. - 2005. - №4. - С.110-133.

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

6. Мисуно И.С. Векторное представление и классификация текстовой информации // Управляющие системы и машины. - 2006. - № 1. - С. 85-91.

7. Мисуно И.С., Рачковский Д.А., Слипченко С.В. Распределенное представление данных в задачах классификации // Системные технологии. - 2006. - № 1. - С. .

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

9. Слипченко С.В., Мисуно И.С., Рачковский Д.А. Свойства кодирования числовых величин случайными гиперпрямоугольными рецептивными полями // Математичні машини і системи. - 2005. - № 4. - С. 15-29.

10. Рачковский Д.А., Слипченко С.В., Мисуно И.С., Куссуль Э.М., Байдык Т.Н. Разреженное бинарное распределенное кодирование числовых векторов // Проблемы управления и информатики. - 2005. - № 6. - С. 57-72.

11. Слипченко С.В., Рачковский Д.А., Мисуно И.С. Декодирование разреженных бинарных распределенных кодов скалярных и векторных величин // Компьютерная математика. - 2005. - № 3. - С. 108-120.

12. Misuno I.S., Rachkovskij D.A., Revunova E.G., Sokolov A.M. SNC: The Software Neurocomputer With Modular Architecture // Междунар. конф. "Проблемы нейрокибернетики". - Ростов-на-Дону, Россия. - 2002. – Т. 2. - С. 109-113.

13. Рачковский Д.А., Мисуно И.С., Ревунова Е.Г. Случайное векторное индексирование документов и семантические представления слов // V Всероссийская конф. "Нейроинформатика-2003". - М.: МИФИ. - 2003. – Т. 2. - С. 213-218.

14. Markman A.B., Rachkovskij D.A., Misuno I.S., Revunova E.G. Analogical reasoning techniques in intelligent counterterrorism systems // X-th Int. Conf. "Knowledge-Dialogue-Solution" KDS-2003. - FOI-Commerce, Sofia, Bulgaria. - 2003. - P. 445-453.

15. Misuno I.S. Reduction of feature pool in large-scale classification tasks // Междунар. конф. "Проблемы нейрокибернетики". - Ростов-на-Дону, Россия. - 2005. - Т.2. - С.70-73.

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

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

АНОТАЦІЯ

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

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.23 – Системи та засоби штучного інтелекту. – Інститут проблем математичних машин і систем НАН України, Київ, 2006.

Дисертація присвячена розвитку і підвищенню