Vu Dissertation Ppt

Vu Le PhD Defense George Mason University February 20th, 2008

Overview Research Problem Abstraction for Collaboration Abstraction for Tutoring Tutoring: Lesson Design and Generation Tutoring: Test Learning and Generation Learning and Tutoring Agent Shell Summary of Contributions and Conclusion

Research Context Intelligent Assistants that:  learn complex problem solving expertise directly from human experts;  support human experts in complex problem solving and decision making;  teach their complex problem solving expertise to nonexperts.

teaches

Agent

Expert

collaborates Agent User

Agent

KB

KB

KB

teaches Student

Problem-Reduction/Solution Synthesis Paradigm The reduction representation of a class of problems is a quadruple (P, S, RO, OS) where:

S1

i

P - class of problems; S - solutions of problems;

P1 S1 … P1 S1

RO - reduction operators, each reducing a problem to sub-problems and/or solutions, SO - synthesis operators, each A problem P1 is solved by: synthesizing the solution  successively reducing to simpler of a problem fromitthe solutions of through the application of the itsproblems sub-problems. reduction operators;  finding the solutions of the simplest problems;  successively combining these solutions through the application of synthesis

P1

RO

1

1

P2 1

n

n

S2 … P2 S2 1 m m

SOj P3 S3 1

1

…

Pp3 Sp3

Application Domain: Intelligence Analysis

Complexity of the Reasoning Trees Assess whether Al Qaeda has nuclear weapon

Total Nodes = 1758

Problem: Complexity of the Reasoning Trees

?

 difficulty in understanding the complex reasoning impedes human-agent collaboration;

collaborate Agent User

 complex reasoning hinders teaching problem-solving expertise;  complex reasoning makes building tutoring systems for expert knowledge difficult.

KB

?

? Agent author

Instructor

teach

KB Student

Research Question How to abstract the complex reasoning processes to facilitate: Abstraction for collaboration

 human-agent collaboration in complex problem solving and decision-making.  teaching complex problemsolving knowledge to nonexperts.  rapid development of intelligent tutoring systems for expert knowledge;

collaborate Agent User

KB

Abstraction for tutoring

Agent author

Instructor

teach

KB Student

Related Research on Abstraction  Abstraction has been used in different areas of AI to facilitate problem solving: • Planning (Knoblock, 1991)1 • Constraint Satisfaction (Mozetic, 1991)2 • Reasoning about Physical Systems (Nayak and Joskowics, 1996)3 A problem is first solved in an abstract space and the abstract solution is refined for the full solution of the original space.  In our research we have investigated the abstraction of reasoning to facilitate  displaying, browsing, understanding complex reasoning – abstraction for collaboration  tutoring of complex reasoning –Artif. abstraction for tutoring 1. Knoblock, C. A. 1991 Automatically generating abstractions for planning. Intell. 68, 243– 2.

302. Mozeticˇ, I. 1991 Hierarchical model-based diagnosis. Int. J. Man–Machine Stud. 35, 329–362.

Abstraction of Reasoning  Both types of abstraction of reasoning share the same foundation: • The reasoning tree is partitioned into sub-trees • Each sub-tree is abstracted in different ways for different purposes.  Abstraction for collaboration facilitates the understanding of the obtained solution (for expert user).  Abstraction for tutoring facilitates the identification and teaching of the problem solving strategies (for instructor and student).

Overview Research Problem Abstraction for Collaboration Abstraction for Tutoring Tutoring: Lesson Design and Generation Tutoring: Test Learning and Generation Learning and Tutoring Agent Shell Summary of Contributions and Conclusion

Abstraction for Collaboration Abstract Level

APa APb

APe

APb

Rd1 P2

P3 Rd2

APa

APc APd

P1

Sub-trees abstracted to nodes

Presented as TOC

Concrete Level

APc

APd

APe

P4

P5

P6

Rd3

Rd4

Rd5

S1

S2

S3

Abstract and Concrete Reduction Tree TOC

Abstract tree

Reduction of a problem to its main sub-problems

Detailed tree

Abstract and Concrete Reduction and Synthesis Tree Problem: Solution

Abstract tree

Reduction and Synthesis Tree

Detailed tree

Abstraction-Based TOC

Evaluation Results students 10 9

CS681-06 MAAI-07

students

8

8

TOC is easy to understand

7 6

7 6

It is easy to learn how to browse the reasoning tree using TOC

5

5

4

4

3

3

2

2

1

1

0

0 strongly disagree

strongly disagree

disagree

neutral

agree

strongly agree

disagree

neutral

agree

strongly agree

students 9 8 7 6

students

It is easy to browse the reasoning tree using TOC

6

5

5

4

4

3

3

2

2

1

1

0

0

strongly disagree

disagree

neutral

agree

strongly agree

TOC is adequate to represent an abstraction of the reasoning tree

strongly disagree

16 16 disagree

neutral

agree

strongly agree

Abstraction for Collaboration: Contributions  Developed and formalized the process of reasoning tree abstraction for collaboration.  Developed an approach that: • partitions a large concrete reasoning tree into meaningful and manageable subtrees; • uses the partition to generate an abstract tree that plays the role of a table of contents (TOC) for the complex concrete tree; • facilitates the display, browsing, and understanding of the concrete reasoning tree by using the abstract tree (TOC).

Overview Research Problem Abstraction for Collaboration Abstraction for Tutoring Tutoring: Lesson Design and Generation Tutoring: Test Learning and Generation Learning and Tutoring Agent Shell Summary of Contributions and Conclusion

Abstraction for Tutoring Expert Problem Solving Concrete Level

Abstract Strategy 1

P1

Problem Solving Strategy 1

Rd1 P2

Abstract Level AP1 ARd1

P3

AP2

ARd2

Rd2

Problem Solving Strategies 2, 3, 4

AP3

P4

P5

P6

Rd3

Rd4

Rd5

S1

S2

S3

AS1

Abstract Strategy 2

 The reasoning tree is partitioned and abstracted based on the used problem solving strategies.  The abstract tree consists of a hierarchical set of abstract strategies learned from concrete reasoning trees.  The abstract strategies are tutored to the students.

Reasoning Tree and Its Abstraction for Tutoring Assess to what extent the piece of evidence favors the hypothesis.

Concrete Tree (1758 nodes)

Consider the relevance and the believability of the piece of evidence Assess to what extent the piece of evidence favors the hypothesis, assuming that the piece of evidence is believable

Assess the believability of the piece of evidence

Assess to what extent the piece of evidence EVD-Dawn-Mir01-02c favors the hypothesis that Al Qaeda considers deterrence as a reason to obtain nuclear weapons.

Assess to what extent the piece of evidence EVD-Reuters-0101c favors the hypothesis that Al Qaeda desires to obtain nuclear weapons.

Q: What factors determine how a piece of evidence favors a hypothesis? A: Its relevance and believability.

Q: What factors determine how a piece of evidence favors a hypothesis? A: Its relevance and believability.

Assess to what extent the piece of evidence EVD-Dawn-Mir01-02c favors the hypothesis that Al Qaeda considers deterrence as a reason to obtain nuclear weapons, assuming that EVD-Dawn-Mir01-02c is believable.

Assess the believability of EVDDawnMir01-02c

Assess to what extent the piece of evidence EVD-Reuters-01-01c favors the hypothesis that Al Qaeda desires to obtain nuclear weapons, assuming that EVD-Reuters-01-01c is believable.

Assess the believability of EVDReuters-0101c

Abstr act Tree (217 nodes )

22 Abstra ct Reduct ion

Abstraction for Tutoring: Contributions  Formalized the abstraction of reasoning trees for tutoring expert problem solving.  Developed abstract tree generation method.  Formulated a theorem on the existence and uniqueness of the abstract reasoning tree for a given concrete reasoning tree and given abstraction rules.

Overview Research Problem Abstraction for Collaboration Abstraction for Tutoring Tutoring: Lesson Design and Generation Tutoring: Test Learning and Generation Learning and Tutoring Agent Shell Summary of Contributions and Conclusion

   

Tutoring: Lesson Design and Generation Design Operato rs

Designe d Lesson

Abstra ct tree Abstraction-based lesson design through Drag-n-Drop operations The instructor controls how the lesson is to be taught, adds explanations, definitions Automatic generation of lesson’s script Script-based lesson generation adapted to the knowledge base

Lesson Fragment Hypothesis support from a piece of evidence Abstract reduction strategy

Lesson section on Evidence

Automatically generated illustration of the abstract strategy

Lesson Fragment Hypothesis support from a piece of evidence

Abstract synthesis strategy

Automatically generated illustration of the abstract strategy

Evaluation of Generated Lessons Expert analysts

students 12 10 8

students 12

The examples facilitate the understanding of the presented topic

MAAI-06

8 6

4

4

2

2

0 strongly disagree

0 neutral

The examples facilitate the understanding of the presented topic

10

6

disagree

agree

strongly agree

The tutoring system helps me to learn the addressed topic

strongly disagree

students 10

students 8

8

6

6

4

4

2

2

0

strongly disagree

disagree

neutral

Novice analysts

agree

strongly agree

0 strongly

disagree

neutral

CS681-06

agree

strongly agree

The tutoring system helps me to learn the addressed topic

disagree

neutral

agree

strongly agree

Evaluation of Tutoring students 10 9 8

students

Hypothesis assessment through evidence analysis

9 8

Subjective Prior Knowledge students Subjective Post Knowledge 10 Objective Test-Based Evaluation

CS681-06

9

Information content and credibility

8

7

7

6

6

5

5

5

4

4

4

3

3

3

2

2

2

1

1

1

7 6

0

None Very low

Low Medium

0

High Very high

Credibility of the reporter of a piece students of evidence

None Very low Low Medium High Very high

students

0

Credibility of tangible evidence

9

8

8

7

7

7

6

6

6

5

5

5

4

4

4

3

3

3

2

2

2

1

1

1

0 None Very low

Low Medium High

Very high

None Very low Low Medium High Very high

Grades of Generated Tests

9

0

Credibility of reported evidence

students

None Very low

Low

Medium High

Very high

0

50-

60-69

70-79

80-89

90-100

Lesson Design and Generation: Contributions Created an approach to the development of lessons for tutoring expert problem solving knowledge in a complex domain, that can  Rapidly author the lessons that teach • abstract problem solving strategies; • (student-controlled) definitions, detailed descriptions of concepts with examples, and examples of the applications of the abstract strategies.

 Automatically generate the lessons adaptable to the content of the domain knowledge base • teaches only the strategies that can be illustrated in the current knowledge base; • allows changing the knowledge base without changing the lessons.

Overview Research Problem Abstraction for Collaboration Abstraction for Tutoring Tutoring: Lesson Design and Generation Tutoring: Test Learning and Generation Learning and Tutoring Agent Shell Summary of Contributions and Conclusion

Test Generation

 Automatic generation of tests based on the content of the knowledge base and the learned lessons.  There are 3 different types of test: omission, modification and construction tests.

Test Learning

 The agent learns a test rule by generalizing the example (including the explanations and the hint) based on the corresponding reduction rule from the domain knowledge base.  Different knowledge bases result in different tests without instructor’s involvement.

Test Learning and Generation: Contributions Developed methods for:  Learning of different types of test questions by modifying and enhancing examples of reduction rules from the domain knowledge base.  Automatic generation of test questions in the context of a reasoning tree, together with hints and explanations.  Dynamic adaptation of the generated test questions to the lessons taken.

Overview Research Problem Abstraction for Collaboration Abstraction for Tutoring Tutoring: Lesson Design and Generation Tutoring: Test Learning and Generation Learning and Tutoring Agent Shell Summary of Contributions and Conclusion

Problem: Hard to Build ITS for Expert Knowledge Long, difficult and error-prone process (Anderson, 1992)4  Knowledge acquisition bottleneck • domain knowledge (Buchanan and Wilkins, 1993; Feigenbaum 1993)5,6 • pedagogical knowledge (e.g. lessons and exercises) (Murray, 1999)7  Requirement of artificial intelligence programming skills for the instructor (Koedinger et al., 2003)8 4. Anderson, J.R., Intelligent Tutoring and High School Mathematics. in The second International Conference on Intelligent Tutoring System, (Berlin, Germany, 1992), Spring–Verlag.. 5. Buchanan, B. and Wilkins, D. (editors). Readings in Knowledge Acquisition and Learning: Automating the Construction and Improvement of Expert Systems. Morgan Kaufmann, San Mateo, CA., 1993. 6. Feigenbaum, E.A. Tiger in a Cage: The Applications of Knowledge-based Systems. The Fifth Annual Conference on Innovative Applications of Artificial Intelligence. AAAI, 1993. 7. Murray, T. “Authoring Intelligent Tutoring Systems: An Analysis of the State of the Art”, International Journal of Artificial Intelligence in Education, 1999 8. Koedinger, K. R., Aleven, V. A., and Heffernan, N. T. (2003). Toward a Rapid Development Environment for

Learning and Tutoring Agent Shell  A learning and tutoring agent shell facilitates the development of problem solving and tutoring agents.  It extends a learning agent shell with the tutoring related modules (Tecuci, 1998).9  The tutoring agent is built by • defining the abstraction of the reasoning tree used in problem solving, • designing the lessons based on abstraction, • teaching the agent to generate test questions.

9. Tecuci, G. “Building Intelligent Agents”,

Architecture of Learning and Tutoring Agent Shell Ontology Elicitation, LearningandRefinement Ontology Viewers and Editors Ontology Graphical Browsers Scenario Elicitation, Script Editor Ontology Learning and Refining

KnowledgeIntegration, Import, andExport

DiscipleLearningAgentShell

RuleLearningandRefinement Task and Rule Learning Modules

Mixed-initiative, Multi-agent Framework Multi-Agent Framework TaskAgenda Modules

Mixed-Initiative Reasoner

Plausible Explanation Generation Modules

InteractionModel LearningandRefining

ExportTools

Tutoring

Lesson Design

Lesson Generation Module

Lesson Script Engine

Rule Refinement Modules

ProblemSolving Problem Solving Modules

Test Learning

Test Generation Module

Rule Analysis Modules

Abstraction Editor Assumptions Modules

KnowledgeManagement, VerificationandValidation KnowledgeManagementModule

KnowledgeIntegrationTools

ImportTools

Authoring

SystemVerificationModules

KnowledgeBaseValidation Modules

Control Wizards for Rule Refinement

Student Model

Knowledge Management

KnowledgeRepository Management Managementof Distributed KnowledgeRepository

Abstract Knowledge Management

Tutoring Knowledge Management

KnowledgeBaseVersioning

Knowledge Base Management

Learning Agent Shell System knowledge base

Domain knowledge base

Pedagogical knowledge base

Comparison with Related ITS Research  Current approaches to authoring of tutoring systems for expert problem solving knowledge have several limitations: • Knowledge acquisition bottleneck for domain knowledge and pedagogical knowledge, such as Slide Tutor (Crowley, 2003)10 • Requirement of artificial intelligence programming skills for the instructor CTAT – Cognitive Tutors (Koedinger et al., 2003)8 • Systems that are easy to build use limited domain knowledge and do not address complex real-world problems, such as Assistment Builder (Turner, 2005)11 and Simulated Student (Matsuda, 2005).12 • Systems that handle deeper knowledge are hard to build, such as CTAT – Cognitive Tutors (Koedinger et al., 2003)8  This dissertation provides solutions to overcome these problems: • Uses a learning agent shell to facilitate knowledge acquisition. • Uses abstraction-based lesson design and generation, as well as test learning and generation for rapid authoring of ITSs. 10. Crowley, R., Medvedeva, O., “A General Architecture for Intelligent Tutoring of Diagnostic Classification Problem Solving”, AMIA Symposium 2003 11. Turner, T., Macasek, M., Nuzzo-Jones, G., Heffernan, N., Koedinger, K. “The Assistment Builder: A Rapid Development Tool for ITS”, 12th Artificial Intelligence In Education, Amsterdam, 2005. 12. Matsuda, N., Cohen, W., Koedinger, K., “An Intelligent Authoring System with Programming by

Learning and Tutoring Agent Shell : Contributions Developed:  The concept of Learning and Tutoring Agent Shell as a generic software tool for rapid development of learning and tutoring assistants: • Incorporates a Learning Agent Shell to overcome the knowledge acquisition bottleneck (Tecuci, 1998).9 • Provides a methodology for rapid development of an intelligent tutoring system without programming.

 An experimental learning and tutoring agent shell.  An experimental tutoring system for the domain of intelligence analysis.

Overview Research Problem Abstraction for Collaboration Abstraction for Tutoring Tutoring: Lesson Design and Generation Tutoring: Test Learning and Generation Learning and Tutoring Agent Shell Summary of Contributions and Conclusion

Summary of Main Contributions  Approach to abstraction of reasoning that facilitates the display, browsing, and understanding of complex reasoning trees.  Approach to abstraction of reasoning that facilitates the tutoring of expert problem solving knowledge.  Methods for abstraction-based lesson design and generation.  Methods for learning and generation of test questions.  Learning and Tutoring Agent Shell concept, prototype and use case in Intelligence Analysis.

Expected Research Impact  Improvement of the user-agent collaboration in problem solving.  Improvement of the authoring of tutoring systems for expert problem solving knowledge.  Improvement of the process of building complex cognitive assistants capable of problem solving, learning, and tutoring.

Limitations and Future Research  The current methods for defining abstractions need to be further simplified to be used by a subject matter expert without any assistance from a knowledge engineer.  Additional work is needed to improve instructional aspects of the developed ITSs related to: • Student interactions • Student model • Instructional designs  Apply abstraction of reasoning to • Guide the expert to make explicit his/her reasoning process • Learn reasoning rules from the expert

Questions