Modified: 96.5.23, Owner: Hiroshi Yamakawa,

Situation decomposition using Matchability Criterion

1. Matchabe principle and Matchability criterion

Conventional many model selection criteria select a unique model on the basis of trade off with for the "Simplicity of a model" and "Consistency for data". This principle is called the razor of Ockham's razor and there are some famous information standard Akaike's information criterion (AIC), Minimum Description Length (MDL) etc.

Matchable principle saying that recognition and action system select the model (inside structure/expression) which maximize matching opportunities. Therefore Matchable principle in the trade off between "Coverage for Data" and "Simplicity of a model" .

Furthermore, Matchability criterion estimates the extent of a matching opportunity.

Figure 1. Matchable principal and Ockham's razor

2. Situation decomposition - selecting features and events -

Situation decomposition extracts the part, from the information of an attribute base that consists of the combination of set of the event (record) and set of a feature (attribute/field) like database, as shown in the figure 2. The part that should extract it is the partial situation that a feature and an event were selected simultaneously. There are many possible partial situations which can be selected.

Situation decomposition algorithm extracts Matchable situations that are local maximums of matchability criterion in event and feature selecting space.

Figure 2. Situation decomposition

3. Simple example

In the case that an event is existing in two plane state in cubes of 3 features with arrangements like figure 3, situation decomposition algorithm takes out the three situation two planes and the straight line that cross with two planes . For instance, two features and x+z=1 plane form events that y axis was disregarded in Matchable situation 1 (MS1), are selected.

Figure 3. Two plain exists in cubic space

The prediction will be improved using Matchable situation that was extracted. For instance, considering the multi-valued function φ MS1 (0,1)=1. (1) Generalization can be done, even if the right half of input situation A is lost, (2) Distinguish outputs of MS1 and MS2. (Without distinction the output may be the mean value of two situation output. )

4. Applications

Matchable situation obtained by situation decomposition method reflects the information structure of source data. Therefore, prediction ability to source data improves, so this method is effective an effect for such as a data analysis, prediction, reasoning, action decisions. This method can be applicable as preprocessing for many standard data analysis methods. Furthermore, situation decomposition technology collects the features which has strong relationship for each other, this can be extend as self-organization algorithms.

+ Extracting Near-Wall Situation

A mobile robot, that has a range sensor surrounding its body is collects sensor signals in simulation. Situtation decomposition method extracts near-wall situation [2]. The selection of near-wall situation is shown bellow.

  • Event selection: Wall is in the range.
  • Feature selection:Direction of wall.

The advantage of using near-wall situation are (1) Influence from the sensor of the direction other than a wall is not received ,(2) A corner is recognized as two walls.

Figure 4. Mobile robot extracts Near-Wall situation


  1. Hiroshi Yamakawa, (1998). " Proposing Matchability Criterion for Situation Decomposition - Extracting situations each of which contains a rule -," Proc. Int. Conf. on Neural Information Processing (ICONIP'98), vol.3, pp.514-517.. [List/Abstract/Paper(English/Japanese)/Poster]
  2. Hiroshi YAMAKAWA, Hiroyuki OKADA, Nobuo WATANABE Tomoharu MOHRI. (1998). " Extracting Situation for Mobile Robot using Infrared Sensor - Applying Situation Decomposition Technique based on Matchability Criterion to Mobile Robot -," 16th Annual Conference of the Robotics Society of Japan (RSJ'98), Vol.2 pp.647-648, (2I21).[List/Abstract/Paper]
  3. Yamakawa, H. (1996). "Matchability Oriented Feature Selection for Recognition Structure Learning," Proc.International Conference on Pattern Recognition (ICPR-96). Vienna, Austria, vol.4, pp.123-127, 1996. [List/Abstract/Paper]]
  4. Yamakawa, H.(1996). "Feature Selection for Acquiring Internal Structure of Recognition System based on Matchability," Technical report of IEICE, PRMU96-12, pp.1-8. (in Japanese) [List/Abstract/Postscript/HTML]