A Semantic Web Technique as Logical Inference Puzzle-Solver for Bongard Problems⋆

Abstract

Bongard Problems (BPs) are a set of 100 visual puzzles set as a benchmark test for understanding the human concept learning abilities depending on contexts. It is still obscure how the human mind recognizes objects under minimal information, like amodal problems where only minimal information are available as sensory input. Though BPs have been well known among AI researchers as solutions towards understanding such human visual perception abilities, only a little progress has been made towards solving a set of BPs. In this study, a semantic web based meta-knowledge was developed along with a hierarchical logical inference to mimic human-logical inference ability in solving the Bongard problems. We applied this method to solve a set of fourteen BPs based on visual inputs from a perceiver (through an interface) and successfully demonstrated the system to nd the unique distinction between the two classes in a given problem.

Keywords

• Cognition Meta-data Analogy making Ontology Knowledge Graph Resource Descriptive Framework (RDF)

-

In recent years development in Arti cial Intelligence has led to an abrupt enhancement in the ability of machines to imitate humans abilities [ 1 ]. Development of such intelligent machines, for context understanding, not only helps researchers to understand human reasoning ability but is also bene cial for the upliftment of the society. In this paper to mimic such higher-level cognitive abilities of our brain, we have focused on solving of Bongard Problems. Bongard Problems are a set of 100 puzzles formulated by a Russian scientist M.M.Bongard in mid-1960 [ 2, 3 ]. They were popularized by Douglas R. Hofstadter in his book [ 2 ], to demonstrate the gap between human and computers visual cognitive abilities [ 2 ]. ⋆ This work was partly supported by JSPS 16H01616, 17H06383 and the New Energy and Industrial Technology Development Organization (NEDO).

Each BP (Fig. 1) consists of two lumps, with 6 boxes on left side and the other set of 6 boxes on the right side [ 2, 3 ]. The solution to this analogy problem is a unique difference between both the lumps, such that the unique property on one side does not hold true for the other side of the same BP [ 2, 3 ]. Computer scientists Kazumi Saito and Ryohei Nakano, in early 1995, developed a rstorder logic based concept learning approach with adaptive searching (RF4) to solve 21 BPs out of 100 BPs [ 4 ]. Five years later, Harry Foundalis developed, Phaeaco, a two-layer architecture to mimic the cognitive computing of visual information for logical inference of the possible solution to a given BP [ 3 ]. With the limitations of lower level descriptions for more complex BPs (with higher complex inter-relationships between features), Phaeaco could solve 10 BPs.

Feedback To modify the existing class and instance

Long Term Knowledge (Protege API)

RDF Vocabulary [Ontology] RDF Querry (SPARQL)

XML to lexical Representation

Prediction of the

Solution

Relations and Exclusions

Semantic Rules (SWRL) and

Restrictrions Java Framework (Apachi Jena API)

Input

Visual Instances (Lower-Level Cognition)/ GUI

Image Processing

Fig. 2. Ontological framework to solve Bongard Problems.

Our Approach

BPs, as shown in Fig. 1, are two-dimensional black and white images; hence with the use of highly efficient recurrent visual processing algorithms, it is relatively easy to obtain the features. In this paper, more emphasis has been laid on efficient machine-understandable knowledge representation and reasoning abilities for predicting the solution to a given BP. Since BPs have an in nite set of infeasible search possibilities (with a massive amount of data obtained from a single box in a BP) for inferring a unique solution, it is nearly impractical to use recursive searching algorithms for making logical predictions. Hence continuous optimization of search space using ontology-based organized knowledge of the raw concepts and their exible relationships is a practical approach towards solving BPs. As shown in Fig. 2, the visual instances (Shape, Count, Texture, Size, Possition etc) from the user (GUI) are obtained and are converted to an RDF based format of data. The SWRL rule reasoner is formulated in a way to create new inferred properties from the perceived instances. An example of SWRL to check for dissimilarity in the texture of objects in a given BP, with each box indexed as- Li (left side) and Ri (right side) (i 1; ::6), is as follows(?Li T exture ?a)^(?Ri T exture ?b)^(?a Dif f erentF rom ?b) >(Lef t Inf ered T exture ?a)^(Right Inf ered T exture ?b). These SWRL rules for each instance can be generalized as- jj(Li 9P ?a) ∩(Ri 9P ?b) ∩(Li 9(:P ) ?b) ∩(Ri 9(:P ) ?a) ∩(?a ∩?b = )jj jj(Lef t 9P Pb)jj∩jj(Right 9P Pa)jj. This extensive knowledge base is then queried using SPARQL query, and if the solution to the given BP can be formulated at this stage, the predictions are outputted else a feedback based inference is carried out. 4

Result

In this paper, Jena API based knowledge graph was designed as the long-term memory with 1152 axioms and 34 properties. The visual instances and their characteristics obtained from the user interface were fed as an input to the static ontology. The input data was dynamically stores in an <s; p; o> format along with the properties of each instance. For the logical inference of the solution for a BP, 45 SWRL rules were formulated with an ability to cross-check similarities. A survey was carried out by Harry Foundalis, by using 31 students as subjects, to understand the varying difficulty levels of BPs [ 3 ]. Based on the number of students who were successful in solving the given BP, we have categorized the BPs into three different categories: Easy, Moderate and Difficult. It was observed that 42 BPs could be categorized as easy based on the performance of the 31 subjects. However, based on Phaeaco's performance, 14 BPs could be categorized as easy Problems for both human subjects and computer program (Table 1). The results of these 14 BPs, using our approach, are presented in Table 1. The inferred knowledge of each BP undergoes three-level regressive funneling and pruning approach. Each stage notices a reduction in the predicted outcome to the selected BP. 14 BPs were solved using this ontological approach to mimic human based context understanding at the higher level of cognition.

Conclusion

This paper aims to impersonate the human ability in an ill-posed problem with in nite search space. We developed a semantic-based approach with logical transparency using RDF based understanding of the puzzles for the machine. Our approach also states the application of linked metadata-based approach as a pathway towards understanding multidimensional analogies and their broad scope in making the machine to understand human intuitions for daily life problems. For future work, we plan to optimize this reasoning process and investigate new approaches for enhancing the logical rules. We also intend to incorporate datadriven recursive process with this ontological knowledge base, to further enhance the learning of visual objects and their properties autonomously.

References

1. McCarthy , J. , Hayes , P.-J.: Some philosophical problems from the standpoint of arti cial intelligence . Machine Intelligence Journal 4 , 463 { 502 ( 1969 )

2. Hofstadter , D. -R.: Godel, Escher, Bach: an Eternal Golden Braid . New York: Basic Books ( 1979 )

3. Foundalis H. Phaeaco : A Cognitive Architecture Inspired by Bongard s Problems. Doctoral dissertation , Indiana University, Center for Research on Concepts and Cognition (CRCC) , Bloomington, Indiana. ( 2006 )

4. Kazumi , S. , Ryohei , N.: Adaptive concept learning algorithm: RF 4 . Transactions of Information Processing Society 36 ( 4 ): 832 { 839 ( 1995 )