COSC-574: Automated Reasoning

Fall 2017

Contents

Announcements

Where, When, Who

Class Time: TR 2:00 PM–3:15 PM
Classroom: REI 284
   
Instructor: Mark Maloof
Office: 325 St. Mary's Hall
Office Hours: TR 12:00–1:30 PM (or by appointment).

Description

This graduate lecture surveys methods of automated deductive reasoning. Through traditional lectures, programming projects, paper presentations, and research projects, students learn (1) to understand the foundations of logical and probabilistic methods of automated reasoning. (2) to implement algorithms for logical and probabilistic reasoning, (3) to comprehend, analyze, and critique papers from the primary literature, (4) to replicate studies described in the primary literature, and (5) to design, conduct, and present their own studies. Topics include propositional logic, predicate logic, resolution proof, production systems, Prolog, uncertain reasoning, certainty factors, Bayesian decision theory, Bayesian networks, exact inference, approximate inference, first-order probabilistic models, probabilistic programming languages, and applications. Students complete programming projects using Java.

Prerequisites: Students should have taken undergraduate courses in computer science through data structures; at the very least, students must be able to implement trees and graphs in a high-level object-oriented programming language. Students should have also taken undergraduate courses in mathematics, such as probability, statistics, and perhaps propositional and first-order logic.

Recommended Text:

Additional Resources:

Learning Goals

By the end of the semester, students will be able to:

Policies

My course policies are designed to supplement the CS Department's Honor Policy. Unless stated otherwise when I distribute an assignment, the following is the default for all assignments for this course. I've developed my policies from past teaching experiences and from the CS Department's Honor Code at George Mason University.

I am obligated to refer all suspected cases of academic dishonesty by master's students to the Honor Council. I am obligated to refer all suspected cases of academic dishonesty by doctoral students to the dean of the Graduate School. If you have any questions about these policies or how they apply, please discuss such concerns with me during class, during office hours, or by e-mail.

In my experience, students at Georgetown do honest work. The small percentage of students who have submitted someone else's work as their own did so because they did not manage their time wisely.

Students must follow proper scholarly practice for all submitted work, whether graded or ungraded and whether a draft or final version of a proposal, paper, or program. We must acknowledge our reliance on the work of others through citation.

Students may be quite adept at and knowledgeable about citing and quoting material from traditional sources, such as books and articles. Typically, we do not have cite facts, common math formulae, or expressions of our own ideas, observations, interpretations, and analyses, However, new graduate students in computer science may not realize that formulae, theorems, proofs, algorithms, and programs can require the same treatment as any other form of expression.

For convenience, you do not need to cite the course materials, conversations with me or information you obtain from class lectures and discussions. If you are unsure about what requires citation or what constitutes proper scholarly practice, please ask me during class, during office hours, or by e-mail.

I design my courses and assignments so students have what they need to complete the assignments individually without consulting outside resources. I determine the size of and credit for assignments based on the assumption that the work for them is the result of individual effort using only the course resources and materials. Students who use outside resources to complete assignments may not be eligible for full credit. Students who do not acknowledge their use of outside resources to complete assignments may be in violation of my course policies and the university's policies on academic integrity.

The following list details acceptable and unacceptable practices:

Policies dealing logistics:

Assignments and Grading

String Grades::getLetterGrade()
{
  if (grade >= 94)
    return "A";
  else if (grade >= 90)
    return "A-";
  else if (grade >= 87)
    return "B+";
  else if (grade >= 84)
    return "B";
  else if (grade >= 80)
    return "B-";
  else if (grade >= 67)
    return "C";
  else
    return "F";
} // Grades::getLetterGrade

Materials: Readings, Videos, and Links

Schedule

  1. Introduction: Definitions, Areas, History, Paradigms
  2. Propositional logic and resolution proof for the propositional case
  3. Predicate logic, Most-general Unifiers
  4. Resolution proof for predicate logic
  5. Proof strategies, Prolog
  6. Post's Productions, Rule-based Systems, Rete Algorithm
  7. Midterm Exam
  8. Uncertainty, Probability Review, Certainty Factors
  9. Bayesian Decision Theory
  10. Bayesian Networks
  11. Exact Inference
  12. Approximate Inference
  13. Probabilistic First-order Logics

Other Interesting Links