Syndicate this site (XML)
« test... LaTeX | Main | Conditional probabilities, and "the argmax thinggy" »
April 25, 2009
Some wobbly steps forward... the math
I feel so liberated! I stumbled upon a tool that lets me easily convert LaTeX to something I can paste into my blog. Yes, I'm relying on 3rd-party tools, but, I don't even care. What I like is EASY. Not long ago, I would have bent over backwards, doing things the hard way, just so I could have done it "properly" so that I wouldn't be reliant on external resources, using only server space that I'm paying for (and therefore have some guarantee of its reliability), etc. However nowdays I save such effort only for the most important stuff. These days, I value shortcuts very much. So I'm gonna try this out.
So what else can I tell you about decision theory?
I can tell you that calculations will often include an expected value. I'm still trying to work out the big picture in my head, but, usually, the expected value of an action is equal to the sum of the probabilities of all possible outcomes, multiplied by the value of each action. Does that make sense?
You start with a simple probability distribution. I like to think in graphs and pictures. I've seen a lot of discrete probability distributions, so I will conjure up a discrete example (as opposed to a continuous example) here.
Suppose I am a magical fairy, and I wave my magic wand. Here is a probability distribution showing the possible outcomes of my wand-waving. As you can see, it is most likely that a tree will grow. It is slightly less likely that a rainbow will appear in the sky. Or, the smallest chance is that I will have stars twinkling on my fingertips as a result of my action.
Fig 1: A probability distribution for a planning problem
So the whole graph represents the results of an action taken. The other day, I was talking about the utility function. This is where you attribute some value to each possible outcome. So, suppose I am really hungry: the event that a rainbow appears in the sky won't help me, nor will stars twinkling on my fingertips. However, the tree might be an apple tree or something. So, I will place a high value on the event of the tree growing, and low values on the rest of the event. (If one of the events was "a hungry monster appears", I might assign this a negative value - a "cost" - because the hungry monster could eat some of my food, and that would be very bad!)
I don't know much about designing utility functions. So I am just going to wing it here. I'll just whip up a piecewise function like so, I hope it is not too ugly.
Latex:
r(x)=\begin{cases}
x = \text{A rainbow appears} & y=1\\
x = \text{A tree grows} & y=5\\
x= \text{Sparkles appear on your fingertips} &y=1\end{cases}
I probably didn't do that right. I was thinking that r(x) is my utility function ("r" stands for "reward"). The argument, x, specifies the event or action that was chosen where and of course the big X is defined in the probability distribution above.
I'll have to design a couple more of these and maybe send email to one of my mentors for help on the specifics!!
Anyway. So far, we have
- the probability distribution showing all possible actions and their likelihoods
- the utility function showing how much I "like" each of the possible outcomes above
Finally, here's the part where I wanted to try out my LaTeX skills. The expected utility of an action, E(x) is calculated simply by multiplying the utility by the likelihood of the outcome of that action. In other words, you multiply the probability of "a rainbow appears", which is 0.3 by its utility, which is y=1. Then you multiply similarly for the other two events. Finally, you sum all these numbers together.
So, E(x) =
Which expands to E(x) =
Latex: P(\text{x=A rainbow appears})r(x) +P(x=\text{A tree grows})r(x) + P(x=\text{Sparkles appear on your fingertips})r(x)
Hmm... I'm uncomfortable with my notation for r(x) here... and also for E(x) it doesn't taste right... but I can't put my finger on the problem. But anyway... moving on...
E(x) =
Latex:P(\text{x=A rainbow appears})(1) +P(x=\text{A tree grows})(5) + P(x=\text{Sparkles appear on your fingertips})(1)
Finally, E(x) =
E(x) =
E(x) = 3.
Why did we sum all the numbers together? Well, if you want to know the overall expected cost for the entire situation, you note that the probability of any of these evens occurring is 1. When you factor in the rewards, you get a number (in this example, we got "3") that can be compared to another situation, say, if you were using a different utility function or if you had a different set of events to deal with.
I think. Gosh, I'm not even sure anymore. I need to think about this! I still have questions about the "state", too: Do actions result in states? Yes, obviously, but where would these fit in for my example?
Well that was fun, but clearly I have more work to do! I hope to come back with another example after I've done a little more reading. Eep! And I haven't gotten as far as employing a Markov Decision Process, or even applying a policy, or playing with observations or states. And the layout of my math looks ugly on this blog, LOL. And the LaTeX isn't rendering in my RSS reader.
But overall this wasn't bad for my first time.
Posted by Frozone Permalink on April 25, 2009 08:34 AM
| Comments (2)
categorized under Computer Science & AI
Comments
Hey Steph,
For what it's worth, the Latex seems to be rendering fine in google reader. Also, I really enjoy your writing. I don't generally enjoy reading about statistics, but I got to the end of this post!
Anyway, about the Latex tools thing. My approach comes from the Pragmatic Programmers(http://www.pragprog.com/). They say "Don't Use Wizard Code you Don't Understand". I generalize this to: "Don't use tools you don't understand". So, usually the advice I give is that it's ok to use any tool so long as you understand what it's doing for you.
But, your understanding doesn't have to be complete.
For example: I think it's ok for me to use the java compiler because I know it takes my java source and converts it into java bytecode. In turn, it's ok for me to use a JVM because I know that it interprets java byte code as executable statements.
The point is, that I know enough that if the java compiler or JVM failed me for whatever reason, I would be able to dig up some manual and figure out what was going wrong.
It looks like you can say some very similar things about your Latex/blog tool, so (in my opinion) it's ok for you to use it as a shortcut.
Sorry if that was a tad long winded, but I thought you might just enjoy the comment.
Posted by: Kevin Baribeau at April 27, 2009 12:50 PM
Thanks Kevin -- positive feedback is so valuable! As a blogger yourself, you'll understand that it means the difference, over time, of your posts turning into "rambling thoughts to myself" vs. "good writing that other people will be interested in reading". Or at least that's the way it is from my perspective. :D
Thanks for sharing your approach. I think it's becoming more and more important to use third party tools, and it's nice to be able to fall back on some kinda philosophy as a guideline for when to/not to use them!
Posted by: Steph (a.k.a. Frozone) at April 27, 2009 05:44 PM
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,
