Резкие пороги емкости в линейной ассоциативной памяти

## Перевод abstract Сколько ассоциаций ключ-значение может сохранить линейная память размером $d\times d$? Мы показываем, что ответ зависит не только от $d^2$ степеней свободы в матрице памяти, но и от критерия извлечения. В изотропной гауссовской модели для хранимых пар мы демонстрируем, что извлечение топ-1, при котором каждый сигнал должен превзойти своего крупнейшего отвлекающего фактора, требует логарифмической модели размера $d^2\asymp n\log n$. Мы доказываем, что конструкция памяти с корреляционной матрицей, которая хранит ассоциации путем суперпозиции внешних произведений ключ-цель, достигает этого масштаба через резкий фазовый переход, и что такое же масштабирование необходимо для любой линейной памяти. Таким образом, логарифм является внутренней экстремальной ценой декодирования winner-take-all. Далее мы рассматриваем извлечение по списку, при котором правильная цель не обязательно должна быть уникальным элементом с наивысшим баллом, но должна оставаться среди сильнейших кандидатов. Чтобы формализовать этот режим, мы предлагаем критерий Tail-Average Margin (TAM), выпуклый критерий верхнего хвоста, который сертифицирует включение правильной цели в контролируемый список кандидатов. При этом критерии извлечения по списку емкость следует квадратичному масштабу $d^2\asymp n$. При нагрузке $n/d^2\toα$ мы разрабатываем точную асимптотическую теорию для эмпирического рисков минимизатора TAM через двумерный скалярный вариационный принцип. Теория имеет богатую феноменологию: в пределе без рифленостей она дает замкнутую критическую нагрузку, отделяющую удовлетворительные и неудовлетворительные фазы, и предсказывает предельные законы истинных оценок, оценок конкурентов, маржей и процентных профилей. Наконец, экстраполяция с малым хвостом приводит к предполагаемому резкому порогу top-1 $d^2\sim 2n\log n$. ## Ключевые выводы 1. Количество ассоциаций, которые может хранить линейная память, зависит как от размерности памяти, так и от критерия извлечения. 2. Для извлечения top-1 требуется логарифмическое увеличение размера модели, что связано с фазовым переходом в конструкции памяти. 3. Извлечение по списку требует квадратичного масштаба и вводит новый критерий Tail-Average Margin (TAM). 4. Разработана точная асимптотическая теория, позволяющая предсказывать различные характеристики при заданной нагрузке. 5. Выведен предполагаемый резкий порог для top-1 извлечения, который может иметь важные практические последствия. ## Практическая значимость Результаты исследования имеют потенциальное применение в области машинного обучения и обработки данных, особенно в системах, где необходимо извлечение информации из больших объемов данных. Это может быть полезно для разработчиков алгоритмов, работающих с ассоциативной памятью, а также для исследователей в области теории информации и статистики. ## Ограничения и критика Работа не учитывает влияние шумов и ошибок в данных, что может существенно повлиять на результаты. Также не рассматриваются сложные структуры данных, которые могут требовать более сложных подходов к извлечению. Кроме того, в исследовании не учитываются практические аспекты реализации предложенных теорий в реальных системах, что может ограничить его применение.