Бодякин В.И., Чистяков А.А.

НЕЙРОСЕМАНТИЧЕСКАЯ ФОРМА 
ПРЕДСТАВЛЕНИЯ ИНФОРМАЦИИ

(На правах рукописи от 12.07.10.)

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

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

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

Проблема представления информации и знаний - одна из актуальнейших в направлении разработке систем искусственного интеллекта (ИИ). Форма представления информации - это тот фундамент, на котором строится все здание системы и которым определяются основные теоретические и конструктивные особенности разрабатываемой системы. Соответственно, удачно выбранная форма представления информации делают систему не только простой и эффективной, но и легко развиваемой, и, наоборот, неудачно выбранная форма представления информации – это, в конечном счете, всегда неработающая информационная система. Т.е. выбор формы представления информации для информационной системы - это первый, определяющий шаг на пути проектирования системы ИИ.

В дальнейшем, под потоком данных из предметной области (ПО) будем понимать ТФ как текстовую последовательность символов произвольного алфавита (А), в которой размер алфавита много меньше длины текста (L), т.е., L >> |A|. Естественно, что в реальных потоках данных неизбежно повторение не только отдельных символов, но и их устойчивых сочетаний, характерных для конкретного источника потока данных, особенно это свойственно для естественно языковых текстовых потоков.

Алгоритм нейросемантического преобразования информации. Кратко рассмотрим один из алгоритмов формирования нейросемантической структуры (НСС) на произвольном текстовом потоке [ ].

Первый шаг. Выбираем максимально возможную длину "слова" в k-знаков (например, 2 ≤ k ≤ 8).

Второй  шаг. Если словарь не пуст, то выбираем первое "слово" из словаря S и закрашиваем им ТФ. И так делаем со всеми "словами" из словаря, пытаясь закрасить ТФ.

Если словарь S пуст, то переходим третьему шагу.
Третий шаг. Слева направо выбираем первые знаки ТФ, еще "не закрашенные", не более k (l  ≤ k), формируем из них "слово" и заносим его в словарь S.

Далее этим "словом" проходим по всем "незакрашенным" участкам исходного текста и "закрашиваем" в нем все участки, тождественные этому "слову". При этом в характеристиках слова отмечаем: его длину – l и число закрашиваний им ТФ – w.

И так делаем до тех пор, пока не будет "закрашена" вся ТФ.

Четвертый шаг. Вместо "закрашенных" последовательностей ставим индексы соответствующих им "слов" из словаря. В результате исходная ТФ преобразуется в последовательность индексов словаря и в сам словарь.

Пятый шаг. Вычисляем (обычным способом) суммарный "битовый вес" Р_n полученной последовательности индексов и словаря ("слов" с w ≥ 1).

Сравниваем вычисленное значение Р_n с его предыдущим Р_n-1. Если  Р_n ≥Р_n-1 , то переходим на восьмой шаг (условие 1а и 1б).

Шестой шаг. Вводим параметр (функционал) упорядочивания "слов" в словаре F, допустим, как:  F = l ^k * w + (l + w) и сортируем "слова" словаря в порядке убывания их величин F.

Седьмой шаг. Делим словарь на две группы "слов" (в соотношении, примерно, 1:3). Освобождаем словарь от группы слов с меньшим F и переходим на второй шаг алгоритма.

Восьмой  шаг. Рассматриваем индексную последовательность как новую ТФ для формирования следующего иерархического словаря S. При этом длина  индексной последовательности сокращается, примерно, в k раз, т.е. L _n+1 » L_n&asump; / k.

Если длина этой последовательности L _n+1 > 1, то переходим на первый шаг алгоритма.

Девятый шаг. Stop. НСС построена.

В результате исходная текстовая форма преобразуется в иерархическую структуру словарей (см. рис. 3), т.е:

ТФ  →  S₁,S₂, … S_n.

Условие формирования НСС. Существует несколько алгоритмов построения НСС [ ], но основная особенность НСС заключается в том, что, минимизируя физическую ресурсоемкость (R_НСС) НСС,

            R_НСС = Р₁ +Р₂  + Р₃ + … + Р_n-1 + Р_n  (бит)

       1/P(компрессия) = ---------------------------------------------------------       →  0,        (1а)

       при  t → ∞              RТФ  = объем ТФ  в битах

       или       ΔR_НСС  / ΔTФ   →  0                                                                                              (1б)

       при  t → ∞
мы автоматически в НСС получаем причинно-следственную структуру процессов предметной области (ПО), а т.к. каждый процесс в ПО имеет имя, то, соответственно, в НСС получаем иерархическую семантическую структуру ПО.

Структуру словарейS₁,S₂, … S_n, в которой выполняется (1а и 1б), будем называть нейросемантической структурой (НСС). "Нейро", т.к. каждое "слово"  словарей НСС физически отображается нейроподобным N-элементом. Т.е. имеет место взаимнооднозначное соответствие:

Автоструктуризация. НСС – это пример 1-го формального преобразования количественной (естественной) текстовой формы представления информации в качественную форму, в которой из континуальной (практически непрерывной, неструктурированной) текстовой формы образуется иерархическое множество образов данной ПО в виде ориентированного многодольного графа, отображающего причинно-следственные связи образов (объектов-процессов) ПО. Для инженерной практики НСС – это готовая причинно-следственная структура объектов-процессов ПО при разработке вычислительной системы для конкретных задач. Назовем процесс формирования НСС автоструктуризацией.
Качество функционирования НСС отображается отношением числа корректных пар (N-элемент « "слово-процесс" ПО) на общее число N-элементов ИС. Естественно, что в процессе автоматической подстройки ИС под конкретную, априорно неизвестную ПО, на начальном этапе ввода текстового потока "НСС-качество" не велико (<< 1), а далее, "НСС-качество" полностью зависит от алгоритмов информационной системы. На рис. 2 приведен характерный вид графика: "НСС-качество" – log (tn).

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

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

      L = {01100101011011011010001101101001}.

Выберем, например, k1=2 и разделим исходную последовательность длиной L на подпоследовательности (цепочки) по k1 символов.

Каждую уникальную цепочку по k1 символов занесем в словарь (L1 - 1-й слой НСС), а вместо нее поставим ссылку на эту цепочку символов в словаре.

     1-й шаг k1=2

В результате исходная последовательность символов превратится в последовательность ссылок (l1) и словарь (L1), причем число элементов в последовательности ссылок l1 в k1 раз меньше, чем число символов в исходном тексте l0.

Повторим эту процедуру. Разделим последовательность ссылок l1 по k2 (k2=2) ссылок и сформируем новый иерархический словарь, представляющий совокупность словарей L1 и L2.

      2-й шаг k2=2
l1   1211123122431221                           Номера цепочек в словарях
                                                                 1    2    3    4    5    6
                                                                 12  11  31  22  43  21      L2
l2    1 2 1 3 4 5 1 6                           +      "01"10"11"00"                     L1

В результате получим последовательность ссылок l2 на словарь L2 и два словаря L1 и L2, причем, число элементов в этой последовательности (l2) в k2 раз меньше, чем число элементов в последовательности l1.

Многократно (а точнее [logk l0], где k - параметр системы) раз применяя эту процедуру, получим рекурсивно-ссылочную НСС вместо исходного текста l0.

3-й шаг k3=2
l2    12134516                               Номера цепочек в словарях
                                                      1    2    3    4     5   6
                                                     12  13  45  16             L3
                                                     12  11  31  22  43  21       L2
l3   1234                                +   "01"10"11"00"                       L1
...................................................................................................

       4-й шаг k4=2
Номера цепочек в словарях
l3    1234                                                 1    2    3    4    5    6
                                                              12  34                               L4
                                                              12  13  45  16                L3
                                                              12  11  31  22  43  21    L2
l4      1 2                                     +     "01"10"11"00"              L1

      5-й шаг k5=2
                                                                              Имена
l4    12                                                                   словарей
                                                            12                L5
                                                            12   34                    L4
                                                            12   13  45  16                  L3
                                                            12   11  31  22  43  21   L2
l5     1                                      +         "01"10"11"00"              L1
.....................................................................................................
т.е. исходная последовательность символов полностью переходит в НСС.

Полученную НСС можно преобразовать до более привычного вида, добавив новый словарь с "привычными" терминальными элементами "0" и "1" (алфавит - А), заменив терминальные элементы словаря L1 ссылками на новые терминальные элементы. В результате НСС приобретет следующий вид:

НСС с терминальным алфавитом А={"0","1"}, построенная на исходном тексте l₀.

Все словари (слои) этой НСС строятся по одному принципу, кроме А (или 1-го) словаря. Этот словарь является "терминальным" и служит для интерфейса между НСС и исходным текстом l₀.

НСС и исходный текстl₀ являются взаимопереводимыми и эквивалентными с точки зрения содержащейся в них информации, но НСС обладает рядом полезных свойств, которые заслуживают особого рассмотрения.е словари (слои) этой НСС строятся по одному принципу, кроме А (или 1-го) словаря. Этот словарь является "терминальным" и служит для интерфейса между НСС и исходным текстомl₀.

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

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

Алгоритм обратного преобразования НСС в ТФ осуществляется уже за меньшее число операций и идет "сверху-вниз".

На первом шагеS_n преобразуется в "слово" индексов и заносится в стек n. Первый индекс I_n стека, раскрывает "слово" в словаре S_n-1 , которое заносится в стек  n - 1. Из него выбирается первый индекс  I_n-1  и т.д. до первого терминального словаря S₁, индексы которого являются исходными символами ТФ в алфавите А.

В результате первого прохождения по НСС "сверху-вниз" в ТФ формируется последовательность, соответствующая "слову" словаря S₁. После выдачи терминальных символов в ТФ, стек I₂ увеличивается на единицу, и в ТФ выдается второе "слово" и так до тех пор, пока не освободиться весь стек I₂.

После этого стек I₃ увеличивается на единицу, формируется новый стек в I₂. Первый индекс которого есть следующее "слово" в ТФ и т.д., пока не освободится I_n стек.

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

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

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

Следует также отметить, что все технические характеристики памяти на базе НСС (время доступа, коэффициент компрессии-сжатия, надежность-пла­стичность хранения информации и др.) имеют тенденцию к улучшению как в среднем, так и в абсолютных значениях по мере роста объема вводимой информации из ПО (см. рис. 4).

Следует также отметить, что все технические характеристики памяти на базе НСС (время доступа, коэффициент компрессии-с

жатия, надежность-пла­стичность хранения информации и др.) имеют тенденцию к улучшению как в среднем, так и в абсолютных значениях по мере роста объема вводимой информации из ПО (см. рис. 4).

Рис. 4.

Сравнивая различные формы представления информации для систем искусственного интеллекта, в частности ТФ и НСС, можно отметить как их преимущества, так и их недостатки.
Из преимуществ ТФ можно отметить универсальность, и из ее недостатков - избыточность, громоздкость, "медлительность" … .

К преимуществам НСС можно отнести:

- ассоциативное сведение однотипных событий-процессов, произошедших в разные времена и в различных контекстных ситуациях в единое "ментальное целое", т.е. преодоление в "ментальном мире" НСС всех пространственных и временных расстояний;

- автоматическое выделение семантических единиц ПО;

- улучшение всех существенных технических характеристик памяти: время доступа, коэффициент компрессии-сжатия, надежность-пластичность хранения информации и др., по мере роста объема вводимой информации (см. рис. 4);

- большую функцио­нальную близость к естественному прототипу - централь­ной нервной системе, чем современные модели нейронных се­тей [1], за которыми исторически закрепилось направление нейрокомпьютинга.
НСС по своим информационно-функциональным свойствам близка к ансамблям биологических нейронов.

- …

Особенности вышеперечисленных характеристик НСС являются основанием для построения на её базе крупномасштабной ассоциативной па­мяти (ИС), работающей со слабоструктурированными текстовыми пото­ками.

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

Сжатие (компрессия). Хотя выполнение условий 1а и 1б необходимо для проявления свойства автоструктуризации НСС, они также отображают и возможность использования НСС как архиватора для ТФ.

Не рассматривая детально в данном материале направление современной архивации, которое достаточно хорошо представлено в [6,8  и  также в Интернете, например, на сайтах http://data-compression.com, http://www.arctest.narod.ru ], мы сравним естественный процесс компрессии в НСС с лучшими архиваторами.

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

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

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

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

Цель данного эксперимента заключалась в демонстрации потенциальных возможностей эффективного сжатия на основе НСС для сверхбольших объемов данных. Поэтому, ряд существенных для практики показателей архиваторов, таких как: быстродействие сжатия и восстановления, ограничения на память, удобство применения и пр., в данном случае специально не учитывались. Однако по временам работы процессора Pentium IV с частотой 1,7 гигагерц разница практически не отличалась, особенно при распаковке. Следует заметить, что использованный макет алгоритма НСС является только начальной разработкой и, очевидно, имеет конструктивный резерв для дальнейшего улучшения по сравнению с "классикой"  RAR и ZIP.

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

Список литературы

1. Бодякин В.И., Куда идешь, человек? (Основы эволюциологии. Информационный подход). - М. СИНТЕГ, 1998, 332с.
2. Бодякин В.И. Нейролингвистическая форма представления информации на нейроноподобных элементах, - тезисы семинара-совещания «Алгоритмы обработки информации в нейроноподобных системах», г. Н-Новгород, 14-16 сентября 1993г.
3. Бодякин В.И. Информационные иерархически-сетевые структуры для представления знаний в информационных системах. //Проблемно-ориентированные программы. Модели, интерфейс, обучение: Сб. трудов. – М.: Институт проблем управления, 1990.
4. Бодякин В.И., Чистяков А.А., Развитие систем хранения данных и архитектура памяти на основе нейросемантических структур, - в сб. Проблемы информатики - материалы III научной конференции "От истории природы к истории общества: "Прошлое в настоящем и будущем", М., 2001.
5. Бодякин В.И., Чистяков А.А. Ассоциативные информационные структуры и модели памяти, - Материалы  V Международной конференции “ От истории природы к истории общества и будущему человечества”  13.05 – 17.05  2002 года, секция “ Математические модели “. - Москва, 2004. – 49 с.
6. Shannon C. A mathematical theory of communication, Bell System Tech. J., 27 (1948), № 3, 379-423; 28 (1948),  № 4, 623-656.
7. Кузнецов Н.А. Информационное взаимодействие в технических и живых системах. Информационные процессы. 2001, том 1, №1, с. 1-9.
8. Фомин А.А. Основы сжатия информации. Санкт-Петербургский гос. технический университет, 1998.
9. Bell T., Witten I., Cleary J. Modeling For Text Compression. - ACM Computing Surveys. Vol.21, No.4( Dec.1989), pp.557-591.
10.  Moffat A., Bell T., Witten I. Lossless Compression for Text and Images.- Algorithms and Theory of Computation Handbook /Eds. M. J. Atallah, CRC Press Inc., Boca Raton, FL, 1998, pp.12.1-12.23.
11. Балашов К.Ю. Сжатие информации: анализ методов и подходов. - Препринт / Ин-т техн. Кибернетики НАН Беларуси; № 6, Минск, 2000.
12. Баранов Г. Обзор методов сжатия данных. - журнал PC Club, ноября 1998 г.
13. Huffman D. A Method for the Construction of Minimum-Redundancy Codes.- Proceedings of IRE, vol.40, N9, pp.1098-1101, September 1952.
14. Gallager R. Variations on a Theme by Huffman.- IEEE Transactions on Information Theory, Vol. IT-24, No. 6, Nov. 1978. pp. 668-674.

 Замечания