回路計算量理論に基づく視覚探索を実現するニューラルネットワークの計算原理の解明

基于电路复杂性理论阐明实现视觉搜索的神经网络计算原理

• 批准号: 22K11897
• 负责人: 内沢 啓
• 金额: $ 1.91万
• 依托单位: Yamagata University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22K11897/
• 关键词: 回路計算量; ニューラルネットワーク; 計算複雑さ; 視覚探索

本年度は視覚探索にかかわる論理関数の中でも特に、Conjunction Search 関数と呼ばれる論理関数（Conj関数）に着目し、Conj関数を計算するしきい値回路について、素子数がどれほど必要になるのかを理論的に調査することにより、Conj関数がしきい値回路にとってどれほど難しい情報処理タスクであるかについて評価を行った。その主結果として、ニューラルネットワークの理論モデルとしてしきい値回路を捉えた際に重要なパラメータとなる段数、エネルギー、重みについて、段数とエネルギーがともに準線形に制限されおり、かつ重みが準指数に制限されていた場合、Conj関数を計算するためにしきい値回路が必要とする素子数が指数的に大きいことを明らかにした。Conj関数は定数段数、線形エネルギーかつ定数重みのしきい値回路で計算可能であることから、この結果は段数とエネルギーに対する制限が、しきい値回路の計算能力に非常に大きな影響を与えることを示唆している。また、実際のニューラルネットワークでも段数、エネルギー、重みといったパラメータに対して、計算資源として制限があると考えられるため、Conj関数に類する情報処理タスクが、ニューラルネットワークにとって計算困難であることも示唆する結果と言える。加えて、この素子数が指数個必要となることを示す結果が、特定の条件下の下ではほぼ最適なものであることも、具体的にConj関数を計算するしきい値回路を設計することにより同時に示した。本研究の結果は、Conj関数を計算するしきい値回路だけでなく、行列の階数に関連するある条件を満たす論理関数であれば適用できるものとなっており、幅広い情報処理タスクについて、ニューラルネットワークが同様の困難性に直面している可能性を示唆する結果となっている。

This year, we will explore the logic relationship of the middle class, Conjunction Search relationship and call logic relationship (Conj relationship), focus on the purpose, Conj relationship calculation, value loop, element number, necessary, theoretical investigation, information processing, evaluation, etc. The main result is that the number of segments, the number of segments. Conj is related to the number of fixed segments, the number of linear segments, and the number of linear segments. The number of segments, the number of occurrences, the occurrence, the number of occurrences, the occurrences, the occurrence, the number of occurrences, the occurrences, the occurrence, the occurrence, the number of occurrences, the occurrence, the The number of elements added to the index is necessary to indicate the result. Under certain conditions, the optimal value is calculated. The specific number of elements is calculated. The loop is designed. The results of this study show that the logical correlation is applicable to the calculation of the Conj correlation, the difficulty of the Conj correlation, and the possibility of the conj correlation.

项目成果

An <i>O</i>(<i>n</i>²)-Time Algorithm for Computing a Max-Min 3-Dispersion on a Point Set in Convex Position

计算凸位置点集最大-最小3-色散的<i>O</i>(<i>n</i>²)时间算法

• DOI: 10.1587/transinf.2021fcp0013
• 发表时间: 2022
• 期刊: IEICE Transactions on Information and Systems
• 影响因子: 0.7
• 作者: KOBAYASHI Yasuaki;NAKANO Shin-ichi;UCHIZAWA Kei;UNO Takeaki;YAMAGUCHI Yutaro;YAMANAKA Katsuhisa
• 通讯作者: YAMANAKA Katsuhisa

Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions

XOR 函数有向图上的同步布尔有限动力系统

• DOI: 10.1007/s00224-022-10111-x
• 发表时间: 2022
• 期刊: Theory of Computing Systems
• 影响因子: 0.5
• 作者: Ogihara M.;Uchizawa K.
• 通讯作者: Uchizawa K.