Structure-based associative memory

From: Medyntsev, Anatole ( anatole.medintsev@novavox.ru ) Date: 2000-02-09 18:02

 (Просьба использовать равноширинный шрифт чтобы не "сползали" схемы)
 

 Медынцев А.Л.
 

 Постоянная ассоциативная память, основанная на изменении структуры.
 

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

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

 Логика работы традиционных систем ассоциативной
   памяти как правило состоит в следующем:
   - на вход подается двоичный вектор-образец в котором
   задана только часть битов.
   - осуществляется выборка тех векторов (вектора),
   хранимых в памяти, так что значения заданных
   в векторе-образце битов совпадают с соответсвующими
   битами выбираемых векторов.
   Данная модель реализует ассоциативную выборку по точному
   совпадению. Альтернативный вариант, состоит в том, что в
   качестве результата выбирается вектор, "ближайший" к
   вектору-образцу в том смысле, что он содержит минимальное
   количество битов, отличающихся от заданных в образце
   среди всех векторов, хранимых в памяти.
 

 Если результат выборки - несколько векторов, то в
   некоторых приложениях в качестве результата можно
   использовать "обобщенный" вектор (например такой, что
   N-й бит получает то значение, которое имеют большинство
   N-ых битов векторов в выборке).
 

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

 Очевидные отличия состоят в следующем:
 

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

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

 3. "Природная" ассоциативная память может осуществлять
   выборку в условиях искаженного образца, по которому
   осуществляется поиск. (т.е. можно предположить, что
   реализуется модель поиска "ближайшего"). C другой
   стороны, достаточно часто ассоциативная выборка
   выполняется с ошибками. То есть выборка выполняется
   правильно с некоторой вероятностью <1.
 

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

 Ниже рассматривается один из возможных
   подходов.
 

 1. Ассоциативный поиск в пространстве
   троичных векторов.
 

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

 	На вход системы ассоциативной памяти подается вектор-образец
   в котором некоторые биты заданы, а значения остальных не
   определено. Поэтому для задания образца обычно используют
   два вектора. Первый из них содержит значения битов, а второй-
   определяет какие из них активны (заданы). Очевидно, что
   такое кодирование избыточно и достаточно использовать векторы,
   каждый элемент которых может принимать
   три значения +1 - True, -1 False, 0 - Undef.
   (В дальнейшем обозначается "+", "-", "0" соответственно.).
   В дальнейшем изложении мы будем использовать именно такие векторы.
 

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

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

 Предполагаем, что запоминаемые векторы не содержат 0-ых
   элементов, а вектор-образец может содержать.
 

 Пусть заданы два вектора размерности N: a[i] и b[i]. В
   качестве меры близости между этими векторами будем
   использовать величину:
   D(a,b)=а[1]*b[1]+....+a[N]*b[N]
 

 (по существу эта величина суть
   <число совпадающих битов
   >-<число несовпадающих битов
   >)
 

 Замечание: Является ли данный способ вычисления "близости"
   универсальным в том смысле, что он подходит для всех задач?
   Гипотеза состоит в том, кодируя некоторые признаки не одним
   битом а несколькими, мы можем получить ту меру близости,
   которая необходима в задаче.
 

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

 Таким образом, если реализовывать такую память в виде некоторого
   устройства, то оно будет содержать следующие основные элементы.
 

 	- вычислитель степени "близости": содержит N входов, на которые
   подаются значения элементов вектора-образца и М выходов,
   на которых мы получаем величину D для каждого из хранимых
   векторов.
 

 	- устройство выбора максимального элемента (элементов):
   M входов, M выходов. Выдает вектор который содержит 1 в том (тех)
   элементе (-ах), где достигается максимум. Остальные элементы
   устанавливаются в 0.
 

 	- генератор результата: содержит M входов и N выходов;
   Минимально должен обеспечивать следующее:
   если на одном из входов 1, то на выходе должен генерироваться
   вектор, соответствующий этому входу. (Вопрос о том, что
   должно происходить, если мы имеем 1 на нескольких входах пока
   не рассматривается).
 

 	Это очень приближенная схема, в которй мы не фиксируем в какой форме
   (цифровой, аналоговой ) реализованы все элементы устройства. Для логики
   функционирования это не важно.
 

 Очевидно, что для вычисления величины D(m,v[l]) для
   всех M векторов требуется N*M операций типа
   сложение/вычитание (умножение сводится к тривиальным
   логическим операциям, поскольку элементы векторов +1,-1 or 0.).
   Естественно можно построить устройство из М*N сумматоров/вычитателей,
   реализующее вычисление этих величин. Очевидно, что такой вариант не
   годится, поскольку
   - число элементов оказывается большим;
   - сами элементы (сумматоры), если их реализовывать
   как цифровые, достаточно сложны;
   Так что, ниже мы опишем некоторые возможные подходы решения следующих
   проблем:
   - как уменьшить число элементов в таком устройстве;
   - какие элементы, существенно более простые в реализации,
   чем сумматоры использовать в качестве базовых;
 

 Вопрос: можно ли уменьшить об'ем необходимых вычислений,
   зная заранее какие именно векторы запоминаются. Другими
   словами, можно ли построить преобразователь с N входами
   и M выходами, состоящий из менее чем M*N сумматоров,
   который по заданному входному вектору-образцу вычисляет
   величину D для всех M векторов.
 

 Известен очень эффективный способ вычисления этих величин
   для случая когда набор векторов представляет собой
   функции Уолша.
   (функции Уолша образуют матрицу, известную как
   матрица Адамара). (см. [1]).
   Матрица Адамара имеет размерность N=2**n.
   Ниже приведена матрица, образованная функциями Уолша
   для N=2**3=8 (с точностью до перестановки строк это
   матрица Адамара для N=8)
 

   + + + + + + + +
   + + + + - - - -
   + + - - + + - -
   + + - - - - + +
   + - + - + - + -
   + - + - - + - +
   + - - + + - - +
   + - - + - + + -
 

 Преобразование Уолша-Фурье реализует умножение
   вектора на эту матрицу за N*Ln(N) операций типа
   сложение/вычитание (Ln - логарифм по основанию 2).
   Получаемый вектор-результат и есть величины D для
   вектора-образца и векторов, образующих матрицу Адамара
   (известны как функции Уолша).
 

 Структура быстрого преобразователя Уолша-Фурье (N=8) имеет
   следующий вид:
 

 <вход>
 

   | |  | | | |  | |
   +o+ -+o+ +o+ -+o+
   | |  | | | |  | |
   | L-+] | | L-+] |
   | ---| | | ---| |
   | |  | | | |  | |
   +o+  +o+ +o+  +o+
   | |  | | -- | -- |
   | |  | L-+--+-+] |
   | | L---+] | || |
   | L--] || | || |
   | |  || | || |
   | ---+----| | || |
   | |  | ---+-- || |
   | |  | | | ---| |
   | |  | | | |  | |
   | |  | | | |  | |
   +o+ -+o+ +o+ -+o+
   | |  | | | |  | |
    <выход>
    ,где элемент
   a| |b
    | |
    +o+
   c| |d
    реализует следующие операции:
 

 с=a+b;
   d=a-b;
 

 структура преобразователя определяется рекурсивно
   (см [2]) и содержит в общем случае N*Ln(N)/2 таких
   элементов.
   Для того, чтобы получить на выходе вектор,
   на котором достигается максимум величины D необходимо выполнить
   следующие операции:
   - выполнить преобразование Уолша-Фурье для вектора образца;
   - выбрать максимальный элемент (элементы) в полученном векторе;
   - выполнить обратное преобразование Уолша-Фурье для вектора,
   элементы которого равны 1, для максимальных значений и 0
   для остальных. Таким образом, если результат выборки один
   вектор, то на выходе будет получен именно он, если несколько,
   то поэлементная сумма выбранных векторов. В последнем случае,
   в качестве "обобщенного" результата выборки можно использовать sign
   от полученного вектора.
   Общая схема преобразователя N=8 имеет вид:
 

   <вход>
 

    | |  | |  | |  | |
   -+-+--+-+--+-+--+-+]
   |Преобразователь   |
   |  Уолша-Фурье     |
   |                  |
   |                  |
   LT-T--T-T--T-T--T-T-
   -+-+--+-+--+-+--+-+]
   |Генератор         |
   |вектора максимумов|
   LT-T--T-T--T-T--T-T-
   -+-+--+-+--+-+--+-+]
   |Обратный          |
   |преобразователь   |
   | Уолша-Фурье      |
   |                  |
   LT-T--T-T--T-T--T-T-
    <выход>
 

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

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

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

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

 Ниже излагается подход, использующий БП Уолша-Фурье.
   Вопрос о его эффективности также остается открытым.
   Можно ли воспользоваться этим результатом для произвольного
   набора векторов?
 

 	 Пусть задано М векторов размерности N (т.e. матрица МxN).
   Идея использования преобразователя УФ для произвольной
   матрицы основана на том, что
   - можно переставлять строки и столбцы исходной
   матрицы;
   - в преобразователе УФ можно использовать только часть
   входов и часть выходов;(На неиспользуемые входы
   подается значение 0).
 

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

 	 Исходная матрица:
 

 	 + - + -
   + + - -
   - - + -
   + - - +
 

 	Результат погружения:
 

   3 1 4 2
   + + + + + + + +
   1 + + + + - - - -	 Числами обозначены номера строчек/столбцов
   + + - - + + - - исходной матрицы.
   3 + + - - - - + +
   4 + - + - + - + -
   2 + - + - - + - +
   + - - + + - - +
   + - - + - + + -
 

 Существует конструктивное доказательство того, что для произвольной
   матрицы MxN такая матрица Адамара существует. Реализован
   алгоритм выполняющий операцию "погружения" для произвольной
   матрицы (результат получен Е.C. Лавровой).
 

 Если исходная матрица "похожа" на матрицу Адамара, то размерность
   матрицы	в которую ее удается "вписать" не сильно отличается от исходной,
   и следовательно преобразователь остается достаточно компактным.
   Однако, в худшем случае, размерность необходимой матрицы Адамара равна
   2**N, где N - длина строк исходной матрицы, и размер преобразователя
   становится недопустимо большим.
 

 	Как решить эту проблему?
   Каждому входу преобразователя УФ соответствует столбец матрицы
   Адамара, каждому выходу - строка.
   Таким образом, в терминологии преобразователя операция "вписывания"
   состоит в выборе подходящих входов/выходов ПУФ.
   В результате используется только часть входов и выходов преобразователя.
   Зная какие именно входы/выходы необходимы в конкретном случае
   общую структуру преобразователя можно упростить за счет:
   - удаления элементов, выходные значения которых не используются;
   - упрощения или удаления элементов, входы которых не используются;
   (Вход не используется - т.е. на входе 0)
 

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

 ----------------------------------------------------------------
   Oбозначения:
    |
   -+] разветвление
   | |
    -+-]
   L-T-- унарный минус
    | выход не используется
   -+-
 

 --------------------------------------------------------------------
 

 Правила редукции:
 

   0
   | | |
   | | -
   > -+]
   +o+ | |
   | | -+-]
   L-T--
    0
   | | |
   | | -
   > -+]
   +o+ | |
   | |
    -+-]
   L-T-- L--]|
   | | -
   > --+-
   +o+ +o+
   | | | |
   -+-]
   L-T--
   | |
   --+---] |
   | ----+-+
   | | | |
   | | | | -
   > | |
   | | | | | |
   +o+ +o+ +o+
   | | | | | |
 

 и.т.д.
 

 --
 

 ------------------------------------------------------------------------
 

 Например, eсли ПУФ используется так:
   (т.е. задействовано 3 входа и 3 выхода )
 

   0 0 0 0 0
   | | | | | | | |
   +o+ -+o+ +o+ -+o+
   | | | | | | | |
   | L-+] | | L-+] |
   | ---| | | ---| |
   | | | | | | | |
   +o+ +o+ +o+ +o+
   | | | | -- | -- |
   | | | L-+--+-+] |
   | | L---+] | || |
   | L--] || | || |
   | | || | || |
   | ---+----| | || |
   | | | ---+-- || |
   | | | | | ---| |
   | | | | | | | |
   | | | | | | | |
   +o+ -+o+ +o+ -+o+
   |-+ | | | |-+ |
   -+ -+ -+
 

 то результат редукции имеет вид:
   (порядок входов/выходов сохранен)
 

   | | |
   | | |
   +o+ --+]
   | L---]| |
   | ----+----
   | | | |
   | | | |
   | | | |
   +o+ +o+
   | | -+ |
   | L-----+--]
   | | |
 

 В какой степени такая редукция сокращает исходный ПУФ пока неясно.
   Гипотеза состоит в том, что в худшем случае преобразователь, полученный
   в результате "погружения" в матрицу Адамара и последующей редукции содержит
   не больше элементов, чем дает прямое использование М*N сумматоров.
   Если это так, то число элементов преобразователя для
   матрицы MxN оценивается как:
 

 N*Lg(N) <= Ne <= М*N,
 

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

 	В целом, если такая оценка будет достаточно хорошей, и удастся
   решить технические проблемы реализации таких преобразователей
   а именно:
   - как создавать об'екты, структура которых зависит от хранимой
   в них информации;
   - как эффективно реализовать базовый элемент;
 

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

 	2. Реализация базового элемента.
 

 	Если ориентироваться на создание ассоциативной памяти, состоящей из,
   по крайней мере, нескольких тысяч базовых элементов типа
   сложение/вычитание, то использование в качестве таких базовых
   элементов обычных сумматоров явно нереально.
 

 	Известна аналоговая реализация преобразователя Уолша-Фурье [3],
   (использует резисторы и диоды). Однако при большом количестве
   элементов добиться стабильной работы подобной схемы по видимому не
   удастся.
 

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

 	Прежде всего отметим, что работа ассоциативного преобразователя
   обеспечивается существованием обратного преобразования. Из структуры
   ПФУ видно, что его обратимость есть следствие обратимости базового
   элемента:
 

 a| |b
   | |
   +o+
   c| |d
 

 	Таким образом, если мы хотим сохранить обратимость преобразования,
   необходимо, чтобы базовая операция была обратимой.
   В качестве такой операции можно попытаться использовать операцию,
   заданную на множестве {-1,0,+1} и определяемую так:
 

   | a | b |c=a+b |d=a-b| (***)
   +---+----+-------+-----+
   | 1 | 1 | 1 | 0 |
   | 1 | 0 | 1 | 1 |
   | 1 | -1 | 0 | 1 |
   | 0 | 1 | 1 | -1 |
   | 0 | 0 | 0 | 0 |
   | 0 | -1 | -1 | 1 |
   | -1| 1 | 0 | -1 |
   | -1| 0 | -1 | -1 |
   | -1| -1 | -1 | 0 |
   | | | | |
   L---+----+-------+------
 

 	При использовании этой операции на выходе преобразователя УФ могут
   появляться только 1,0,-1. Поэтому вместо выбора элемента,
   на котором достигается	максимум выбираются элементы равные 1.
 

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

 Некоторое развитие этой идеи - использование базового
   элемента, поведение которого имеет вероятностный характер.
   Например можно логику работы вышеприведенного элемента
   изменить так: исключить значение 0; результат операции
   для случаев 0 определяется случайно
   (с вероятностью 0.5 - "+1", 0.5 - "-1"). В этом случае
   по статистике появления на выходе 1 и -1,по-видимому,
   можно более точно оценить величину D, чем при использовании
   операций (***).
 

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

 	Здесь следующие вопросы подлежат исследованию:
   - как и для чего можно использовать такую упрощенную
   ассоциативную память (насколько часто она выдает "ошибочные"
   результаты; какое количество заданных битов вектора-образца
   обеспечивает достаточно надежную выборку и.т.п.)
   - как реализовать наиболее эффективно такую базовую операцию;
   - может ли найти эта упрощенная операция применение в областях,
   где традиционно применяются преобразователи Уолша-Фурье.
 

 В данном материале не затрагивались вопросы, связанные с технололгией,
   поскольку эта сфера автору не известна совершенно. Общая ситуация в области
   технологии такова, что традиционная технология ориентирована на серийный
   выпуск устройств одинаковой структуры. Генерация структуры, индивидуальной
   для каждой совокупности векторов-очень дорого. Поэтому необходима какя-то
   иная технология (если таковая существует), при которой технологический
   процесс управляется непосредственно набором векторов, которые необходимо
   запомнить. Как реализовать такое "выращивание" - управляемое
   инфрормацией?....
 

 ------------------------------------------------------------------------
 

 	Автор не является специалистом по ассоциативной памяти;
   Идея использования БП Уолша-Фурье возникла достаточно
   случайно.
   Поэтому автор нуждается в конструктивной критике и поддежке;
 

 ----------------------------------------------------------------------------
 

 P.S.
   Модель "внимания" основанная, использующая приближенную выборку.
 

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

 Как известно минимальная глубина дерева поиска обеспечивается при его
   сбалансированности. Поэтому стратегия опроса должна быть следующей:
   необходимо запрашивать тот бит, который обеспечивает наиболее
   сбалансированное разбиение текущей выборки. Более точно: нужно
   просуммировать все вектора текущей выборки
   (считая, что они состоят из 1 и -1) и опросить тот бит, для котрого значение
   суммы ближе к 0. (В результате опроса будет получена новая выборка
   с которой повторяется тот же процесс).
   Если положить, что результат выборки в случае, если выбрано
   несколько векторов выдается в виде суммы этих векторов, то весь процесс можно
   рассматривать как пошаговое уточнение резулдьтата, при котором на каждом
   шаге опрашивается тот бит, значение которого ближе всего к значению
   "не определено". Такое "поведение" является грубой моделью поведения
   человека при изучении об'ектов (в частности при задавании вопросов).
   Вопросы задаются про те признаки, значение которых в наибольшей степени не
   определено.
 

 Можно предположить, что движение глаз (переключение внимания)
   при распознавании изображения также может быть рассмотрено в рамках этой
   модели.
 

 P.P.S
   Отдельный случай, когда сигнал поступает последовательно
   Для БПФ Фурье известно как выстраивать вычисления в этом случае.
   В нашем случае, когда у нас урезанный преобразователь Фурье надо
   действовать по аналогии с обычным БПФ Уолша. Как - вопрос.
   (вроде бы больших проблем быть не должно).
 

 Может это и все, а может какого-то куска не хватает пока не додумал.