AI Lab

Open Artificial Intelligence Laboratory

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

Автор Легков Георгий Алексеевич.

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

Ключевые слова: позиционные системы счисления, базис, основание, числовая последовательность.

Позиционные системы счисления являются системами представления числовых значений [1]. Способ разбиения множества значений, заложенный в основу этих систем позволяет «удобно» представить лишь незначительную часть из множества всех возможных числовых последовательностей. В данном случае к «удобным» относятся те числовые последовательности, которые нет необходимости хранить в памяти в виде заданного массива значений. Достаточно знать (или хранить) базис [1] позиционной системы счисления в виде числовых значений соответствующих каждому её разряду.

Для таких числовых последовательностей значение любого элемента легко получить по номеру занимаемой им позиции. Наглядным примером такой «удобной» последовательности является натуральный ряд чисел.

Представление числовых последовательностей с помощью базиса позиционных систем счисления

Между представлениями чисел позиционных систем счисления с разным основанием (двоичным, троичным и т.д.) существует взаимно однозначное соответствие. Возможен перевод чисел позиционных систем счисления с одним основанием в числа с другим основанием. Это позволяет, не теряя общности, рассмотреть возможность представления числовых последовательностей на примере разбиений множества значений в двоичной системе счисления.

Далее, разбиение множества значений входящих в состав последовательности — это представление его в виде объединения попарно непересекающихся подмножеств. Число таких пар подмножеств равно числу разрядов в двоичном представлении номеров позиций последовательности. Разбиение на два непересекающихся подмножества внутри каждой пары определяется нулевым или единичным значением соответствующего двоичного разряда.

Представим числовую последовательность, составленную из m значений, где m = 2R. Очевидно, что номер позиции любого элемента этой последовательности может быть представлен в двоичном виде из R разрядов. Пусть значение элемента этой последовательности, расположенного на позиции n определяется по формуле:

y(n) = a1(n)d1 + a2(n)d2 + a3(n)d3 +…+ aR(n)dR (1)

Здесь: y(n) – значение элемента последовательности, соответствующее позиции n;

ai(n) – значение (равное 0 или 1) двоичного разряда по номеру i, соответствующее позиции n;

di – значение заданного базиса позиционной системы счисления или «вес» двоичного разряда по номеру i.

Для базиса, представленного в соответствии с номерами разрядов значениями: 20, 21, 22,…, 2R-1 (номера разрядов возрастают слева на право), последовательность значений, определяемых по формуле (1), представляет собой натуральный ряд целых чисел в десятичном представлении.

Описанное правило позволяет формировать бесконечное множество числовых последовательностей, так как множество числовых значений базиса, строго говоря, бесконечно. На рис. 1 и рис. 2 представлены примеры последовательностей, сформированных по двум разным базисам. В Таблице 1 указаны числовые значения этих базисов для каждого двоичного разряда (R=6).

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

Рис. 1. Последовательность значений (базис-1)

Рис. 2. Последовательность значений (базис-2)

Таблица 1

Значения выбранных базисов

Номер разряда

1

2

3

4

5

6

Базис-1

0.591

-0.644

0.380

-1.009

-0.019

-0.048

Базис-2

-0.692

0.858

1.254

-1.594

-1.441

0.571

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

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

pR = m/2m (2)

Здесь: m = 2R – число позиций последовательности значений;

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

Зависимость критерия (2) от числа разрядов R представлена на рис. 3.

Рис. 3. Зависимость доли последовательностей формируемых по базису от её длины.

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

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

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

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

Первое. Коммутативное представление числовых последовательностей обеспечивает полиномиальный рост затрат памяти и числа операций в алгоритмах, реализуемых на их основе.

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

Второе. Позволяет значительно ослабить требования гипотезы компактности (H+), фактически сведя их к единственному - два разных образа, принадлежащие разным классам, не должны отображаться одной и той же точкой в признаковом пространстве [3]. Вместе с тем, взаимное расположение точек признакового пространства, принадлежащих разным классам, становится не существенным, так как не приводит к значительному увеличению временных и ёмкостных затрат алгоритмов, основанных на коммутативных представлениях числовых последовательностей.

Третье. Ранжирует признаки, участвующие в формировании признакового пространства. Другими словами, в заданном признаковом пространстве, определяет строго однозначный порядок признаков от «бесполезного» до «полезного», по их влиянию на вероятность ошибки распознавания. Это свойство оказывается полезным в алгоритме распознавания на этапе формирования признакового пространства. С его помощью, при необходимости, можно осуществлять ротацию признаков, не снижая надёжность распознавания.

Четвёртое. Обеспечивает объективный контроль надёжности распознавания для заданного признакового пространства. Что позволяет своевременно определять необходимость расширения признакового пространства за счёт дополнительных признаков. Или наоборот, начинать удалять избыточные признаки, из числа «бесполезных», без ущерба для надёжности распознавания в данном алгоритме.

К настоящему времени нейронные сети на основе коммутативных представлений числовых последовательностей, в рамках компьютерного моделирования, подтвердили свою эффективность в решении ниже представленных прикладных задач[2].

1. Распознавание речевых команд.

2. Помехоустойчивое кодирование.

3. Аппроксимация и сжатие данных с потерями.

4. Определение простых чисел без разложения на множители.

5. Технические системы управления и управляемый выбор альтернатив.

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

Заключение

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

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

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

1. Вальциферов. Ю.В., Дронов В.П. Ч.1. Арифметические и логические основы ЭВМ. Учебное пособие // Московский государственный университет экономики, статистики и информатики – М., С 20-23.

2. Легков Г.А. Нейроподобная сеть на основе топологических преобразований цифровых последовательностей // Нейроинформатика-2010. XII Всероссийская научно-техническая конференция. Сборник научных трудов. Ч. 2. М.: МИФИ. 2010. C. 75-82.

3. Загоруйко Н.Г. Гипотезы компактности в методах анализа данных // Сиб. журн. индустр. матем., 1:1 (1998), 115–119

Обсудить на форуме (комментариев 16).
Исследования Распознавание Ограниченные возможности разбиений позиционных систем счисления и моделирование нейроподобных сетей