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. Doctor of Engineering, Professor; member at the Presidium
Russian Academy of Natural Sciences
Moscow, Russian Federation
Belarusian State University Nikonov Vladimir G. Doctor of Engineering, Professor; member at the Presidium
Russian Academy of Natural Sciences
Moscow, Russian Federation
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.
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.
Related Articles
1. MATHEMATICAL MODELING, NUMERICAL METHODS AND COMPLEX PROGRAMS Pages: 6-13 Issue №6518
ABOUT BIJECTIVITY OF TRANSFORMATIONS DETERMINED BY QUASI-HADAMARD MATRIXES
bijective mapping
threshold function
quasidemocracy matrix
Show more
2. MATHEMATICAL MODELING, NUMERICAL METHODS AND COMPLEX PROGRAMS Pages: 26-30 Issue №5869
Geometrical approach to the argumentum of bijection of one coordinate-threshold reflection
bijective mapping
threshold function
multidimensional cones
quasidemocracy matrix
Show more
Information Security Pages: 36-41 DOI: 10.33693/2313-223X-2023-10-2-36-41 Issue №23034
Construction of a Reversible Full-cycle Transformation in a Threshold Basis
substitution
threshold function
full cycle
Show more
2. MATHEMATICAL MODELING, NUMERICAL METHODS AND COMPLEX PROGRAMS Pages: 31-36 Issue №5869
The constructive method for synthesis of balanced k-valued algebraic threshold functions
multivalued logic
threshold function
algebraic threshold function
balanced function
Show more
3. INFORMATION TECHNOLOGY AND AUTOMATION SYSTEMS Pages: 53-59 Issue №3742
ON A DECOMPOSITION OF BOOLEAN FUNCTIONS REPRESENTED BY QUADRATIC INEQUALITIES
Boolean functions
threshold function
decomposition
quadratic inequalities
Show more
Multiscale modeling for information control and processing Pages: 50-58 DOI: 10.33693/2313-223X-2021-8-3-50-58 Issue №19706
On the Complexity of Specifying a Symmetric Group of Permutations of Degree 2n in a Threshold Basis on a Promising Element Base
threshold function
symmetric group
implementation of permutations
threshold basis
complexity of implementation
Show more
6. INFORMATION SECURITY Pages: 39-49 Issue №9439
ABOUT POSSIBILITY OF USING FRACTAL MODELS IN DATA SECURITY SYSTEM CONSTRUCTION
fractal
protection of information
function complications
threshold function
Show more
INFORMATION SECURITY Pages: 132-139 Issue №11955
MODIFICATION OF A GEOMETRICAL ALGORITHM OF CHARACTERIZATIONk-VALUED THRESHOLD FUNCTIONS
threshold function
k-valued logic
geometric algorithm the characterization of threshold functions
the proof of convergence
Show more
INFORMATION SECURITY Pages: 140-145 Issue №11955
ABOUT THE CONSTRUCTION OF SPATIAL-DECOMPOSITION ALGORITHM BASED ON THE ELLIPSOIDS ADAPTIVE ALGORITHM GEOMETRIC PARALLELIZATION
systems of linear inequalities
k-valued logic
method of ellipsoids
geometric parallelization]
the adaptive algorithm of ellipsoids
Show more
