Розглядаються питання, пов’язані з розпізнаванням скінченних множин за допомогою двопорогових нейронних елементів. Показано, що задача навчання ДНЕ є NP-повною. Також наведено умови, виконання яких забезпечує двопороговість булевих функцій, які задаються за допомогою списків рішень.
We study finite set dichotomies on bithreshold neurons. We prove that training a BN is NP-complete task. We also give sufficient conditions ensuring that decision list represents a bithreshold function.
- Хайкин С. Нейронные сети: полный курс / С. Хайкин. – 2-е изд. – М.: Вильямс-Телеком, 2006.– 1104 с.
- Розенблатт Ф. Принципы нейродинамики / Ф. Розенблатт. – М. : Мир, 1965. – 480 с.
- Novikoff, A. On convergence proof for perceptrons / A. Novikoff. – Proceeding of Symposium on Mathematical Theory of Automata. Polytechnic Institute of Brooklyn. – 1963, v. XII.
- Минский М. Персептроны / М. Минский, С. Пейперт. – М.: Мир, 1971. – 262 с.
- Бахарев, А. Т. Оптимизация многопороговых моделей / А. Т. Бахарев // Пробл. случайного поиска. – Рига – 1975, вып. – C. 209–214.
- Blum A. Training a 3-Node Neural Network is NP-Complete / A. Blum, R. Rivest // Neural Networks. – 1992, Vol 5. – PP. 117–127.
- Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982. – 416 с.
- Anthony M. Discrete Mathematics of Neural Networks / M. Anthony. – Philadelphia: SIAM, 2001. – 132 c.
- Гече Ф. Властивостi бульових функцiй реалiзовних на двопорогових елементах / Ф. Гече, А. Батюк, В. Коцовський // Вiсник Нац. ун-ту «Львiвська полiтехнiка». Комп’ютерна iнженерiя та iнформацiйнi технологiї. – 2001. – № 438. – С. 22–25.
- Rivest, R. Learning decision lists / R. Rivest // Machine Learning – 1987. – # 2 – PP. 229–246.
- Anthony M. Threshold functions, decision lists, and the representation of Boolean Functions /M. Anthony // Technical Report NC-TR-96-028, Neurocolt Technical Reports, 1996.