> Root Entry F _2@G\d2@WordDocumentdObjectPool/@;_2@;_2SummaryInformation(
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~qcCompObj_mObjInfo^Equation Native [CompObjsj
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`adefghijklmnoprstuvwxyz{|}~ !"$)+,-./0258:;<=>?@ABCDFKMNOPQRSTUVWY\]`bcdefghijklmnoqtLE0l
FMicrosoft Word Document
MSWordDocWord.Document.69qes labeled with the same (formula, value) pair can be distinguished by their positions in the knowledge representation graph. This is the idea underlying procedures for searching for attributes of an object which approximate the classification of the object given by an expert. These attributes are called classifiers ([SS91a]). Our method can be regarded as a formal approach to constructive induction ([KM90]). The searching process can either be interactive or automated.
One of the most important steps in searching for the appropriate set of attributes is the strategy for selecting the best attributes from those constructed in the preceding step [AD91], [BSS94], [BS94], [FU92], [K86], [KTM93], [MMS91], [ZS93]. Rough set methods [Pa91] provide possible strategies. One of them is based on the idea of reducts [Pa91] calculated from the original set of attributes. However, the accuracy of the classification induced by a randomly chosen reduct is not satisfactory for unseen objects. In [BSS94] a new method of calculating dynamic reducts has been presented. This method gives us the ability to extract the most promising attributes by indicating the most frequent reducts found on subsets of the training set of objects.
The problem of decision rules synthesis for object classification has been intensively studied (see e.g. [KM90], [MCM83], [MCM86], [MT94], [SL90], [GB92], [GB93], [PS93], [S93a,b], [Dr92]). We apply the so-called boolean reasoning [Br90] and rough set methods for decision rules synthesis.
We discuss the problem of optimal decision rules synthesis. Decision rules have the following form: (((( where ( and (( are boolean combinations of descriptors (i.e. pairs a(v where a is an attribute and v is its value) built from conditional attributes and a decision approximating the expert decision [SG94], respectively. The decision rules are generated with some numerical factors expressed in terms of basic functions of evidence theory (basic probability assignments, belief and plausibility functions) and rough membership functions computable from a given decision table. These factors can be used in the decision making. Our approach of rule synthesis is based on construction of some boolean functions from modified discernibility matrices [SR91]. Two kinds of optimal decision rules are considered: rules with minimal number of conditions and rules with minimal number of descriptors [PS93], [S93a,b].
To determine the efficiency of the system we implement three searching methods namely automatic attribute generation, relevant feature extraction (using dynamic reducts) and inductive reasoning methods. We apply these methods in fields like pattern recognition, in particular, optical character recognition (OCR) (see e.g. [IOO92],[PR93]). Our aim is to illustrate how the system can be used rather than to solve problems in OCR like the handwritten character recognition problem.
OCR is probably the most rapidly growing area of artificial intelligence research over the past few years. The idea of using printing and handwriting as a computer interface has captured attention of many industrial companies as well as leading research centers all over the world. While the problem of recognizing machine-printed characters has virtually been solved resulting in the development of high perfomance recognition systems, the problem of recognizing handwritten characters has as yet not been completely solved.
There are two main approaches to the problem of handwritten pattern recognition: the statistical/decision theoretic approach and the syntactic/linguistic/ grammatical/structural approach. Each of them has their own merits and demerits. Statistical techniques do not handle satifactorily information about interconnections in complex patterns. On the other hand, syntactic-formal language theories present some serious drawbacks in dealing with recognition of handwritten patterns, where class variations are practically infinite and do not always obey strict rules imposed by formal mathematical models. The only reasonable solution is a hybrid method combining ideas from both approaches. The majority of recent publications have been dedicated to different models and solutions of static analyzers which are specific to some subclass of the problem. Only very few attempts have been made in the field of automated design of universal and flexible recognizers. In this paper we propose an approach to the problem of handwritten character recognition based on the rough set method [Pa91, S93c]. We have attempted to develop an integrated system for interactive generation of recognition engines using modern tools such as modal logic and rough set methods. Our system is not only a new approach to the traditional OCR problem but is also a convincing illustration of the major role logic and rough set theory play in the fields of artificial intelligence and pattern recognition.
The paper is structured as follows:
In Section 2 we introduce some essential background to rough sets and modal logic, in particular to decision tables, set approximations, and the syntax and semantics of multi-modal logics. In Section 3 various types of decision rules are recalled including rules with minimal number of conditions or descriptors on the left hand side [PS93], [S93a,b] as well as rules with certainty coefficients [S93a,b], and some examples of the inductive inference method are given. In Section 4 we present a thorough description of the methods implemented in the system; we briefly describe the problem of approximating the expert's decision using decision tables and dynamically constructed attribute sets; and we explain the nature of attribute classes used in the system, namely mask, topological and modal attributes. In Section 5 we describe the main modules of the system - feature extraction and optimization. The feature extraction module allows the designer to create various attributes that meet his preferences; the optimization model uses optimal decision rules (discussed in Section 3) to reduce the created sets of attributes with minimal loss of the approximation precision. We describe how the algorithm for searching formulae distinguishing objects is implemented in the system, as well as how dynamic reducts [BSS94] are calculated and used for relevant feature extraction.
In Section 6 the results of computer tests to determine the efficiency of the system are presented and discussed, in particular we discuss the influence of modal attributes on the classification accuracy.
Section 7 concludes with some proposals concerning further work.
The general scheme of the system is represented in Figure 1:
INCLUDEPICTURE "C:\\PROG\\ORLOWSKA\\02\\FIG01.EPS" \* MERGEFORMAT \d
Figure 1.
2 Basic Notions
2.1 Rough Set Preliminaries
2.1.1 Basic Definitions
Information systems [Pa91] (sometimes called data tables, attribute-value systems, condition-action tables, knowledge representation systems etc.) are used for representing knowledge.
Rough sets have been introduced as a tool to deal with inexact, uncertain or vague knowledge in artificial intelligence applications.
In this section we recall some basic notions related to information systems and rough sets.
An information system is a pair A=(U,A), where U is a non-empty, finite set called the universe and A - a non-empty, finite set of attributes, i.e. a: U(Va for a(A, where Va is called the value set of a.
Elements of U are called objects and interpreted as, e.g. cases, states, processes, patients, observations. Attributes are interpreted as features, variables, characteristic conditions etc.
Every information system A=(U,A) and a non-empty set B(A define a B-information function
EMBED Equation.2
defined by InfB(x)={(a,a(x)): a(B}. The set {InfA(x): x(U} is called the A-information set and it is denoted by INF(A).
We consider a special case of information systems called decision tables. A decision table is any information system of the form A=(U,A({d}), where d(A is a distinguished attribute called decision. The elements of A are called conditions.
One can interpret a decision attribute as a kind of classification of the universe of objects given by an expert decision-maker, operator, physician, etc. Decision tables are called sets of examples in machine learning [KM90].
The cardinality |d(U)| of the image d(U) = {v: d(x)=v for some x(U} is called the rank of d and is denoted by r(d). We assume that the set Vd of values of the decision d is equal to {1,...,r(d)}.
The decision d determines the partition CLASSA(d)={X1,..,Xr(d)} of the universe U, where Xk ={x(U: d(x)=k} for 1( k ( r(d). The set Xi is called the i-th decision class ofA.
Let A=(U, A) be an information system. With every subset of attributes B(A, an equivalence relation, denoted by INDA(B) (or, IND(B), in short) called the B-indiscernibility relation, is associated and defined as follows:
IND(B)={(s,s)(U2 : for every a(B, a(s)=a(s)}
Objects s,s satisfying relation IND(B) are indiscernible by attributes from B.
Minimal subsets B(A satisfying IND(B)=IND(A) are called reducts of A. The set of all reducts of A is denoted by RED(A).
Let A be an information system with n objects. By M(A) [SR91] we denote an n(n matrix (cij), called the discernibility matrix of A such that
cij = {a(A: a(xi)(a(xj)} for i,j=1,...,n.
A discernibility function fA for an information system A is a boolean function of m boolean variables EMBED Equation.2 corresponding to the attributes a1,...,am respectively, and defined by
fA( EMBED Equation.2 ) =df /\{\/ EMBED Equation.2 : 1(j* 1}
(where BdA(() = EMBED Equation.2 ) is a partition of the universe U. Moreover the following equality holds:
EMBED Equation.2 for (((A with |( | >1.
(
The classification (partition) of the universe U described in Proposition 2.2 is called the standard classification of U approximating in A the classification CLASSA(d) (given by an expert).
By APP_CLASSA(d) we denote the family:
{AX1,..., AXr(d) }({BdA(() : (((A and |( | > 1}
We have a clear interpretation of the new classification. An object from the universe U of A is represented by an information (from INF(A)) described in the rows of A. The object can be classified exactly on the basis of that information only when the category (i.e. the equivalence class of the indiscernibility relation INDA(A)) corresponding to that information) is included in Xi for some i. Otherwise, that category is included in a boundary region of the form BdA((), for some (. Then the considered object from U (represented by a given information) belongs to the boundary region of all sets Xi, where i(( and do not belong to sets Xj, where j(( (i.e. it is in the union EMBED Equation.2 but we do not have enough information to decide in which of the sets Xi it is).
There is a natural correspondence between subsets of ( and elements of APP_CLASS (d), which can be expressed by the following function:
EMBED Equation.2
It is easy to observe that the generalized decision (A has the following property: (A(x) is the unique subset ( of ( such that x(FA(( ) for any x(U.
The function mA: P(()(R+, called the standard basic probability assignment of A is defined by
EMBED Equation.2 , for any ( ((.
Proposition 2.3 ([SG94]) The function mA defined above is a basic probability assignment (in the sense of evidence theory).
(
The above definition has a clear interpretation. If ( = {i} then m(( ) is the ratio of the number of all objects from the universe U (of A) certainly classified by attributes from A as being in Xi to the number of all objects in U. If |( | >1 then mA(() is the ratio of the number of all objects from the universe U (of A) certainly classified by attributes from A as being in the boundary region BdA(( ) to the number of all objects in U.
The belief function Bel of A is defined by
BelA(( ) = EMBED Equation.2
where ( (( and mA is the standard probability assignment of A.
The interpretation of the above definition follows from the following theorem [SG94]:
Theorem 2.4 Let A=(U,A({d}) be a decision table. For arbitrary ((( the following equality holds:
BelA(( ) = EMBED Equation.2
(
The belief function BelA is Bayesian iff all decision classes of A are definable by the set A of conditions. In particular, the belief function BelB where B=(U,A({(A}), is Bayesian.
Corollary 2.5
Let A=(U,A({d}) be a decision table. For arbitrary ((( the following equality holds:
PlA(( ) = EMBED Equation.2
(
The value BelA(() (PlA(()) is the ratio of the number of objects from U certainly (possibly) classified into the union EMBED Equation.2 to the number of all elements in the universeU.
The commonality function of A is defined by
QA(() = EMBED Equation.2
where (((.
2.3 Modal Logic Preliminaries
In this chapter we present some applications of modal logics, which for the last 20 years have been investigated in Computer Science as well [Sti92].
In contrast to other kinds of logics, modal logic has, beside of classic logic connectives, special functors called modal connectives (or modal operators, functors) expressing natural notions such as: its possible that ..., its necessary, that .... Only one of these two notions is needed as an original term, because each can be defined by the other:
Its possible that A is equal to Its not necessary, that not A
Modal logic is intentional, because logical values of its compound formulas do not depend only on logical values of component formulas.
Modal logics, which formulas contain more than one type of modalities are called multi-modal. The syntax of the propositional multi-modal logic is presented below:
1. The language of multi-modal propositional logic takes as primitive or undefined symbols the following ones:
i) A denumerably infinite set V of propositional variables, which we write as p,q,r...(with or without numerical subscripts).
ii) A set of classical propositional connectives: EMBED Equation.2 ;
iii) The family of modal connectives: {(m ,(m}m(M , where M is a finite set of actions or modality labels.
2. Well-formed formula of multi-modal propositional logic are defined as follows:
i) Any propositional variable is a formula of multi-modal propositional logic.
ii) If ( and ( are formulas of multi-modal propositional logic, then ((, (((, (((, (((, (((, (m(, (m( are formulas.
iii) Every formula is either a propositional variable or is constructed from propositional variables (or from already constructed formulas) by applying the rule ii) a finite number of times.
Some connectives are definable by the other ones:
((( =Df (((((((), ((( =Df ((((, ((( =Df (((()(((((),
(m( = Df ((m((.
Let ( be a formula of a multi-modal propositional logic. The depth |(| of a formula ( is defined inductively by:
i) |(| = 0 for (( V ;
ii) |((| = |(|;
iii) |(((| = |(((| = |(((| = |(((| = max (|(|, |(|);
iv) |(m( | = |(m( | = |(| + 1.
S.Kripke [K59], [K63] defined the so-called possible world semantics for modal formulas. His work is regarded as a major breakthrough in this field, because it brought not only a highly suggestive and intuitive, but also well-defined semantics.
A Kripke model is any triple K = (W,{Rm}m (M, val( where
- W is a certain non-empty set ( set of possible worlds, set of states);
- {Rm (W(W, m(M}is a family of binary (accessibility) relations over W;
- A valuation function val :V(W({0,1} assigns a logical value to any propositional variable in a given world.
For a given Kripke model K, the logical value of any compound modal formula ( in any world w(W is determined by the so-called satisfiability relation K,w |= ( defined as follow:
i) for p(V K,w |= p if and only if val(p,w) = 1
ii) K,w |= ((( if and only if K,w |= ( or K,w |= (
iii) K,w |= (( if and only if its not true, that K,w |= (
iv) K,w |= (m ( if and only if K,w |= ( for any w( W such that (w,w)(Rm
v) K,w |= (m( if and only if there is some w( W such that (w,w)(Rm and
K,w |= (
In the sequel we show how modal formulas and Kripke models can be applied to feature extraction.
3 Decision Rules
In this section we recall the definition of decision rules and some methods based on boolean reasoning for their synthesis.
Let A=(U,A({d}) be a decision table and let
EMBED Equation.2
The atomic formulas over B(A({d} and V are expressions of the form a=v, called descriptors over B and V, where a(B and v(Va. The set F(B,V) of formulas over B and V is the least set containing descriptors over B and V and closed with respect to the classical propositional connectives (disjunction) and (conjunction).
Let ((F(B,V). Then by tA we denote the meaning of t in the decision table A, i.e. the set of all objects from U with the property t, defined inductively as follows:
if t is of the form a=v then tA ={x(U: a(x)=v}.
(((()A=(A((A ; (((()A=(A((A.
We do not use the negation connective because in the case of information systems the complement of any definable set is definable by union and intersection.
The set F(A,V) is called the set of conditional formulas of A and is denoted by C(A,V).
A decision rule for A is any expression of the form
td=i where t(C(A,V) and iVd.
The decision rule td=i for A is true in A iff tA((d=i)A; if tA=(d=i)A then we say that the rule is A-exact.
In the following sections we present a method for synthesis of different forms of decision rules. The method is based on boolean reasoning with application of some properties of the discernibility matrices and their modifications.
3.1 Decision Rules for Consistent Decision Tables
In this section we assume that considered decision tables A are consistent. We present two methods for decision rules synthesis.
The first method allows to obtain the exact decision rules, i.e. the description of all decision classes in the form of decision rules. The description of decision classes is minimal in the following sense: it is not possible to describe all decision classes by any proper subset of the set of conditions occurring on the left hand side of any rule.
The second method also allows to obtain the description of all decision classes in the form of decision rules. The left hand sides of any rule is a disjunction of descriptor conjunctions. The description of the decision classes is minimal in the following sense: any conjunction of descriptors occurring on the left hand side of any rule is minimal, i.e. the rule will not remain valid if one eliminate any descriptor from that conjunction. Some versions of the presented here methods are discussed in [S93a-c].
3.1.1 Decision Rules With Minimal Number Of Conditions
The method, which we are going to present, consists of two steps. In the first step we show how to modify the discernibility matrix notion to compute the set RED(A,d) of all relative reducts of A. In the second step we show how any relative reduct BRED(A,d) allows to obtain directly the description of each decision class in the form of the decision rule. On the left hand side of all decision rules only attributes from B occur. The description of the decision classes is minimal in the following sense: it is not possible to obtain a description of all decision classes by attributes from any proper subset of B.
Let A=(U,A{d}) be a consistent decision table and let M(A)=(cij) be its discernibility matrix. We construct a new matrix M'(A)=( EMBED Equation.2 ) assuming EMBED Equation.2 = if d(xj)=d(xj) and EMBED Equation.2 =cij-{d}, otherwise. The matrix M'(A) is called the relative discernibility matrix of A. Now one can construct the relative discernibility function fM(A) of M'(A) in the same way as the discernibility function was constructed from the discernibility matrix (see Section 2). One can show that the following proposition is true:
Proposition 3.1 For any BA the following conditions are equivalent:
(i) B(RED(A,d)
(ii) B is a prime implicant of fM(A)
(
Let us recall that in the condition (ii) elements of B are treated as boolean variables corresponding to attributes. Proposition 3.1 allows to compute the set of all relative reducts by computing the set of all prime implicant of fM(A).
Now, for any B(RED(A,d) we construct the set TraceA(B)={(InfB(x),d(x)): x(U}.
To obtain the decision rule corresponding to the i-th decision it is enough to take all pairs from TraceA(B) with the second element equal to d=i and create the disjunction ai of all conjunctions of descriptors occurring on the first position in those pairs. The constructed decision rule has the form
ai d=i
We have the following:
Proposition 3.2 Let A=(U,A({d}) be a consistent decision table and let B(RED(A,d). The decision rules ai(d=i where i=1,...,r(d) are exact in A and the descriptions of decision classes defined by them are minimal, i.e. for any B(B do not exist formulas bi for i=1,...,r(d) from C(B,V) such that the decision rules bid=i are exact in A for i=1,..,r(d).
(
3.1.2 Decision Rules with Minimal Number of Descriptors
First we show how to construct a description of the decision classes by exact in A decision rules
(i( d=i
where (i(C(A,V) is a disjunction \/((i of conjunctions ((i of minimal sets (i of descriptors for i=1,...,r(d). The set (i defines in A a non-empty set of objects, i.e. ((i)A(( and is minimal in the following sense: the decision rule
( EMBED Equation.2 (d=i
is no longer valid in A for any EMBED Equation.2 ((i satisfying (( EMBED Equation.2 )A ((. The decision rule with the above property is called minimal with respect to the descriptors in A.
The method allows to generate decision rules with one more property, namely if
\/((i (d=i
is an arbitrary of the constructed decision rules for A and ( is a set of descriptors such that
(((d=i
is valid in A and ((()A(( then (i(( for some i. The decision rules with the above property are called complete with respect to the descriptors in A.
Now we recall a method ([S93a-c]) allowing to compute for a given consistent decision table A the description of all decision classes of A in the form of decision rules exact in A which are complete and minimal with respect to descriptors.
Let A= (U,A({d}) be a consistent decision table and M'(A)=( EMBED Equation.2 ) be its relative discernibility matrix. We construct new matrices (columns of relative discernibility matrix)
M(A,k)=( EMBED Equation.2 ) for any xk(U
assuming EMBED Equation.2 = EMBED Equation.2 if d(xi)(d(xj) & (i=k ( j=k) and EMBED Equation.2 =(, otherwise. The matrix M(A,k) is called the k-relative discernibility matrix of A. Now one can construct the k-relative discernibility function fM(A,k) of M(A,k) in the same way as the discernibility function was constructed from the discernibility matrix [SR92].
Let Atr(() denote the set of all attributes corresponding to propositional variables occurring in the prime implicant ( of fM(A,k) and let Trace(A,k) be the following set of descriptor conjunctions:
{/\{a=a(xk): a(Atr(()}: ( is a prime implicant of fM(A,k)}.
Now let (i for any i({1,...,r(d)}) be a disjunction of all formulas from the set
EMBED Equation.2 .
Proposition 3.3 [S93a-c] Let A=(U,A({d}) be a consistent decision table. The decision rules:
(i(d=i where i({1,...,r(d)}
are complete and minimal with respect to descriptors in A.
(
Similarities of these rules to those discussed for AQ algorithms were presented in [St94].
3.2 Decision Rules for Inconsistent Decision Tables
In this section we consider inconsistent decision tables. One can transform an arbitrary inconsistent decision table A=(U,A({d}) into a consistent decision table A(=(U,A({(A}) where (A: U(P(() is the generalized decision of A defined in Section 2.1 and (={1,...,r(d)} (see also [St94] for more details). It is easy to see that A( is a consistent decision table. Hence one can apply to A the methods presented in the previous section to obtain for any ((( with EMBED Equation.2 the decision rules of the form:
(( ((A=(
We have the following proposition relating these rules with the standard basic probability assignment of A:
Proposition 3.4 If ((((A=( is a decision rule obtained by applying to A( any method presented in Section 3.1 and EMBED Equation.2 then
(i) EMBED Equation.2
(ii) EMBED Equation.2 .
(
In a similar way one can construct rules corresponding to the lower approximation of the union of decision classes Xi where i((. The cardinality of this set is related to the value BelA(() (see Section 2.2). It is enough to construct a decision table
B( =(U,A({b(})
where b((x)=1 if (A(x)(( and b((x)=0, otherwise.
It is easy to observe that B( is a consistent decision table. Hence applying the methods presented in Section 3.1 we have:
Proposition 3.5 If (( (b(=1 is a decision rule obtained by applying to B( any method presented in Section 3.1 and EMBED Equation.2 then
(i) EMBED Equation.2
(ii) EMBED Equation.2
(
In a similar way one can construct rules corresponding to the upper approximation of the union of decision classes Xi where i((. The cardinality of this set is related to the value PlA(() (see Section 2.2). It is enough to construct a decision table
P(=(U,A({p(})
where p((x)=1 if (A(x)(( (( and p((x)=0, otherwise.
It is easy to observe that P( is a consistent decision table. Hence applying the methods presented in Section 3.1 we have:
Proposition 3.6. If (((p(=1 is a decision rule obtained by applying to p( any method presented in Section 3.1 and EMBED Equation.2 then
(i) EMBED Equation.2
(ii) EMBED Equation.2
(
One can apply the same method for the generation of decision rules related to the commonality function.
4 Two Main Concepts: Feature Extraction and Classification of New Objects
4.1 Feature Extraction
The vast majority of pattern-recognition systems developed in the past 20 years contains systems that have been designed to deal with a specific problem or set of objects (postal address, numerals, etc.). In each system the recognizing concepts and techniques are pre-defined and remain unchanged during the development of the system. Such systems may present excellent performances in dedicated applications, but they are usually inadequate for other environments or other sets of objects. Our research has been focused on a meta-system which can be used as a high level tool to develop various recognition engines that meet users needs. The approach used in our system is based on the Rough Set theory and target recognition systems are built using a machine-learning process. In our example each recognition system is based on a decision table that has the digit image database as its object space. The decision attribute contains information about the recognition results (expert decision) of the digits. At the beginning, all the digits in the table are totally indiscernible because the attribute set is empty. During the learning process the user will successively create new attributes for the object set and add them to the decision table. Each new attribute brings into the decision table new information that may divide existing boundary sets into smaller ones, which means the approximation of experts classification is improved.
Therefore, with the attributes being added to the decision table, the recognition of objects becomes more accurate. The user continues the process until all digits in the base are properly classified. He may then test his new system on a set of digits not belonging to the database to see how it performs on new objects. During the attribute creation process he will be able to see the effects of his actions on the classifying results and therefore can make the best choice what to do in the next step. The process of building a target recognition table is also referred to as training or information acquisition. The difference between our meta-system and other dedicated recognizers lies in the flexibility of the attribute set. While dedicated systems have fixed attribute sets specific to the concepts employed, our meta-system gives the user the possibility to modify his attribute set in order to produce the target recognizer that is best suited to his needs. This unique feature of the system allows users to create various kinds of recognizers using one common high-level tool.
From the pattern recognitions point of view, attributes are used to extract the patterns specific to each class of objects. The system later scans for these patterns in new test objects to determine to which class it belongs. The final performance of the target systems therefore relies completely on the chosen attribute set. Attributes used to create recognition systems, like the theoretical approaches to the pattern recognition problem, may be classified as statistical or syntactic-structural. Statistical attributes usually are used to extract the common numerical and discrete patterns contained in the objects from the training set, while syntactic-structural are intended to reflect the structural patterns (e.g., strokes or shapes in digit images ) and the interconnections between them. Depending on the nature of the object set, one kind of attributes may be better than the other and vice versa, but the best performance is usually gained by combining both two approaches.
Attributes are used as a mean to distinguish classes of objects from each other, which in terms of Rough Set theory is to split boundary sets into smaller ones. In the process of building target recognizers in the meta-system, the decision which boundary set is to be split belongs to the user, and therefore he should have a tool to divide every boundary set he feels like to. In our system we have created such a tool using modal concepts described in Section 2. The main idea is to find characteristic modal formulae that have different values for objects belonging to different classes, which allows us distinguish them from each other. An algorithm for finding such formulae has been developed. This new kind of attribute is proved to be powerful in splitting classes which are very hard to divide by other traditional attributes and it is one of the unique features of our system.
4.1.1 Implementation of the modal concept.
The states (worlds) u,w ( W are called distinguished by a formula ( if only
K,u |= ( and K,w |= ((
For a given Kripke model K = (W,{Rm}m(M, val( we define a family of binary relations {Dn, n(N} in W assuming: (u,w)(Dn if and only if u and w can be distinguished by a formula with depth not greater than n.
Its obvious that Dn ( Dk if n ( k, where n,k (N.
For each label m(M and each state w(W we define Rm(w) as a set of states u(W such that (w,u)(Rm.
Remarks
We can assume that if states u and w are distinguished by formula (, then ( has one of the following forms: (m( or ((m( or p or (p, where p(V. This fact is easy to prove by induction with respect to the structure of formula (. Indeed, if formula ( distinguishes states u and w and ( is e.g. in the form (=(1((2 then we have
K,u |= (1((2 and K,w |= (((1((2), so
(K,u |= (1 or K,u |= (2) and (K,w |= ((1 and K,w |= ((2)
i.e. either (1 or (2 distinguishes u from w.
Lemma 4.1 If Dn = Dn+1 for some n(N then Dn = Dn+t for any t(N.
(
Proof
We shall prove this lemma by induction with respect to t.
The case t = 1 is obvious.
Let us suppose that Dn = Dn+1 and Dn =Dn+t (Dn+t+1 for some t,n(N.
Because Dn+t ( Dn+t+1, there exists a pair (u,w)(Dn+t+1 such that (u,w)(Dn+t. Hence there exists a formula ( with depth n+t+1 which distinguishes u from w i.e.
K,u |= ( and K,w |= ((
Let us notice that without losing the generality we can assume that ( = (m( for some m(M, then we have (( ( ((( (m(() ( (m(( and |(| = n+t.
Let Rm(u) = {u1,..,ui}( W and Rm(w) = {w1,..,wj}( W. We have
K,u |= ( iff (k({1,..,i} K,uk |= ( (1)
K,w |= (( iff (l({1,..,j} K,wl |= (( (2)
We can assume that i(1, because if Rm(u)=( then (u,w)(D1. From (1) and (2) it follows that formula ( distinguishes states u1,.,ui from state wl. Then {(u1,wl),..,(ui,wl)}(Dn+t=Dn. It means that there exist formulas (1,..,(i with depth not greater than n such that formula (k distinguishes uk from wl for any k({1,..,i} i.e. K,uk|=(k and K,wl|=((k.
Let (= (1((2(..((i and ( = (m(, then
|(| = |(| + 1 ( max(|(1|,|(2|,..,|(i|) + 1 ( n+1.
INCLUDEPICTURE "C:\\PROG\\ORLOWSKA\\02\\FIG02.EPS" \* MERGEFORMAT \d
Figure 2.
For any k({1,..,i} K,uk |= ( and K,wl |= ((, so K,u |= ( and K,w |= (( i.e. u can be distinguished from w by formula ( with depth not greater than n+1, therefore (u,w) ( Dn +1 = Dn=Dn+t, a contradiction.
(
The idea of the lemma is illustrated on Figure 2.
Now we can construct an algorithm generating all pairs that are distinguishable. The algorithm has the following structure:
Algorithm 4.2
Procedure Analysis
begin
Compute (D0);
n := 0;
repeat
n := n+1;
Compute (Dn)
until Dn = Dn -1
end.
Application
Using procedure Analysis one can easily solve the following problems:
Problem 1: For a given Kripke model K = (W,{Rm}m(M, val( and states u,w(W check if there exists a formula which distinguishes u from w.
Problem 2: For a given Kripke model K = (W,{Rm}m(M, val( find the set of all pairs (u,w) ( W(W of distinguishable states .
Problem 3: For a given Kripke model K = (W,{Rm}m(M, val(, subsets S, S' ( W check if S distK S' i.e. if there exists a formula ( such that K,s |= ( and K,s' |= (( for any s(S and s'(S'.
The presented above method may be used in searching for partition of a given set of states in order to split them into classes of discernibility such that two states belonging to different classes are always distinguishable .We will apply this method to the machine learning process used in handwritten digit recognition .
4.2 Classification of New Objects
The main purpose of every recognition system is correct recognition of objects for which it has been designed to deal with. Once we have achieved a decision system with properly classified examples, there are many concepts of how to classify new objects. The simplest way is to compare the attribute value vector of a new object with value vectors of every object in the decision table in order to find an exact match. If there is such a match, the new object is stated to belong to the same class as its matched counterpart. If the table contains no object with the same value vector, the new object is said to be rejected.
There are two kinds of errors in the process of recognition new objects, one is rejection and the other is wrong classification i.e. the new object is assigned a class to which it actually does not belong. Wrong classification and rejection are usually two sides of a medal: If the decision system easily accepts new objects, the wrong classification may be high and vice versa. This is because rejection is the result of information overloading in the decision table when wrong classification is due to information shortage. Many concepts have been developed to improve correct recognition as well as to reduce rejection rate (see e.g. [KM90], [MCM83,86], [MT94]). In our system we investigate some such concepts by applying rough set methods. One of them is to compute reducts and decision rules corresponding to these reducts to decrease the information overloading with classification structure remaining intact. Another approach is to use special classification function that examine the similarity of new objects to already classified objects instead of their identical matching. Such functions are usually referred to as distances measures because they are based on some similarities (expressed often in terms of distances) of new objects to those present in the decision table. They can greatly reduce the rejection rate but must be chosen with special care to assure the correctness of the classification.
In our experiments, instead of exact value vectors matching, we used a method based on matching with decision rules. From the original decision table A a set of decision rules with minimal number of descriptors is created. For each value vector v of an unseen object the rule set is scanned to find all the rules ((d=i, whose the left hand side ( matches the value vector v, i.e. v( (A . The new object with the value vector v is assigned a decision i by a number ni(v) of rules matching v with i. We have different strategies of choosing for v the final decision computed from the set of numbers ni(v) . The simplest one applied in our system is so-called majority voting, i.e. the final decision is the one with the greatest number ni(v), more precisely, it is chosen randomly from the set
{j: nj(v)= maxi ni(v)}.
In our system we have also implemented some other general strategies for classifying new objects. Among them is the following one.
From the original decision table A a set of subtables is created. Any subtable corresponds to a dynamic reduct (with the stability coefficient greater than a given threshold). Next we generate for these subtables a family of sets of decision rules with minimal number of descriptors. The final decision of a new object is the result of a competition between the decisions proposed by sets of decision rules from that family.
5 Description of the System
As an illustration of application of pattern recognition concepts discussed in Section 2 we have implemented a meta-system in which user can create systems recognizing hand-written numerals. We use a database of 800 scanned handwriting digits for learning purposes and a set of 400 other digits for testing. The system can be divided in two modules: The Attribute Module allows user to create his own attributes of different kinds which can be used later in the Learning Module to create user-defined recognition system. The Database used in the system is a part of the huge handwriting character database maintained by the National Institute of Standards and Technologies of the United States. It is called NIST Special Database and serves as a valuable source of data for many researchers all over the world. The data have been collected with scanners and different pointing devices to extract characters and digits from the special forms written by many people in the US. All digits in our database have one normalized format of 32x32 and are black-white. Information about a digit is stored in a file containing its binary image, which has the size of 128 bytes and its character identification (i.e. what type is the digit stored in the file).There are 1200 files of digits from 0 to 9 written by 18 different persons.
5.1 Feature Extraction
The attributes used to create decision tables are of three different kinds: Mask Attributes, Modal Formula Attributes and Topological Attributes. Below is the detailed description of them:
5.1.1 The Mask Attribute Concept
Each mask attribute contains a special bitmap image called a mask. A mask is a table of 32x32 pixels which can have values of 1 or 0. A mask therefore is a bitmap image with the same format as digits binary representation.
When we compare such a mask with a binary image of a digit, we will find that on some positions the two images have the same pixels value, on other positions the values are different. Each position at which the values are identical is encountered as a match. For every pair of a mask and a digit image we have a unique number of matches ranging from 0 to 1024 (so this number can be treated as the Hamming distance between the mask and the digit). If two digits are similar, there is a great chance that in the comparison with the same mask the numbers of matches will not differ very much from each other. Therefore the number of matches can be used as a characteristic of digit classes. We can then use this number to produce attributes that distinguish digit classes from each other.
The basic concept of mask attributes can be evaluated and improved in order to create better distinguishing attributes. We can, for example, explicitly specify the regions in the mask as relevant so that in the comparison process only pixels from these regions will be taken into account instead of all pixels of the mask. We can also use different functions that transform the number of matches into the attribute value in order to improve the tolerance and flexibility of the attribute. In our system the user has the ability to edit, save the mask to the disk as well as load a previously saved mask. He will also be able to select the acceptance level as a parameter for the attributes value assigning function: EMBED Equation.2 f: D{0,1} where D is the set of digits
EMBED Equation.2
We also allow the user to use a special kind of masks, i.e. masks loaded from digit image. By selecting a proper acceptance level, the user can create an attribute that selects out all the digits similar to the digit served as a mask.
5.1.2 Modal Formulas as an Attribute Concept
This concept is derived from the modal logic theory described in Section 2. We describe here the implementation of the algorithm presented in Section 4.2.
Let us suppose that W={w1,w2,..,wk}. We code the set W as the set {1,2,..,k}. We define a global array
Result : Array [1..k,1..k] of Key
where Key = record
minus : Boolean;
next : {0,..,k};
label : M;
end;
Result [i.j] ( nil if wi and wj are distinguished and found (at current step of the algorithm). Then information containd in Key can be used to find a formula distinguishing wi from wj. We have some conditions to determine if (u,w) ( Dn:
there exists a propositional variable p(V such that val(p,u) ( val(p,w), then (u,w)(D0 and Result[u,w].next =0. The formula which distinguishes u from w has the form ( = p.
there exists a label m(M such that Rm(u)=( and Rm(w)((, then (u,w)(D1, Result[u,w] = [False, w, m], where w( Rm(w), and the formula which distinguishes u from w has the form ( = (m ( where ( = p if val (p,w) = 1 and ( = (p otherwise, for any p from V.
there exist a label m(M such that Rm(u)(( and there exists a state w(Rm(w) such that (u(Rm(u), (u,w)(Dn-1 then Result[u,w]=[True,w,m] and Result[w,u]=[False,w,m] and the formula which distinguishes u from w has the form (=(m((1(..((l) if Rm(u) = {u1,..,ul} and (I distinguishes ui from w for i=1,..l.
(w,u)(Dn and Result[w,u].minus = False, then the formula which distinguishes u from w has the form ( = (( where ( distinguishes w from u.
Now we present a procedure Compute(i: Integer) which computes the binary relation Di, assuming that array Result contains all pairs of Di -1.
Procedure Compute ( i :Integer);
{we assume that i ( 2 and the array Result contains all pairs of Di-1 }
begin
Di := Di -1;
1. for j:=1 to k do
begin
S := { s(W : Result[j,s] is not empty};
{ S is a set of states s(W such that (j,s)(Di -1}
for each m(M do
begin
X := { u (W : Rm(u) ( S };
Y := { w (W : j ( Rm(w) };
Di := Di ( (X ( Y) ;
end
end
2. Update array Result with information corresponding to those pairs that belong to the set (Di \ Di-1)
end;
Below we present the detailed description of the procedure Find (i,j : W) which produces a formula distinguishing state wi from wj (if such a formula exists) [TS93].
Procedure Find ( i,j : W);
{recursive procedure }
begin
if Result[i,j].next = 0 then
Find a variable p(V such that val(p,i) ( val(p,j)
if val(p,i)=1 then write(v)
else write((v)
else
if Result [i,j].minus then
begin
write(-);
Find(j,i);
end
else
begin
m:= Result[i,j].label;
s := Result[i,j].next;
write((m);
if Rm(i) = ( then
{let p ( V }
if val(p,s) = 1 then write(p)
else write ((p)
else
begin
write(();
for each r(Rm(i) do
begin
write(();
Find(r,s);
end;
write());
end
end
end;
Remarks [TS93]:
If |M|=n and |V|=e then the procedure Analysis can find all distinguishable pairs in O(n*k4 + e*k2) time, where k is a number of states in the Kripke model.
Given the array Result it is possible to find a formula (if such a formula exists) distinguishing given states with time complexity of order O(k2*n*e).
The main idea is to build an oriented, labeled graph representation of each digit image from the database. We then will use the algorithm 4.2 to find a modal formula that has different values for the graphs representation of digits belonging to different classes. The values of such a formula calculated for all digits in the database can be used as a distinguishing attribute for the decision table. In order to employ the mentioned algorithm, we will combine graphs of two digits for which we want to find a distinguishing formula into one graph and apply the algorithm for special initial nodes that are specific to the graph type.
The modal formula concept is very flexible and is proved to be resistant to the noise in the digit images. The graph representation can reflect both local and non-local features of the digit image and allows to produce very universal attributes. Its weak spot may be the time required to find the formula, due to the high complexity cost of the algorithm.
In our system we use three graph types to implement the modal logic concept described above. In the first graph type each digit image from the database is divided into 32 rows. In each row we consider sequences of neighboring black pixels as nodes. Each node has one attribute, the value of which depends on the length of the black sequence. If this length is greater than 8, the node will be attributed as Long, otherwise its will have value (Long.
The edges of the graph are established in accordance with the following rules:
Two nodes in the graph are connected iff:
They correspond to two black sequences in two adjacent rows.
and
Their corresponding black sequences have a vertically adjacent part, i.e. there is at least one pixel in one sequence lying directly below or above another pixel in the second sequence.
The labels of the edges are defined as follows:
Assuming that e is an edge leading from a node n1 in the row r1 to a node n2 in the row r2 and c1 and c2 are the horizontal coordinates of the middle points of the corresponding black sequences. The edge e is then labeled as:
LDown iff (r1 < r2) and (c1-2 > c2)
Down iff (r1 < r2) and (c1-2 ( c2 (c1+2)
RDown iff (r1 < r2) and (c1+2 < c2)
LUp iff (r1 > r2) and (c1-2 > c2)
Up iff (r1 > r2) and (c1-2 (c2 (c1+2)
RUp iff (r1 > r2) and (c1+2 < c2)
This graph type is intended to reflect the local connectivity of black strokes in the image. For example, the topmost node of a digit 0 will probably have two lower neighbors, when the similar node of a digit 1 probably will not.
The second graph type is a bit more flexible and is described as follows: Each binary image is divided into rectangular regions of size m(n, where 1( m,n (32 are parameters specified by user. Each such a rectangular is considered as a node of the graph. The user can choose some attributes for all nodes in the graph from a set of six pre-defined attributes:
The first attribute has value 1 iff all the pixels in the rectangular are white.
The second attribute is 1 iff all the pixels in the rectangular are black.
The third through sixth attribute is 1 iff the number of black pixels exceeds 20%,40%,60%,80% total number of pixels in the rectangular.
The user will also be able to choose a set of pre-defined labels to be used in the graph. These reflect simple information about adjacency of nodes concerned, i.e. if e is the edge leading from n1 to n2, then label of e tells us whether n2 is in the North, South, East, West, NE, SE, SW, NW of n1. The second graph type is our attempt to store in the graph both local and non-local information about the digit image. The user can adjust the ratio between two types of information by selecting various rectangular sizes and attribute sets.
We have also decided to include a third graph type as an interesting variation of the second type. In this type, instead of eight different label types we have only one denoting the neighboring relation between rectangulars. The user only has to mention the attribute types that are to be included in the graph.
5.1.3 The Topological Attribute Concept
The idea of using topological features of the digit images is to simulate humans way of digits recognition. The digit image is scanned to extract information about special shapes or curves. It is very easy to see that each type of digits has their own characteristic shapes and strokes that other types do not have. The topological features can then be a very effective tools to produce powerful distinguishing attributes. They can withstand heavy noise in the digit images because is does not depend very much on local features in the image. The main disadvantage of this concept is the trade-off between the efficiency and the complexity of the algorithm used to extract topological information.
Our topological attributes are created as follow: Every white pixel in the digit image is scanned in four directions: North, East, South, West for black pixels. The white pixels may be then surrounded by 0, 1, 2, 3, or 4 black pixels.
We are particularly interested in the following bay configurations:
Enclosed Bay: The white pixels is surrounded in all four directions by black pixels.
North Open Bay :The pixels are surrounded in three directions except the North.
Analogously for East, South, West, NE, SE, SW and NW Open Bays.
The user can specify what types of bay he is interested in. He will also type in the acceptance level similar to the one for mask attributes. If percentage of the number of pixels that have the specified bay configuration exceeds the acceptance level, the digit will have an attribute value of 1. Otherwise, this value will be 0.
Topological attributes allow us to produce distinguishing attributes very quickly. For example, to separate digits type 0 from 5, one can simply create an attribute searching for an Enclosed Bay.
5.2 Optimization of Target Systems
Once a decision table has reached the full approximation of the experts decision, it can be regarded as a knowledge base for classification new digits. However, systems constructed by the interactive process of creating and adding various kinds of attributes usually contain noise and much more information than actually needed to recognize new digits. This leads to high rejection and confusion rates of classification new objects and therefore low performance of the generated systems. In order to improve efficiency of target systems, we must eliminate the information overloading in the final decision table so that to exclude as many redundancy as possible. In this system we compute for each generated system the decision rules [BSS94] on the basis of the dynamic reducts. New digits then are classified using these decision rules.
5.3 Remarks on the Implementation
The system has been implemented on IBM PC as a Windows application using the C++ programming language. All Windows graphics interfaces have been designed and implemented using Resource Workshop and Object Windows library from Borland C++ 4.52 Frameworks. Extensive works are being conducted to port the system to UNIX platforms.
6 Experiments with the system
In the experimental system we have implemented two concepts of recognizing new digits, the first one uses simple identity relation for classification and the second using dynamic rules calculated for the decision table generated during the learning process. The results of the tests showed the superiority of the second method over the first. Using 800 objects for training and 400 other for testing, the system has properly recognized 34% new digits by the first method and 87% by the second.
Another problem of the recognition process is the variation of the input data which can be illustrated in handwriting by different writing styles of different persons. The variation in writing styles has been proved to be infinite and unpredictable. This fact has tremendous effects on the quality of the recognizers. If the new digits collection has been written by a author whose style is not recorded in the learning database, one can expect rapid drop of the recognition efficiency. The problem is widely known and, unfortunately, so far no satisfactory solution has been found except using extremely large sets of data for the learning process. This, however, causes many difficulties to the developers and seriously reduces the efficiency and flexibility of systems produced.
We have chosen for testing in our experiments a more difficult data configuration to demonstrate the abilities of the concepts implemented in our system. As a learning data base we have taken 800 digits samples from about 20 writers and for testing purposes we used 400 digit samples from completely different persons. In addition, the testing set has been chosen specially to contain strangely looking digits which may cause problems even for a human being. The attribute set has been produced during a short learning process. We simply took ten masks' attributes based on ten digits written by the first author with acceptance levels around 70 percent, a set of nine topological attributes with acceptance levels of 1 (reflecting only the presence of corresponding topological feature). A few modal attributes have been added in the final phase to improved the classification quality within the decision table. We have noticed that the learning time and classification will be better if we use mask attributes as the first to be included in the decision table. The topological and modal attributes perform much better on boundary sets and classification classes produced by mask attributes. The next attribute type that we recommend to add in the next step is the topological type. With wisely chosen acceptance levels they can do the majority of the job needed to classify the digits in the learning database. The modal attributes are especially useful in the final phase to split ambiguous classes that remain
We also present a study of how each attribute type affects the rejection and confusion rates. From the experiences with the system we have drawn the following conclusion about the efficiency of attribute categories:
i) Mask attributes:
These are very simply and can be quickly computed. Their classification power is not as high as topological attributes but they do not cause many reject cases. The efficiency of masks' attributes increases rapidly on data which comes from similar sources i.e. written by the same person.
ii) Topological attributes:
Very powerful and flexible. They can greatly increase the recognition quality and keep rejection rates in low level. Their main drawback is the high computing costs.
iii) Modal attributes:
Very efficient in eliminating ambiguities but may cause high rejection rates, because they produce information overloading in the values generated for classes that did not require splitting operation, which may cause unnecessary rejection later in recognizing new objects. The modal attributes are intended to split a set of indiscernible objects into two smaller with better classification, which they do extremely well. But this operation also has a side effect. Besides of the classes it splits, the modal attribute assigns to every other class in the decision tables a value which is more or less inadequate to them. This gifted information occasionally may help improve the classification, but in most cases they present an information redundancy as they do not necessarily reflect the real features of the objects they are attached to. Although the classification results are not affected by this information overloading, modal attributes may raise up the rejection rate during the process of classification new objects.
We have done some interesting experiments to illustrate the effectiveness of inductive reasoning and dynamic reduction methods introduced in Section 2. We have created a decision table over a set of 800 objects with 80 attributes, of which 18 are topological, 46 are masks and 16 are modal logic attributes. The classification rate was 100% i.e. all 800 training objects were properly recogniRoot Entry _2Sd2WordDocumentdObjectPool/@;_2@;_2SummaryInformation(qc
/0:;@A"#[\WuySUVe Z
p
''\:]:^:d:e:f:h:i:o:p:q:r:t:w:x:y:UuVPaPuDPJUJJhD
<A*dt<#`#())*Y*c*t***a++E,--+.C..>h>h>>>>>>>>>>> >>>
>>>>>>>>>_>>>>>>>>O>>_>>_hxxxxx
Bhxx%./0W1223e33k44Z555]666n7759:;-;m;;;;"<<=
>>B????nAAA>O>>O>O>O>>>_>_>>>h>h>>_>>>>f>V>>>>>>>>_>>>>_>_>Z>>w>">hxxxx&AABeBBBB1CFFGG~HHJ:KKcMNOPVQQ(RPR~RRRbSSSSUdUU>>>?>?>,>>>>>>>>>>>>>>>>>>_>>>>>>>>/>>>xhxxx hx;
x4."UUWXX4YeYY
ZZZZ$[5^^^k____p`r`,bXb|bbccvcccUdVddddddeeee>>E>>>_>>5>>>>>>
>_>>>_>>>>>>>>>>>>_>>>O>>>>>>,>>>xhxhxhxxx(effhXhhiitjj-kkkDlm5mkm{mmnnInhnin^ooo-ppOqqqqDrrrsssssuu>>>>>>>>>
>f>>>n>>>>>_>>>>>>>
>>>_>}>
>
>
>
>
>>>>>>>N>xxhxx*uuvvw>>>>>>_>>>>>>>(>>>>>>>>?>>>>E>>>>>>{>>>hxxxx
x4#ӈ4;Љ03SU^_*,'7ivj>_>>_>>>U>>V>>>>>_>>>>>>>>>>>>>>>V>>>_>>>>>>V>>>_>>hxhxxx*46Ʀ?@klѪӫ45=UW]>{ذ4]>>>>>>
>>>>>>>>
>j>>>>>\>
>
>>>>>>>>>
>n>>
>
>_>>>xxhxhxx'۲ܲhiwɴ۴38=`ҺYt>>>>>>>>>>>>>>>>>>r>z>>>>>>> >>x
x4hxhxxx 1%-!13Uj~PQ
>>>>>>>
>>$ >>j>>>>>>>>>>>V>>U>U>>>>>
x4h
x4hhxxxx 4>g z&AX^|#(.5Ngv ">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>Lx+"19HNSXYiI#Io
^4O>>>>>>>>>_>_>>>>>>>>O>>>>>>>>>>/>>>_>
x4
x4hx Oq\G'p{Sg Z
q
wKXcfr\ ,!.">> >>>>>>>>>
>>>>> >>>>>>>>>>>>>>> >>>>>>>>>>xxxxx).""##$%H&D''B((f):*D++X,,---U.D///g001;2P3445+6675889[:\:]:f:g:h:>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>h`%+h:u:v:w:x:y:>K(@(Normal ]a k2@2 Heading 13Uc:@: Heading 2x
U]a bc$@$ Heading 3 xU @ Heading 4h^"A@"Default Paragraph Font &@ Footnote Referenceh)@Page Number"O"Normal 2a c,@",
Footnote Text ]k @2 Footer! @B Header!2OR2Abstract ]ck.Ob.Autorh3V]k6Or6Institute 13 ]ck Oq Institute 26O6
References0 ]ck&O&Title
hcOTitle 2y7#
!"#
!"y7y:#!
!!" #a#c'/-8e?GP$XX_cikr}Uǥҷu{+f(y7]b.@Ua
$g
![x|!(k (!"
<A*dt< ` %&&'Y'c't'''a((E)**++C++,-W.//0e00k11Z222]333n445678-8m8888"99:
;;B<<<<n>>>>?e????1@CCDD~EEG:HHcJKLMVNN(OPO~OOObPPPPRdRRRTUU4VeVV
WWWW$X5[[[k\\\\p]r],_X_|__``v```UaVadaaaabbbbcceXeefftgg-hhhDij5jkj{jjkkIkhkik^lll-mmOnnnnDoooppppprrrsst{ح4]ۯܯhiwɱ۱38=`ҷYt13Uj~PQ
4>g z&AX^|#(.5Ngv "19HNSXYiI#Io
^4Oq\G'p{SgZqwKXcfr\,. !"H#D$$B%%f&:'D((X))***U+D,,,g--.;/P012+3345556[7]7y7Root Entry _27`2WordDocumentObjectPool/@;_2@;_2SummaryInformation(qcDocumentSummaryInformation8_8345769796~F@;_2``2_917773498"xF``2
`2_834576976rF
`2
`2
!"#$%&'(*/123589<>?@ABCDEFGHIJKLMNOPQSVWX[]^_`abcdefghijklmnopqrstvy|~՜.+,0HPpxInstytut Matematyki UW 6#2. Basic NotionsOh+'0 4@
ht
2. Basic NotionsEEBartomiej SolarzEDNormal.dotZaklad Logiki Matematycznej3hMicrosoft Word for Windows 95@@F#@ʫ2@)2@7H2#
- )@((
{ %~
FMicrosoft Equation 2.0DS EquationEquation.2_834576975
3lF
`2
`2_834576973fF
`2@`2_834576972 `F@`2@`2_834576970ZF@`2@`2_834576969TF@`2`2_834576967NF`2`2_834576966
HF`2`2_834576964AF`2 n"`2_1014635014:F n"`2 n"`2_85014595993F n"`2+`2_834576961,F+`2+`2_834576960&F+`273`2_834576958 F73`273`2_834576957F73`2^<`2_834576955F^<`2^<`2_917776012F^<`2^<`2_834576952FC`2C`2_834576951FC`2'M`2_834576949F'M`2'M`2_834576948F'M`2'M`2_834576946F'M`2T`2_834576945 FT`2T`2_834576943FT`2]`2_917776280%F]`2]`2_834576941!F]`2e`2_834576939Fe`2e`2_834577866$4Fe`2`n`2_920053592F`n`2`n`2_834577863F`n`2Zv`2_920053805#:FZv`2Zv`2_834577861+FZv`2Zv`2_834577860FZv`2@`2_834577858)'F@`2@`2_834577857F@`2`#`2_920115193F`#`2`#`2_834577855-(F`#`2`#`2_834577853F`#`2 K`2_834577852.,F K`2 K`2_834577851F K`2@`2_834577849&~F@`2@`2_834577848xF@`2`2_83457784720rF`2`2_834577846lF`2`2_8345778451fF`2 `2_8501467307`F `2 `2_834577842ZF `2ܱ`2_83457784185TFܱ`2~`2_850147248NF~`2~`2_834577838HF~`2`2_834578480BF`2`2_920116105*<F`2F`2Ole
+e"System- M::`` p .1@@&MathType0Symbol-!"System- i::` p .1@&MathType Symbol-!"System-o q`X7[o ::, w .1&MathType@ Times New Roman Cyr+-!0"System-? mX:^I
7C:\PROG\ORLOWSKA\02\FIG02.EPS Equation@
e
METAFILEPICT4^4 p .1&MathTypeP Symbol-!e"System-du Equation@
~H
METAFILEPICT```F4 p .1@@&MathType0Symbol-!"System-hhh$ jALdu Equation@
~H
METAFILEPICT```4 p .1@@&MathType0Symbol-!"System-hhh$ jALbi Equation@
e
METAFILEPICT4^5 p .1&MathTypeP Symbol-!e"System-Sk Equation@
~H
METAFILEPICT```4 p .1@@&MathType0Symbol-!"System-hhh$ jAL J Equation@
e
METAFILEPICT4^5 p .1&MathTypeP Symbol-!e"System-. Equation@
ȍEٙ3+¹3
METAFILEPICT```( p .1@@&MathType0Symbol-!"System-hi Equation@
METAFILEPICT`6, p .1@&MathType Symbol-!"System-o q`X7[wl Equation@
0$
METAFILEPICT) w .1&MathType@ Times New Roman Cyr+-!0"System-?: 4<440<t544|00&p<55;<GHYZmnAB`a,- =>01562=vwUVWXY`afgh>?vwcdJ=VJJJtV]nUhUcZMNA B !!1#2#& &S)T)**U*V*W*X*Y*b***0+1+++H,Z,e,f,h,k,t,u,,,,,,,,,,,,,,,,,,,,,,
---+-2-----... ..+.,.?.@.A.uDS1ceKuDS1avKkcuDcJJVhJVUuD:auDnNA.B.C.N.Q.R.S.T.X.[.\.].b.c.p.s.t.u.v.y.z.{.|.........//?/@/B/E/F/G/H/R/S/T/U/z//////0000000000000000000000001111111:1;1O1P1Q1R1d1e111JJUJVhVcuDcZ11111111111111111111111111111111111111222222N2O2P2Q2w2z2{2|2}2222222222222222233333 3
33
33333!36393b3c3u3v3w3y333hJUJJhVhVUh\33333333333333333333334444*4+4546484F4[4_4`4k4l4n4r4s4t4u4w4x4y4z4{4|4}4~444444444444444445555-5.54555;5<5Z5[5\5]5^5q5hn
uD6eKuD6avKuDUhJJVhJUVQq5r5s5t5x5z555555555555555555555555555555556'6+6,6-6A6E6F6G6Z6[6`6a6c6f66666666666žJUUVhVhJV
uDL1eKuDL1avKk
uDM1eKuDM1avKkJJJ
uDO1eKuDO1avKkhuD
uDP1eKuDP1avK=66666666666666666666666777
7777#7$7>7?7@7E7F7Y7Z7[7\7]7v7x7y7z7{7}7~7777777777777777777777777/8ƿUh
uDI1eKuDI1avKk
uDJ1eKuDJ1avKkuDV^UJJJJVhVJI/808588898:8G8Q8T8V8Y8Z888999999)9*9+9,9-9091929=9>9?9^9_99999999999999::`:a:o:p:r:t:u:w:x::::::::::::::::;
;;;; ;!;J^hVh
uDF1eKuDF1avKkV^
uDG1eKuDG1avKkuDVnN!;$;%;&;';(;,;;;O;P;Q;d;g;h;i;j;k;l;p;q;s;v;w;x;y;;;;;;;;;;;;;;;;;;;;;;;;;;;;;<<<<<<
<<<<<<<<<<<3<4<?<I<K<X<^<_<`<o<p<q<r<~<<<<<<<JJ$]JJVVhUV^hJY<<<<<<<<=====3=4=A=B=C=D=E=F=G=l=m=|==========================================>>>>>>>> ????????!?#?$?%?2?:?>???F?JJVUhJVhJVnJVUZF?I?J?K?L?M?P?Q?j?k??????????????????????????A@B@@@AA
AAAA(A*A+A:A;AA@AAAKALAMANAnAoA~AAAuDzB?B@BABBBDBEBFBGBVBWB¼
uDLavuD>e
uDdKavuD
JV]V]
JeV]
uDp=Ue
uDIav
uD4<Ue
uD4Hav
uDUVUV]UUc
uDUc>WBXBYB[B\B]B_BaBbBeBgBhBwBxByBzB{B}B~BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBüuD22]avKkcuDDe
uD\SavuDCe
uDQav
JeV]uD`BUVe
uD,PavUVuDUVuD$Ae
uDNavuDUV]UV]hJeV]hV
uDU
uD?Ue5BBBBCCC!C%C&C'C+C,C0CCCCCJDKDDDkElEFFFFGGGGGGGGGHH!H"H#H%H&HH?H[H\HaHdHeHfHhHiH~HHHHHHHHHHHHHHHƻuDA1UVceKuDA1]avKkUVcuDUVcJeUV]UV] JeVhcnJVVnVU
uDUuD22UeKEHHHHHHHHHHHjIkI|I}IJJLJMJOJPJJJJJ9K:KKKLLMMNNObOmPnPEQFQXQlQmQnQQQQQQQQQQQQQQQQRR(R)R*R+R3R4RGRHRIRJRRRRRRRRR
uD@1eKuD@1avKkuDJUhJU]JQcUcnUV]UVJeVNRRRRRRRRRRRRRRRRRRRRRRR
SS
SSSSSSSS S>S?S@SOSPS^S_S`SaScSeSfSgSjSkS~SSSSSSSSSSSSSSSSSSSSSSSSSSS
uD=1eKuD=1avKkJU]
uD>1eKuD>1avKkuDJJqVJQVUhUKSSSSTTTTTTTTTT!T"TSTVTWTXTZT]T^T_T`TaTfTgThTiTkTlTmTnToTpTTTTTTTTTUUUU
U
UUUUU3U5UdUfUgUhUlUoUpUqUrUsU~UUUUUUUUUUUUUVVJUJnU]JJQJqVVuD
uD;1eKuD;1]avKkPVVV
VVVVAVBVCV^V_VjVyVzV{VVVVVVVVVVVVVVVVVVVVVVV1W2W6W7WWWWWWW#X$X*X+X[X\XXXXXXXXXX5Y6Y7Y8Y=Y?Y@YAYBYCYDYFYGYHYJYKYLYMYQYRYSYTYUY[Y\Y]YlYJqVhV^JnJVhJQUVUhYlYnYoYpYqYuYvYYYYYYYYYYYYYYYYYYZZZ
ZZZPZQZhZZZZZZZZZZZZZZZZZZZ[[[[[[[[
[[[
[[[[[[[[[z[JhVhV^UncJcJQJ
uD81eKuD81avKk
uD&6eKuD&6avKkuDJqVUhVGz[{[[[[[[[[[g\j\k\\\\\\\\\\\] ]+],]}]~]]]]]]]]]]]]]]]]]]]]^^)^*^,^j^k^r^s^|^^^^^^^^^^^
___ɿJVuD51ceKuD51avKkcuDcJQn
uD71eKuD71avKkuDJJJqVVhUhUVF_)_*_+_,_-_D_E_I_J_U_V_W_X_Y_Z_[_\_f_g_h_i_x_y_z_|_}_~_________________________````p`q`r``````````````aa'ancJcUcJ
uD41eKuD41avKkuDUJU]UhJJQJqVVVhJVJ'a(a5a6a7aXaYa_a`acakalamanaoaaaaaaaaabbbbbb(b)b@bDbGbHbYb\b]b^b_b`bdbebxbybzb{bbbbbbbbbbbbbcc$c%c'c(c)c*c+c,c-cScTcUcVcwczc{c|c}c~ccccJJQJ
uD21eKuD21avKkuDUhUnhJqVVhVRccccccccccccccc-d0d2d9d;d=d>d?d@dAdBdCdDdVdcdhdidkdldmdndodpdqddddddddddddddddddddddddddddddUeVeie»c
uD/1eKuD/1avKkJQJJqVJdJnUUhVJcuD
uD11eKuD11avKkFiejekeleeeeeeeeeeeeeeeeeeeeeff g1g7g8gii1i**kkkklllllllll l!l#l$l%l&l(l)l*l+l-l.l/l0l2l3l4l5l5m6m7m8m:m=m>m?m@mAmBmCmDmGmHmImJmLmNmOmPmQmRmSmUmVmWmXmZm]m^m_m`mambmcmdmemfmgmkmlmmmnmqmsmtmumvmwmxmymmmmmmmVJhJJJJJJJyJjXmmmmmmmmnn n
nnnnnnnn"n#n$n%n*n+n,n-n2n3n4n5n?n@nDnEnNnOnPnQnWnXnYnZn`nanhninnn^olo{o|o}ooooooooooooooooooooppEpHpJJJJhJU]UVncJhJJJJJyJJUVJJjLHpJpKpLpMpNpppppppppq1q3q4q:q;qWqXqYq\q]qvqyqqqqqqqqqqqqqqqqqqqqqqqqqqqrrrrrrr r!r,r-r@rArBrCrGrHrNrOrPrQrtrurrrrrrrrrU]ccJhJJJyJVJJjUU]JJUVSrrrrrss\s]ssssssssssssssssssssssssstttt&t>tFtGtHtItNtOtPtQtRt\t]t^tatttutzt{ttttttttt u
uuu u!u"u#u$u%u0u1uJt]VhJ]JJ
uDʥ1eKuDʥ1avKkuDJVnUUcchcJjcK1u2uLuMuXuYudueuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuvvvvvv v
vvv
vvvRvSvvvvvvvvvvvvvww wwwww?w@wAwHwIwJwKwLwOwUwVwWwXwJJJJJtJ]VUn]UhYXwYwmwowrwwwxw|wwwwwwwwwwwwwwwwwwwwwww
xxxxxxyy(y)yyy{{{{{{q|r|||}}}}}}}}}}}}}}~~abijlmopqruDeVccnJUhUV]VhZ $%&'(*+,-.45HIJKLMOQRkmnoހ߀فځ܁݁ƬUhhUe
uD-6eKuD-6]aevKkVhV]
uDǥ1eKuDǥ1]aevKknuDe
uDX6eKuDX6]aevKkeB݁ށ
GH.3456=>?@BCDEIJKLރ߃'(JnV]cJcUhhVh]UVJX
-.ۅ܅݅ޅ;=ˆ̆͆Ά߆JgJJJaJaVcJc]JJVhV]VUU !-.QRSTUVWƇǇЇч
Jghuvʈˈ͈̈ΈψЈш҈
Vn
uD¥1eKuD¥1avKJ
uDĥ1eKuDĥ1avKJ
uDť1eKuDť1avKuDJnJJUhUVhJgVD4567:NOPQRSTZ[\]^͉̉Ή,-YZĊŊȊɊʊˊ̊͊Ί·J
uD6eKuD6aevKkeuDee
uD1eKuD1avKuDJUJVhJJUhVJJJgD͋ϋЋыҋ
!"#;<=>?@PQRtuÌČŌƌϯ̭̭UhhUJ
uD1eKuD1aevKkJJVhV
uD1eKuD1aevKkeuDe
uD1eKuD1aevKkeCƌǌ4789Íč
)*+,-./0;<=FGHOPQRÎĎŎ
JJc
uD1eKuD1avKkuDJaVJUUhhVhnJgVPPQSTU+,Z[]^_`abcopŐƐ,-.fgőƑǑȑüJaV
uD1eKuD1avKkuDJJqVJQJUhJ JVhJnVcUccJcUVH[\^_nrstuvwxyђҒ
%&'(*+,ܙnJqVJJc
uD1eKuD1]avKk
uD1eKuD1]avKk
uD1eKuD1]avKkuDV JVhJaVcUJqUhJJVh JqVh:'(),-./0123=>?@AHIJKLMNOTUVWX,-.WXklmnopwxz{
uD52eKuD52]avKkVh
uD1eKuD1]avKkuDJJbVcJUhJJV JqVhUJqVC$%&-./0:;fhijkÖĖ˖̖͖ΖϖЖіҖӖԖՖږۖܖݖޖ
45ijz~ÿɯJJgVJJJU[hJJ JqVhUUhnJqVJVhVcJcuD
uD1eKuD1]avKkEܗݗ/012456֘"#efÛ>?ߝstefPQ):@iǪU]JjJUVnsncJc
uD1eKuD1]avKk
uD72eKuD72]avKk
uD1eKuD1avKkuDDǪȪΪϪЪѪ(),-.DEFGϫЫѫ/0125<Ȭɬʬ34VWlmnopqJUVJyJJJJJVJhhJUJjJU]RqrsȭɭϭЭѭҭحڭ"#'*568?@DGQRUVW\ȮɮͮЮ֮ڮޮ߮JJUc
JUcJUJJU]hJjW'().>?@Cbc}~ !"#$'(*+,-.45CDLMRSTU]^fglmno{|VhVJ"JJJJyJUJU]nJjJhJSǰȰʰ˰ϰаѰ
;<STXYfgqrtu|}
"#$)*,-/0129:<=>?JJhJJhJJyVhJVJ$JjJU]U?@ABDEFGNORSTU^_deklrstwxyײزٲڲܲ %&,-.]^./ivwnc
JUcJU]JUuDFauDJJhJJfJhJyPwƴǴɴдѴҴִڴߴ,-3=XY\]abcdefhkl{|Ƶ7B]^abfghijkmpqU]hJ]JJJVJhJU]nhUVǶȶζ϶Զնضܶݶp<=սܽ:LNP)*+.BEJKz|9:;?yz019=hVhUhJVJJaVnVUJJ]U]JjU=m~<ANQbmcdklIJfgtuyJjUVJJhuD6ceKuD6acvKuDcc]U
uD01eKuD01avKuDVJyz-.12NOfgtuxyz9:;<=>?@ACDEFMNVW\]cdeuvUJJ"UVJVJyJJjJJhJVij
"#&,.134=>?GH pruxy}&JJJJJhUJy\&0X]^bw}
"#$')-/457inpqrx|}~JhJJJVUVJU\"&0147<GJMORSXYawxhUVJU"zed (learned). We then performed two tests of classification on 400 new objects. Two approaches of classification new objects have been employed. The first one was based on the identity comparison while the second used the procedures for calculating dynamic rules. The first approach gave a very poor classification rate. The second method has been realized in two attempts. In the first attempt we joined attributes by 5 in each group , thus creating a decision table with 18 attributes. For that table we calculated a set of reducts and used reduct majority voting to classify new objects. By this method a recognition rate of 87 % has been achieved. In the second attempt attributes have been grouped by 2 resulting in a table with 40 attributes. From this attribute set 83 reducts have been extracted. Also, we have found three dynamic reducts, each consisting of 26 grouped attributes. Rules produced by these reducts allowed to achieve a new object recognition rate of 86%, thus comparable with the results gained by static rules. Moreover, rules computed from one of these three reducts allowed to achieve a new object recognition rate of 84%, which is also comparable with the result gained by static rules.
By applying the reduct approximations and local dynamic reducts [BS94] we have managed to increase the classification rate up to over 92%.
Conclusions
Two main aspects of the problem of object classification have been discussed: feature extraction and decision rule synthesis.
In our system we have implemented several different methods for feature synthesis. We have employed an automated mechanism for feature searching as well as an interactive tool for defining features explicitly by the user. In the former case we proposed an algorithm searching for feature from a set of multi-modal formulas while the later case involves designing topological and mask attributes.
In addition to some standard methods of decision rule synthesis, we have implemented some new methods for improving the quality of the new object classification. One of them is related to dynamic reducts and allows to extract relevant features used in the process of decision rule synthesis. Another is intended to resolve conflicts arising in the process of new object classification induced by a given set of decision rules.
Experiments performed have shown the effectiveness of proposed methods. We are working on an extension of the system by implementing new algorithms searching for formulas that can help distinguish two collections of objects (current implementation allows searching only for formula distinguishing pairs of isolated objects), as well as employing more advanced tools for designing non-structural attributes, namely tolerance relations and attribute quantization. We work also on inductive reasoning methods for improving the quality of new object classification. We are under a process of porting the software to more powerful UNIX platform, and conducting experiments with a much larger data base (about 230.000 digit samples).
This work was partially supported by the grant T11C01011from State Committee for Scientific Research (Komitet Badan Naukowych).
References
[AD92] Almuallim H., Dietterich T.G., Efficient algorithms for identifying relevant features, Proc. of the Ninth Canadian Conference on Artifitial Intelligence, University of British Columbia 1992, Vancouver, British Columbia, 38-45.
[BSS94] Bazan J., Skowron A., Synak P., Dynamic Reducts as a tool for extracting laws from decision tables, In: Proc. of the International Symposium on Methodologies for Intelligent Systems, October 16-19, 1994, Charlotte, NC, Lecture Notes in Artificial Intelligence No.869, (eds.) M.Zemankova, Z. Ras, Springer-Verlag, Berlin, 1994, 346-355.
[BS94] Bazan J., Skowron A., Synak P., Discovery of decision rules from experimental data, Proceedings of the Third International Workshop on Rough Sets and Soft Computing (RSSC94), November 10-12, 1994, San Jose State University 1994, 526-533.
[BK86] Bhatnager R.K., Kanal, L.N.: Handling uncertain information: A review of numeric and non-numeric methods. In: Uncertainty in Artificial Intelligence, (eds.) L.N. Kanal. and J.F. Lemmer, North - Holland, Amsterdam 1986.
[BL85] Brachman R.J., Levesque H.J.: Readings in Knowledge Representation, Morgan Kaufmann 1985.
[Br90] Brown F.M. Boolean Reasoning, Kluwer, Dordrecht 1990.
[D92] Downton, A., C., Tregidgo, R.,W., S., Leedham, C., G., Hendrawan, Recorgnition of handwritten British postal addresses. From Pixels to Features III. Frontiers in Handwriting Recorgnition, (eds.) S. Impedovo
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abdefghijklmnoprstuvwxyz{|}~ and J.C .Simon, North-Holland 1992, 129-144.
[Dr92] De Raedt L., Interactive Theory Revision. An Inductive Logic Programming Approach, Academic Press, 1992.
[DP80] Dubois D., Prade H.: Fuzzy Sets and Systems: Theory and Applications, Academic Press, 1980.
[FU92] Fawcett T.E., Utgoff P.E.: Automatic feature generation for problem solving systems, In: Proc. of Ninth International Workshop on Machine Learning (ML92) (ed.) D. Sleeman, Morgan Kaufmann, San Mateo, 1992, 144-153.
[GB92] Grzymaa-Busse J.W.: LERS- A System for learning from examples based on rough sets, In: Intelligent Decision Support. Handbook of Applications and Advances of the Rough Sets Theory (ed.) R. Sowiski, Kluwer, Dordrecht 1992, 3-18.
[GB93] Grzymaa-Busse D.M., Grzymaa-Busse J.W.: Comparison of machine learning and knowledge acquisition methods of rule induction based on rough sets, Proc. of the International Workshop on Rough Sets and Knowledge Discovery RSKD93, Banff, Canada, October 12-15, 1993, 297-306.
[HC84] Hughes G.E., Cresswell M.J.: A Companion to Modal Logic, Methuen London & New York 1984.
[IOO92] Impedovo S., Occhinegro S., Ottaviano L., A new method for automatic reading of typed/handwritten numerals. In: From Pixels to Features III. Frontiers in Handwriting Recognition, (eds.) S. Impedovo and J.C.Simon, North-Holland 1992, 163-169.
[K59] Kripke S.: A completeness proof in modal logic, J. Symbolic Logic 24, 1-14-1959.
[K63] Kripke S.: Semantical analysis of modal logic I: normal propositional calculi, Zeitschrift f(r Mathematische Logic und Grundlagen der Mathematik 9, 67-96, 1963.
[K86] Kittler J.: Feature selection and extraction, In: Handbook of pattern recognition and image processing, (eds.)Young and Fu, Academic Press, New York 1986
[KM90] Kodratoff Y., Michalski R.: Machine learning: An Artificial Intelligence approach, vol.3, Morgan Kaufmann, San Mateo, 1990.
[KTM93] Kane R., Tchoumachenko I., Milgram M.: Extraction of knowledge from data using constrained neural networks, Proc. ECML93, Lecture Notes in Artificial Intelligence vol.667, Springer Verlag, Berlin, 1993.
[MMS91] McMillan C., Mozer M.C., Smolensky P.: The connectionist science game: Rule extraction and refinement in neural network, Proc. of the 13-th Annual Conference on the Cognitive Science Society, Hilsdale, NJ (also as CU-CS-530-91, University of Colorado) 1991.
[MCM83] Michalski R., Carbonell J, Mitchell T.: Machine learning: An Artificial Intelligence approach, vol.1, Tioga, Palo Alto, 1983
[MCM86] Michalski R., Carbonell J, Mitchell T.: Machine learning: An Artificial Intelligence approach, vol.2, Morgan Kaufmann, Los Altos, 1986
[MT94] Michalski R.,Tecuci G.: Machine learning: A Multistrategy approach, vol.4, Morgan Kaufmann, San Mateo, 1994
[Mu92] Muggelton S. (ed.): Inductive logic programming, Academic Press 1992
[PR93] Pattern Recognition Vol.26 Number 3. Handwriting Processing and Recognition, Pergamon Press, March 1993
[Pa82] Pawlak Z.: Rough sets, International Journal of Information and Computer Science 11(1982) 344-356.
[Pa91] Pawlak Z.: Rough sets: Theoretical aspects of reasoning about data, Kluwer, Dordrecht 1991.
[PS93] Pawlak Z., Skowron A.: A rough set approach for decision rules generation. ICS Research Report 23/93, Warsaw University of Technology, also In: Proc. of the IJCAI93 Workshop W12: The management of Uncertaining in AI, France 1993.
[SD90] Shavlik J.W., Dietterich T.: Readings in Machine Learning, Morgan Kaufmann, San Mateo, 1990.
[Sh76] Shafer G.: Mathematical Theory of Evidence, Princeton University Press 1976.
[SP90] Shafer G., Pearl J., Readings in Uncertain Reasoning, Morgan Kaufmann, San Mateo, California, 1990.
[SL90] Shrager J, Langley P, Computational methods of scientific discovery and theory formation, Morgan Kaufman, San Mateo, 1990.
[SG94] Skowron A., Grzymala-Busse J.W.: From rough set theory to evidence theory. In: Advances in the Dempster-Shafer Theory of Evidence, (eds.) R.R.Yager, M. Fedrizzi and J. Kacprzyk, John Wiley and Sons, New York 1994, 193-236.
[Sk90] Skowron A.: The rough sets theory and evidence theory. Fundamenta Informaticae 13,(1990), 245-262.
[S93a] Skowron A.: Boolean reasoning for decision rule generation, In: Proceedings of the 7-th International Symposium ISMIS'93, Trondheim, Norway 1993, (eds.): J. Komorowski and Z. Ras Lecture Notes in Artificial Intelligence, vol.689, Springer-Verlag, Berlin, 1993, 295-305.
[S93b] Skowron A.: A Synthesis of Decision Rules: Applications of Discernibility Matrices, Proceedings of the Conference on Intelligent Information Systems, Augustow, Poland, June 7-11, 1993.
[S95] Skowron A.: Synthesis of decision systems from experimental data, In: Proc. SCAI-95 Fifth Scandinavian Conference on Artificial Intelligence, (eds) A.Aamodt, J. Komorowski, IOS Press 1995, 220-238.
[SP97] Skowron A., Polkowski L.: Synthesis od decision systems from data tables, In: Rough Sets and Data Mining: Analysis of Imprecise Data, (eds.) T.Y. Lin and N. Cecerone, Kluwer 1997,259-300.
[SS91] Skowron A., Stepaniuk J.: Towards an approximation theory of discrete problems, Fundamenta Informaticae vol.15(2) 1991, 187-208.
[SS91a] Skowron A., Stepaniuk J.: Searching for Classifiers In:, Proceedings of the First World Conference on Foundations of Artificial Intelligence (eds.) M. de Glas, D. Gabbay, Paris, July 1-5 1991, 447-460.
[SS93] Skowron A., Stepaniuk J.: Intelligent Systems Based on Rough Set Approach, Foundations of Computing and Decision Sciences, vol.18(3-4), 1993, 343-360.
[St94] Stepaniuk J.: Decision Rules for Decision Tables, Bulletin of the Polish Academy of Sciences, Technical Sciences, Vol.42, No. 3, 1994, 457-469.
[Sti92] Stirling C.: Modal and temporal logics, In: Handbook of Logic in Computer Science vol.2, (eds.) S. Abramsky, D.M. Dabbay and T.S. Maibaum, Clarendon Press, Oxford 1992, 478-563.
[TS93] Trung N.T., Son N.H.: An Approach to the Handwriting Digit Recognition Problem Based on Modal Logic, ICS Research Report 44/93, Warsaw University of Technology, 1-58.
[ZS93] Ziarko W., Shan N.: An incremental learning algorithm for constructing decision rules, Proc. of the International Workshop on Rough Sets and Knowledge Discovery, Banff 1993, 335-346.
PAGE
PAGE 9
$7.A 0
k- iX:^
e
C:\PROG\ORLOWSKA\02\FIG01.EPS::4@ p .1&MathTypeP Symbol-!e"System-ic::`` p .1@@&MathType0Symbol-!"System-hhh$ jAL u::`` p .1@@&MathType0Symbol-!"System-hhh$ jALep::4@ p .1&MathTypeP Symbol-!e"System-ri::`` p .1@@&MathType0Symbol-!"System-hhh$ jALsk::4@ p .1&MathTypeP Symbol-!PIC
;>)LMETA(CompObj=?ZObjInfo@
Equation Native <Ole
6PIC
AD4LMETA0CompObjCE.ZObjInfoF-Equation Native ,<Ole
TPIC
GJRLMETA=CompObjIK;fObjInfoL:Equation Native 7Ole
wPIC
MPuLMETA\CompObjOQZfObjInfoRYEquation Native UOle
PIC
SVLMETA}CompObjUW{mObjInfoXzEquation Native xhOle
PIC
Y\LMETACompObj[]fObjInfo^Equation Native Ole
PIC
_bLMETACompObjacfObjInfodEquation Native Ole
PIC
ehLMETACompObjgifObjInfojEquation Native hOle
PIC
knLMETACompObjmofObjInfopEquation Native Ole
PIC
qtLMETACompObjsufObjInfovEquation Native Ole
.PIC
wz,LMETA!CompObjy{fObjInfo|Equation Native hOle
APIC
}?LMETA4CompObj2mObjInfo1Equation Native /hOle
\PIC
ZLMETAH|CompObjFmObjInfoEEquation Native BOle
jPIC
hLMETAaCompObj_mObjInfo^Equation Native ]@Ole
xPIC
vLMETAoCompObjmmObjInfolEquation Native k@Ole
PIC
LMETA}CompObj{mObjInfozEquation Native y@Ole
PIC
LMETACompObjmObjInfoEquation Native @Ole
PIC
LMETACompObjZObjInfoEquation Native \Ole
PIC
LMETACompObjZObjInfoEquation Native <Ole
PIC
LMETACompObjZObjInfoEquation Native <Ole
PIC
LMETACompObjZObjInfoEquation Native <Ole
PIC
LMETACompObjfObjInfoEquation Native @Ole
PIC
LMETACompObjfObjInfoEquation Native @Ole
PIC
LMETACompObjfObjInfoEquation Native @Ole
PIC
LMETACompObjmObjInfoEquation Native dOle
PIC
LMETACompObjZObjInfoEquation Native \Ole
4PIC
2LMETA%CompObj#mObjInfo"Equation Native `Ole
EPIC
CLMETA:CompObj8mObjInfo7Equation Native 5LOle
ZPIC
XLMETALCompObjJmObjInfoIEquation Native FOle
nPIC
lLMETA`CompObj^mObjInfo]Equation Native [|Ole
PIC
LMETAtCompObjrmObjInfoqEquation Native o`Ole
PIC
LMETACompObjmObjInfoEquation Native Ole
PIC
LMETACompObjmObjInfoEquation Native Ole
PIC
LMETACompObjmObjInfoEquation Native LOle
PIC
LMETACompObj mObjInfoEquation Native Ole
PIC
LMETAXCompObjmObjInfoEquation Native Ole
%PIC
#LMETACompObjfObjInfoEquation Native POle
8PIC
6LMETA+CompObj)mObjInfo(Equation Native &POle
KPIC
"ILMETA>CompObj!#<mObjInfo$;Equation Native 9POle
^PIC
%(\LMETAQCompObj')OmObjInfo*NEquation Native LPOle
|PIC
+.zLMETAiCompObj-0gfObjInfofOle10Native/1bEquation Native _Ole
PIC
25LMETA`CompObj47fObjInfoOle10Native68Equation Native }Ole
PIC
9<LMETACompObj;>fObjInfoOle10Native=?Equation Native Ole
PIC
@CLMETACompObjBEfObjInfoOle10NativeDFEquation Native |Ole
PIC
GJLMETATCompObjIKmObjInfoLEquation Native 0Ole
PIC
MPLMETATCompObjOQmObjInfoREquation Native 0Ole
PIC
SVLMETATCompObjUWmObjInfoXEquation Native 0Ole
PIC
Y\LMETATCompObj[]mObjInfo^Equation Native 0Ole
PIC
_bLMETApCompObjac
mObjInfodEquation Native 4Ole
%PIC
eh#LMETACompObjgimObjInfojEquation Native <Ole
3PIC
kn1LMETA*CompObjmo(mObjInfop'Equation Native &<Ole
GPIC
qtELMETA9CompObjsu7ZObjInfov6Equation Native 4\Ole
ZPIC
wzXLMETALCompObjy{JZObjInfo|IEquation Native H<Ole
rPIC
}pLMETAaCompObj_mObjInfo^Equation Native [~< .1&&MathTypepTimes New Roman-2
2
r(d) 2
=#2
2
i
1 iff p Times New Roman(- 2
PfTimes New Roman-2
4
ercentage 2
5
of the num 12
H
ber of mat 12
L
ches in th 2
>
e comparis 1
2
Qon 2
i
of d 2
.
with the . 2
mask over 1 2
1
the total 2
number of 1 2
$
pixels spe 2
cified 2
i
is g2
!
reater tha 2
n the acce 2
ptance lev
2
el2
i
0 if ot 2
0herwise .Symbol- 2
ZF 2
F 2
F 2
F 2
F 2
F 2
3F 2
iF 2
F
&
"System-7@L,, )((
+9
FMicrosoft Equation 2.0DS EquationEquation.20 P .1&&MathType@
&
"System-L,̜hJpmJ\iJ
PlA
q()=xU:A
x()q{}abUab
FMicrosoft Equation 2.0DS EquationEquation.29q' .1``& &MathTypeMPSymbol-2
(MPSymbol-2
5)MPSymbol-2
f
(MPSymbol-2
)PSymbol-2
,{PSymbol-2
>} "-PDPDl
l
llTimes New Romanl-
2
TPlY 2
x 2
U 2
x 2
o
U@PSymbol- 2
rAPSymbol- 2
q 2
2
N
q 2
= 2
2
! 2
E 2
ETimes New Romanl- 2
:Y@Times New Romanl- 2
A
&
"System->L'
̼iJlmJ|iJ
xU:A
x()q{}=gq
()A
=pq
=1()Pq
FMicrosoft Equation 2.0DS EquationEquation.29q .1@&.&MathTypeMPSymbol-2
h(MPSymbol-2
)PSymbol-2
.{PSymbol-2
@}3PSymbol-2
(3PSymbol-2
)3PSymbol-2
L(3PSymbol-2
)Times New Romanl- 2
x 2
U 2
x 2
pPSymbol- 2
2
# 2
G 2
G
2
"= 2
Q= 2
W=Times New Romanl- 2
:YPSymbol- 2
2
Pq 2
g@PSymbol- 2
Gqc 2
}qc`PSymbol- 2
4qS@Times New Romanl- 2
A 2
LA 2
@PuTimes New Romanl- 2
D1
&
"System-L
L(JJJ
bq
=1()Bq
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29q! .1``& &MathType,PSymbol-2
z0(,PSymbol-2
zb)Times New Roman- 2
`b@PSymbol- 2
+qc`PSymbol- 2
MqSPSymbol- 2
`= 2
` 2
`Times New Roman- 2
`1@PSymbol- 2
B
&
"System-L!|̘hJhmJTiJ
BelA
q()=xU:A
x()=q{}abUab
FMicrosoft Equation 2.0DS EquationEquation.29q W .1`&@&MathTypeMPSymbol-2
(MPSymbol-2
)MPSymbol-2
(MPSymbol-2
)PSymbol-2
{PSymbol-2
T} "-PDPD
lvl"Times New Romanl-2
FBelY 2
Ox 2
U 2
jx 2
U@Times New Romanl- 2
A 2
6
APSymbol- 2
q 2
2
q 2
k= 2
- 2
=Times New Romanl- 2
:Y
&
"System-L ̴iJdmJtiJ
xU:A
x()q{}=bq
()A
=bq
=1()Bq
FMicrosoft Equation 2.0DS EquationEquation.29qS+ .1@&&MathTypePSymbol-2
m(PSymbol-2
)PSymbol-2
.{PSymbol-2
}PSymbol-2
(PSymbol-2
)PSymbol-2
5(PSymbol-2
)Times New Romanl- 2
x 2
U 2
x 2
bPSymbol- 2
2
? 2
= 2
4= 2
=Times New Romanl- 2
:YPSymbol- 2
2
tq 2
^b@PSymbol- 2
qc 2
+qc`PSymbol- 2
qS@Times New Romanl- 2
A 2
\%
A 2
\BTimes New Romanl- 2
1
&
"System-LS+LiJlmJ|iJ
A
=q()A
FMicrosoft Equation 2.0DS EquationEquation.29q U .1` &&MathType:PSymbol-2
z0(:PSymbol-2
z)PSymbol- 2
` 2
`Uq`PSymbol- 2
O@Times New Romanl- 2
XA 2
|APSymbol- 2
`]= 2
` 2
`
&
"System-L|̔lJqJlJ
mA
q()=xU:A
x()=q{}abUabfJ
FMicrosoft Equation 2.0DS EquationEquation.29q l .1@&`&MathTypePSymbol-2
(PSymbol-2
)PSymbol-2
(PSymbol-2
%)PSymbol-2
{PSymbol-2
}
} "-AUA#U#
STimes New Romanp- 2
6m 2
x 2
QU 2
x 2
U@Times New Romanp- 2
PA 2
Q APSymbol- 2
(q 2
2
qPSymbol- 2
= 2
n 2
=Times New Romanp- 2
P:Y
&
"System-L$ ̴iJdmJtiJ
xU:A
x()=q{}=aq
()A
=A
=q()A
"#$%&'()*+-0356789:;<=>@CDGIJKLMNOPQRSTUVWXY[`bcdefginpqrstuw|~
FMicrosoft Equation 2.0DS EquationEquation.29q+ .1&&MathTypePSymbol-2
m(PSymbol-2
)PSymbol-2
.{PSymbol-2
}PSymbol-2
(PSymbol-2
)PSymbol-2
5(PSymbol-2
)Times New Romanl- 2
x 2
U 2
xPSymbol- 2
2
G= 2
= 2
4= 2
j=Times New Romanl- 2
:YPSymbol- 2
2
Kq 2
;a 2
2
nq@PSymbol- 2
qc`PSymbol- 2
*O@Times New Romanl- 2
A 2
\%
A 2
[A 2
XA
&
"System-IL+
LlJqJlJ
A
=q()A
FMicrosoft Equation 2.0DS EquationEquation.29q U .1` &&MathType:PSymbol-2
z0(:PSymbol-2
z)PSymbol- 2
` 2
`Uq`PSymbol- 2
O@Times New Romanp- 2
XA 2
|APSymbol- 2
`]= 2
` 2
`
&
"System-L|L(JJJ
dA
=q()Ad
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29q P .1`&&MathType3PSymbol-2
x0(3PSymbol-2
x)PSymbol- 2
`d 2
`Dq`PSymbol- 2
dN@PSymbol- 2
TA 2
eAPSymbol- 2
`L= 2
` 2
`
&
"System-L||HJJJ
#TraceA,k():dxk
()=i{}k
U
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29qN : .1
&@
&MathType3PSymbol-2
(3PSymbol-2
i)3PSymbol-2
(3PSymbol-2
)PSymbol-2
v{PSymbol-2
}Times New Roman-2
Trace| 2
k 2
Fd 2
x 2
QiY@Times New Roman- 2
kT 2
kTPSymbol- 2
ZATimes New Roman- 2
=,P 2
:iPSymbol- 2
T=@MT Extra- 2
3U'
&
"System-LNp$<JJJ
*ijk
c
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29qW .1 &@&MathType`@Times New Roman-
2
ij55 2
kTTimes New Roman- 2
8c
&
"System-LWT$<JJJ
*ij,
c
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29qW .1 &@&MathType`@Times New Roman-
2
ij55Times New Roman- 2
8c@Times New Roman- 2
,0
&
"System-0LWT$<JJJ
*ijk
c
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29qW .1 &@&MathType`@Times New Roman-
2
ij55 2
kTTimes New Roman- 2
8c
&
"System-LWT$<JJJ
*ijk
c
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29qW .1 &@&MathType`@Times New Roman-
2
ij55 2
kTTimes New Roman- 2
8c
&
"System-LWT@/27171
*ij,
c New Roman-
2
FMicrosoft Equation 2.0DS EquationEquation.2; .1`&@&MathType`Times New Roman-
2
ijYYTimes New Roman0y- 2
cTimes New Roman- 2
,L
&
"System-L| /2$7171
*i,
g
FMicrosoft Equation 2.0DS EquationEquation.2; .1``&@>&MathTypePTimes New Roman0y- 2
8iYTimes New Roman- 2
,LSymbol- 2
g
&
"System-L| /2$7171
*i,
g
FMicrosoft Equation 2.0DS EquationEquation.2; .1``&@>&MathTypePTimes New Roman0y- 2
8iYTimes New Roman- 2
,LSymbol- 2
g
&
"System-L| /27171
*i,
g
FMicrosoft Equation 2.0DS EquationEquation.2v; .1``&@>&MathTypePTimes New Roman- 2
8iYTimes New Roman0y- 2
,LSymbol- 2
g
&
"System-L|$lJqJlJ
*ij,
c
FMicrosoft Equation 2.0DS EquationEquation.29q4 .1&@&MathTypeP@Times New Romanp-
2
ij55Times New Romanp- 2
6c@Times New Romanp- 2
,0
&
"System-L4@$lJqJlJ
*ij,
c
FMicrosoft Equation 2.0DS EquationEquation.29q4 .1&@&MathTypeP@Times New Romanp-
2
ij55Times New Romanp- 2
6c@Times New Romanp- 2
,0
&
"System-L4@$lJqJlJ
*ij,
c
FMicrosoft Equation 2.0DS EquationEquation.29q4 .1&@&MathTypeP@Times New Romanp-
2
ij55Times New Romanp- 2
6c@Times New Romanp- 2
,0
&
"System-L4@H(JJJ
V=#Va
VdaA
U
FMicrosoft - Edytor rwna 2.0
!$&'()*+,-./01369;<=>?@ABDGHKMNOPQRSTUVWY\_abcdefghijkmpsuvwxyz{|}~DS EquationEquation.29q+ N .1&&MathTypeTimes New Roman- 2
` V 2
`V 2
`DV@Times New Roman- 2
~a` 2
d` 2
oa` 2
mAuPSymbol- 2
`g= 2
`4@PSymbol- 2
@MT Extra- 2
U'
&
"System-L+F@),d ,
,,,,
FMicrosoft Equation 2.0DS EquationEquation.2U
; .1` &,@ &MathType@Symbol- 2
2
2
2
`| 2
Times New RomanX- 2
,` 2
,` 2
,` 2
,`
&
"System-7
LU
D(JJJ
mA
D()Dq
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29qN .1`& &MathTypeAPSymbol-2
u}(APSymbol-2
u)Times New Roman- 2
`m@Times New Roman- 2
AuPSymbol- 2
`D@PSymbol- 2
?Du 2
@PSymbol- 2
`=@PSymbol- 2
`qc
&
"System-LN[0<JJJ
#Xiiq
U
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29qq+ .1 &&MathTypeTimes New Roman- 2
`X@Times New Roman- 2
i5 2
;i5@PSymbol- 2
2
qc@MT Extra- 2
5U'
&
"System-Lq+hHJJJ
A#Xiiq
U
abUab
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29qV d .1 &m&MathType "-YShhS@Times New Roman- 2
MA 2
M9X 2
U@Times New Roman- 2
i5 2
vi5@PSymbol- 2
v 2
v~qc@MT Extra- 2
U'
&
"System-LV4`(JJJ
A#Xiiq
U
abUab
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29q<V d .1&m&MathType "-YShhS33@cTimes New Roman- 2
MA 2
MX 2
U@Times New Roman- 2
i5 2
voi5@PSymbol- 2
v 2
vqc@MT Extra- 2
eU'
&
"System-L<VD(JJJ
mA
D()Dq
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29qN .1@&&MathTypeAPSymbol-2
uE(APSymbol-2
u)Times New Roman- 2
`m@Times New Roman- 2
AuPSymbol- 2
`D@PSymbol- 2
?Du 2
@PSymbol- 2
`=@PSymbol- 2
`qc
&
"System-LNHtHJJJ
mA
q()=FA
q()abUab
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29q .1`@&&MathTypeAPSymbol-2
(APSymbol-2
)APSymbol-2
2(APSymbol-2
I) "-]]IITimes New Roman- 2
@m 2
F 2
U@Times New Roman- 2
(Au 2
AuPSymbol- 2
"q 2
q 2
=
&
"System-L (ѠJJJ
FA
q()=AXi
ifq={i}forsomei(1ird()ifq=Bd
q()ifqab>1{
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29q}L m .1@
& &MathType`APSymbol-2
(APSymbol-2
) "-APSymbol-2
(APSymbol-2
)APSymbol-2
u (APSymbol-2
u )H H] ]Times New Roman- 2
HF 2
A 2
X
2
ifYY 2
iY2
-forY|
2
some| 2
iY 2
iY 2
Or| 2
Qd
2
M
ifYY
2
` Bd
2
` ifYY@Times New Roman- 2
Au 2
i5PSymbol- 2
q 2
q 2
q 2
` ]q 2
` q 2
Z= 2
= 2
2
M 2
2
= 2
2
` > 2
c 2
c 2
c 2
c 2
c 2
c 2
c 2
c 2
O cTimes New Roman- 2
{| 2
t}| 2
x(iTimes New Roman- 2
1 2
`
1
&
"System-L}Lh0<JJJ
#Xiiq
U
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29qq+ .1 &&MathTypeTimes New Roman- 2
`X@Times New Roman- 2
i5 2
;i5@PSymbol- 2
2
qc@MT Extra- 2
5U'
&
"System-JLq+8JJJ
#AXiiq
U
#BdA
D()Dq,Dab>1
U
=A#Xiiq
U
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29qq .1 &&MathType "-N3PSymbol-2
~ (3PSymbol-2
~!) "--
Times New Roman- 2
`A 2
`nX
2
`Bd 2
`
A 2
`:X@Times New Roman- 2
Ji5 2
;i5 2
I Au 2
i5 2
i5@PSymbol- 2
2
2
>i 2
PSymbol- 2
` 2
`=@PSymbol- 2
qc 2
qc 2
qc@MT Extra- 2
5U' 2
7U' 2
U'PSymbol- 2
`O
D@PSymbol- 2
Du 2
2Du@Times New Roman- 2
,0@Times New Roman- 2
M1`
&
"System-KLq
Ѡ,JJJ
%BNA
Xi
()iq
I
%-BNA
Xi
()iq
I
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29qB+ ' .1&
!"$'*,-./0123457:=?@ABCDEFGHJMPRSTUVWXYZ[]`acdehjklmnopqrstuvwxy{~&MathType3PSymbol-2
x(3PSymbol-2
x)3PSymbol-2
x@(3PSymbol-2
x)Times New Roman-
2
`BN 2
`|X
2
` BN 2
`X@Times New Roman- 2
OAu 2
^i5 2
Di5 2
Au 2
i5 2
i5@PSymbol- 2
} 2
PSymbol- 2
`a 2
`-@PSymbol- 2
qc 2
Fqc@MT Extra- 2
3I' 2
I'
&
"System-LB+8 G4lJqJlJ
mD()Dq
FMicrosoft Equation 2.0DS EquationEquation.29q [ .1`& ;&MathTypeLPSymbol-2
(LPSymbol-2
)Times New Romanp- 2
mPSymbol- 2
D PSymbol- 2
?D 2
PSymbol- 2
U PSymbol- 2
qt
&
"System-L[04<JJJ
mD()Dq
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29qN [ .1&`&MathTypeAPSymbol-2
u(APSymbol-2
u)Times New Roman- 2
`mPSymbol- 2
`D@PSymbol- 2
?Du 2
@PSymbol- 2
^=@PSymbol- 2
\qc
&
"System-JLN4<JJJ
mD()DQ
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29q<N C .1&&MathTypeAPSymbol-2
u(APSymbol-2
u )Times New Roman- 2
`mPSymbol- 2
`7D@PSymbol- 2
?Du 2
aQ 2
@PSymbol- 2
w=
&
"System-JL<N4<JJJ
mD()DQ
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29q<N C .1&&MathTypeAPSymbol-2
u(APSymbol-2
u )Times New Roman- 2
`mPSymbol- 2
`7D@PSymbol- 2
?Du 2
aQ 2
@PSymbol- 2
w=
&
"System-HL<NPΘlJqJlJ
#DR(A,ArialF)={aA:aR for some RDR(A,F)}.
U
#DR(A,F)={aA:aR for some RDR(A,F)}.
U+10]!2
FMicrosoft Equation 2.0DS EquationEquation.29q
W .1 @&&MathType`Times New Romanp-
2
`DR 2
`0a 2
`A
A 2
`a 2
`
R2
`for someY|P| 2
`gR
2
`DR Arial- 2
`G(k 2
`,Y 2
`)k 2
`{k 2
`
:Y 2
`+(k 2
`,Y2
`)}.kkYTimes New Romanp- 2
`A 2
`r P 2
` P 2
`A Arial- 2
`F 2
`FPSymbol- 2
`= 2
`" 2
` 2
`w@MT Extra- 2
3U'
&
"System-L
WTPhlJqJlJ
{BArialF:CRED(B,d)}abFab
DRe
(A,F)={CRED(A,d):{BF:CRED(B,d)}abFab1-e}
FMicrosoft Equation 2.0DS EquationEquation.29q1h .1&&MathType "-[h h[b bE@E Arial- 2
{k 2
:Y 2
(k 2
5
,Y
2
r)}kkTimes New Romanp- 2
B 2
h BPSymbol- 2
2
Arial- 2
F 2
FTimes New Romanp- 2
_C2
RED 2
d
&
"System-L1hPlJqJlJ
DRe
(A,ArialF)={CRED(A,d):{BF:CRED(B,d)}abFab1-e}
DRe
(A,F)={CRED(A,d):{BF:CRED(B,d)}abFab1-e}
FMicrosoft Equation 2.0DS EquationEquation.29q# .1 @ & &MathType "-DDHH77Times New Romanp-
2
`JDR 2
`iC2
` RED 2
`
d 2
^C2
^RED 2
^d@PSymbol- 2
eTPSymbol- 2
`e Arial- 2
`(k 2
`,Y 2
`@)k 2
`{k 2
`(k 2
`\
,Y
2
`):kY 2
^{k 2
^.:Y 2
^=(k 2
^|,Y
2
^)}kk 2
`}kTimes New Romanp- 2
`A 2
`{A 2
^?B 2
^B Arial- 2
`XF 2
^ZF 2
b=FPSymbol- 2
`= 2
` 2
^c 2
^ 2
`. 2
`-Times New Romanp- 2
`1
&
"System-L#(P`lJqJlJ
RED(A,d)%RED(B,d)BArialF
I
RED(A,d)%RED(B,d)BF
I/]/999n
FMicrosoft Equation 2.0DS EquationEquation.29q+ .1`& &MathTypeTimes New Romanp-2
JRED 2
d2
RED 2
d Arial- 2
(k 2
,Y 2
L)k 2
@(k 2
,Y 2
)kTimes New Romanp- 2
.A 2
B@Times New Romanp- 2
>BPSymbol- 2
@PSymbol- 2
@ Arial- 2
>Fu@MT Extra- 2
nI'
&
"System-L+JJJ
B
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29q` .1@&y&MathType "-O@OTimes New Roman- 2
HB
&
"System-L`JJJ
B
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29q` .1@&y&MathType "-O@OTimes New Roman- 2
HB
&
"System-L`JJJ
B
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29q` .1@&y&MathType "-O@OTimes New Roman- 2
HB
&
"System-L`JJJ
B !"$)+,-./0258:;<=>?@ABCDFKMNOPQRSTUVWY\]`bcdefghijklmnoq
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29q` .1@&y&MathType "-O@OTimes New Roman- 2
HB
&
"System-KL`JJJ
a*
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29q .1&@d&MathType Times New Roman- 2
8a@Times New Roman- 2
*`
&
"System-L JJJ
cij*
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29q{ .1@&@&MathType`Times New Roman- 2
8c@Times New Roman-
2
ij55@Times New Roman- 2
*`
&
"System-L{h JJJ
cij*
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29q{ .1@&@&MathType`Times New Roman- 2
8c@Times New Roman-
2
ij55@Times New Roman- 2
*`
&
"System-GL{h@8oFoF
a1*
,...,am*
FMicrosoft Equation 2.0DS EquationEquation.2*{G X .1@&`
&MathType@Times New RomanV- 2
a 2
aTimes New Romanp- 2
mTimes New RomanV- 2
1Times New Romanp- 2
* 2
*Times New RomanV- 2
,\ 2
M.` 2
.` 2
.` 2
,\
&
"System-L*{hor 7 55
a7
FMicrosoft Equation 2.0DS EquationEquation.2*{F X .1@&`
&MathType@Times New Roman- 2
a 2
aTimes New Roman- 2
mTimes New Roman- 2
1Times New Roman- 2
* 2
*Times New Roman- 2
,\ 2
M.` 2
.` 2
.` 2
,\
&
"System-@@@=@@@=@@@=L*{hor|XJJJ
InfB
:UCourierPB#VaaB
U
()
FMicrosoft - Edytor rwna 2.0DS EquationEquation.29qE .1&@&MathTypeTimes New Roman-2
@KInfiY 2
@U 2
@B 2
@O V@Times New Roman- 2
Bu 2
a` 2
ia` 2
iBuTimes New Roman- 2
@:iPSymbol- 2
@< 2
@G 2
qy 2
,y 2
jy 2
q
y 2
,
y 2
j
y@PSymbol- 2
iu0Courier- 2
@%P@MT Extra- 2
z U'
&
"System-LE0l&&&&&&&&A.13q56/8!;<F?AWBBHRSVlYz[_'aciekmHpr1uXw݁ƌǪq?w=y&U.AUeuӈ"O."h:y:'U'W'++?+A+122]2q2s2222222222E4Y4[4}4446)6+6666<<<*>:><>n>~>>>>>>>>.?>?@?F?V?X?g?w?y?????????????~EEE3OGOIOOOOjP~PPPPPuVVVVVVZZZ[[[\\\d_x_z_```aaaUbibkbbbbgggppp|||}}}4}H}J}Є͈ψш
Ŏǎя
%'Wkmzܔ/1ׯٯy7C:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::C::!!gy7UPracownia Komputerowa!C:\USERS\TRUNG\ksiazka\rozdz2.docPracownia Komputerowa!C:\USERS\TRUNG\ksiazka\rozdz2.docZaklad Logiki Matematycznej*C:\USERS\Trung\ksiazka_orlowska\rozdz2.docZaklad Logiki Matematycznej*C:\USERS\Trung\ksiazka_orlowska\rozdz2.docZaklad Logiki Matematycznej*C:\USERS\Trung\ksiazka_orlowska\rozdz2.docZaklad Logiki Matematycznej*C:\USERS\Trung\ksiazka_orlowska\rozdz2.docZaklad Logiki Matematycznej*C:\USERS\Trung\ksiazka_orlowska\rozdz2.docZaklad Logiki Matematycznej*C:\USERS\Trung\ksiazka_orlowska\rozdz2.docZaklad Logiki Matematycznej*C:\USERS\Trung\ksiazka_orlowska\rozdz2.docZaklad Logiki Matematycznej
A:\rozdz2.doc@Apple LaserWriter Pro 630LPT1:PSCRIPTApple LaserWriter Pro 630Apple LaserWriter Pro 630g 3dXX'`R/RdCustom page 1BBCustom page 2BBCustom page 3BBApple LaserWriter Pro 630g 3dXX'`R/RdCustom page 1BBCustom page 2BBCustom page 3BBTimes New RomanSymbol&Arial5Courier New5MS LineDrawFBrush Script MTTimes New Roman CE"e&
&&
-###!Q2. Basic NotionsBartomiej SolarzZaklad Logiki MatematycznejܥhW ey:d\7666:d...>N^7
"=???BLL
XQ7
77
xx
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~x=Sd2hbBbxx=Chapter 2
Decision Rule Synthesis for Object Classification
Jan G.Bazan1, Hung Son Nguyen2, Tuan Trung Nguyen3,Andrzej Skowron2, Jaroslaw Stepaniuk4
1 Institute of Mathematics, Pedagogical University, Rejtana 16A,35-310 Rzeszw, Poland
2 Institute of Mathematics, University of Warsaw, Banacha 2,02-097 Warsaw, Poland
3 Institute of Computer Science, University of Warsaw,Banacha 2,02-097 Warsaw, Poland
4 Institute of Computer Science, Technical University of Biaystok, Wiejska 45A, 15-351 Biaystok
Abstract: We discuss two applications of logic to the problem of object classification. The first is related to the problem of employing multi-modal logics in automatic feature extraction. The second is based on inductive reasoning for discovering optimal feature set with respect to the precision of classification and for improving the performance of decision algorithms. We also present an exemplary system for recognizing handwritten digits based on boolean reasoning, rough set methods and feature discovery by applying multi-modal logic.
1 Introduction
In this paper we present a general system for classifying objects. The aim of the system is to generate, on the basis of training object samples, a set of decision rules for correct classification of objects, in particular new ones, different from those in the training set. We assume that this system operates on a set of objects previously classified by an expert. In this system the set of attributes (for an object) is not predefined, as in traditional classification systems, by the designers, but the appropriate set of attributes is automatically selected from a general set of attributes specified by the designer. Attributes in the system are represented by multi-modal formulae that express the structural properties of the classified objects. Objects are represented by labeled graphs from a Kripke model. In any such model, the problem of searching for relevant attributes can be regarded as finding multi-modal formulae distinguishing the states of the Kripke model. The system has been designed so that the user can decide what type of labeled graphs are to be used for the representation of objects. This makes the system very flexible in the inductive reasoning method of searching for relevant attributes.
In our exemplary system each object is represented by a knowledge representation graph. The nodes and edges in such a graph are labeled by some pairs of the form (formula, logical value) or by triples (formula, logical value, pointer). In the latter case the pointer is given from the formula to a sub-graph (or a partial order of sub-graphs in more complicated cases) defining a model in which the formula is evaluated. The pairs (formula, logical value), where the formula is a multi-modal formula, represent attributes. One of the simplest examples of a knowledge representation graph can be constructed by splitting raster images representing objects into sections; the nodes of the graph are labeled with atomic formulae (and their corresponding logical values) representing patterns contained in the sections, and the edges are labeled with information about the interconnection between adjacent sections.
Our method is based on a logical approach and uses some ideas known in the knowledge representation literature [BL85].
Two nod"&0147<GJMORSXYawxAB+,89FGMNTU
1267?@FGWX\]eflm{|JhVJhUVJU]*