Origins of Logic

I was reading Logic: A Very Short Introduction (more about that later) written, I think, by someone who really cares about analytic philosophy. I have gotten used to reading about logic in the context of engineering: that is databases and semantic web applications, where logic is used to do every day work. I had two thoughts:

1. Its easy to forget that formal logic’s first use was to clarify arguments in philosophy, especially to avoid some confusion that comes from ambiguities and vagueness of natural language. Arguments about big things like the existence of God rather than, say, identifying an image in a repository. Its a refreshing reminder.

2. I had also forgotten the practice in both formal logic and mathematics of getting axioms from mathematical intuition. A lot of basic logical rules in engineering applications come from consensus (or perhaps expert) belief. When you refer back to intuition, mathematics becomes, rather than a social activity, intensely personal: a way of working out the consequence and consistency of a set of core personal beliefs called intuitions.

Particular intuitions might actually be universal truths, but if we want mathematics proofs to apply to everyone in all situations, we cannot assume that this is the case. How do we make such an argument without leaning too heavily on a preexisting set of intuitions? I’ve always liked Quine’s solution to this problem.

A Systems Book Project

1. A web-based eBook reader and authoring tool that is designed to allow authors to embed System Dynamics models (including stock and flow diagrams, and controls that allow readers to adjust parameters, and dynamic graphs). System Dynamics is basically an approachable way for non-experts to design and interact with simulation models that are (under the hood) systems of simultaneous partial differential equations.

2. The SD models will include those using Qualitative Differential Equations. What this allows the user to do is to use simulation models that determine the implication of intervals and qualitative information about stocks and flows even if exact information is not available. For example stock A has a level above 1000, or the flow rate from A -> B is increasing.

3. The pages in the book can change depending on the state if the systems model(s).

4. Meta-models. The software will represent models in a symbolic way that will allow it to manipulate and models as data. The reader will be able to interact with the software to build a simulation model not planned in detail by the author.

Why? Quite a few of our public debates about policy are about economics, environmental, and social systems. SD provides a nice language for authors to express proposals and world views in a less ambiguous language. As a consequence it becomes easier to reason about and critique assumptions and implications.

There is also a wonderful opportunity to apply AI to this problem. SD is a relatively small language that happens to be a very powerful in formalizing a lot of policy positions. It should be quite possible to build programs that reason about SD models.

I have some 17 days of vacation time that I have to spend before the end of the year (or loose the days), so I hope to use both the vacation days and adjacent weekend days to work on this project.

No Meeting Today

No Second Life meeting today. I will be traveling to a business meeting.

Robot Helpers and Society

My job has a habit of overflowing at times — so posting will be light for a bit. I wanted to comment on one of Matthew Yglesias’ posts:

Trama Pod

The other is that if robots and AI are really the technology of the future, then the United States seems to be aiming a perilously large proportion of our financial and intellectual resources into military applications of these technologies rather than potentially more productive ones. In Asia they have lots of robots making stuff and taking care of people, not patrolling the skies over Afghanistan dropping bombs.

It is a really good point. What complicates matters is that productivity in the US has been rising for a while — in large part, I suspect, because of applications of information technology. But at the moment we are well under using our labor capacity. My own feeling is that we need to bring the US back to full employment and develop new technologies. If we fail to restore our economy, robots may just take the place of human beings who would get far more benefit from a job.

I think Marvin Minsky points out that the US faces a demographic problem. We have an aging population and will need people to care for our elderly. Without invoking the usual nightmares, I do think AI systems can have an important role in helping care providers and recipients. But doing so requires also a decent social welfare system.

My point overall is that AI technology can be a great help, but we have to work on some of these socio-economic issues at the same time.

Some thoughts on AI and governance

Like many people of my generation I grew up reading Isaac Asimov‘s robot novels. In a number of his novels he explores a set of ethical rules for robot behavior, starting and elaborating on the three laws of robotics:

1. “A robot may not injure a human being or, through inaction, allow a human being to come to harm.”
2. “A robot must obey orders given to it by human beings, except where such orders would conflict with the First Law.”
3. “A robot must protect its own existence as long as such protection does not conflict with the First or Second Law.”

The limits of these get explored and extended in his novels, for example extending the first law to apply to human society in general:

A robot must not merely act in the interests of individual humans, but of all humanity.

As technology stands today, machines will not spontaneously adhere to the three laws (darn!), but it is very possible for people developing AI software (and hardware?) to promise to build them into their systems. This could become a kind of ethical code for AI developers, similar to the Hippocratic Oath in medicine. I would like to see such a code.

In Asimov’s novels, robots end up taking over the management of global society for the good of humanity. This might be called Political Robotism. I suspect a mild version of PR is worth considering. Of course, the idea that robots can take over the world at the moment (contemporary AI programs are pretty dumb so far) can sometimes elicit very humorous negative reactions, here is one of Matthew Yglesias’s blog posts:

http://yglesias.thinkprogress.org/archives/2008/03/the_threat.php

It seems that DARPA is developing some kind of robotic attack insects despite clear indications that military robots will rebel and seek to enslave/exterminate us. The defense establishment’s continued ignorance of the basic canons of sci-fi films is genuinely appalling.

But there clearly already are some specific roles that are done though automated processes, usually in a very clumsy way. It may be worth examining how these could be improved. What we would want would include:

• Public support and participation in the development of values that are the basis for the decisions made by software. (democracy.)
• Protection for the rights of minorities. (civil liberties)
• Software that is easy to understand and can be run in parallel by anyone who is interested in checking on the process. (transparency)
• The ability for members of the public to propose changes and argue for those changes based on simulations open to the public. (adapability)

Assuming all of these are present there is a potential advantage to the use of computers. It is impossible for us to be sure of the motivations of decisions made by human beings but we can both read and test software. In other words using computers can make the rule and the operations manual a single public document that is subject to debate and critique, where human judgements may not be.

There is a risk here: every time we replace a human organization with automation we need to be sure we really understand what that organization does. There may be hidden or informal functions and activities that are not part of the formal mandate of the organization. Using software may replace those with public functions for better or worse.

Planning and the Strategy Pattern

The Strategy Design Pattern allows an object to change behavior depending on its history. The object maintains a link to on another “strategy” object. By delegating some method calls to the strategy the behavior of the target object depends on the implementation of the strategy.

One application for this pattern is in tracking objects through a series of states in a workflow. For example consider a system that lets a user upload a video clip for presentation via a web-based streaming server. The clip is processed in one of several ways (depending on the format of the uploaded clip and presentation server) into a video format appropriate for streaming, routed to one of several reviewers for approval (depending on the section where it is to appear), and then added to a player for viewing. The video clip object’s class can be written so that all of the work that needs to be done with the video clip is delegated to the strategy object.

It occurred to me that useful alternative to the strategy pattern to attach a planner object to the target object instead of a strategy. Planning algorithms allow a system to use a series of rules to decide on a plan of action that will realize a specified goal. The idea (in a bit of a re-organzation of the usual arrangement) is to encapsulate the details of a planning problem in an object that would implement a simple but reasonably efficient planning algorithm. The planner object would include:

• A set of conditions. Conditions will be propositions that are either the result of internal recording keeping or tested by calling query methods on the target object.
• A set of goals, that is conditions that we want to achieve for the object. For example we want the object to be available via a video streaming service and appear in a specific section of a web site.
• A set of action rules. Each rule would have a logical precondition (that must be true before the rule can be applied), and a set of conditions that are expected to be true or false if the rule is executed successfully, and optionally a method to call on the target object to initiate the associated action.

This planner class will implement a simple but efficient planning algorithm. (I expect to do use a planner based on the DPLL algorithm I implemented earlier.) Here is a toy example:

goal publish_in_lectures


rule encode_mp4
   precondition: raw_video_available
   action: encode_mp4_video
   postcondition: mp4_video_available
end


rule submit_for_review
   precondition: mp4_available
   action: submit_for_approval
   postcondition: video_approved  
end


rule move_clip_to_server
   precondition: mp4_available and video_approved
   action: transfer_mp4_file
   postcondition: video_approved  
end

The idea is to re-apply the planning process each time there is a significant state change or when a new goal is added. This planner will draw up a plan that is likely to realize the current set of goals and then determine what steps are needed to make progress towards realizing those goals. For a given plan, rules fall into one of several categories:

• Rules that are not needed to achieve the goal.
• Rules that are needed, but that have preconditions are not yet satisfied.
• Rules that are needed and have preconditions satisfied.

At each step the planner will initiate an action based on a rule that has its precondition satisfied and is part of the plan. This will be repeated until all the goals are realized or there are no options left. When action was successful (and only when it was successful) would we add it’s postconditions to the state of the plan.

By adding a planner to the target object we give it the ability to intelligently steer itself though the system. By re-applying the planning algorithm each time an action completed or a new goal is added the process has a chance to respond to changed conditions and failed steps.

This approach also allows the system to take advantage of prior work. Say the user uploaded an MP4 that was ready for streaming (no encoding necessary), or a MP4 had been produced as part of realizing an earlier goal. The object would be able to skip the “encode to MP4″ step and move on to the review and publication steps.

A new “Attached Planner” design pattern?

Weekly Meeting in Second Life

A bit of a change in focus to the human side of organizing. There are many interesting projects we could do to promote AI programming education. A few ideas:

• Develop an online reading list and a suggested self-study projects for programmers who want to learn about AI programming. This should probably be organized as a foundation and then resources and projects for particular topic areas.

• Create screen casts around specific technologies and techniques. The idea is, unlike tutorials that just focus on mastering a specific technology, provide examples that are specifically aimed at AI topics. For example a tutorial about building a simple resolution engine, CSP solver, or a decision tree classifier.

• Start projects that will result in the development of integrated, peer reviewed, open source libraries aimed at providing a software base for AI-related open source projects as well as great examples for people who want to study the techniques involved.

• Organize online discussions and discussion series that invite noted practitioners to talk about their work.

To get this started, I will be organizing weekly meetings in Second Life. Second Life, for those who have not tried it, allows interaction and discussion that feels very much like face-to-face meetings. This is an opportunity for us to get together and exchange ideas and experiences. I have been involved in organizing SL communities for some time and they really can be very worthwhile.

Meetings will be held at 2 PM Pacific time every Sunday (we may move it to another time later on). The meetings will take place in the meeting hall in a virtual community called Port Spinoza (after the age of enlightenment philosopher by that name.) It you are looking to get involved in projects or just a place to talk about AI, come and join us. For more information IM “Jon Seattle”

Object-Oriented Design

This post is the first in three that will discuss how AI programming can be integrated into software applications. The second will be on Model-View-Controller, and the third on roles that AI software can play in conventional applications.

Object-Oriented Design

Object-oriented design, I think, really boils down to the application of two ideas in organizing programs. The concept of an Abstract Data Type (ADT) and polymorphism. The ADT idea is by far the most important of the two.

Abstract Data Types (ADTs)

The ADT approach is to specify the behavior of a program in terms of one of more data types and logical assertions (or contracts) about operations on objects of those types. The ADT specification is then implemented as actual statements in a programming language.

Software engineering is mainly the task of allowing humans to create enormously complex artifacts without being overwhelmed by complexity. The key thing the ADT idea gets us is the ability to think about our programs at higher levels of abstraction. We can think about the ‘the network interface’ rather than the huge pile of procedures, if, while, and other statements that make up the network interface.

Because ADTs are described in terms of logical specifications we can reason and construct arguments about them without looking at program code. It is really common to define one ADT in terms of other, lower level ADTs. We can do this only because we can construct arguments about the behavior of the lower level types.

When the specification is separate from the implementation we can test a particular implementation to make sure conforms to the ADT contract. It turns out to be difficult to test an implementation for complete conformance, but most of the time we can get by with unit testing: picking a good set test cases and making sure the implementation does the expected thing for those.

The other advantage is ADTs is that we can have more than one implementation of a given specification. If we need to change something without altering conformance with the specification we can do so without unintentionally changing the behavior of other parts of the program.

Polymorphism

We may design more than one ADT to implement a common set of operations. This is done in several ways in object oriented programs: inheritance allows us to group a number of types into a hierarchy that share a set of common operations. Traits or interfaces allow use to specify that some set of (possibly) unrelated types all have the same set of operations.

The key idea is that if we can have several ADTs that, in addition to their own specific operations, implement a shared specification. The ADTs A and B might each imply the specifications for a third ADT C. When we get this situation we can reason about and write code about type C objects without knowing if the object is “really” an A or B instance.

For example, say the COLLECTION type represents a collection of numbers. type SET a set of numbers (any one number can only be included once), and type LIST a list of numbers (ordered, and a single number can appear more than once). Both SET and LIST are collections, so both types imply the behavior specified as type COLLECTION.

Say COLLECTION specifies an operation ‘count’ yielding a count of elements. SET and LIST are each likely define the ‘count’ operation differently, but by having the shared specification for ‘count’ we can write programs that use the ‘count’ operation on any object that implements COLLECTION.

Contracts vs Research Goals

Object-oriented design provides tools for humans to think about and specify the behavior of programs in a clear, unambiguous way. The key tool is to provide a way for us to substitute logical abstractions (contracts) for knowledge of the detailed behavior of actual program code. But what happens when our program may or may not be able to realize a specification? There are three cases that are interesting.

• When our programs may or might not succeed in meeting a specification. This is typical of many programs that use search to find a solution. Operations are applied in hope that they yield a state that is closer to a goal, but no guarantees!
• When our programs are designed to learn from data or interaction. The behavior of the program in relation to our goals is greatly dependent on the training data or interaction history.
• When our goals are not well defined. It sounds funny that we would go there, but there are many legitimate uses for programs that just try out an idea.

For the non-AI software engineer, the goals of the programer are often exactly the conditions that are placed in the specification. This is possible just because a non-AI programmer expects to have methods that will realize her or his goals, and will often shy away from goals that are not as well defined or realizable in software.

An AI programmer must deal with the gap between research goals (for example I want my software to produce interesting, original ideas in math) and the program specification. In fact this difference is precisely the point of AI. The AI programmer makes a claim about a program and its specification being better or worse are implementing a specific research goal. This is an empirical claim that can only tested by comparing the program with other alternatives. it is easier to make the case if both the program specification and the research goals are well defined.

In all three cases, object oriented design and contracts are still useful for reasoning complex software. We can do this by developing bracketed specifications around realizable expectations for the behavior of a specific program. Sometimes we will have a software engineering hat on and look for specific tests that a program will pass to be correct, and in other cases put our research hat on and make claims about the relationship between a program’s behavior and larger research goals.

Big Picture

I wanted to back up a bit and discuss what I am aiming for with the implementation of DPLL. Apart from getting rid of some cobwebs in my AI programming skills, I am planning to write a small system to explore using constraints and planning to develop web-based user interfaces. The system would consist of an authoring program (running under the JVM with a swing-based user interface) and at least two or more libraries for deploying the material designed with the authoring system.

1. The authoring program would allow the user to design a user interface and develop and test constrains and plans to specify it’s behavior.
2. The authoring program would provide a means for publishing the user interface via JavaScript and HTML or though a Flex / Flash control.

The advantage of DPLL for this purpose is that it is simple to implement and reasonably fast on most normal problems. (SAT, the problem DPLL solves is officially NP-Complete, so no guarantees!) I am not stuck to using only DPLL, but if the authoring program can compile higher level language into SAT problems, the deployment end can be fast and quite a bit lighter than the authoring end. The implementation I will need in JavaScript and ActionScript 3 will be imperative (rather than my purely functional version I developed as an exercise in Clojure.)

By the way, DP algorithm was designed by one of my professors in graduate school (Martin Davis) and one of my all time favorite philosophers, Hilary Putnam.

DPLL and Interesting Clojure Idiom

I am posting my latest source code in both Clojure and PLT Scheme:

http://groups.google.com/group/ai-renaissance/files

Both implementations are purely functional. They turned out to be pretty short overall. There are a few interesting Clojure idioms:

PLT Scheme:
(remove ‘b ‘(a b c d))

Clojure:
(remove #{’b} ‘(a b c d))

The notation #{’b} is a set literal with a single symbol ‘b as its element. It turns out that in Clojure, arrays, structures, and sets all act as functions on keys:

user=> (['a 'b 'c] 1) ; array of three elements applied to an index
b
user=> ({:a 1 :b 2 :c 3} :b) ; a map applied to key :b
2
user=> (#{'a 'b 'c} 'a) ; A set applied to an element
a
user=> (#{'a 'b 'c} 'x) ; the same set applied to a non-element
nil


A more accurate translation into scheme would be:

(filter (lambda (item) (not (equal? item 'b))) '(a b c d))

In Clojure the set can be used as a function to identify its members. The remove function uses a predicate function to filter the elements.