АРХИТЕКТУРА НЕЙРОННЫХ СЕТЕЙ НА ОСНОВЕ КОДОВ НА ГРАФАХ
Аннотация
Одним из важных достижений теории помехоустойчивого кодирования является
открытие кодов на графах и их важного подмножества низкоплотностных кодов
(LDPC-кодов). Используя проверочную матрицу кода на графе, можно получить марков-
ское случайное поле. LDPC-код может быть вложен в модель Изинга (разновидность мар-
ковского случайного поля) путем использования топологии тора с отрицательной
кривизной. При этом кодовые слова соответствуют седловым точкам (экстремумам) в
модели, а треппин-сеты соответствуют локальным минимумам. Использование
LDPC-кодов с увеличенным кодовым расстоянием позволяет максимально разнести седло-
вые точки, и таким образом повысить устойчивость нейронной сети к шуму и мощность
представления. При этом блочная и разряженная структура, характерная для тора отри-
цательной кривизны, упрощает мультиплексирование и снижает число обучаемых пара-
метров нейронной сети. Целью исследования являются снижение вычислительной сложно-
сти и увеличение точности нейронных сетей за счёт применения априорных структурных
(квазициклических) разряженных графов для широкого класса задач машинного обучения на
марковских случайных полях. В работе представлен новый подход, позволяющий осуществлять синтез архитектур нейронных сетей на основе кодов на графах. Предложенный под-
ход осуществляет эффективное представление марковских случайных полей за счёт при-
менения разряженных блочных (квазициклических) матриц (тензоров). Предложенный под-
ход позволяет снизить число обучаемых параметров и логарифмически снизить слож-
ность мультиплексирования тензора. Полученная на основе предложенного подхода архи-
тектура трансформера в задаче поиска пути (pathfinder) с конкурса трансформеров (long
range arena) заняла пятое место по точности классификации изображений 94.95% (1.72%
от первого места) при значительно меньшей сложности (число параметров (умножений)
синтезированной сети меньше в более чем 5 раз). Применение предложенного подхода к
задачам факторизации на плотных графах, сетевых задачах, поверхностных сетках, кова-
риационных матрицах позволило увеличить точность реконструкции по метрике Фробе-
ниуса (на отдельных задачах на 8 порядков) в сочетание с упрощением структуры мульти-
плексора в сравнение с методами усеченного сингулярного разложения TSVD и хордовой
разряженной факторизации.
Литература
Theory, 1981, Vol. 27, No. 5, pp. 533-547.
2. Mézard M., Montanari A. Information, Physics, and Computation. Oxford Graduate Texts,
2009, 569 p.
3. Tanner R., et al. LDPC block and convolutional codes based on circulant matrices, IEEE
Transactions on Information Theory, 2004, Vol. 50, No. 12, pp. 2966-2984.
4. Sukar L.E. Veroyatnostnye grafovye modeli. Printsipy i prilozheniya [Probabilistic graph
models. Principles and applications]. Moscow: DMK Press, 2021, 338 p.
5. Stan Z. Li. Markov Random Field Modeling in Image Analysis. Springer London, 2009, 362 p.
6. Usatyuk V., Sapozhnikov D., Egorov S. Spherical and Hyperbolic Toric Topology-Based
Codes on Graph Embedding for Ising MRF Models: Classical and Quantum Topology Machine
Learning, 2023, 71 p. Available at: https://arxiv.org/abs/2307.15778.
7. Yi T., et al. Long Range Arena: A Benchmark for Efficient Transformers. ICLR, 2021, 15 p.
8. Koen M.I. Prikladnaya lineynaya algebra dlya issledovateley dannykh [Applied linear algebra
for data scientists]. Moscow: DMK Press, 2023, 328 p.
9. Eckart C., Young G. The Approximation of One Matrix by Another of Lower Rank,
Psychometrika, 1936, Vol. 1, No. 3, pp. 211-218.
10. Fomin F. V., et al. Approximation schemes for low-rank binary matrix approximation problems,
ACM Transactions on Algor., 2019, Vol. 16, No. 1, pp. 12:1-12:39.
11. Camilli F., Mezard M. Matrix factorization with neural networks, American Physical Society,
Phys. Rev. E., 2023, Vol. 107, No. 6.
12. Khalitov R., et al. Sparse factorization of square matrices with application to neural attention
modeling, Neural Networks, 2022, Vol. 152, pp. 160-168.
13. Stoica I., et al. Chord: A scalable peer-to-peer lookup service for internet applications, ACM
SIGCOMM Computer Communication Review, 2001, Vol. 31, No 4, pp. 149-160.
14. Hu Xiao-Yu, Eleftheriou E., Arnold D. M. Regular and irregular progressive edge-growth tanner
graphs, IEEE Transactions on Information Theory, 2005, Vol. 51, No. 1, pp. 386-398.
15. Tian Tao, Jones C. R., Villasenor J. D., Wesel R. D. Selective avoidance of cycles in irregular
LDPC code construction, IEEE Transactions on Communications, 2004, Vol. 52, No. 8,
pp. 1242-1247.
16. Usatyuk V.S., Egorov S.I. Postroenie kvazitsiklicheskikh nedvoichnykh nizkoplotnostnykh
kodov na osnove sovmestnoy otsenki ikh distantnykh svoystv i spektrov svyaznosti [Construction
of quasi-cyclic non-binary low-density codes based on a joint assessment of their distant
properties and connectivity spectra], Telekommunikatsii [Telecommunications], 2016, No. 8,
pp. 32-40.
17. Usatyuk V.S., Egorov S.I. Ustroystvo dlya otsenki kodovogo rasstoyaniya lineynogo blochnogo
koda metodom geometrii chisel [Device for estimating the code distance of a linear block code
using the geometry of numbers method], Izvestiya Yugo-Zapadnogo gosudarstvennogo
universiteta. Seriya: Upravlenie, vychislitel'naya tekhnika, informatika. Meditsinskoe
priborostroenie [News of the South-West State University. Series: Management, computer technology,
computer science. Medical instrumentation], 2017, No. 4 (25), pp. 24-33.
18. Usatyuk V., Egorov S., Svistunov G. Construction of Length and Rate Adaptive MET
QC-LDPC Codes by Cyclic Group Decomposition, 2019 IEEE East-West Design & Test Symposium
(EWDTS). Batumi, Georgia, 2019, pp. 1-5.
19. Usatyuk V., Vorobyev I. Simulated Annealing Method for Construction of High-Girth
QC-LDPC Codes, Intern. Conf. on Telecom. and Signal Proc., 2018, pp. 1-5.
20. Usatyuk V.S. Matlab implementation of TSVD, SF Chord, LDPC PEG+ACE, QC-LDPC
SA+EMD (MET) codes sparse factorization. Available at: https://github.com/Lcrypto/ Classical-
and-Quantum-Topology-ML-toric-spherical.
