## Cs.concordia.ca

Intelligent systemsLevels of thinkingNonmonotonicity and incompletenessEffective questioning3 Problems: Q-All SAT, Q-MINFIX UNSAT, Q-MINFIX SATSeparationsDiscretizationImportant FactorsExplanationsApplication examplesReferences
A system is ✐♥t❡❧❧✐❣❡♥t if it accomplishes feats that, when carriedout by humans, require a substantial amount of intelligence.

Medical diagnosis, processing of natural language, supervisionof complex processes.

An ❡①♣❡rt s②st❡♠ is an intelligent system which in an interac-tive setting asks a person for information and, based upon theresponse, draws conclusions or gives advice.

An ✐♥t❡❧❧✐❣❡♥t ❛❣❡♥t is an intelligent system which perceives itsenvironment by sensors and which uses that information to actupon the environment.

Expert systems and intelligent agents are special cases of intel-ligent systems.

An example of an intelligent system that is not an intelligentagent: an intelligent system that constructs expert systemsfrom data. That intelligent system is not an intelligent agent,unless one accepts the odd notion that creating an expert sys-tem constitutes acting upon an environment.

“Model”: In propositional logic, a satisfying solution. Here, amathematical formulation of a real-world situation.

“Valid”: In propositional logic, a formula that always evaluatesto ❚r✉❡. Here, a formulation that correctly represents a partof the real world of interest.

“Do symptoms s and t imply that disease d or e is present?”
“Is this log-in behavior typical for a hacker?”
We think about which logic module of the first level is to beused. May involve selection, modification, creation of module.

Third Level (= thinking about thinking about think-ing)
We think about which process of the second level is to be used.

Reduction to thinking at lower level generally cannot beachieved by a polynomial algorithm. Note: “cannot” is meantpragmatically in the sense that presently nobody knows of apolynomial reduction.

Link to polynomial hierarchy of theory of computation: kthlevel of thinking corresponds to kth-level of hierarchy.

a, b, c, d, . . . = vectors of Boolean variables∀a ∃b ∀c ∃d . . . D(a, b, c, d, . . .)
Each quantifier introduces another level.

Deduction of theorems T from axioms of a propositional logicformula S.

Finding best satisfying solution for a CNF system propositionallogic formula S. Accelerated theorem proving. Handling ofspecial satisfiability cases.

Conclusion may become invalid when additional information isobtained. Axioms must be modified.

Desired conclusion cannot be derived. Axioms must be modi-fied.

Decide if desired conclusion cannot be derived even if all as-yet-unknown data are obtained.

Decide which type of nonmonotonic reasoning or which discov-ery method of futility is to be used.

Questions are selected so that, as soon as possible, desired con-clusion can be proved or shown to be futile.

Computations constructing intelligent systems that reason atthe first and second levels.

Analyze problem. Formulate logic conditions and constraints.

Define and implement all system operations.

Obtain data about problem. Derive logic conditions and con-straints from the data. Use a metamethod to construct mod-ules for all system operations.

- Cost of ❚r✉❡ or ❋❛❧s❡ for a variable; call this Truecost and
- Representation of unknown values by two values: ❆❜s❡♥t
and ❯♥❛✈❛✐❧❛❜❧❡.

- Likelihood of clauses being applicable.

- Predicates with finite quantifications ∃ (there exists) and ∀
- Quantification of propositional variables. For example, for
all ❚r✉❡✴❋❛❧s❡ values of a subset of the variables, there exist
❚r✉❡✴❋❛❧s❡ values for the remaining variables so that theformula has a specified value. Can be viewed as special caseof predicate with finite quantification.

For variable x: Truecost = 10, Falsecost = −5
∀u ∈ U ∀v ∈ V [¬g(u, v) ∨ h(u, v)]
x = ❆❜s❡♥t: value of x unknown, but could be obtainedx = ❯♥❛✈❛✐❧❛❜❧❡: value of x cannot be obtained
Example of Quantification of Propositional Variables:
CNF formula R with vectors q and x of variables.

CNF formula S with vectors q and y of variables.

For all ❚r✉❡✴❋❛❧s❡ values of the qi of vector q:if R is satisfiable, then S is satisfiable as well.

We often use CNF s②st❡♠ instead of CNF ❢♦r♠✉❧❛.

CNF system: list of variables; list of CNF clauses, each ofwhich uses a subset of the variables.

■♥st❛♥❝❡: CNF system S.

❙♦❧✉t✐♦♥: Either: A satisfying solution of S. Or: The conclusionthat S is not satisfiable.

■♥st❛♥❝❡: CNF system S. For each variable of S, two rationalcost values associated with the values ❚r✉❡ and ❋❛❧s❡ for thatvariable.

❙♦❧✉t✐♦♥: Either: A satisfying solution of S for which the totalcost is minimum. Or: The conclusion that S is unsatisfiable.

Deduction: Core approach of mathematics.

Most reasoning in everyday life is not deduction.

1. Operation of light bulb by switch.

2. Learning to drive by experimentation.

Mathematics: Use probability theory and induction to con-vert such reasoning to deduction.

Here: Want to use just one tool, an extension of propositionallogic.

When additional facts become available, previously proved the-orems remain theorems.

Monotonicity of first-order logic is essential for mathematics.

Conclusion may become invalid by additional information.

1. A conclusion by abduction turns out to be in error.

2. Use of the value ❯♥❛✈❛✐❧❛❜❧❡ in a Question-and-Answer pro-
cess eliminates CNF clauses and thus may eliminate theo-rems.

odel’s Incompleteness Theorem (1931).

We simply do not have the needed clauses.

Statement Y = ¬X → R = X ∨ R should be a theorem, but isnot.

Thus, S ∧ ¬Y = S ∧ ¬X ∧ ¬R is satisfiable, but should beunsatisfiable.

S = S ∧ ¬X = S ∧ Y ∧ ¬X may be unsatisfiable, but shouldbe satisfiable. Must modify S to eliminate this effect.

Subproblem of Treating Futility of Questions in ExpertSystem
Expert system asks for information to prove some result. If theresult cannot be proved at all, the system should stop as soonas this fact becomes evident.

Questions q1, q2, q3. Defects r, s, t.

CNF system R has relationships connecting q1, q2, q3.

q1 → (r ∨ t)q2 → (¬r ∨ ¬t)(q1 ∧ q2) → ¬rq3 → (s ∨ ¬t)
Suppose we want to prove defect t. We are given value q1 =
❋❛❧s❡. It is easy to see that we cannot prove t with this infor-mation.

Problem: Can t be possibly proved by some values for q2 andq3?
If answer is “no”, then it is useless to ask for the values of q2and q3, and we should stop. Thus, proving t is ❢✉t✐❧❡.

CNF system S ; enforces ¬t for theorem proving.

¬q1 ∨ r ∨ t¬q2 ∨ ¬r ∨ ¬t¬q1 ∨ ¬q2 ∨ ¬r¬q3 ∨ s ∨ ¬t¬t
Proving t is futile if, for all ❚r✉❡✴❋❛❧s❡ values of q1, q2, q3satisfying R, the CNF system S is satisfiable.

Enumeration shows that proving t is indeed futile.

On the other hand, if originally q1 = ❚r✉❡, then there are valuesfor q2, q3 so that t can be proved; take q2 = ❚r✉❡.

Definition: An assignment of ❚r✉❡✴❋❛❧s❡ values to q1, . . . , qlis R✲❛❝❝❡♣t❛❜❧❡ if the SAT instance of R with q1, . . . , ql fixedaccording to the given assignment is satisfiable.

■♥st❛♥❝❡: Satisfiable CNF systems R and S that have l ≥ 1special variables q1, . . . , ql among their common variables.

❙♦❧✉t✐♦♥: Either: “All R-acceptable assignments of ❚r✉❡/
❋❛❧s❡ values for q1, . . . , ql are S-acceptable.” Or: An R-accep-table assignment of ❚r✉❡✴❋❛❧s❡ values for q1, . . . , ql that is S-unacceptable.

a, b, c, d, . . . = vectors of Boolean variables∀a ∃b ∀c ∃d . . . D(a, b, c, d, . . .)
Transformation to standard form is trivial. However, even thefastest present-day algorithms for the standard case do notperform well on this particular problem, since the structure isnot exploited.

Ongoing work with A. Remshagen. Recursively fixes qk vari-ables and tries out effect. Learns clauses and predicts SATbehavior to reduce size of search tree, using an extension ofthe heuristic algorithm given later. As an aside, the algorithmproves some special cases to be in NP.

1. Do unit-resolution in R on all variables. All Q variables
fixed in R by unit-resolution are fixed in S as well.

2. Do unit-resolution in S on the Y variables only.

3. If (Q = ∅)
if (R is satisfiable and S is unsatisfiable)
5. If (QRSsat(Q \ {q}, R(q = ❚r✉❡), S(q = ❚r✉❡)) = ❚r✉❡)
Else if (QRSsat(Q\{q}, R(q = ❋❛❧s❡), S(q = ❋❛❧s❡)) = ❚r✉❡)
1. Algorithm learns clauses before backtracking from a given
fixing. Main idea: Unfix Q variables while showing thatthe same conclusion is still valid. The remaining fixed vari-ables produce a clause that excludes that fixing. The learnedclauses are added to R. An enhanced version of the nextheuristic is used for the learning of the clauses.

2. Predict SAT behavior of S using values of fixed Q and Y,
plus a greedy heuristic. Use predictions for backtracking andfor selection process of next Q variable to be fixed.

1. If deletion of all free qk reduces S to a satisfiable S : Fixing
of any qk cannot produce unsatisfiability. Hence, the Q-ALLSAT instance has been solved.

2. (S is unsatisfiable) Compute a minimal unsatisfiable subset
of clauses of S . Let S be corresponding subsystem of S.

Check if qk values exist that satisfy R while causing all lit-erals of the qk in S to evaluate to ❋❛❧s❡.

If such qk exist, then the Q-ALL SAT instance has beensolved.

1. Robot navigation through grid with obstacles.

Question: Can obstacles be so placed that they block therobot?18 instances.

2. Game tree where first player tries to prevent opponent from
reaching goal.

Question: Can first player achieve goal?12 sets of 12 instances each.

(1) Robot case: Each figure is total time (sec) for 18 instances.

Game case: Each figure is average time per set of 12 in-stances.

(2) Error termination in 4 instances.

(3) 1 hr time limit exceeded in 15 out of 18 instances. Used
3,600 sec for these cases in the statistic.

(4) 1 hr limit exceeded for 14 instances.

(5) 1 hr limit exceeded for 4 instances. Error termination for 10
(6) 1 hr limit exceeded for 10 instances.

Robot instances: QRSsat3 at least 200 times faster.

Game instances: QRSsat3 at least 400 times faster.

Subproblem of Learning to Ask Relevant Questions
■♥st❛♥❝❡: Satisfiable CNF system S containing l ≥ 1 specialvariables q1, . . . , ql. An S-unacceptable assignment. For eachqj, a cost of obtaining the given ❚r✉❡✴❋❛❧s❡ value of qj.

❙♦❧✉t✐♦♥: An S-unacceptable partial assignment with minimumtotal cost.

Must carry out tests with given costs to get sets of values.

In medical diagnostic system, have obtained symptom valuesq1, q2, . . . , ql by some tests, and have proved some disease t tobe present.

Want to find out in hindsight which tests should have beendone to get values for some of the variables q1, . . . , ql so thatthe disease could have been proved at least total cost.

Subproblem of Learning to Ask Relevant Questions
■♥st❛♥❝❡: Satisfiable CNF systems R and S having l ≥ 1 vari-ables q1, . . . , ql among their common variables. An assignmentfor q1, . . . , ql that is both R-acceptable and S-acceptable. Foreach qj, a cost of obtaining the given ❚r✉❡✴❋❛❧s❡ value for qj.

❙♦❧✉t✐♦♥: A partial assignment such that each R-acceptable ex-tension assignment is S-acceptable. Subject to that condition,the total cost of the partial assignment must be minimum.

Must carry out tests with given costs to get sets of values.

In medical diagnostic system, have obtained symptom valuesq1, q2, . . . , ql by some tests, and have determined that somedisease t cannot be proved.

Want to find out in hindsight which tests should have been doneto get values for some of the variables q1, . . . , ql so that, at leasttotal costs, the same conclusion could have been obtained.

Training sets A and B consist of records of length n. The kthentry is the value for attribute k. Entries may be ❚r✉❡, ❋❛❧s❡,or ❯♥❛✈❛✐❧❛❜❧❡.

The value ❯♥❛✈❛✐❧❛❜❧❡ means that one cannot get a ❚r✉❡✴❋❛❧s❡value.

Note: Generally, another value is possible: ❆❜s❡♥t. In thatcase, one does not know value, but can obtain it. In this talk,we will not make use of that option.

Find a logic formula that is ❚r✉❡ on A and ❋❛❧s❡ on B, or showthat this cannot be done. The formula s❡♣❛r❛t❡s A from B.

The sets A and B usually are taken from two populations Aand B. A separating formula for A and B may then be usedto predict whether a record is in A or B.

There are effective methods to find separating formulas. In ourapproach, the formulas are in disjunctive normal form (DNF),and we construct them by a recursive process.

Example: (x ∧ ¬y ∧ z) ∨ (¬x ∧ v) ∨ (y ∧ w)
Goal: Logic data sets A and B representing A and B.

Most popular method: Entropy plus Minimum DescriptionLength Principle (MDLP). The principle generally selects thehypothesis that minimizes the description length of the hypoth-esis plus the description length of the data given the hypothesis.

Here, we apply a new method of pattern analysis.

1. Sort the numerical entries of the attribute. Label each entry
of the sorted list by “A” (resp. “B”) if coming from a recordof A (resp. B). The result is a ❧❛❜❡❧ s❡q✉❡♥❝❡.

10.8 3.7 2.9 1.7 0.5 −1.0 −3.5 −11.9
3. Find an interval where the sequence switches from mostly
important the interval. Put a cutpoint c into the middle ofthe interval. Details are given in a moment.

Logic attribute yc: if x ≤ c, then yc = ❋❛❧s❡
1. In the label sequence, replace each A by 1 and each B by 0.

2. Smooth the sequence of 0s and 1s by Gaussian convolution.

The variance of Gaussian convolution is determined by eval-uation of a ❝♦♠♣❡t✐♥❣ r❛♥❞♦♠ ♣r♦❝❡ss. Goal is smoothing sothat randomly introduce differences are eliminated.

3. Select cutpoint where the smoothed data change by maxi-
10.8 3.7 2.9 1.7 0.5 −1.0 −3.5 −11.9
Discussion via example of cancer data.

Cervical Cancer: FIGO I-III versus Recurrence
Derive factors explaining difference between FIGO I-III andRecurrence, using lab data.

1. Partition the data into FIGO I-III cases and Recurrence
2. Discretize the two data sets, getting sets A for FIGO I-III
3. Compute a separating logic formula achieving ❚r✉❡ for A
For each literal (= occurrence of a possibly negated variable)of the formula, count the number of records for which theliteral is needed to achieve ❚r✉❡ for the formula. The countis the ✐♠♣♦rt❛♥❝❡ ✈❛❧✉❡ of the literal for the formula.

Repeat the above step, but exchange the roles of A and B.

4. For each literal l, normalize the two importance values using
the number of records of A or B, whichever applies. Thus,get average importance values f
5. The variables for which at least one of the two possible lit-
≥ 0.4, are the ✐♠♣♦rt❛♥t ❢❛❝t♦rs.

Discussion uses example of FIGO I-III versus Recurrence.

1. Delete from the data all attributes except for the important
factors determined in the previous step.

2. Discretize the sets of FIGO I-III and Recurrence records
3. Compute a logic formula that is ❚r✉❡ on A and ❋❛❧s❡ on B,
and a second formula that is ❋❛❧s❡ on A and ❚r✉❡ on B.

The logic formulas, combined with the discretization infor-mation, constitute the desired explanations.

We define a statistic with 0/1 value via the explanations ob-tained in the previous step.

Hypothesis H0: The explanations produce accurate predic-tions.

Hypothesis H1: The explanations do not produce accurate pre-dictions. Indeed, with some luck, the same accuracy can beachieved by flipping an unbiased coin, which statistically is aBernoulli trial with α = 0.5.

Procedure: Find Explanations and Establish Signifi-cance
1. Split the given data into a training set and a testing set.

2. Obtain explanations from the training data using the earlier
3. Apply the explanations to the testing data and determine
how often the explanations are correct/incorrect.

4. Compare the outcome of Step 3 with results of Bernoulli
5. Use direct computation or approximation by normal distri-
bution to obtain probability p that Bernoulli trials obtainthe same results or better. If p is very small, then acceptH0. Otherwise, accept H1.

The data sets used in this subsection were supplied by theFrauenklinik of the Ruhr-Universit¨
SURVZ (living at present)HER2 (value of second test)Thymidinphosphorylase:
VEGF (Vascular Endothelial Growth Factor)COX2 (Cyclooxygenase 2)K18 (Keratin 18)
HAT AD MED (adjuvant hormone therapy: medication
HER2 STAT (HER2 status (2, 3, ?))FISH STAT (FISH Status (0,1))HISTO TYP (histological tumor type (1,2,3))PT (tumor size (1,2,3,4,?))PN (lymphnode status (1,2,3,?))M (metastasis (0,1,?))G (grading (1,2,3,?))REZ ER (estrogen receptor expression (0,1,?))REZ PR (progesterone receptor expression (0,1,?))Local recurrence and distant metastasis status:
AT LOK (local)AT ABD (abdominal)AT HEP (liver)AT PUL (lungs)AT ZNS (central nervous system)
AT PERI (heart)AT PLEU (pleura)AT ASCI (ascites)AT LYM (lymphangiosis)AT KNO (bone)
HT AD (hormone therapy)HT PA (palliative hormone therapy)CT AD (chemotherapy)CT PA (palliative chemotherapy)ST (radiation)BT (bisphosphonates)Age (years)BEST RES (best response
(1 = complete response,2 = partial response,
TTP (time to progression (weeks))SURV (survival time (weeks))
Which factors influence time to progression (TTP)?
The most important factors influencing TTP are:
∗Note: Values computed by initial method for importance fac-tors. Threshold for that method was 0.2.

The data contain three patients with amazingly high TTP val-ues. Analysis of reasons produces the follow explanation:
In two situations, high TTP values are predicted:
Explain the difference between local recurrence and metastasisusing lab data.

15 patients (3 local recurrence, 12 metastasis)
The difference between local recurrence and metastasis can beexplained as follows.

If K18 ≥ 3.0 and PL M ≥ 2.0,then local recurrence case.

If K18 ≤ 2.0 or PL M ≤ 1.0,then metastasis case.

The data sets used in this subsection were supplied by theFrauenklinik of the Charit´
1. Factors Influencing Time to Progression (TTP)
RESP (responder (0 = no, 1 = yes))AGE (years)PARTUS (number of born children)MENOP (menopause (0 = no, 1 = yes))T (Tumor size (FIGO))N (Lymphnode metastasis (0 = no, 1 = yes))
(0= poorly diff. squamous cell carcinoma,
1= moderately diff. squamous cell carcinoma,2= poorly diff. Adeno-Ca,3= SCC))
TTP (time to progression (months))SCC 0 (squamous cell carcinoma antigen, baseline)SCC 4 (after 4 weeks chemotherapy)
SVEGF 0 (SVEGF-A = vascular endothelial growth
PVEGF 0 (PVEGF-A = vascular endothelial growth
SVEGF D 0 (SVEGF-D = vascular endothelial growth
EGF 0 (epidermal growth factor in pg/ml, baseline)EGF 1 (after 1st cycle 4th dose)
IGF 0 (IGF = insulin like growth 1 factor in ng/ml, baseline)IGF 1 (after 1st cycle 4th dose)
Which factors influence time to progression (TTP)?
Two cases: (1) Using initial data only. (2) Using initial andsubsequent data.

Both cases result in the same most-important attributes:
∗Note: Values computed by initial method for importance fac-tors. Threshold for that method was 0.2.

High TTP values (TTP ≥ 39) are predicted if
Low TTP values (TTP ≤ 19) are predicted if
Note: In the case of SVEGF D 0 < 357, we also havePARTUS = 0.

2. Difference Between FIGO I-III and Recurrence
Note: At present, treatments cannot utilize this information.

We include it here to demonstrate validation.

57 patients (31 for training, 26 for testing)
31 training cases: 19 FIGO I-III, 12 Recurrence
26 testing cases: 14 FIGO I-III, 12 Recurrence
Note: FIGO IV excluded since too few cases.

If ENDOSTATIN < 123.0 or M2PK PLASMA < 18.8,then FIGO I-III case.

If ENDOSTATIN > 123.0 and M2PK PLASMA > 21.8,then Recurrence case.

22 of 26 cases are predicted correctly. Accuracy = 85%.

Significance of conclusion is p < 0.0002.

1. K. Truemper, “Effective Logic Computation” (Wiley, 1998).

2. K. Truemper, “Design of Logic-based Intelligent Systems”
Book “Data Mining and Knowledge Discovery ApproachesBased on Rule Induction Techniques”, E. Triantaphyllou andG. Felici, eds., Springer Verlag, Berlin, 2006:
1. “Learning Logic Formulas and Related Error Distributions”
(coauthored, G. Felici, F. Sun, and K. Truemper).

2. ”Learning to Find Context-based Spelling Errors”, (co-
authored, H. Almubaid and K. Truemper).

3. “Transformation of Rational and Set Data to Logic Data”
(coauthored, S. Bartnikowski, M. Granberry, J. Mugan, andK. Truemper).

“A MINSAT approach for learning in logic domains,” (coau-thored, G. Felici and K. Truemper), INFORMS ❏♦✉r♥❛❧ ♦♥
❈♦♠♣✉t✐♥❣ 14 (2002) 20–36.

Source: http://www.cs.concordia.ca/~chvatal/truemper.pdf

Dr. Maria Fe Corpuz-Bato MEDICAL HISTORY Patient’s name ____________________________________________________________Date Form Completed____/_____/_____ Birth date______/______/______ Weight___________________________*Blood Pressure___________________ Instructions to the Patient: Answer the following questions as completely and accurately as possible. All information is CONFIDENT

A Me m be r of the University of Ma ryland Medical System (http://www.um m s.o rg) | In Partnership with the University of Ma ryland Scho ol of Medicine(http://m edscho ol.um aryla nd.edu/)Em ail (http://www.um m .edu/em a ilpage/em ailthispa ge.cgi) Home (http://www.umm.edu) > Medical Reference (http://www.umm.edu/medref/) > Complementary Medicine(http://www.umm.edu/altmed)N ot