Data processing: artificial intelligence – Neural network – Learning task
Reexamination Certificate
1998-09-21
2001-07-24
Powell, Mark (Department: 2122)
Data processing: artificial intelligence
Neural network
Learning task
C706S047000, C706S061000
Reexamination Certificate
active
06266656
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates to a classification apparatus for automatically generating a classification rule using pre-classified case (or event) data for automatically classifying unclassified cases.
BACKGROUND OF THE INVENTION
As the methods for automatically generating classification rules from the pre-classified events for classification using this generated rule, a wide variety of methods have hitherto been proposed, such as a statistic method, techniques of knowledge-based processing, techniques based on computational learning theories or neural-net-like techniques. These techniques have their merits and demerits and the suitable area differs problem to problem.
The statistic techniques are principally aimed at analyzing event data based on probabilistic models and hence are used for finding out the main tendency latent in the event data. The volume of processing necessary for rule generation is also small. On the other hand, the statistic techniques are not good at exceptional classifying processing operations. The statistic techniques may be exemplified by quantitation II and Bayesian decision.
The techniques of knowledge-based processing and the computational learning theory are the technique and the theory proposed in the course of researches towards realization of the mechanical learning. Stated briefly, the mechanical learning means autonomous generation by a computer of the adaptive knowledge (information, rules or program etc.). The automatic classification may be classed as a part of this mechanical learning function. While the main object of the statistic technique is discovery of the main tendency of event data, the ultimate object of the mechanical learning is increasing the intelligence of the computer, and hence the object is diversified. The object of the mechanical learning differs slightly from one group of researchers to another. For example, the object of the mechanical learning encompasses finding the extent of hypotheses not in contradiction to the events, recognition and processing of event data behaving exceptionally, or automatic generation of event-generating programs etc.
The neural network type technique is a pseudo-system employing pseudo neural cells and can be applied to learning or pattern recognition. Although the technique can be used easily, the classification rule represents a black-box such that the technique is difficult to be checked or corrected by an operator.
In the following, attention is directed to an inductive inference apparatus (JP Patent Kokoku JP-B-07-43722 or U.S. Pat. No. 4,908,778). This JP Patent Kokoku JP-B-07-43722 is aimed at inductively finding a general knowledge for an event, which comes into being by combining various conditions, from events of the pertinent field in order to acquire the knowledge information required for knowledge processing effectively.
This inductive inference apparatus is fed with a set of case data and subsequently generates a sufficient condition and a necessary condition for realization of respective results of classification. Using these conditions, if an unknown condition is given and the sufficient condition is met, the result of classification is decided to hold (true), whereas, if the unknown condition is given and the necessary condition is not met, the result of classification is judged not to hold.
PROBLEM TO BE SOLVED BY THE INVENTION
In the course of eager investigation toward the present invention, the following problem has been encountered.
This technique has a drawback that, if the set of case data cannot be classified logically, it is impossible to generate any valid classification rule. Suppose that the following case data are given:
TABLE 1
cases
results of classification
conditions
Sardine
fish
live in water
Salmon
fish
live in water
Sea bream
fish
live in water
Dolphin
animal
live in water
It is now assumed that, after generation of a classification rule from the above case data, the following case data:
TABLE 2
Cases
Results of classification
conditions
Carp
?
live in water
the results of classification of which are unknown are classified.
The condition “live in water” is not a sufficient condition to derive the classification result “fish” and hence the carp cannot be classified as fish. On the other hand, since “live in water” is a necessary condition for “fish”, the fact that the carp is fish cannot be negated. In short, no positive classification rule can be generated concerning the “live in water” and “fish” from the set of event data aforementioned. These circumstances hold for “animals” as well.
Although the above is logically a matter of course, the following problems are raised in connection with realistic application.
The first problem is that case data that cannot be classified logically are frequently given in realistic application.
The second problem is that the above-described inductive inference apparatus cannot be said to sufficiently exploit the information of the case data. For example, it is desirable that, in case where the majority of cases of the sub-aquatic life is “fish”, and, if these cases are given to the system as case data for learning, a classification rule stating: “although not fully positive, the sub-aquatic life is possibly the fish” is desirably produced. It is also important in this case that the degree of certainty is varied quantitatively.
SUMMARY OF THE DISCLOSURE
In light of the above-mentioned inductive inference apparatus, the problem to be solved by the present invention is:
generating a classification rule quantitatively including the degree of certainty for input of case (or event) data that cannot be classified logically, and
classifying the unknown case (or event) with quantitative values representing the degree of certainty using the generated classification rule.
In generic terms, it is an object of the present invention is to provide an apparatus performing effective learning type automatic classification for realistic classification problems.
The realistic classification problems herein mean such a problem containing cases (or events) that cannot be classified logically as described above and encompassing a wide variety of sorts of the conditions or results of classification.
The effective classification of these realistic classification problems means
i) generating a classification rule effective for classification within realistic time and computational resources; and
ii) outputting the results of classification with quantitative values representing the degree of certainty.
For accomplishing the above object, the present invention resides in introducing a probability value into a classification rule as a quantitative value of certainty, generates the classification rule having the probability value using cases and performs reliable classification using the classification rule.
More specifically, the present invention provides a classification apparatus in which classification rules are automatically generated using known case data, having known results of classification, among case data each of which is made up of a set of a conditional part serving as a clue for classification and a result of classification, and in which unknown case data, having unknown results of classification, are automatically classified using classification rules. The classification apparatus includes an input unit for entering the known case data and the unknown case data, a classification ruled database for storing classification rules including the probabilistic information, a case database for storing the known case data in the form of a network based on the logical relation of the conditional parts, a probability value estimating unit for estimating probability values of the results of classification using the conditional parts of the known case data and the unknown case data as entered and the rules of classification, and a classification rule generating unit for evaluating the validity of the classification rules by statistic verification for suppressing generation of useless classification rules.
Prefe
Foley & Lardner
Khatri Anil
NEC Corporation
Powell Mark
LandOfFree
Classification apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Classification apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Classification apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2503160