AI_Kit aims to be a single dependency for various classic AI algorithms.
Core project goals are:
All of the algorithms (documented below) operate on several core traits, BindingsValue, Unify, Operation.
ai_kit provides optional data structures that implement these traits, allowing all algorithms to be usable out of the box - see Datum and Rule.
Quick examples are provided before, followed by more in-depth documentation.
You can use this library by adding the following lines to your Cargo.toml file:
[dependencies]
ai_kit = "0.1.0"
and adding extern crate ai_kit to your crate root.
This README provides an introduction.
API Documentation is available here
There are three traits and one structure to understand when using this library:
Bindings - similar to a key/value lookup, but with utilities for ensuring that two (or more) keys have the same value.
BindingsValue - a trait allowing a data structure to be used by the Bindings data structure.
Unify - a trait for data structure can be unified with another of the same type.
Operation - a trait for mapping some number of Unify instances to some number of other Unifys.
This is used for implementing Forward and Backward inferencing.
Two data structures can be unified if all of their components are the same or at least of the fields that differ is a variable. The Datum structure implements Unify. Here is an example of unifying datums.
When successful, the unification process returns a Bindings structure, which maps variable names to
their values (when known). It also allows for specifying that two variables are equivalent; in that case,
when the value for one variable is found, it is considerd the value for another.
Anything that implements ai_kit::core::BindingsValue can be used with Bindings; Datum implements BindingsValue:
```rust // Example of using the ai_kit::datum::Datum for variable bindings.
extern crate ai_kit;
use aikit::core::Bindings; use aikit::datum::Datum;
fn main() {
// Create empty bindings
let bindings : Bindings
// Set the variables "?x" and "?y" equal to each other
let bindings = bindings
.set_binding(&"?x".to_string(), Datum::Variable("?y".to_string()));
// Set the value of "?x"
let bindings = bindings.set_binding(&"?x".to_string(), Datum::Float(1.0));
// Verify that "?y" now has the same value
assert_eq!(bindings.get_binding(&"?x".to_string()), Some(Datum::Float(1.0)));
} ```
There are times when a program has certain facts from which further facts can be inferred.
This is implemented by the Operation trait. This is used to implement forward inference and planning. An example of forward chaining reasoning (also called Modus Ponens), would the following:
All men are mortal.
Socrates is a man.
Therefore Socrates is mortal.
The Rule struct implements Operation, and we use it to perform the above inference in rust.
Feature with-constraint
A simple and limited library for checking and satisfying constraints.
Feature with-forward-inference
Implementation of forward-chaining inference - essentially this is inference via Modus Ponens.
Feature with-planner
Planning with backtracking.
Misc data-structures and code for representing the path taken to derive a given inference.
The above algorithms operate on any structures that implement the appropriate core traits (BindingsValue, Unify and Operation).
ai_kit provides default structures that implement the core traits which should be sufficient for many use-cases.
Feature with-datum.
The datum::Datum structure implements the BindingsValue and Unify traits.
#[derive(Clone, Debug, Serialize, Deserialize, PartialOrd)]
pub enum Datum {
Nil,
String(String),
Int(i64),
Float(f64),
Variable(String),
Vector(Vec<Datum>),
}
Because Datum implements the Unify trait, Datum can be unified.
```rust
extern crate ai_kit;
use aikit::core::{Bindings, Unify}; use aikit::datum::Datum;
fn main() {
let d = Datum::Float(0.0);
let empty_bindings : Bindings
// These datums are the same, so they can be unified
let bindings = d.unify(&Datum::Float(0.0), &empty_bindings);
assert!(bindings.is_some());
// These datums are not the same, so they cannot be unified
let bindings = d.unify(&Datum::Float(1.0), &empty_bindings);
assert!(bindings.is_none());
// These datums differ, but the second is a variable, so they can be unified
let bindings = d.unify(&Datum::Variable("?x".to_string()), &empty_bindings);
assert!(bindings.is_some());
// The bindings returned by unification so that the variable ?x now has the same value as d!
assert_eq!(bindings.unwrap().get_binding(&"?x".to_string()), Some(d));
} ```
Feature with-rule.
The rule::Rule structure implements the Operation trait.
#[derive(Clone, Debug, Deserialize, PartialEq, Serialize)]
pub struct Rule<T: ConstraintValue, U: Unify<T>> {
pub constraints: Vec<Constraint>,
pub lhs: Vec<U>,
pub rhs: U,
_marker: PhantomData<T>,
}
```rust
extern crate ai_kit;
use aikit::datum::Datum; use aikit::infer::InferenceEngine; use ai_kit::rule::Rule; use std::marker::PhantomData;
fn main() { // Encode knowledge about mortality let rules = vec![ ( "ruleofmortality".tostring(), // Rules need ids for inferencing Rule { constraints: Vec::new(), lhs: vec![ Datum::Vector( vec![ Datum::Variable("?x".tostring()), Datum::String("isa".tostring()), Datum::String("human".tostring()), ] ) ], rhs: Datum::Vector(vec![ Datum::Variable("?x".tostring()), Datum::String("isa".tostring()), Datum::String("mortal".to_string()), ]), _marker: PhantomData, } ), ];
// Setup our initial knowledge about socrates
let facts = vec![
(
"socrates_is_hu``man".to_string(), // Facts need ids for inferencing
Datum::Vector(
vec![
Datum::String("socrates".to_string()),
Datum::String("isa".to_string()),
Datum::String("human".to_string()),
]
)
),
];
// Infer new knowledge!
let mut inf_engine = InferenceEngine::new(
"demo".to_string(),
rules.iter().map(|&(ref id, ref f)| (id, f)).collect(),
facts.iter().map(|&(ref id, ref r)| (id, r)).collect());
let inferences = inf_engine.chain_forward();
assert_eq!(inferences.len(), 1);
} ```
Forthcoming
Forthcoming
This example takes a bunch of words, and rules for aggregating words into phrases and sentences, and constructs a valid parse of the words. It then saves a graph in GraphViz .dot notation of the actual goal tree constructed into a "parse.dot" in the current working directory.
```rust
extern crate ai_kit;
extern crate serde_json;
use aikit::core::Bindings; use aikit::datum::Datum; use aikit::planner::*; use aikit::rule::Rule; use std::fs::File; use std::io::Write; use std::path;
macrorules! fromjson { ($type: ty, $json: tt) => ({ use serdejson; let x: $type = serdejson::from_value(json!($json)).expect("Expected json decoding"); x }) }
fn main() {
/*
* Inference rules that encode the parts of speech for each word and how to
* compose parts of speech into sentences.
*/
let rules: Vec
// Our input data - a series of words
let data: Vec<Datum> = from_json!(Vec<Datum>, [
{"str": "a"},
{"str": "the"},
{"str": "dog"},
{"str": "cat"},
{"str": "chased"}
]);
// Specify that our goal is to construct a sentence from the provided data using the provided rules
let mut planner = Planner::new(&Goal::with_pattern(from_json!(Datum, {"str": "sen"})),
&Bindings::new(),
&PlanningConfig {
max_depth: 5,
max_increments: 50,
// Don't reuse a given piece of data (ie, a word)
reuse_data: false,
},
data.iter().collect(),
rules.iter().collect());
// Construct the first interpretation
let result = planner.next();
assert_eq!(result.is_some(), true);
let (final_goal, bindings) = result.unwrap();
// What are our expected leaves of the goal (ie, the order of parsed sentences)
let expected_leaves: Vec<Datum> = vec![
"a".to_string(),
"dog".to_string(),
"chased".to_string(),
"the".to_string(),
"cat".to_string()
]
.into_iter()
.map(|s| Datum::String(s))
.collect();
// Verify that the leaves of our plan are as expected
assert_eq!(final_goal.gather_leaves(&bindings), expected_leaves);
// Render the plan using graphviz notation
let graphviz_rendering : String = final_goal.render_as_graphviz();
// Save the plan in the current working directory
File::create(path::Path::new(&"parse.dot"))
.and_then(|mut file| file.write_all(graphviz_rendering.as_str().as_bytes()));
} ```
Here is the expected content of "parse.dot":
``` graph "goal tree 'sen'" {
"'sen' [Actor(8)]" -- "'np' [Actor(6)]"; "'np' [Actor(6)]" -- "'det' [Actor(0)]"; "'det' [Actor(0)]" -- "'a' [Datum(0)]";
"'np' [Actor(6)]" -- "'noun' [Actor(4)]"; "'noun' [Actor(4)]" -- "'dog' [Datum(2)]";
"'sen' [Actor(8)]" -- "'vp' [Actor(7)]"; "'vp' [Actor(7)]" -- "'verb' [Actor(2)]"; "'verb' [Actor(2)]" -- "'chased' [Datum(4)]";
"'vp' [Actor(7)]" -- "'np' [Actor(6)]"; "'np' [Actor(6)]" -- "'det' [Actor(1)]"; "'det' [Actor(1)]" -- "'the' [Datum(1)]";
"'np' [Actor(6)]" -- "'noun' [Actor(5)]"; "'noun' [Actor(5)]" -- "'cat' [Datum(3)]";
} ```
If you have graphviz installed locally, you can convert this graph into a PNG file:
dot -Tpng parse.dot > parse.png
Some features depend on other features. This is summarized in the following table:
| Feature | Requires |
|---------|----------|
| with-planner | with-constraint |
| with-forward-inference | with-planner with-constraint |
| with-rule | with-constraint |
| with-constraint | N/A|
| with-pedigree | N/A |
| with-datum | N/A |
Examples in this document are tested as part of the build process using skeptic.