9:15 - Dr. Josh McCoy, joshua.allen.mccoy@gmail.com, Center for Games and Playable Media
10:00 - Dr. David Cope, howell@ucsc.edu, Workshop in Algorithmic Music Composition
10:45 - Dr. Marilyn Walker, mawalker@ucsc.edu, Natural Language and Dialogue Systems Lab
Question of the Day: A Nigerian Prince invites you to a potluck at his house. Wanting to know how many people you’ll need to cook for, you ask about how many people will be there. Rather than give a straight answer, The Prince tells you that the number of attendees will be such the smallest number such that he is guaranteed that among the guests, either:
At least three of the guests will be mutual friends, or
At least three of the guests will be mutual strangers (none of the three knows either of the other two)
How many guests will there be?
Problem Set (1/3)
Algorithms
Big O
Induction/Recurrence
Machine Learning
Supervised Learning - Conceptual Learning
Unsupervised Learning - Unlabeled Data
Reinforcement Learning - Multi-armed bandit
Information Classification
http://scikit-learn.org/stable/auto_examples/cluster/plot_lena_ward_segmentation.html
Review Abductive, Inductive, Deductive
Event Calculus
initiated(F,T) :-
happens(E,T),
initiates(E,F,T).
terminated(F,T) :-
happens(E,T),
terminates(E,F,T).
holds(F,T+1) :-
holds(F,T),
not terminated(F,T).
-holds(F,T+1) :-
-holds(F,T),
not initiated(F,T).
holds(F,T+1) :-
initiated(F,T).
-holds(F,T+1) :-
terminated(F,T).
holds(F,0) :- initially(F).
-holds(F,0) :- not initially(F).
http://en.wikipedia.org/wiki/Answer_set_programming
In ASP, search problems are reduced to computing stable models, and answer set solvers — programs for generating stable models—are used to perform search. The computational process employed in the design of many answer set solvers is an enhancement of the DPLL algorithm and, in principle, it always terminates (unlike Prolog query evaluation, which may lead to an infinite loop).
Planning
STRIPS
http://en.wikipedia.org/wiki/STRIPS
There is a single causal agent and this agent is the planner;
Representing and reasoning about several causal sources; entities that can affect change in the world, greatly complicates planning; and perhaps necessitates that planning take a different form. Research began with this simpler and more tractable situation where only the planner can affect the world. Thus, the planner has complete control over the changes that occur.
The planner is given a well-defined goal which remains fixed over the course of planning;
The expressions that describe the goal are crucially involved in the planning process. If these are ill-defined the planning is impossible. And, since the choice of actions is dictated by the goal, if the goal changes then all of these decisions must be revisited and potentially revised.
The planner is assumed to have functionally complete and accurate knowledge of the starting situation;
Note the term 'functionally complete.' The planner needs to know everything necessary to create a plan that will be successful. This may include very little knowledge of the starting situation or a great deal. Deciding what needs to be known is part of what can make planning difficult. And, if the functionally important knowledge is not accurate, then the planner can't be sure that the plan created will be successful.
The planner is assumed to possess the knowledge required to accurately model the world;
Without this requirement there is no guarantee that the plan created will be successful.
The planner is assumed to possess the resources (time and memory) required to use this model to reason about the possible worlds associated with the different courses of action that might be pursued.
Planning is, in general, an intractable problem. And, if the world is complex then modeling the world may also be intractable. This assumption is simply a warning to restrict the research to tractable planning domains.
http://www-rci.rutgers.edu/~cfs/472_html/Planning/Intro_Planning_472.html
http://www.inf.ed.ac.uk/teaching/courses/ai2/module4/tutorials/tut4.pdf
HTN
In artificial intelligence, the hierarchical task network, or HTN, is an approach to automated planning in which the dependency among actions can be given in the form of networks.
Planning problems are specified in the hierarchical task network approach by providing a set of tasks, which can be:
primitive tasks, which roughly correspond to the actions of STRIPS;
compound tasks, which can be seen as composed of a set of simpler tasks;
goal tasks, which roughly corresponds to the goals of STRIPS, but are more general.
Models of Motivation