Дед отпугиватель мышей купил на Елаб по хорошей стоимости.

КАТЕГОРИЗАЦИЯ WEB ДОКУМЕНТОВ С ИСПОЛЬЗОВАНИЕМ САМООРГАНИЗУЮЩИХСЯ НЕЙРОННЫХ СЕТЕЙ

1 Введение

Стремительный рост числа web документов превышает в настоящее время возможности информационно-поисковых систем. Индексация, использование ключевых слов и статистических методов поиска не могут обеспечить желаемую релевантность результатов поиска и часто порождают новые проблемы [1]. Для того чтобы результаты поиска были интересными и обозримыми, пользователи вынуждены усложнять запросы путем введения в них булевых функций, многократно выполняя их. Поэтому актуальными становятся задачи создания интеллектуальных агентов, способных классифицировать и понимать содержание web документов, фильтровать сообщения электронной почты, подписных листов и т.д. [2-10].

Для решения этого класса задач были предложены методы обучения категоризации больших коллекций текстовых документов [1-10]. В последнее время для решения этой задачи активно применяются искусственные нейронные сети, реализованные в соответствии с парадигмой коннекционизма, благодаря которой была достигнута высокая точность классификации [2, 3, 6, 8-10]. В рамках этой парадигмы было предложено использовать простые рекуррентные сети [2, 3, 6, 11-13].

Применение известных алгоритмов самоорганизации Ивахненко [14, 15] позволяет минимизировать избыточность нейронных сетей и упростить тем самым искомые соотношения. Ниже эти алгоритмы развиваются на основе предложенных автором критериев [16, 17] применительно к задаче категоризации web документов.

2 Применение рекуррентной нейронной сети

В отличие от нейронных сетей прямого распространения, в рекуррентных сетях, состоящих из входного, скрытого и выходного слоев, у нейронов второго слоя имеется две группы входов. Первая группа входов i-го нейрона соединена синаптическими связями с m сенсорными элементами, а вторая - соединена с выходами элементов, вносящих задержку выходных сигналов на один такт, i= 1, ... , m. Конфигурация подобной сети (рис. 1) определяется числом входов m и нейронов l _ m скрытого слоя.

В каждый момент времени k нейронная сеть анализирует одно слово wk документа, представленное m-мерным вектором q[k]= (q1[k], ..., qm[k]). Значения qi этого вектора соответствуют частотам появления слова wk в каждой из заданных категорий документов (число входов m равно числу категорий). Благодаря обратным связям это слово анализируется в контексте с предыдущими словами, появившимися в моменты времени k- 1, k- 2, ... , 0.

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

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

3 Алгоритм обучения символьных правил

В рамках другого подхода искомые правила категоризациии представляются в виде простой системы булевых правил дизъюнкций конъюнкций [4, 5]. В соответствии с этими правилами документ d относится, например, к категории интернет, если

слово интернет присутствует в d OR

фраза всемирная паутина присутствует в d OR

...

фраза глобальная сеть присутствует в d

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

Искомые правила синтезируются на основе мини-экспертов, активизирующихся при появлении в документе некоторых лексических единиц (фраз), состоящих соответственно из одного wi1, двух wi1wi2 и n слов wi1...win, не принадлежащих множеству нейтральных слов (stop-word). Слова каждой из этих фраз появляются в документе d в фиксированном порядке, i1< i2< ... <in, что позволяет ассоциировать их с некоторым автоматически формируемым контекстом документа. Для реализации алгоритма обучения категоризации вводятся пулы, содержащие эти фразы (рис. 2).

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

Для обучения категоризации активные эксперты разделяются на две группы. Эксперты первой группы указывают на принадлежность документа d к категории c= ci, iО {1, ..., m}. Эксперты второй группы указывают на принадлежность d к альтернативным категориям c ci. При этом, на выходе каждого активизированного эксперта появляются значения 0 или 1. Значения всех экспертов далее взвешиваются, нормируются и сравниваются с порогом Q. Его величина изначально устанавливается Q= 1/2, далее она уточняется в процессе настройки вектора pk весовых коэффициентов

pt+1k= ptk , если ct= k,

pt+1k= b ptk , если ct k, p0= p0,

где b О (0, 1) - скорость обучения; t - номер шага обучающего алгоритма; kО {0, 1} - индикатор группы экспертов, p0 - начальное произвольно задаваемое значение вектора.

Настройка весов pt и порога Q продолжается до тех пор, пока число ошибок (функция потерь) уменьшается.

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

4 Использование принципов самоорганизации

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

Самоорганизация нейронной сети начинается с того, что для каждого предполагаемого признака (лексической единицы) wi, извлекаемого из пула Pool1, подсчитывается число ошибок vi (i= 1, ..., m.) классификации обучающих примеров (рис. 2). Далее на оба входа формальных нейронов первого слоя подаются лексические фразы из двух слов, извлекаемые из пула Pool2. Нетрудно показать, что для каждого из таких нейронов существует, по крайней мере, одна из 14 логических функций, обеспечивающая минимальное число ошибок классификации. В этом слое достаточно выбрать только те нейроны, эффективность которых в результате усложнения искомого правила удалось повысить.

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

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

5 Основные выводы

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

ЛИТЕРАТУРА

  1. Feldman R. and Dagan I., Knowledge Discovery in Textual Databases (KDT), Proceedings of the 1st International Conference on Knowledge Discovery (KDD-95), pp. 112-117, Montreal, Aug 1995.
  2. Wermter S., Hybrid Neural Plausibility Networks for News Agents, in print, 1999, 8 p.
  3. Lawrence S., Giles C. L., Context and Page Analysis for Improved Web Search, IEEE Internet Computing, vol. 2, 4, , pp. 38-46, July/August 1998.
  4. Cohen W., Singer Y. Context-sensitive learning methods for text categorization. Proceedings of SIGIR-96.
  5. Cohen W. Text categorization and relational learning. Proceedings of the International Machine Learning Conference (ICML-95), pp. 124-132, Lake Tahoe, CA, Morgan Kaufmann.
  6. Wiener E.et al. A neural network approach to topic spotting. In Symposium on Document Analysis and Information Retrieval, pp. 317-332, Las Vegas, Nevada, 1995.
  7. Shavlik J. and Eliassi-Rad T., Building Intelligent Agents for web-based tasks: a theory-refinement approach, Proceedings of the CONALD Workshop on Learning from Text and the Web, June 1998.
  8. Kohonen T., Self-organization of Very Large Document Collections: State of the art, Proceedings of ICANN98, the 8th International Conference on Artificial Neural Networks, vol. 1, Springer, London, pp. 65-74, 1998.
  9. Honkela T., Pulkki V. and Kohonen T., Contextual Relation of Words in Grimm Tales, Anylized by Self-oranizing Map, Proceedings of International Conference on Artificial Neural Networks, ICANN-95, Ec2 et Cie, Paris, pp. 3-7, 1995.
  10. Kaski S., Lagus K., Honkela K. and Kohonen T., Statistical Aspects of the WEBSOM System in Organizing Document Collections, Computing Science and Statistics, (Scott, D. W., ed.), Interface Foundation of North America, Inc.: Fairfax Station, VA, 29, pp. 281-290, 1998.
  11. Wermter S., Knowledge Extraction from Transducer Neural Networks, in print, 1999, 18 p.
  12. Lawrence S., Giles L. and Fong S., Natural Language Grammatical Inference with Recurrent Neural Networks, IEEE Transactions on Knowledge and Data Engineering, 1998.
  13. Graven M., Shavlik J., Using Neural Networks for Data Mining, Future Generation Computer Systems: special issue on Data Mining, 1997.
  14. Ivakhnenko A.G., Ivakhnenko G.A. and Mьller J.A., Self-Organization of Neural Networks with Active Neurons, Pattern Recognition and Image Analysis, v.4, no.2, pp.185-196, 1995.
  15. Lemke F., Knowledge Extraction from Data Using Self-Organizing Modeling Technologies, Proceedings of the SEAM'97 Conference, 1997.
  16. Schetinin V., Kostunin A., Self-Organization of Neuron Collective of Optimal Complexity, Proceedings of Int. Symposium NOLTA'96, Kochi, Japan, pp. 245-248, 1996.
  17. Щетинин В.Г. Многослойная самоорганизация нейронных сетей оптимальной сложности// Автоматика и вычислительная техника. - Рига, 1998, ╪4. - С.30-37.

Back to Home