ABOUT THE NEW ALGORITM OF CHARACTERIZATION OF k-VALUED THRESHOLD FUNCTIONS
( Pp. 7-14)

More about authors
Burdeliov Alexander Vladimirovich st. prepodavatel kafedry matematicheskogo modelirovaniya i analiza dannyh fakulteta prikladnoy matematiki i informatiki
Belarusian State University Nikonov Vladimir G. Dr. Sci. (Eng.), Professor, Member at the Presidium of the Russian Academy of Natural Sciences
Russian Academy of Natural Sciences
Moscow, Russian Federation
For read the full article, please, register or log in
Abstract:
The article provides an overview of the known approaches to the characterization (learning) of Boolean and k-valued threshold functions. Proposed a new algorithm characterization of k-valued threshold functions for which we use expansion coefficients and increase coefficients for initial approximation of the coefficients of the linear form. Also we give the results of experimental comparisons of the new algorithm with a known Obradovic learning algorithm.
How to Cite:
Burdeliov A.V., Nikonov V.G., (2017), ABOUT THE NEW ALGORITM OF CHARACTERIZATION OF K-VALUED THRESHOLD FUNCTIONS. Computational Nanotechnology, 1: 7-14.
Reference list:
Korobkov V. K. Otsenka chisla monotonnykh funktsiy algebry logiki i slozhnosti algoritma otyskaniya razreshayushchego mnozhestva dlya proizvol noy monotonnoy funktsii algebry logiki // Doklady Akademii Nauk SSSR. -1963. - T. 150, № 4. - S. 744-747.
Korobkov V. K., Reznik T. L. O nekotorykh algoritmakh vychisleniya monotonnykh funktsiy algebry logiki // Doklady Akademii Nauk SSSR. -1962. - T. 147, № 5. - S. 1022-1025.
Butakov E.A. Metody sinteza releynykh ustroystv iz porogovykh elementov // - Moskva: Energiya, 1970.
Dertouzos M. Porogovaya logika // - Moskva: Mir, 1967.
V.I. Belyakov-Bodin i S.I. Rozenblit Issledovanie nekotorykh voprosov sinteza porogovykh funktsiy // - M. Institut teoreticheskoy i eksperimental noy fiziki Gos. Komiteta po ispol zovaniyu atomnoy energii SSSR, 1972.
Rozenblatt F. Printsipy neyrodinamiki. Pertseptrony i teoriya mekhanizmov mozga//- Moskva: Mir, 1963.
Minskiy M., Papert S. Perseptrony // - Moskva: Mir, 1971.
KHachiyan L.G. Polinomial nye algoritmy v lineynom programmirovanii // ZHurnal vychislitel noy matematiki i matematicheskoy fiziki , 1980, T 20.
Zolotykh N.YU. Rasshifrovka porogovykh i blizkikh k nim funktsiy mnogoznachnoy logiki. Dissert. kand. fiz.-mat. nauk. / Nizhegorodskiy gosudarstvennyy universitet im. N.I. Lobachevskogo, Nizhniy Novgorod, 1998.
Zolotykh N.YU. Rasshifrovka porogovykh i blizkikh k nim funktsiy. Dissert. dokt. fiz.-mat. nauk. FGBUN Institut matematiki im.S.L.Soboleva SO RAN, Moskva, 2013.
Nick Littlestone. Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm. Machine Learning. April 1988, Volume 2, Issue 4, pp 285-318.
Obradovic, Z. and Parberry, I. (1990) quot;Learning with Discrete Multi-Valued Neurons, quot; Machine Learning: Proc. 7th Int l. Conf., ed. B. W. Porter and R.J. Mooney, Austin, TX, Morgan-Kaufmann, pp. 392-399.
Obradovic, Z. (1990) quot;Learning with Discrete Multi-Valued Neurons, quot; Machine Learning: Proc. 7th Int l. Conf., ed. B. W. Porter and R.J. Mooney, Austin, TX, Morgan-Kaufmann, pp. 392-399.
Ngom A., Synthesis of Multiple-Valued Logic Functions by Neural Networks, Ph.D. Thesis Dissertation, Computer Science Department, University of Ottawa, Ontario, October 1998.
Anthony M. Learning Multivalued Multithreshold Functions. CDAM Research Report LSE-CDAM-2003-03, January 2003.
Grove A.J., Littlestone N., Schuurmans D. General Convergence Results for Linear Discriminant Updates. Machine Learning, 43, 173-210, 2001.
Chow C. On the characterization of threshold functions. In Proceedings of the Symposium on Switching Circuit Theory and Logical Design (FOCS), pages 34-38, 1961.
O Donnell R., Servedio R.A. The Chow parameters problem. In STOC, pages 517-526. 2008.
Anindya De, Diakonikolas Ilias. Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces. Journal of the ACM (JACM). Volume 61 Issue 2, April 2014.
Burdelyev A.V., Nikonov V.G. O postroenii analiticheskogo zadaniya k-znachnoy porogovoy funktsii. Computational nanotechnology. Vypusk № 2 / 2015.
Burdelev A.V., Nikonov V.G., Lapikov I.I. Raspoznavanie parametrov uzla zashchity informatsii, realizovannogo porogovoy k-znachnoy funktsiey // Trudy SPIIRAN. 2016. Vyp. 46. C. 108-127.
Karmarkar N. A New Polynomial Time Algorithm for Linear Programming , Combinatorica, Vol. 4, nr. 4, p. 373-395, 1984.
Filatov A. YU. Razvitie algoritmov vnutrennikh tochek i ikh prilozhenie k sistemam neravenstv. Dissert. kand. fiz.-mat. nauk. / Irkutskiy gosudarstvennyy universitet, Irkutsk, 2001.
Keywords:
threshold function, k-valued logic, characterization of threshold functions, growth factors, the coefficients of increase.