Bongard problem
Encyclopedia
A Bongard problem is a kind of puzzle invented by the Russian computer scientist
Mikhail Moiseevich Bongard (Михаил Моисеевич Бонгард, 1924—1971), probably in the mid-1960s. They were published in his eponymous 1967 book on pattern recognition
. Bongard, in the introduction of the book (which deals with a number of topics including perceptron
s) credits the ideas in it to a group including M. N. Vaintsvaig, V. V. Maksimov, and M. S. Smirnov.
The idea of a Bongard problem is to present two sets of relatively simple diagrams, say A and B. All the diagrams from set A have a common factor or attribute, which is lacking in all the diagrams of set B. The problem is to find, or to formulate, convincingly, the common factor.
Many computational architectures have been devised to solve Bongard problems, the most extensive of which being Phaeaco, by Dr. Harry Foundalis. Such tasks were relevant to the early days of machine learning
and are still unsolved to this date. The problems were popularised by their occurrence in the 1979 book Gödel, Escher, Bach
by Douglas Hofstadter
, himself a composer of Bongard problems. Bongard problems are also at the heart of the game Zendo
.
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
Mikhail Moiseevich Bongard (Михаил Моисеевич Бонгард, 1924—1971), probably in the mid-1960s. They were published in his eponymous 1967 book on pattern recognition
Pattern recognition
In machine learning, pattern recognition is the assignment of some sort of output value to a given input value , according to some specific algorithm. An example of pattern recognition is classification, which attempts to assign each input value to one of a given set of classes...
. Bongard, in the introduction of the book (which deals with a number of topics including perceptron
Perceptron
The perceptron is a type of artificial neural network invented in 1957 at the Cornell Aeronautical Laboratory by Frank Rosenblatt. It can be seen as the simplest kind of feedforward neural network: a linear classifier.- Definition :...
s) credits the ideas in it to a group including M. N. Vaintsvaig, V. V. Maksimov, and M. S. Smirnov.
The idea of a Bongard problem is to present two sets of relatively simple diagrams, say A and B. All the diagrams from set A have a common factor or attribute, which is lacking in all the diagrams of set B. The problem is to find, or to formulate, convincingly, the common factor.
Many computational architectures have been devised to solve Bongard problems, the most extensive of which being Phaeaco, by Dr. Harry Foundalis. Such tasks were relevant to the early days of machine learning
Machine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
and are still unsolved to this date. The problems were popularised by their occurrence in the 1979 book Gödel, Escher, Bach
Gödel, Escher, Bach
Gödel, Escher, Bach: An Eternal Golden Braid is a book by Douglas Hofstadter, described by his publishing company as "a metaphorical fugue on minds and machines in the spirit of Lewis Carroll"....
by Douglas Hofstadter
Douglas Hofstadter
Douglas Richard Hofstadter is an American academic whose research focuses on consciousness, analogy-making, artistic creation, literary translation, and discovery in mathematics and physics...
, himself a composer of Bongard problems. Bongard problems are also at the heart of the game Zendo
Zendo (game)
Zendo is a game of inductive logic designed by Kory Heath in which one player creates a rule for structures to follow, and the other players try to discover it by building and studying various koans which follow or break the rule...
.
Scientific works on Bongard problems
- Bongard, M. M. (1970). Pattern Recognition. Rochelle Park, N.J.: Hayden Book Co., Spartan Books. (Original publication: Проблема Узнавания, Nauka Press, Moscow, 1967)
- Maksimov, V. V. (1975). Система, обучающаяся классификации геометрических изображений (A system capable of learning to classify geometric images; as translated from the Russian by Marina Eskina), in Моделирование Обучения и Поведения (Modeling of Learning and Behavior, in Russian), M.S. Smirnov, V.V. Maksimov (eds.), Nauka, Moskva.
- Hofstadter, D. R. (1979). Gödel, Escher, Bach: an Eternal Golden Braid. New York: Basic Books.
- Montalvo, F. S. (1985). Diagram Understanding: the Intersection of Computer Vision and Graphics. M.I.T. Artificial Intelligence Laboratory, A. I. Memo 873, November 1985.
- Saito, K., and Nakano, R. (1993) A Concept Learning Algorithm with Adaptive Search. Proceedings of Machine Intelligence 14 Workshop. Oxford University Press. See pp. 347–363.
- Hofstadter, D. R. and the Fluid Analogies Research Group (1995). Fluid Concepts and Creative Analogies: Computer Models of the Fundamental Mechanisms of ThoughtFluid Concepts and Creative AnalogiesFluid Concepts and Creative Analogies: Computer Models of the Fundamental Mechanisms of Thought is a 1995 book by Douglas Hofstadter and other members of the Fluid Analogies Research Group exploring the mechanisms of intelligence through computer modeling...
. New York: Basic Books. - Hofstadter, D. R. (1995). On Seeing A’s and Seeing As. Stanford Humanities Review 4/2 pp. 109–121.
- Hofstadter, D. R. (1997). Le Ton beau de Marot. New York: Basic Books.
- Linhares, A. (2000). A glimpse at the metaphysics of Bongard problems. Artificial Intelligence, Volume 121, Issue 1-2, pp. 251–270.
- Foundalis, H. (2006). Phaeaco: A Cognitive Architecture Inspired by Bongard’s Problems. Doctoral dissertation, Indiana University, Center for Research on Concepts and Cognition (CRCC), Bloomington, Indiana.
- Anastasiade, J., and Szalwinski, C. (2010). Building Computer-Based Tutors to Help Learners Solve Ill-Structured Problems. In Proceedings of the World Conference on Educational Multimedia, Hypermedia and Telecommunications 2010. Toronto, Ontario, Canada: Association for the Advancement of Computing in Education. pp.3726-3732.