О повышении эффективности вычислений при классификации изображений
Ключевые слова:
классификация изображений, полиномы, целые числа, байесовский классификатор
Аннотация
Рассмотрена автоматическая классификация изображений с помощью байесовского классификатора с целыми коэффициентами. Показано, как при сохранении качества классификации можно экономить память и уменьшать количество операций за счёт представления использующихся в классификаторе полиномов, отличающихся от общепринятых указанием только ненулевых коэффициентов. Коэффициенты полиномов округляются и представляются с помощью целых чисел (чисел с фиксированной точкой). Проанализирован способ хранения полиномов, позволяющий хранить только ненулевые коэффициенты полинома (использующиеся при этом для классификации вектора и числа хранятся обычным способом).
Для экспериментов использована база данных MNIST. Для представления коэффициентов полиномов взято семь бит. При хранении коэффициентов без округлений нужно 11,77 Мбайт, при хранении округленных коэффициентов в обычном виде — 2,93 Мбайт, при хранении только ненулевых округленных коэффициентов — 1,3 Мбайт. Количество операций сложения и умножения, необходимых для принятия решения о классовой принадлежности изображения, значительно снизилось.
Дан экономный способ хранения матриц с коэффициентами полиномов на диске. В эксперименте с базой данных MNIST потребовалось лишь 0,35 Мбайт памяти для хранения полиномов в базе данных.
Результаты работы можно использовать при разработке программно-аппаратных средств для автоматической классификации изображений. Интересно также изучение аналогичных приёмов для повышения эффективности вычислений в других классификаторах.
Литература
1. Ту Дж. Р., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978.
2. Tschiatschek S., Paul K., Pernkopf F. Integer Bayesian Network Classifiers // Machine Learning and Knowledge Discovery in Databases. Berlin, Heidelberg: Springer, 2014. Pp. 209—224.
3. Белага Э.Г. О вычислении значений многочлена от одного переменного с предварительной обработкой коэффициентов // Проблемы кибернетики. М.: Физматгиз, 1961. Вып. 5. С. 7—15.
4. Пан В.Я. Некоторые схемы для вычисления значений полиномов с вещественными коэффициентами // Там же. С. 17—29.
5. Селезнева С.Н. Сложность систем функций алгебры логики и систем функций трехзначной логики в классах поляризованных полиномиальных форм // Дискретная математика. 2015. Т. 27. Вып. 1. С. 111—122.
6. Маркелов Н.К. Нижняя оценка сложности функций трехзначной логики в классе поляризованных полиномов // Вестник Московского университета. Серия 15. «Вычислительная математика и кибернетика». 2012. Вып. 3. С. 40—45.
7. Косовская Т.М. Самообучающаяся сеть с ячейками, реализующими предикативные формулы // Труды СПИИРАН. 2015. №. 6. С. 94—113.
8. Алексиадис Н.Ф. Алгоритмическая неразрешимость проблемы полноты для полиномов с целыми коэффициентами // Вестник МЭИ. 2015. № 3. С. 110—117.
9. Алексиадис Н.Ф. Алгоритмическая неразрешимость задачи о нахождении базиса конечной полной системы полиномов с целыми коэффициентами // Интеллектуальные системы. Теория и приложения. 2016. Т. 20. Вып. 3. С. 19—23.
10. Мамонтов А.И., Мещанинов Д.Г. Проблема полноты в функциональной системе линейных полиномов с целыми коэффициентами // Дискретная математика. 2010. Т. 22. № 4. С. 64—82.
11. Мамонтов А.И., Мещанинов Д.Г. Алгоритм распознавания полноты в функциональной системе L(Z) // Дискретная математика. 2014. Т. 26. № 1. С. 85—95.
12. Мамонтов А.И. Об использующем суперпозиции способе эффективного вычисления систем линейных полиномов с целыми коэффициентами // Интеллектуальные системы. Теория и приложения. 2016. Т. 20. Вып. 3. С. 58—63.
13. Мамонтов А.И., Рябинов С.М. Об одном методе экономии памяти при классификации текстов // Программные системы: теория и приложения. 2017. Т. 8. № 4 (35). С. 133—147.
14. Gorban A.N., Wunsch D.C. The General Approximation Theorem // Proc. IEEE IJCNN'98. 1998. Pp. 1271—1274.
15. Горбань А.Н. Обобщенная аппроксимационная теорема и вычислительные возможности нейронных сетей // Сибирский журнал вычислительной математики. 1998. Т. 1. № 1. С. 11—24.
16. Половников В.С. О нелинейных характеристиках нейронных схем в произвольных базисах // Интеллектуальные системы. 2013. Т. 17. № 1—4. С. 87—90.
17. Tschiatschek S., Pernkopf F. On Bayesian Network Classifiers with Reduced Precision Parameters // IEEE Trans. Pattern Analysis and Machine Intelligence. 2015. V. 37 (4). Pp. 774—785.
18. Yi Y., Hangping Z., Bin Z. A New Learning Algorithm for Neural Networks with Integer Weights and Quantized Non-linear Activation Functions // Artificial Intelligence in Theory and Practice II. Boston: Springer, 2008. V. 276. Pp. 427—431.
19. Anguita D., Ghio A., Pischiutta S., Ridella S. A Support Vector Machine with Integer Parameters // Neurocomputing. 2008. V. 72. No. 1—3. Pp. 480—489.
20. Shuang Wu, Guoqi Li, Feng Chen, Luping Shi. Training and Inference with Integers in Deep Neural Networks // Proc. ICLR. 2018. Pp. 1—14.
---
Для цитирования: Мамонтов А.И. О повышении эффективности вычислений при классификации изображений // Вестник МЭИ. 2019. № 5. С. 129—134. DOI: 10.24160/1993-6982-2019-5-129-134.
---
Работа выполнена при поддержке: РФФИ (проект № 17-01-00485а)
#
1. Tu Dzh. R., Gonsales R. Printsipy raspoznavaniya obrazov. M.: Mir, 1978. (in Russian).
2. Tschiatschek S., Paul K., Pernkopf F. Integer Bayesian Network Classifiers. Machine Learning and Knowledge Discovery in Databases. Berlin, Heidelberg: Springer, 2014:209—224.
3. Belaga E.G. O Vychislenii Znacheniy Mnogochlena ot Odnogo Peremennogo s Predvaritel'noy Obrabotkoy Koeffitsientov. Problemy Kibernetiki. M.: Fizmatgiz,1961;5:7—15. (in Russian).
4. Pan V.Ya. Nekotorye Skhemy dlya Vychisleniya Znacheniy Polinomov s Veshchestvennymi Koeffitsientami. Tam zhe:17—29. (in Russian).
5. Selezneva S.N. Slozhnost' Sistem Funktsiy Algebry Logiki i Sistem Funktsiy Trekhznachnoy Logiki v Klassah Polyarizovannyh Polinomial'nyh Form. Diskretnaya Matematika. 2015;27;1:111—122. (in Russian).
6. Markelov N.K. Nizhnyaya Otsenka Slozhnosti Funktsiy Trekhznachnoy Logiki v Klasse Polyarizovannyh Polinomov. Vestnik Moskovskogo Universiteta. Seriya 15. «Vychislitel'naya Matematika I Kibernetika». 2012;3: 40—45. (in Russian).
7. Kosovskaya T.M. Samoobuchayushchayasya Set' s Yacheykami, Realizuyushchimi Predikativnye Formuly. Trudy SPIIRAN. 2015;6:94—113. (in Russian).
8. Aleksiadis N.F. Algoritmicheskaya Nerazreshimost' Problemy Polnoty dlya Polinomov s Tselymi Koeffitsientami. Vestnik MEI. 2015;3:110—117. (in Russian).
9. Aleksiadis N.F. Algoritmicheskaya Nerazreshimost' Zadachi o Nahozhdenii Bazisa Konechnoy Polnoy Sistemy Polinomov s Tselymi Koeffitsientami. Intellektual'nye Sistemy. Teoriya I Prilozheniya. 2016;20;3:19—23. (in Russian).
10. Mamontov A.I., Meshchaninov D.G. Problema Polnoty v Funktsional'noy Sisteme Lineynyh Polinomov s Tselymi Koeffitsientami. Diskretnaya Matematika. 2010; 22;4:64—82. (in Russian).
11. Mamontov A.I., Meshchaninov D.G. Algoritm Raspoznavaniya Polnoty v Funktsional'noy Sisteme L(Z). Diskretnaya Matematika. 2014;26;1:85—95. (in Russian).
12. Mamontov A.I. Ob Ispol'zuyushchem Superpozitsii Sposobe Effektivnogo Vychisleniya Sistem Lineynyh Polinomov s Tselymi Koeffitsientami. Intellektual'nye Sistemy. Teoriya i Prilozheniya. 2016;20; 3:58—63. (in Russian).
13. Mamontov A.I., Ryabinov S.M. Ob Odnom Metode Ekonomii Pamyati pri Klassifikatsii Tekstov. Programmnye Sistemy: Teoriya I Prilozheniya. 2017;8;4 (35): 133—147. (in Russian).
14. Gorban A.N., Wunsch D.C. The General Approximation Theorem. Proc. IEEE IJCNN'98. 1998:1271—1274.
15. Gorban' A.N. Obobshchennaya approksimatsionnaya Teorema i Vychislitel'nye Vozmozhnosti Neyronnyh Setey. Sibirskiy Zhurnal vychislitel'noy matematiki. 1998;1;1:11—24. (in Russian).
16. Polovnikov V.S. O Nelineynyh Kharakteristikah Neyronnyh Skhem v Proizvol'nyh Bazisah. Intellektual'nye Sistemy. 2013;17;1—4:87—90. (in Russian).
17. Tschiatschek S., Pernkopf F. On Bayesian Network Classifiers with Reduced Precision Parameters. IEEE Trans. Pattern Analysis and Machine Intelligence. 2015; 37 (4):774—785.
18. Yi Y., Hangping Z., Bin Z. A New Learning Algorithm for Neural Networks with Integer Weights and Quantized Non-linear Activation Functions. Artificial Intelligence in Theory and Practice II. Boston: Springer, 2008;276:427—431.
19. Anguita D., Ghio A., Pischiutta S., Ridella S. A Support Vector Machine with Integer Parameters. Neurocomputing. 2008;72;1—3:480—489.
20. Shuang Wu, Guoqi Li, Feng Chen, Luping Shi. Training and Inference with Integers in Deep Neural Networks. Proc. ICLR. 2018:1—14.
---
For citation: Mamontov A.I. On Increasing the Computation Efficiency in Classifying Images. Bulletin of MPEI. 2019;5:129—134. (in Russian). DOI: 10.24160/1993-6982-2019-5-129-134.
---
The work is executed at support: RFBR (project No. 17-01-00485а)
2. Tschiatschek S., Paul K., Pernkopf F. Integer Bayesian Network Classifiers // Machine Learning and Knowledge Discovery in Databases. Berlin, Heidelberg: Springer, 2014. Pp. 209—224.
3. Белага Э.Г. О вычислении значений многочлена от одного переменного с предварительной обработкой коэффициентов // Проблемы кибернетики. М.: Физматгиз, 1961. Вып. 5. С. 7—15.
4. Пан В.Я. Некоторые схемы для вычисления значений полиномов с вещественными коэффициентами // Там же. С. 17—29.
5. Селезнева С.Н. Сложность систем функций алгебры логики и систем функций трехзначной логики в классах поляризованных полиномиальных форм // Дискретная математика. 2015. Т. 27. Вып. 1. С. 111—122.
6. Маркелов Н.К. Нижняя оценка сложности функций трехзначной логики в классе поляризованных полиномов // Вестник Московского университета. Серия 15. «Вычислительная математика и кибернетика». 2012. Вып. 3. С. 40—45.
7. Косовская Т.М. Самообучающаяся сеть с ячейками, реализующими предикативные формулы // Труды СПИИРАН. 2015. №. 6. С. 94—113.
8. Алексиадис Н.Ф. Алгоритмическая неразрешимость проблемы полноты для полиномов с целыми коэффициентами // Вестник МЭИ. 2015. № 3. С. 110—117.
9. Алексиадис Н.Ф. Алгоритмическая неразрешимость задачи о нахождении базиса конечной полной системы полиномов с целыми коэффициентами // Интеллектуальные системы. Теория и приложения. 2016. Т. 20. Вып. 3. С. 19—23.
10. Мамонтов А.И., Мещанинов Д.Г. Проблема полноты в функциональной системе линейных полиномов с целыми коэффициентами // Дискретная математика. 2010. Т. 22. № 4. С. 64—82.
11. Мамонтов А.И., Мещанинов Д.Г. Алгоритм распознавания полноты в функциональной системе L(Z) // Дискретная математика. 2014. Т. 26. № 1. С. 85—95.
12. Мамонтов А.И. Об использующем суперпозиции способе эффективного вычисления систем линейных полиномов с целыми коэффициентами // Интеллектуальные системы. Теория и приложения. 2016. Т. 20. Вып. 3. С. 58—63.
13. Мамонтов А.И., Рябинов С.М. Об одном методе экономии памяти при классификации текстов // Программные системы: теория и приложения. 2017. Т. 8. № 4 (35). С. 133—147.
14. Gorban A.N., Wunsch D.C. The General Approximation Theorem // Proc. IEEE IJCNN'98. 1998. Pp. 1271—1274.
15. Горбань А.Н. Обобщенная аппроксимационная теорема и вычислительные возможности нейронных сетей // Сибирский журнал вычислительной математики. 1998. Т. 1. № 1. С. 11—24.
16. Половников В.С. О нелинейных характеристиках нейронных схем в произвольных базисах // Интеллектуальные системы. 2013. Т. 17. № 1—4. С. 87—90.
17. Tschiatschek S., Pernkopf F. On Bayesian Network Classifiers with Reduced Precision Parameters // IEEE Trans. Pattern Analysis and Machine Intelligence. 2015. V. 37 (4). Pp. 774—785.
18. Yi Y., Hangping Z., Bin Z. A New Learning Algorithm for Neural Networks with Integer Weights and Quantized Non-linear Activation Functions // Artificial Intelligence in Theory and Practice II. Boston: Springer, 2008. V. 276. Pp. 427—431.
19. Anguita D., Ghio A., Pischiutta S., Ridella S. A Support Vector Machine with Integer Parameters // Neurocomputing. 2008. V. 72. No. 1—3. Pp. 480—489.
20. Shuang Wu, Guoqi Li, Feng Chen, Luping Shi. Training and Inference with Integers in Deep Neural Networks // Proc. ICLR. 2018. Pp. 1—14.
---
Для цитирования: Мамонтов А.И. О повышении эффективности вычислений при классификации изображений // Вестник МЭИ. 2019. № 5. С. 129—134. DOI: 10.24160/1993-6982-2019-5-129-134.
---
Работа выполнена при поддержке: РФФИ (проект № 17-01-00485а)
#
1. Tu Dzh. R., Gonsales R. Printsipy raspoznavaniya obrazov. M.: Mir, 1978. (in Russian).
2. Tschiatschek S., Paul K., Pernkopf F. Integer Bayesian Network Classifiers. Machine Learning and Knowledge Discovery in Databases. Berlin, Heidelberg: Springer, 2014:209—224.
3. Belaga E.G. O Vychislenii Znacheniy Mnogochlena ot Odnogo Peremennogo s Predvaritel'noy Obrabotkoy Koeffitsientov. Problemy Kibernetiki. M.: Fizmatgiz,1961;5:7—15. (in Russian).
4. Pan V.Ya. Nekotorye Skhemy dlya Vychisleniya Znacheniy Polinomov s Veshchestvennymi Koeffitsientami. Tam zhe:17—29. (in Russian).
5. Selezneva S.N. Slozhnost' Sistem Funktsiy Algebry Logiki i Sistem Funktsiy Trekhznachnoy Logiki v Klassah Polyarizovannyh Polinomial'nyh Form. Diskretnaya Matematika. 2015;27;1:111—122. (in Russian).
6. Markelov N.K. Nizhnyaya Otsenka Slozhnosti Funktsiy Trekhznachnoy Logiki v Klasse Polyarizovannyh Polinomov. Vestnik Moskovskogo Universiteta. Seriya 15. «Vychislitel'naya Matematika I Kibernetika». 2012;3: 40—45. (in Russian).
7. Kosovskaya T.M. Samoobuchayushchayasya Set' s Yacheykami, Realizuyushchimi Predikativnye Formuly. Trudy SPIIRAN. 2015;6:94—113. (in Russian).
8. Aleksiadis N.F. Algoritmicheskaya Nerazreshimost' Problemy Polnoty dlya Polinomov s Tselymi Koeffitsientami. Vestnik MEI. 2015;3:110—117. (in Russian).
9. Aleksiadis N.F. Algoritmicheskaya Nerazreshimost' Zadachi o Nahozhdenii Bazisa Konechnoy Polnoy Sistemy Polinomov s Tselymi Koeffitsientami. Intellektual'nye Sistemy. Teoriya I Prilozheniya. 2016;20;3:19—23. (in Russian).
10. Mamontov A.I., Meshchaninov D.G. Problema Polnoty v Funktsional'noy Sisteme Lineynyh Polinomov s Tselymi Koeffitsientami. Diskretnaya Matematika. 2010; 22;4:64—82. (in Russian).
11. Mamontov A.I., Meshchaninov D.G. Algoritm Raspoznavaniya Polnoty v Funktsional'noy Sisteme L(Z). Diskretnaya Matematika. 2014;26;1:85—95. (in Russian).
12. Mamontov A.I. Ob Ispol'zuyushchem Superpozitsii Sposobe Effektivnogo Vychisleniya Sistem Lineynyh Polinomov s Tselymi Koeffitsientami. Intellektual'nye Sistemy. Teoriya i Prilozheniya. 2016;20; 3:58—63. (in Russian).
13. Mamontov A.I., Ryabinov S.M. Ob Odnom Metode Ekonomii Pamyati pri Klassifikatsii Tekstov. Programmnye Sistemy: Teoriya I Prilozheniya. 2017;8;4 (35): 133—147. (in Russian).
14. Gorban A.N., Wunsch D.C. The General Approximation Theorem. Proc. IEEE IJCNN'98. 1998:1271—1274.
15. Gorban' A.N. Obobshchennaya approksimatsionnaya Teorema i Vychislitel'nye Vozmozhnosti Neyronnyh Setey. Sibirskiy Zhurnal vychislitel'noy matematiki. 1998;1;1:11—24. (in Russian).
16. Polovnikov V.S. O Nelineynyh Kharakteristikah Neyronnyh Skhem v Proizvol'nyh Bazisah. Intellektual'nye Sistemy. 2013;17;1—4:87—90. (in Russian).
17. Tschiatschek S., Pernkopf F. On Bayesian Network Classifiers with Reduced Precision Parameters. IEEE Trans. Pattern Analysis and Machine Intelligence. 2015; 37 (4):774—785.
18. Yi Y., Hangping Z., Bin Z. A New Learning Algorithm for Neural Networks with Integer Weights and Quantized Non-linear Activation Functions. Artificial Intelligence in Theory and Practice II. Boston: Springer, 2008;276:427—431.
19. Anguita D., Ghio A., Pischiutta S., Ridella S. A Support Vector Machine with Integer Parameters. Neurocomputing. 2008;72;1—3:480—489.
20. Shuang Wu, Guoqi Li, Feng Chen, Luping Shi. Training and Inference with Integers in Deep Neural Networks. Proc. ICLR. 2018:1—14.
---
For citation: Mamontov A.I. On Increasing the Computation Efficiency in Classifying Images. Bulletin of MPEI. 2019;5:129—134. (in Russian). DOI: 10.24160/1993-6982-2019-5-129-134.
---
The work is executed at support: RFBR (project No. 17-01-00485а)
Опубликован
2018-11-08
Выпуск
Раздел
Теоретические основы информатики (05.13.17)
