Syndicate this site (XML)
« Sweep of representation techniques, Part 0 | Main | Struggling »
January 31, 2009
Constraint Satisfaction
Constraint Satisfaction Problems
This topic is hard for me because I think that constraint satisfaction is a more powerful tool than the others I've talked about so far, and therefore more difficult to figure out how to use it.
Basically a CSP (constraint satisfaction problem) is when you want to find values for all your variables such that none of the constraints (rules about how variables relate to each other) are violated.
The variables and their constraints are usually defined by a human programmer. (Although I am fascinated by research into how systems can even figure out these parameters!) Applying the CSP model to my domain is a big challenge for me. Later on in this posting, I will explain how some researchers have done it.
Before that, I just wanted to take a sec to brainstorm: How *could* you apply the CSP model?
- Could the variables be possible next-topics to teach the student? Constraints might be related to instructional planning rules. (CSPs plus Planning is another fascinating intersection. I have some papers on that; I wish it were easier to cite research within a blog entry!) And, how would broken-down teaching strategies manifest themselves? As plans? But how do you take an abstraction of a teaching strategy and an ontology and weave em together?
- How about (the variables represent) what to display on the screen? (Current table of contents of the unit you're working on, perhaps some form of your user model, current lesson, some hints, choices for alternative paths to follow / open exploration, a log of things you've accomplished so far, contact people - other students or teachers, obviously your scratchwork for the current problem or exercise you're working on... etc!!) Constraints might be rules of good HCI... when and where to provide the tools to the learner.
- What if the variables represent learning objects, and the constraints be some pedagogical rules on how to present the objects to the learner?
Hrrm.... Baby's calling. The trend continues for me to require shorter blog postings. I have to fragment my ideas into smaller posts. It hurts!
But I will be back later with more CSP stuff.
February 02, 2009
Kk, I'm back.
Since I've been presenting all the techniques so far as graph problems, I will explain how you can view CSPs as graphs as well.
Given a problem definition, you can create nodes for each variable, and edges for each constraint that involves those variables. This is called a constraint graph.
You could also look at a CSP as a graphing problem, where each node represents a complete assignment of values to all your variables. Edges link together the nodes where there is exactly 1 assignment-difference between them. That is, the 2 connected nodes are identical save for 1 variable having a different value assignment. Thus, the solution to your CSP can be regarded as a graph traversal. I think this might be a kind of "local search" because you start with a complete solution, and are just tweaking at each step to reduce the number of constraint violations.
You could also make each node a *partial* solution to the CSP. For instance, the root would be "no variables assigned values", then each child node at level 1 would have 1 variable assigned a value. Then, the grandchildren each have 2 values assigned, where one of them is the value inherited from the parent.
I'm not very familiar with algorithms to solve CSPs: such as traversals for the graphing-problems. I do know about a couple of heuristics: the order in which you "commit" values to variables is important. If I remember correctly, it's best to choose the variables with the smallest domains first. (Minimum Remaining Values Heuristic) Then, you have to choose which values leave the biggest world of possibilities open. (Least Constraining Variable Heuristic)
I'm interested in finding out what to do if your constraints, variables & domains are unknown.
Whew! That almost hurt! I don't know why it was so hard to "vocalize" all that. Maybe because I was frightened of explaining it incorrectly. I'm such a perfectionist; it hurts to publish something that isn't polished and perfect! But that's not the point of these notes.
Next, I wanted to note how CSPs have been used in AIED.
Hrm, baby's fussing. Will have to do this later!
February 03, 2009
In this paper, authors describe the constraints in their system as tuples: one tuple is like an evaluator that tells you in which cases this constraint is relevant. The other member of the tuple is the actual constraint that has to be satisfied. In this system, I saw the task domain ontology as being "blended in" with the representation of the problems the student is working on; the domain is represented as correct solutions to problems. The system can be very effective in its responses to students because it can detect where the "holes" are in student knowledge with its observations of the competencies demonstrated by students.
Waa, baby's awake. Laters!
Posted by Frozone Permalink on January 31, 2009 08:34 AM
| Comments (0)
categorized under Domain Knowledge Representation (DKR)
Comments
Post a comment
Index to Steph's Notes
Feb. 24th 2007 - Weee! This new part of my website is not an entry, but rather a permanent fixture whose purpose is to "Look Down on All Those Notes With Some Grand Vision of Organization". Wish me luck. LOL- Representing meta-data (fuel) & the different kinds of "hooks" that intelligent systems can use (how fuel is injected into the motor of the engine)
- Motivation: Semantic net / Rationalizable to a machine
- Semantic network
- Genetic graph
- Prerequisite AND/OR graph
- Constraint Satisfaction Problems
- Bayesian networks / causal graphs
- Technology & Philosophy: RDF, modus ponens,
- Predicates, Logic & situation calculus
- What kinds of data? - What kinds of meta-data would an AIEd system possibly need, and how is it represented?
- task domain knowledge
- "is-prerequisite-to"-type knowledge
- interactions with learning objects & other learners - (location, composition is-a/part-of, sequencing by restricting navigation, personalization, ontologies for LO context)
- lesson plans, curriculum plans, practicing sessions (What is stored, what is generated on the fly? What is remembered?)
- How to organize it - When is it stored in a database? Meta-data? Agent memory banks? Protocols? Repositories? XML files? Home-servers? WSDL services? Frameworks? Portable banks? P2P access?
- Database of object-agent interactions
- Concept of "Home" on a P2P network -- maybe the bulk of a learning object's usage data is on its home server and can be queried using WSDL or something ? Similar homes for each student's usage history, etc. Baggage problem.
- Links to the ontologies
- referring to a concept/relationship - ex. AgentOwl?
- Generation of this data
- Rationalization: For use by other AIEd systems
- What is generated - discuss items under part I.C.
- When it's generated - describe procedural model, which parts of the engine generate what (isa-part-of data, XML feeds, web services, meta data bout groups and collaboration, protocols, examples Friend of A Friend FOAF project)
- Technical notes of HOW it's generated: JENA, issues of implementation demo, my Hermione & Ron agent examples, lol
- Usage of this generated data - see part IV. A.
- Given the engine, who uses it?
- Students / Learners / "Me"
- instructional planning, student model, pre-requisites, tutoring, coaching, collaboration,constructivism
- Teachers / Educators / "Me"
- putting together lessons
- be able to browse through task domain knowledge in an objective / encyclopaedia format, then be able to pick-and-choose what you need for your students
- compose examples, design explanations, pull together diagrams, learning objects, etc. Haystack Relo?
- Administration / Governement / Structure / Crowd Control
- as restrictions/obstacles/sand pit to the robot in agent environment
- can't just have a swarm of students and teachers out there -- need structure of courses, curriculum, objectives, requirements (at least, we do in this day and age!) - Report cards, evaluation, feedback
- government, marks, certificates, requirements, funding, curriclum, attendance, delinquent, non-attending, motivation
- school''s images, goals, strengths, payroll, HR, security, accounts, permissions, privacy
- registration, failed courses
- User Environment -- How does this engine work? What does the user see on the screen?
- Introduction - Given a background in educational psychology, how does the system present itself -- what does the user see, and were does this data come from? Links to thoughts from part I.)
- Task Domain Browsing - Suppose you're you're just idly browsing through the "raw" content. How would it look when it's not wrapped around a learning-context or lesson or tutorial or anything. 'Cross between browsing a raw task domain ontology and browsing a learning object repository.
- Cleaning up the data -- Visualizing the data for humans to pick through the task domain and work on it. Suppose the "Subject Expert" discovers an advancement in science and needs to update the "world's" domain knowledge. (I used the "Subject Expert" terminology from Ontologies to Support Learning Design Context - Thanks Chris) How would they make corrections to ontologies and learning objects, or at least point the users of "old" objects towards adopting the newer ones.
- "Modes" - Learning & Lessons / Checklist - Homework, Assignments, Courses being taken / Collaborative mode / Teaching mode / Calendar- email -adminisrative mode -- See also the different kinds of scenarios in the ActiveMath system
- Evolution of this engine
- target some key implementation hooks discussed in part I - design an experiment/demo
- scrape a page - (Note, scraping can only give objective data, not in-context dat)
- LO repository - related to browsing the task domain?
- a learners "To Do" list - where does it come from? Assignments, courses.
- sample group scenario
- sample teacher lesson planning
- sample data "left behind"
- sample use of that data
- Data mining (for what? lol )
- discovery / generation of ontologies - when do you need to hunt for them, and when do you have to have a solidly-known & predictable ontology?
- I/O - where it happens, which languages, protocols, which agents perform i/o and when, precepts, actuators
- Role Assignments
- My Environment Adapts to me
- Displaying feedback from the server on JSP pages (Software engineering considerations)
- Sketching out a design (Content planning vs. Delivery planning)
- agent negotiations / social structures / ummm... Web 2.0 ?
- garbage collection of meta data
- Artificial Intelligence & Evolution
- Memory Culling: Necessary part of intelligence? (artificial or human)
- Applications for the Genetic/Evolutionary algorithm
- open learning environments
- Agents, pets, grouping, Community modelling
- Protocols - finding groups, cyber dollars, state diagrams (?)
- "Community Studies" - graphs & communication hubs, types of communities (free-for-all, hierarchy of authority, etc.)
- implications of joining a community - what do you share, which parts of your student model are relevant
- Walls & sand traps -- deliberate restrictions as problem-solving for learning
- Communication channels - individual-to-individual, individual-to-community, chat channels, agent-only "administrative" communications, ex. requests for related learning objects in a particular community, etc.
- Educational/Pedagogical focus (this part probably shouldn't be its own section but rather incorporated into the whole picture, but it's separate for me right now because I'm still only just starting to learn about it.)
- Semantics - what there is to talk about in Education
- ex. Merril's First Principles of Instruction, linking educational terms to AI terms
- Pedagogical skills for tutors -- supporting human *and* artifical tutors
- Student modelling - what the machine needs to know about the student, pedagogically-speaking, about learning history/preferences
- Roles - Simulated students, Coaches, Tutors, Teachers,
