Georgia Tech Fall 2019
David Joyner, Ph.D. Professor
Ashok Goel, Ph.D. Professor
Course Website: http://lucylabs.gatech.edu/kbai/fall-2019/
Youtube Lectures : https://www.youtube.com/watch?v=onRUvL2SBG8&list=PLAwxTw4SYaPkdANSntXhY0btWkpPglDGD&index=1
Software Python: www.python.org/
Udacity
https://auth.udacity.com/sign-in
Note that you must sign in with Organization then choose Georgia Tech
Transcript
Homework must be complete using Joyner Document Format (aka JDF) https://drive.google.com/drive/folders/1xDYIomn9e9FxbIeFcsclSbXHTtHROD1j
Complete your assignment using JDF, then save your submission as a PDF. Assignments should be submitted to the corresponding assignment submission page in Canvas. You should submit a single PDF for this assignment. This PDF will be ported over to Peer Feedback for peer review by your classmates. If your assignment involves things (like videos, working prototypes, etc.) that cannot be provided in PDF, you should provide them separately (through OneDrive, Google Drive, Dropbox, etc.) and submit a PDF that links to or otherwise describes how to access that material.
This is an individual assignment. All work you submit should be your own. Make sure to cite any sources you reference, and use quotes and in-line citations to mark any direct quotes.
Late work is not accepted without advanced agreement except in cases of medical or family emergencies. In the case of such an emergency, please contact the Dean of Students.
There are 26 Lessons (aim to watch 2 per week)
Fundamental Conundrums
Characteristics of AI Problems
What are AI Problems?
Anything a human does can be an AI problem
Consider Jeopardy contestant as an AI Agent?
They must listen, understand, search their data (find answer), frame response as a question.
Three Fundamental Processes/Forms: Learning - Reasoning - Memory
We learn to reason, our learning is stored in Memory
AI seeks to unify these three processes under the heading DELIBERATION
Four Schools/quadrants of AI: Thinking, Human Like, optimally, acting
Extra Reading: https://people.eecs.berkeley.edu/~russell/aima1e/chapter01.pdf
Consider
In this course we define:
Architecture:
Our courses is broken into the following areas
In this lesson, we'll talk specifically about what you should expect from CS7637.
Learning goals
Learning Outcomes
Learning methodology
Introduction to Computational Psychometrics
Raven's Progressive Matrices
Went through a few examples of the Raven Matrices
Principles of CS7637
Be on the lookout for the seven principals, they'll occur again and again throughout the course.
These principles will come again and again in this particular class. So we highly recommend that you take a moment, pause the video and read over the principles once again.
Is a type of knowledge representation
Each knowledge representation has a language/vocabulary (aka lexicon), and content. Content can be the representation of a relationship. For example equality in an equation, or Position (over, under, etc)
A semantic network first seeks to represent knowledge by identifying objects (Labelling) and their relationships. Ex: circle inside square. Then it seeks to describe a transformation between states. Consider 2 image A & B, from the Maven's progressive matrices. Each image will contain some shapes. Our task is to define the transformation of the image from A to B using a well defined vocabulary of relationships. This constructs the semantic network.
A: Square inside circle; Triangle above Circle
B: Circle inside square;
Transform: Circle expanded, Triangle deleted
Good representation characteristics
Example: Guards & Prisoners
Three guards and three prisoners are on one side of a river and must cross using a boat. Boat can only transport 1-2 people at a time. Prisoners may never outnumber guards on either side, but they can be alone.
Textbook: page 33
The first of many problem solving methods
Given a problem, generate potential solutions, then test each solution for efficiency. In a perfect world with perfect and complete knowledge, infinite computational resources, and perfect reasoning methods you could come up with the perfect solution each time. But the world is not like this so you must generate several plausible answers and test each one.
Recall: Guards and Prisoners problem. Previously we discussed simply the representation. We ignored the algorithm of how an AI agent would solve the problem.
Frames -> Understanding -> common sense reasoning -> scripts
Functions, Properties, Relationship to previous topics
Ashok ate a frog: What is common sense reasoning. Is the frog dead or alive?, where was it?, did it make him happy?
Deconstruction of the sentence into a frame Ate: The verb but you could use the subject/noun (On the left we have Slots, on the right is the filler) Subject: Ashok Object: frog Location: time: utensil: Object-alive: false Object-is: in stomach Subject-mood: happy
A frame is a knowledge structure. Like a molecule they have a structure Frames can also point to frames. In the above example we could construct a frame for Ashok. Then the filler would point into the Ashok frame. This can lead to more and more complex frames.
Frame Properties: Represent stereotypes, Provide default values(in-stomach), Exhibit inheritance (The idea of frames comes from OO - programming)
A semantic network as a frame:
Object
Name x
shape Triangle
size Large
Fill false
inside
Above
Object
Name y
shape circle
size medium
Fill false
inside pointer to x
Above
Object
Name z
shape circle
size small
Fill true
inside
Above pointer to y
Is the first step in analogical reasoning which is at the core process of cognition. Sometimes it is simply the best guess best on previous learnings.
Suppose your given a square (ie a new problem). Your first instinct would be to compare it to what's in your memory. You would retrieve the most similar problem from memory. Then you'd apply the solution to the problem from memory to the new problem.
What is "most similar"? One method might be using frames. However if you used distances you would be on the verge of a nearest neighbour approach: which is using the Euclidean distance between points. In the real world however things are much more difficult
Suppose you were looking at a map of a city, and you have shiny new automated car. Unfortunately though your car only comes with a few preset navigation paths. Where you need to go represents a new problem. What do you do?
One method would be to map each preset route onto a 2D grid, and each preset destination onto a 2D grid. On each of these grids you would also place your start and end. Then minimizing the sum of error should yield the best result.
This leads to the Knn method
$$d = \sqrt{\sum_{i=1}^{k} (c_i - p_i)^2 } $$Summary
This lesson cover the following topics:
Memory is as important as Learning/Reasoning so that we can fetch the answer to similar cases encountered in the past and avoid having to redo the non-trivial task of learning and reasoning, thereby saving effort.
A case is an encapsulation of a past experience that can be applied to a large number of similar situations in future. The similarity metric can be as simple as the Euclidean distance metric or a complex metric involving higher dimensions.
kNN method is one method to find the most similar case from memory for a new problem
In some cases, we need to adapt the cases from our memory to fit the requirements of the new problem. In some cases, we also need to store cases based on qualitative labels along with numeric labels to make the comparison applicable for particular situations.
Learning by storing cases in memory has a very strong connection to Cognition since human cognition works in a similar manner by recording cases and applying them to new problems in real world by exploting the patterns of regularity in them.
In case based reasoning an AI agent solves new problems by analogy to previously encountered problems. It builds on recording cases. Here it is similar but needs not be the same.
Similar to the previous unknown block problem. What if we encounter a new problem? It may be similar to pother blocks and it may not.
Let's revisit the map and the automation car with a limited preset memory.
Our new problem is not in the preset solutions
Notice how we've unified storage and learning!
Assumptions:
Adaptation: does not need to be exact. It simply needs to be close enough to be sufficient. This saves a good deal of resources. So in our map problem we can take a preset route ... and by adding a bit we adapt it to get to our desired destination.
Adaptation by recursion: Suppose we want to get from our home to a restaurant. If we had a preset route from home to work and from work to the restaurant. Then the two cases can be put together to formulate a final solution.
Adaptations by Rules: Rules are a type of heuristic, a rule of thumb. So now that we know how to get from home to restaurant, we can flip to get from restaurant to home.
Case evaluation: What if our heuristic solution fails? We may have used one way roads?
Case storage: It's only by accumulating and storing data that we can build upon our learning
By Indexing: Could be as simple as the co-ordinates of start and end points. these are basically just tags to identify cases and make searching easy, efficient, and effective.
Using Discrimination Tree: Are basically decision trees. A series of nodes (decisions) that need to be made. All together they represent the learning process. They can be binary (yes-no) or more complex.
Purpose: Build upon case based learning by focusing on the abstraction of concept from the case based examples. Variabilization, Specialization, and Generalization are how we abstract the concept.
Suppose you have a definition and some problem. You would try to infer from the definition whether the problem fits it. If a bacon lettuce tomato between sliced bread is a sandwich then is a hot dog a sandwich? How we answer depends greatly on the variables/parameters we feel are necessary to the sandwich solution as well as how far the problem is in comparison. Would BLT in between concrete bricks be a sandwich? Also note that 2 different people may deduce different cases from the BLT sandwich, ie their background knowledge is different.
In general AI agents as well as people learn on a case by case basis. This is generally performed in a supervised manner where both pos & neg re-enforcements are provided.
In a nutshell
For each case an AI agent will either generalize or specialize. Positive case not encountered previously will improve our generalization, whereas neg examples will lead to a specialization to exclude such cases.
In each iterative case what is learned must be incorporated into the learned case. Incorporating background knowledge into the definition involves a climb tree heuristic. In our previous BLT example this could be say edibleness? or it could be bread. A blt on rye, ciabatta, or bun. Any form of bread would still consititute a sandwich.
Heuristics for Concept Learning
How do we specialise and generalize? We look for the following heurisitcs
Overview: Learning Concepts; Equivalence classes; Concept hierarchies; types of concepts; Bottom-up search
Definition: Mapping sets of precepts in the world into equality classes, for the purpose of actions.
Imagine that we have a set of precepts (a general rule intended to regulate behavior or thought): Has wings? Has feathers etc. We assume for simplicity that they have a binary result. Depending on the precept and their combinations there may be many actions possible.
If the number of actions is $2^m$ and the number of precept combinations is $2^n$. then just 10 precepts(n) leads to 1024 combinations. This number can get very large very quickly and a computer would run out of resources.
Suppose we wanted to create a classification of BIRD.
Recall: Frames -> Understanding -> Commonsense Reasoning -> Scripts
Understanding
Consider: Ashok made pancakes for David with a griddle
Frame:
Verb: make
Agent: Ashok
Beneficiary: David
Thematic Object: pancakes
Instrument: Griddle
Notice that in building the frame we used a top down approach. Beginning with the verb, then moving to both the agent of the verb and the beneficiary of the verb, then the outcome of the verb, and finally the tool of the verb
How do we resolve ambiguous words in a sentence: An idea hit me vs A ball hit me use hit in vastly different ways.
Thematic Role frame Categories: Verb, Agent, CoAgent, Destination, conveyance.
Are generally derived from Prepositions with Semantic Roles
| Preposition | Thematic Role |
| By | Agent, Conveyance, location |
| For | beneficiary, duration |
| From | source |
| To | destination |
| With | co-agent, instrument |
In AI Ontology is a conceptualization of the world. Example
Things
-> Agents
-> People
-> Ashok
-> David
-> Objects
-> Conveyances
-> Car
-> Train
-> Locations
-> Park
-> Statue
Resolving in ambiguity in words: It's hard to explain things to kleptomaniacs as they always take things literally
In this case each meaning might have it's own frame like representation
Context can be used to distinguish between different understandings. But also different sentences can have the same meaning. Equivalence can be described as the specification of a primitive action. So for example Ahok ate a frog, Ashok consumed a frog, Ashok ingested a frog all mean the same thing. The verb is different in each but the underlying idea is the same. This underlying idea is the Primitive Action.
Consider the following list (Ontology) of Primitve Actions: Move-Body-Part, Expel, Propel, See, Smell, Move-Possession, Think-about, Move-Object, Ingest, Speak, Hear, Feel, Move-Concept, Conclude
These may not be complete, they're intent is to illustrate. So for Ashok we may use "ingested" in both sentences.
When building a frame the primitive is the verb enacted by the agent, subject.
If the primitive is missing then it must be implied. Ex: John fertilized the field => John put fertilizer on the field.
Ashok put the wedge on the block:
Scripts are the culmination of Frames and common sense reasoning.
Common Sense: Frames -> Understanding -> Reasoning -> Scripts
Consider the sentence: Ashok wanted to become rich, he got a gun.
Some may say this makes sense? Maybe Ashok robbed a bank or held someone up. In either case background inference was used to imply a context which the sentence didn't give.
Stories help you make sense of the world.
Imagine you went to a coffee house. You know exactly what to do. It doesn't matter which coffee house you walk into, your actions will be the same. You'll get in line, you'll give your order, you'll pay for it, you'll wait for the order to be completed. You're basically following a script.
A causally coherent set of events
Causally: Each event sets off, or causes, another
Coherent: The causal connections between events make sense
Events: The parts are actions or scenes in the world
Parts of a script
Scripts are often represented using a frame and should capture the knowledge representations. These frames should define the various action frames. Several of the action frames can be considered a scene when they form a sequence of action frames.
To learn a script an agent uses
To using a script an agent might use
Here the agent learns about connecting concepts. Concept Space, Abstraction, Analogical Transfer.
Imagine you needed to transport soup. You have the options: Backpack, Pitcher, Box, Car. Which would you use? A human knows that a pitcher would be best but how would an agent make that connection?
What sort of prior knowledge should an AI Agent have to make the connection that the pitcher is the best utensil for the task of transporting soup? An AI Agent needs some understanding of causal relationships. So for example it might know that a pitcher carries water.
Object enables Drinking
because
Object carries liquids because it is concave
Object is liftable because it is light
All together these define the characterisitcs of the concept cup.
Imagine your given the following info:
Asked: This object is light and made of clay. It has concavity and a handle. The bottom is flat, and the sides are thick
Is this object a mug?
Given the Mug description: There are 3 conditions: Stability, Drinking, and the protection against
Similarly the pot description gives the conditions: Concavity, limits heat transfer, thick sides, made of clay.
Understanding new problems in terms of familiar problems. Addressing new problems by transfering knowledge from previous problems. Similarity via relationships, and/or objects. Recall the K-nearest neighbour example of the driving agent.
Consider: There's a patient with a tumour, and a doc with a laser gun. The laser gun will kill the tumour, but will also kill all cells around the tumour. What should the doctor do?
Consider the idea of similarity as a spectrum. On the one end the target case and the source case are highly similar, on the other end there is a large difference between the two. You can think of this as a matrix like illustration.
| More Similar | ||||
| Relations | Objects | Features | Values | |
| Similar | Similar | Similar | Similar | |
| Similar | Similar | Similar | dissimilar | |
| Similar | Similar | dissimilar | dissimilar | |
| Similar | dissimilar | dissimilar | dissimilar | |
| Less similar |
Transferring Knowledge from familiar problems requires:
Recall that case based reasoning is very similar, instead of Mapping & transfer it used adaptation. Another large difference between analogical reasoning and case based is the domain. In analogical reasoning they do not have to be the same. Analogical differences focus on the objects, relationships, features and value similarities.
Superficial Similarity: Features, counts, objects (Unary Relationships)
Deep Similarity: Relationships between objects, Relationships between relationships (tertiary Relationships)
Types of Similarity (measures)