Project Overview (Fall 2020)

The class project in CS7637: Knowledge-Based AI involves constructing an AI agent to address a human intelligence test.  The overall process is the same across all three projects; what differs is the complexity of the problems (and their representations) that your agent will address. So, this document is long, but it is effectively the directions for all three projects of this semester.

In a (Large) Nutshell

The CS7637 class project is to create an AI agent that can pass a human intelligence test. You’ll download a code package that contains the boilerplate necessary to run an agent you design against a set of problems inspired by the Raven’s Progressive Matrices test of intelligence. Within it, you’ll implement the Agent.py file to take in a problem and return an answer.

There are four sets of problems for your agent to answer: B, C, D, and E. Each set contains four types of problems: Basic, Test, Challenge, and Raven’s. You’ll be able to see the Basic and Challenge problems while designing your agent, and your grade will be based on your agent’s answers to the Basic and Test problems. Each project will add a problem set or two: on Project 1, your agent will answer set B; on Project 2, your agent will answer sets B and C; and on Project 3, your agent will answer sets B, C, D, and E. Thus, Projects 1 and 2 build toward Project 3, the ultimate deliverable. Your grade will be based on three components: how well your agent performs on the problems, how your agent is implemented and revised, and a project reflection you turn in along with your agent.

Different problems will also give your agent different amounts of information. Certain problems in problem sets B and C (specifically, the Basic and Test problems) will provide “verbal” representations. Verbal representations are structured representations that verbally describe what’s inside  a figure in a problem. For example, in the problem below, a verbal representation would describe figure B as “a large, unfilled circle inside a very large, unfilled square”, and figure C as “a small, unfilled, rotated square inside a very large, unfilled square”, using a more structure representation. Your agent would take those descriptions and produce an answer from the eight choices. In all the other problem sets, however, your agent will only be given the images themselves — what we call a “visual” representation — in .png format. It will have to take in the image of the figures themselves and do its reasoning based on those.

Every problem set provides visual representations, so you can try approaching these problems using visual representations (instead of or in addition to using verbal representations) as early as you want. Project 3’s problem sets (D and E) only provide visual representations, so you’ll have to try a visual approach eventually. However, verbal approaches tend to be somewhat easier because a human has already interpreted the figure, so you may find it best to rely mostly on the verbal representations for the first two projects. Note that all the optional problems (the Challenge and Raven’s problems) only provide visual representations, so if you want to try those problems during Projects 1 and 2, you’ll want to try a visual approach then. Your agent will run against every problem on Project 3, though, so you’ll never miss out on the chance to give those a try.

Don’t worry if the above doesn’t make sense quite yet — the projects are a bit complex when you’re getting started. The goal of this section is just to provide you with a high-level view so that the rest of this document makes a bit more sense.

Background and Goals

This section covers the learning goals and background information necessary to understand the projects.

Learning Goals

One goal of Knowledge-Based Artificial Intelligence is to create human-like, human-level intelligence. If this is the goal of the field, then what better way to evaluate intelligence of an agent than by having it take the same intelligence tests that humans take?

There are numerous tests of human intelligence, but one of the most reliable and commonly-used is Raven’s Progressive Matrices. Raven’s Progressive Matrices, or RPM, are visual analogy problems where the test-taker is given a matrix of figures and asked to select the figure that completes the matrix. An example of a 2x2 problem was shown above; an example of a 3x3 problem is shown below.

In these projects, you will design agents that will address RPM-inspired problems such as the ones above. The goal of this project is to authentically experience the overall goals of knowledge-based AI: to design an agent with human-like, human-level intelligence; to test that agent against a set of authentic problems; and to use that agent’s performance to reflect on what we believe about human cognition. As such, you might not use every topic covered in KBAI on the projects; the topics covered give a bottom-up view of the topics and principles KBAI, while the project gives a top-down view of the goals and concepts of KBAI.

About the Test

The full Raven’s Progressive Matrices test consists of 60 visual analogy problems divided into five sets: A, B, C, D, and E. Set A is comprised of 12 simple pattern-matching problems which we won’t cover in these projects. Set B is comprised of 12 2x2 matrix problems, such as the first image shown above. Sets C, D, and E are each comprised of 12 3x3 matrix problems, such as the second image shown above. Problems are named with their set followed by their number, such as problem B-05 or C-11. The sets are of roughly ascending difficulty.

For copyright reasons, we cannot provide the real Raven’s Progressive Matrices test to everyone. Instead, we’ll be giving you sets of problems — which we call “Basic” problems — inspired by the real RPM to use to develop your agent. Your agent will be evaluated based on how well it performs on these “Basic” problems, as well as a parallel set of “Test” problems that you will not see while designing your agent. These Test problems are directly analogous to the Basic problems; running against the two sets provides a check for generality and overfitting. Your agents will also run against the real RPM as well as a set of Challenge problems, but neither of these will be factored into your grade.

Overall, by Project 3, your agent will answer 192 problems. More on the specific problems that your agent will complete are in the sections that follow.

Verbal vs. Visual

Historically in the community, there have been two broad categories of approaches to RPM: verbal and visual. Verbal approaches attempt to solve RPM based on verbal representations of the problems. In these representations, a human initially describes the contents of the figures of a problem using a formal vocabulary, and an AI agent then reasons over those representations. Visual approaches, on the other hand, attempt to solve RPM based strictly on the images themselves: they take as input the raw image data and perform their analysis from there. Examples of verbal approaches include Carpenter, Just & Shell 1990 and Lovett, Forbus & Usher 2009. Examples of visual approaches include Kunda, McGreggor & Goel 2013 and McGreggor & Goel 2014.

Much research has been done examining the differences between these approaches in humans (e.g. Brouwers, Vijver & Hemert 2009). Within artificial intelligence, visual approaches are generally more robust in that an initial phase of human reasoning is not necessary. Thus, the ultimate goal for these projects will be to solve RPM-inspired problems visually. However, visual problem-solving tends to be significantly more difficult. Thus, you will start by having the option to use both verbal and visual approaches (using verbal representations we have produced for you), and by the last project you will use only visual methods.

Details & Deliverables

This section covers the more specific details of the projects: what you will deliver, what problems your agents will solve, and what representations will be given to you.

Project Progression

In this offering of CS7637, you will complete three projects:

  • Project 1: Problem set B
  • Project 2: Problem set C
  • Project 3: Problem sets D and E

Each problem set consists of 48 problems: 12 Basic, 12 Test, 12 Raven’s, and 12 Challenge. Only Basic and Test problems will be used in determining your grade. The Raven’s problems are run for authenticity and analysis, but are not used in calculating your grade.

On each project, you will have access to the Basic and Challenge problems while designing and testing your agent; you will not have access to the Test or Raven’s problems while designing and testing your agent. Challenge and Raven’s problems are not part of your grade, though note that the Challenge problems will often be used to expose your agent to extra properties and shapes seen on the real Raven’s problems that are not covered in the Basic and Test problems.

As mentioned previously, the problems themselves ascend in difficulty from set to set. Additionally, only visual representations will be given for problem sets D and E, so for project 3 you’ll be required to do some visual reasoning.

For each project, your code must be submitted to the autograder by the deadline. However, it is okay if your project is still running after the deadline. You are only permitted 12 submissions per project.

On each project, you will also complete a project reflection describing your process of constructing your agent, your agent’s performance and limitations, and your agent’s connection to human cognition.

Grading

Your grade on the project is based on three criteria: your agent’s performance on the Basic and Test problems (30%), your agent’s implementation and revision (20%), and the project reflection you submit along with your agent (50%).

Performance

For performance, your agent will be graded on whether it meets minimum performance goals. The minimum performance goal is: 7 or more problems correct on each set of 12 problems. The Basic and Test sets are each worth 15%: meeting the minimum goal on both earns the full 30%, while meeting the goal on only one earns 15%. Meeting the goal on neither earns 0%. (For Project 3, where there are four sets instead of two, each is worth 7.5%.)

Note that we will use your single best submission to calculate these scores. Your best scores on each set must come on the same submission. For example, if you reached 7/12 on the Basic B set on your third submission and 7/12 on the Test B set on your fifth submission, but never reached 7/12 on either set on any other submission, you would receive 15% instead of 30%.

Revise & Reflect

For implementation and revision, we will look at the implementation of your agent as well as your patterns of revision. We expect you to run your code on Gradescope relatively often: this is how we will judge your revision process. This area is more subjective, but generally, you will receive credit as long as (a) your agent reaches perfect performance on Basic and Test problems, (b) your agent gets better over a series of a few submissions, even if it never reaches perfection, or (c) you keep trying and making non-trivial revisions, even if your agent’s performance is not getting better. In other words, you’ll receive credit for a successful agent or continued attempts to build a successful agent.

You should notice that between Performance and Revise & Reflect, there is no heavy incentive to design a near-perfect agent at all costs. This is intentional: we want you to design agents that are somewhat successful, but beyond that, we care more about novel and interesting approaches than about success-at-all-costs approaches.

Journal

For the journal, you will write a personal reflection on your process of constructing the agent. It will include an introduction and conclusion, as well as a journal entry for each individual submission to the autograder. In each journal entry, you should include the submission to which the entry corresponds, a description of what has changed, a reflection on the relationship between your latest agent and human cognition, and a reflection on the agent’s performance.

Revise & Reflect and Journal credit are deeply intertwined: you’ll know that you’re fulfilling our goals for implementation if you find you have plenty to write about in your journal.

Top Performers

As noted, project grading specifically encourages either having a great agent or continually trying to improve your agent. Someone whose agent works perfectly on their first submission will receive the same implementation score as someone whose agent slowly gets better over a series of several submissions, even if they never come close to perfect performance.

However, we do want to have some incentive for doing well. Thus, on each of the three projects, the top 10 performers in the class will receive 5 extra points on their final average. This effectively means they can skip a test (or a couple questions on a homework, or some participation), or just let the extra points compensate for lost points elsewhere in the class.

Note that a single student can only receive this once; students who already received this bonus on an earlier project will be skipped in finding the top 10 on a later project. Top 10 will be calculated by total score on the problems graded for that project (e.g. Basic B and Test B for Project 1; Basic C and Test C for Project 2). If necessary, ties will be broken first by performance on the Raven’s problems, then on the Challenge problems.

Getting Started

To make it easier to start the project and focus on the concepts involved (rather than the nuts and bolts of reading in problems and writing out answers), you’ll be working from an agent framework in Python.  You can get the framework in one of two ways:

  • Clone it from the master repository with ‘git clone —-recurse-submodules https://github.gatech.edu/Dilab/KBAI-package-python.git’ (Python).
  • Download Project-Code-Python as a zip file.  This method allows you to obtain the code if you are having trouble accessing the Georgia Tech Github site.

You will place your code into the Solve method of the Agent class supplied.  You can also create any additional methods, classes, and files needed to organize your code; Solve is simply the entry point into your agent.

The Problem Sets

As mentioned previously, in project 3, your agent will run against 192 problems: 4 sets of 48 problems, with each set further broken down into 4 categories with 12 problems each. The table below gives a rundown of the 16 smaller sets, what will be provided for each, and when your agent will approach each.

Key:

  • P1?, P2?, and P3?: Whether that set will be used on that project.
  • Graded?: Whether your agent’s performance on that set will be used in determining your grade for the project (Basic and Test are used for grading, Challenge and Raven’s are just used for authenticity and curiosity).
  • Provided?: Whether you’ll be given a copy of those problems to use in designing your agent (you’ll see Basic and Challenge problems, but Test and Raven’s will remain hidden).
  • Visual?: Whether your agent will have access to visual representations of the set (which it will for all problems).
  • Verbal?: Whether your agent will have access to verbal representations of the set (you’ll have verbal representations for sets B and C, but not for sets D and E).

Thus, for the first two projects, you’ll be addressing the easier two sets of problems using visual and/or verbal representations. For the final project, you’ll address the final two sets of problems using their visual representations only. It might, therefore, be prudent to get an early start on the visual methods!

Within each set, the Basic, Test, and Raven’s problems are constructed to be roughly analogous to one another. The Basic problem is constructed to mimic the relationships and transformations in the corresponding Raven’s problem, and the Test problem is constructed to mimic the Basic problem very, very closely. So, if you see that your agent gets Basic problem B-05 correct but Test and Raven’s problems B-05 wrong, you know that might be a place where your agent is either overfitting or getting lucky. This also means you can anticipate your agent’s performance on the Test problems relatively well: each Test problem uses a near-identical principle to the corresponding Basic problem. In the past, agents have averaged getting 85% as many Test problems right as Basic problems, so there’s a pretty good correlation there if you’re using a robust, general method.

The Problems

You are provided with the Basic and Challenge problems to use in designing your agent. The Test and Raven’s problems are hidden and will only be used when grading your project. This is to test your agents for generality: it isn’t hard to design an agent that can answer questions it has already seen, just as it would not be hard to score well on a test you have already taken before. However, performing well on problems you and your agent haven’t seen before is a more reliable test of intelligence. Your grade is based solely on your agent’s performance on the Basic and Test problems.

All problems are contained within the Problems folder of the downloadable. Problems are divided into sets, and then into individual problems. Each problem’s folder has three things:

  • The problem itself, for your benefit.
  • A ProblemData.txt file, containing information about the problem, including its correct answer, its type, and its verbal representation (if applicable).
  • Visual representations of each figure, named A.png, B. png, etc.

You should not attempt to access ProblemData.txt directly; its filename will be changed when we grade projects. Generally, you need not worry about this directory structure; all problem data will be loaded into the RavensProblem object passed to your agent’s Solve method, and the filenames for the different visual representations will be included in their corresponding RavensFigures.

Working with the Code

The framework code is available here as Project-Code-Python.zip.  It is also available from git via ‘git clone –recursive https://github.gatech.edu/Dilab/KBAI-package-python.git’.  Note that these code packages contain a file instructing your agent to only look at those problems relevant for Project 1; you may modify ProblemSetList.txt to alter what problem sets your code runs against locally. This will not affect what it runs against on Gradescope.

The Code

The downloadable package has a number of Python files: RavensProject, ProblemSet, RavensProblem, RavensFigure, RavensObject, and Agent. Of these, you should only modify the Agent class. You may make changes to the other classes to test your agent, write debug statements, etc. However, when we test your code, we will use the original versions of these files as downloaded here. Do not rely on changes to any class except for Agent to run your code. In addition to Agent, you may also write your own additional files and classes for inclusion in your project.

In Agent, you will find two methods: a constructor and a Solve method. The constructor will be called at the beginning of the program, so you may use this method to initialize any information necessary before your agent begins solving problems. After that, Solve will be called on each problem. You should write the Solve method to return its answer to the given question:

  • 2x2 questions have six answer options, so to answer the question, your agent should return an integer from 1 to 6.
  • 3x3 questions have eight answer options, so your agent should return an integer from 1 to 8.
  • If your agent wants to skip a question, it should return a negative number. Any negative number will be treated as your agent skipping the problem.

You may do all the processing within Solve, or you may write other methods and classes to help your agent solve the problems.

When running, the program will load questions from the Problems folder. It will then ask your agent to solve each problem one by one and write the results to ProblemResults.csv. You may check ProblemResults.csv to see how well your agent performed. You may also check SetResults.csv to view a summary of your agent’s performance at the set level.

The Documentation

Included in the downloadable is the documentation for interacting with the code (API/index.html in the downloadable). You may use this and the in-line comments to understand the structure of the problems. Briefly, however:

  • RavensProject: The main driver of the project. This file will load the list of problem sets, initialize your agent, then pass the problems to your agent one by one.
  • RavensGrader: The grading file for the project. After your agent generates its answers, this file will check the answers and assign a score.
  • Agent: The class in which you will define your agent. When you run the project, your Agent will be constructed, and then its Solve method will be called on each RavensProblem. At the end of Solve, your agent should return an integer as the answer for that problem (or a negative number to skip that problem).
  • ProblemSet: A list of RavensProblems within a particular set.
  • RavensProblem: A single problem, such as the one shown earlier in this document. This is the most complicated and important class in the project, so let’s break it into parts. RavensProblem includes:
    • A Dictionary of the individual Figures (that is, the squares labeled “A”, “B”, “C”, “1”, “2”, etc.) from the problem. The RavensFigures associated with keys “A”, “B”, and “C” are the problem itself, and those associated with the keys “1”, “2”, “3”, “4”, “5”, and “6” are the potential answer choices.
    • A String representing the name of the problem and a String representing the type of problem (“2x2” or “3x3”).
    • Variables hasVisual and hasVerbal indicating whether that problem has a visual or verbal representation (all problems this semester have visual representations, only some have verbal representations).
  • RavensFigure: A single square from the problem, labeled either “A”, “B”, “C”, “1”, “2”, etc. All RavensFigures have a filename referring to the visual representation (in PNG form) of the figure’s contents. Problems with verbal representations also contain dictionaries of RavensObjects. In the example above, the squares labeled “A”, “B”, “C”, “1”, “2”, “3”, “4”, “5”, and “6” would each be separate instances of RavensFigure, each with a list of RavensObject.
  • RavensObject: A single object, typically a shape such as a circle or square, within a RavensFigure. For example, in the problem above, the Figure “C” would have one RavensObject, representing the square in the figure. RavensObjects contain a name and a dictionary of attributes. Attributes are key-value pairs, where the key is the name of some general attribute (such as ‘size’, ‘shape’, and ‘fill’) and the value is the particular characteristic for that object (such as ‘large’, ‘circle’, and ‘yes). For example, the square in figure “C” could have three RavensAttributes: shape:square, fill:no, and size:very large. Generally, but not always, the representation will provide the shape, size, and fill attributes for all objects, as well as any other relevant information for the particular problem.

The documentation is ultimately somewhat straightforward, but it can be complicated when you’re initially getting used to it. The most important things to remember are:

  • Every time Solve is called, your agent is given a single problem. By the end of Solve, it should return an answer as an integer. You don’t need to worry about how the problems are loaded from the files, how the problem sets are organized, or how the results are printed. You need only worry about writing the Solve method, which solves one question at a time.
  • RavensProblems have a dictionary of RavensFigures, with each Figure representing one of the image squares in the problem and each key representing its letter (squares in the problem matrix) or number (answer choices). All RavensFigures have filenames so your agent can load the PNG with the visual representation. If the problem has a verbal representation as well (hasVerbal or hasVerbal() is true), then each RavensFigure has a dictionary of RavensObjects, each representing one shape in the Figure (such as a single circle, square, or triangle). Each RavensObject has a dictionary of attributes, such as “size”:“large”, “shape”:“triangle”, and “fill”:“yes”.

Libraries

The only permitted libraries are the latest version of the Python image processing library Pillow and the latest version of numpy. For installation instructions on Pillow, see this page. For installation instructions on numpy, see this page. No other libraries are permitted.

Image Processing

Generally, we do not allow external libraries, but since Python has no native support for image processing, an external library must be used. The only external library we support for image processing for Python is Pillow. You can install pillow simply by running easy_install pillow. More comprehensive information on installing Pillow can be found here. We have included a code segment below on loading an image from a file with Pillow.

Submitting Your Code

This class uses Gradescope, a server-side autograder, to evaluate your submission. This means you can see how your code is performing against the Test problems even without seeing the problems themselves. Note that we will look at your submission history when evaluating your implementation: we want to see that you modified your agent over time, either to try to improve its performance or to experiment with different approaches. So, you should submit early and often. However, you are limited to 12 submissions per project to avoid over-stressing the autograder and to disincentivize “brute force” methods for solving the problems.

Submitting

To get started submitting your code, go to Canvas and click Gradescope on the left sidebar. Then, click CS7637 in the page that loads.

You will see six project options: Projects 1, 2, and 3, and an Error Check for each project. The Error Check project allows you to ensure your code will run on the server before using one of your 12 submissions; it will run your code only against the Basic and Challenge questions. Runs against Error Check do not count toward your grade and do not count against your 12 submissions.

Project 1 will run your code against Basic B, Test B, Challenge B, and Raven’s B. Project 2 will run your code against Basic C, Test C, Challenge C, and Raven’s C. Project 3 will run your code against Basic D+E, Test D+E, Challenge D+E, and Raven’s D+E. Select the project you want to submit to.

To submit your code, drag and drop your project files (Agent.py and any support files you created; you should not submit the other files that we supplied) into the submission window. You may also zip your code up and upload the zip file. You’ll receive a confirmation message if your submission was successful; otherwise, take the corrective action specified in the error message and resubmit. We recommend submitting to the Error Check first to ensure that your code will be accepted.

Getting Your Results

Then, wait for the autograder to finish. If there are no errors, you will see a detailed summary of your results. Each row in the test result output is the result of a single problem from the problem set: you’ll see a score of Pass label if your agent answered the question correctly, and a Fail label if your agent did not answer the question correctly. Your overall score can be found at the top right of the screen and in the summary at the bottom of the test results.

If you’d like to resubmit your code, click “Resubmit” found at the bottom-right corner of the autograder results page. You can analyze and compare your submission results using the “Submission History” button on this page, too.

Selecting Your Results

Once you have made your last submission, click Submission History, and then click Active next to your best submission. This is the only way to commit your final score to Canvas and get points; Gradescope does not select your best score automatically. You must do this to receive points for your submission.

Relevant Resources

Goel, A. (2015). Geometry, Drawings, Visual Thinking, and Imagery: Towards a Visual Turing Test of Machine Intelligence. In Proceedings of the 29th Association for the Advancement of Artificial Intelligence Conference Workshop on Beyond the Turing Test. Austin, Texas.

McGreggor, K., & Goel, A. (2014). Confident Reasoning on Raven’s Progressive Matrices Tests. In Proceedings of the 28th Association for the Advancement of Artificial Intelligence Conference. Québec City, Québec.

Kunda, M. (2013). Visual problem solving in autism, psychometrics, and AI: the case of the Raven’s Progressive Matrices intelligence test. Doctoral dissertation.

Emruli, B., Gayler, R. W., & Sandin, F. (2013). Analogical mapping and inference with binary spatter codes and sparse distributed memory. In Neural Networks (IJCNN), The 2013 International Joint Conference on. IEEE.

Little, D., Lewandowsky, S., & Griffiths, T. (2012). A Bayesian model of rule induction in Raven’s progressive matrices. In Proceedings of the 34th Annual Conference of the Cognitive Science Society. Sapporo, Japan.

Kunda, M., McGreggor, K., & Goel, A. K. (2012). Reasoning on the Raven’s advanced progressive matrices test with iconic visual representations. In 34th Annual Conference of the Cognitive Science Society. Sapporo, Japan.

Lovett, A., & Forbus, K. (2012). Modeling multiple strategies for solving geometric analogy problems. In 34th Annual Conference of the Cognitive Science Society. Sapporo, Japan.

Schwering, A., Gust, H., Kühnberger, K. U., & Krumnack, U. (2009). Solving geometric proportional analogies with the analogy model HDTP. In 31st Annual Conference of the Cognitive Science Society. Amsterdam, Netherlands.

Joyner, D., Bedwell, D., Graham, C., Lemmon, W., Martinez, O., & Goel, A. (2015). Using Human Computation to Acquire Novel Methods for Addressing Visual Analogy Problems on Intelligence Tests. In Proceedings of the Sixth International Conference on Computational Creativity. Provo, Utah.

…and many more!