Knowledge graphs enhance LLM performance

The AI landscape is evolving rapidly, particularly in how we approach knowledge retrieval for large language models (LLMs). While vector databases have gained significant traction, I'm convinced that knowledge graphs represent a more powerful paradigm for next-generation AI systems.

Why knowledge graphs? They offer structured relationships and semantic context that simple vector similarity can't match. These graphs, refined over decades of development, provide rich interconnections that capture the nuanced relationships between concepts. Projects like DBpedia demonstrate how well-curated knowledge graphs can enhance AI applications with deeper contextual understanding and more precise information retrieval.

I'm also curious about the democratization of LLM application development through new low-code tools. Three platforms have caught my attention:

* LangFlow - Visual programming for LangChain applications
* Flowise - Drag-and-drop UI for building LLM workflows
* ChainForge - Interactive environment for LLM app development

These tools are transforming how we build AI applications, making it possible to create sophisticated LLM-powered solutions through intuitive block diagrams and parameter configuration, generating production-ready Python or JavaScript code.

Bar Camp Boston 2013 talk on automation of science

This is an outline for a talk I gave at Bar Camp Boston 8 on the automation of science. It's a topic I've blogged and spoken about before. The shortened URL for this post is http://goo.gl/rv3Xik.

In 2004, a robot named Adam became the first machine in history to discover new scientific knowledge independently of its human creators. Without human guidance, Adam can create hypotheses to explain observations, design experiments to test those hypotheses, run the experiments using laboratory robotics, interpret the experimental results, and repeat the cycle to generate new knowledge. The principal investigator on the Adam project was Ross King, now at Manchester University, who published a paper on the automation of science (PDF) in 2009. Some of his other publications: 1, 2, 3.

Adam works in a very limited domain, in nearly complete isolation. There is plenty of laboratory automation but (apart from Adam) we don't yet have meaningful computer participation in the theoretical aspect of scientific work. A worldwide scientific collaboration of human and computer theoreticians working with human and computer experimentalists could advance science and medicine and solve human problems faster.

The first step is to formulate a linked language of science that machines can understand. Publish papers in formats like RDF/Turtle or JSON or JSON-LD or YAML. Link scientific literature to existing semantic networks (DBpedia, Freebase, Google Knowledge Graph, LinkedData.org, Schema.org etc). Create schemas for scientific domains and for the scientific method (hypotheses, predictions, experiments, data). Provide tutorials, tools and incentives to encourage researchers to publish machine-tractable papers. Create a distributed graph or database of these papers, in the role of scientific journals, accessible to people and machines everywhere. Maybe use Stackoverflow as a model for peer review.

Begin with very limited scientific domains (high school physics, high school chemistry) to avoid the full complexity and political wrangling of the professional scientific community in the initial stages. As this stuff approaches readiness for professional work, deploy it first in the domain of computer science and other scientific domains where it can hope to avoid overwhelming resistance.

Machine learning algorithms (clustering, classification, regression) can find patterns in data and help to identify useful abstractions. Supervised learning algorithms can provide tools of collaboration between people and computers.

The computational chemistry folks have a cool little program called Babel which translates between a large number of different file formats for representing molecular structures. It does this with a rich internal representation of structures, and pluggable read and write modules for each file format. At some point, something like this for different file formats of scientific literature might become useful, and might help to build consensus among different approaches.

A treasure trove would be available in linked patient data. In the United States this is problematic because of the privacy restrictions associated with HIPAA regulation. In countries like Iceland and Norway which have universal health care, there would be no equivalent of HIPAA, and those would be good places to initiate a Linked Patient Data project.

Setting up an RDF server in VirtualBox, part 2

This is the second part of a two-part (maybe N-part?) series about setting up an RDF server in a VirtualBox instance with the Ubuntu 12.04 server distribution. In this part, I'll set up Mediawiki as a place to conveniently edit RDF/Turtle documents.

You might be thinking, what about Semantic Mediawiki? Doesn't this already exist? My experience with SMW was disappointing. The source syntax for creating links is pretty straightforward, and the silly naming scheme for importing external ontologies doesn't seem too bad. But when you want to do any real work with external ontologies, it gets difficult. After a few days of hacking around I couldn't find a way to say that a predicate defined in my SMW instance was owl:sameAs some predicate defined externally. At that point, I decided to strike out on my own.

The results of that effort are on GitHub at https://github.com/wware/stuff/tree/master/semantic-wiki. The setup script is to be run in the VirtualBox instance after the Ubuntu 12.04 server installation (with LAMP and SSH servers enabled) has completed.

This is a work in progress. When I've got it beaten into presentable shape, I'll put it up at http://willware.net with more explanatory material.

Setting up an RDF server in VirtualBox, part 1

VirtualBox is an open-source virtual machine that you can use on Windows, Mac OSX, or Linux to run one of the other operating systems. Here I'll be using VBox on an Ubuntu Linux desktop machine to set up an Ubuntu server machine. The point in doing that when the two operating systems are so similar is to keep the two environments separate, and to discover what I'll need when I move the server to a VPS.

I'm doing this on a laptop with a 160 gig partition with Ubuntu 10.04 desktop. I can comfortably dedicate 20 gig to the virtual hard disk image. The VM will run Ubuntu 12.04 server. No shared folders because they won't be available on the VPS.

Make sure you have a good fast Internet connection for the Ubuntu desktop machine, and download the Ubuntu server ISO. It's available as 32-bit or 64-bit. If you're not sure about your CPU, you're probably better off with 32-bit. Set up VirtualBox:
$ sudo apt-get install virtualbox-ose

Now you'll find "VirtualBox OSE" in the Applications->Accessories menu in the upper left of the screen. Click on that, and when the window comes up, click on the light blue "New" icon. Pick a machine name, and Linux/Ubuntu as the virtual machine type, and give yourself a decent amount of RAM and hard disk space. It's nice to start the hard drive with 20 or 30 gig if you can spare it. Once the VM is created, go into settings for it, click "Storage" and click the third line with the CDROM icon. To the right of "CD/DVD device" click the yellow folder icon and navigate to the Ubuntu server ISO that you downloaded earlier. Set "Network" to the "Bridged adapter" option. Under shared folders, add your home directory (read only) and give it a name you'll remember. Now it's time to start the VM and install Ubuntu server on the virtual hard disk you've created. Before I could do this on my laptop, I found I needed to go into Settings->System->CPU and enable PAE.

During the installation process, you'll be asked what kinds of servers you want to run. Select "OpenSSH server" (so you can ssh/scp into the VM) and "LAMP server" (to get Apache and MySQL) and "Tomcat Java server" (to pick up a bunch of Java stuff you'll want for Jena). If you select an empty password for the root user on MySQL, you'll need to enter it multiple times, so you may want to select something almost as trivial like "root". You don't need to worry too much about security with a VM that will only be reachable on the local subnet.

When the installation is done, the machine will reboot, and the VM window will close and re-open. Go to the "Devices" menu at the top and under "CD/DVD devices", unclick the Ubuntu server ISO.

On to Jena. Looks like there is some good advice here, but some of it is dated so I'm tweaking it a bit: http://ricroberts.com/articles/installing-jena-and-joseki-on-os-x-or-linux

Log into the virtual machine and type:
$ sudo su -

# chmod 777 /opt

# exit

$ cd /opt

$ wget http://www.apache.org/dist/jena/binaries/apache-jena-2.7.4.tar.gz
$ wget http://www.apache.org/dist/jena/binaries/jena-fuseki-0.2.5-distribution.tar.gz

$ for x in *.gz; do tar xfz $x; done

$ rm *gz               

$ mv apache-jena-2.7.4 apache-jena

$ mv jena-fuseki-0.2.5 jena-fuseki

$ chmod u+x jena-fuseki/s-*

Add these lines to your .bashrc:
export FUSEKIROOT="/opt/jena-fuseki"
export JENAROOT="/opt/apache-jena"
export PATH="$FUSEKIROOT:$PATH"
export CLASSPATH=".:$JENAROOT/lib/*.jar:$FUSEKIROOT/*.jar"

You'll want to copy some client-side Ruby scripts from the server's Fuseki directory to your host machine. My VM is at 192.168.2.7, so on the host machine I typed:
$ scp 192.168.2.7:/opt/jena-fuseki/s-* .
I also needed to install Ruby on the host machine.

Now you can start up the Fuseki server and load it with some data. The docs for Fuseki are here. On the server:
$ cd /opt/jena-fuseki
$ ./fuseki-server --update --mem /dataset

This starts an empty database of RDF triples. This database is in-memory and non-persistent, and will vanish when you control-C. Back on the host machine, you can enter some data into the database:
$ ./s-put http://192.168.2.7:3030/dataset/data default family.rdf
$ ./s-put http://192.168.2.7:3030/dataset/data default wares.rdf

This is a small semantic graph talking about who in my family is married and whose kids are whose. To  make sure the data was actually stored, we can query it.

$ ./s-get http://192.168.2.7:3030/dataset/data default

This prints out the entire database in Turtle, an update of N3. Or we can get the same thing in JSON:

./s-query --service http://192.168.2.7:3030/dataset/query 'SELECT * {?s ?p ?o}'

I can see that I don't have the time and energy to get everything done in one sitting that I hoped I would accomplish. So this is part 1, and a part 2 will follow later, and I'll make sure they include links to each other.

A Semantic Network of Patient Data

This idea has two inspirations. One is this TED talk by Dave deBronkart or "e-Patient Dave". The other is the work that has been done on the semantic web and linked data.

Dave's talk is about patients taking control of their medical records and sharing them with other like-minded patients, so that they can learn from one another's histories and experiences. Some of these patients, including Dave, had terminal diagnoses and were able to improve or resolve those conditions because of having shared data with others.

The semantic web is the idea of formatting information so that computers can do more with it than simply store it or transmit it or display it on a screen. Computers can understand the meaning of the information much as a human would, so they can reason about it and draw new conclusions that aren't already spelled out. I first learned about it in a 2001 article in Scientific American. There are some more details here. I've blogged in the past about some of the basic ideas.

In the semantic web, all "things" (nouns, basically) are assigned URIs (web addresses). Relationships between things (and relationships are also things) are represented as RDF, where every statement is a triple of URIs, being a subject, predicate, and object. These statements are often printed or transmitted in XML, but the N3 language is more readable for people. Typical relationships look something like this.
  Will, town, "Framingham MA".
  Will, name, "William Ware".
  Will, pet, cat#12345.
  cat#12345, name, "Kokopelli".
  cat#12345, birthyear, 2003.
Strings ("William Ware", "Kokopelli") and numbers (2003) can be raw data, everything else is a URI. The idea is that a URI connects you to the rest of the semantic web of meaning, so if you don't know what a "pet" is, you can follow that URI, or query other triples with "pet" in them, to find out more.

You might wonder if it's silly to have such a primitive representation for knowledge. It allows the same kinds of economies of scale that we get by representing information in a computer with ones and zeroes. Because the format is so simple and uniform, we can build processing architectures that can be very efficient, and people have been doing that for over ten years. We have scalable databases for RDF, and when we set up rules that mimic set theory, we can build reasoning engines that extract new conclusions from the data.

When data is formatted with an appropriate ontology, it can be searched in rich complex ways, and computers can look for patterns and correlations that a human might not notice. When applied to patients' medical data, the results might be new medical knowledge or new treatment options.

There are other ways to find new information hidden in patient data. Semantic web technology is great for pure logic, but for quantitative measures (a dosage increase in this medication seems to cause a decreased amount of that neurotransmitter) we can turn to machine learning, where progress in the last decade or two has been explosive, given the data available on the web and the economic rewards for finding patterns in it.

An idea I've blogged about in the past (and spoken about at a couple of very small conferences) is applying this to general scientific literature, with the goal of hastening scientific progress and in particular medical progress (since I'm an old fart now and interested in that sort of thing).

If this topic interests you and you wish to discuss it, I'm starting a Google Groups forum for that purpose.

UPDATE: I've discovered that there is a company in Cambridge, MA called PatientsLikeMe which already pools patient data into a database, and sells subscriptions to that database. I don't know if they place the same emphasis on machine-tractable formats that I've done above. But knowing that somebody is doing it on a commercial basis, I don't see much point in trying to replicate that effort in my evenings and weekends.

Tim BL's talk on Linked Data

I learned a lot from Tim Berners-Lee's TED talk from February 2009 about Linked Data. He talks a bit about his motivation for inventing the Web, which was that the data he encountered at CERN was in all different formats and on all different computer architectures and he spent a huge fraction of his time writing code to translate one format to another. He talks about how much of the world's data is still locked up in information silos -- a million disconnected little islands -- and how many of the world's most urgent problems require that data be made available across the boundaries between corporations, organizations, laboratories, universities, and nations. He has laid out two sets of guidelines for linked data. The first is for the technical crowd:

1. Use URIs to identify things.
2. Use HTTP URIs so that these things can be referred to and looked up ("dereferenced") by people and user agents.
3. Provide useful information about the thing when its URI is dereferenced, using standard formats such as RDF/XML.
4. Include links to other, related URIs in the exposed data to improve discovery of other related information on the Web.

The second set is for a less technical crowd:

1. All kinds of conceptual things, they have names now that start with HTTP.
2. I get important information back. I will get back some data in a standard format which is kind of useful data that somebody might like to know about that thing, about that event.
3. I get back that information it's not just got somebody's height and weight and when they were born, it's got relationships. And when it has relationships, whenever it expresses a relationship then the other thing that it's related to is given one of those names that starts with HTTP.

It's a very eloquent talk, reminding me in places of David Gelernter's prophetic book Mirror Worlds.



What's remarkable about the Linked Data idea is that, as much as people tend to dismiss the whole semantic web vision, it really is making remarkable progress. The diagram above shows several interlinked websites with large and mutually compatible data sets.

• DBPedia aims to extract linked data from Wikipedia and make it publicly available.
  
• YAGO is a huge semantic knowledge base. Currently, YAGO knows more than 2 million entities (like persons, organizations, cities, etc.). It knows 20 million facts about these entities.
  
• Lexvo.org brings information about languages, words, characters, and other human language-related entities to the Linked Data Web and Semantic Web.
  
• The Calais web service is an API that accepts unstructured text (like news articles, blog postings, etc.), processes them using natural language processing and machine learning algorithms, and returns RDF-formatted entities, facts and events. It takes about 0.5 to 1.0 second depending on how big a document you send and the size of your pipe.
  
• Freebase is an open repository of structured data of more than 12 million entities. An entity is a single person, place, or thing. Freebase connects entities together as a graph.
  
• LinkedCT is a website full of linked data about past and present clinical trials.
  

Berners-Lee has recommended a very small set of Linked Data principles.

• Use URIs as names for things.
  
• Use HTTP URIs so that people can look up those names.
  
• When someone looks up a URI, provide useful information, using the standards (RDF*, SPARQL)
  
• Include links to other URIs so that they can discover more things.
  

Set theory, OWL, and the Semantic Web

Despite my interest in semantic web technology, there is one area I've had a little mental block about, which is OWL. If you just sit down and try to read the available technical information about OWL, it's clear as mud. Imagine my surprise when clarity dawned in the form of the book Semantic Web for Dummies by Jeffrey Pollock, who explains in Chapter 8 that OWL amounts to set theory. The book is surprisingly good, I recommend it.

I attended elementary school in the 1960s, when the U.S. was trying a stupid educational experiment called New Math. The basic premise was that little kids needed to know axiomatic set theory, in order for the U.S. to raise a generation of uber math geeks who could outperform the Soviet engineers who put Sputnik into orbit. If only I'd taken more seriously all this nonsense about unions and intersections and empty sets, I might have avoided all that trouble with schoolyard bullies. Oh wait.... Anyway, in order to fulfill this obviously pointless requirement, our teacher would spend the first three weeks of every school year drilling us on exercises in set theory and then move on to whatever math we actually really needed to learn for that year. The take-home lesson was that intersection was preferable to union, because writing the result of a union operation meant I had to do more writing and it made my hand hurt. In retrospect it's amazing that I retained any interest in mathematics.

Set theory came into vogue as guys like David Hilbert and Bertrand Russell were fishing around for a formal bedrock on which to place the edifice of mathematics. The hope was to establish a mathematics that was essentially automatable, in the belief that as a result it would be infallible. So they went around formalizing the definitions of various mathematical objects by injecting bits of set theory. One of the more successful examples was to use Dedekind cuts to define the real numbers in terms of the rational numbers.

Hopes of the infallibility of mathematics' new foundation were dashed by Kurt Godel's brilliant incompleteness theorem, described as “the most signal paper in logic in two thousand years.” It was possible to define mathematical ideas in set theoretic terms, and to formalize the axioms, and to automate the proof process, but at a cost. Godel proved the existence of mathematical truths that were formally undecidable -- they could neither be proved nor disproved. Hilbert had hoped that once mathematics was formalized, no stone would be left unturned, and all true mathematical statements would be provable. The story of Godel's theorem (not the history, just an outline of the proof itself) is a wonderful story, well told in Hofstatder's book Godel, Escher, Bach.

But getting back to semantic web stuff. Here are some basic ideas of OWL.

• Everything is an instance of owl:Thing. Think of it as a base class like java.lang.Object.
• Within an ontology, you have "instances", "classes", and "properties".
• "Classes" are essentially sets. "Individuals" are elements of sets.
• A "property" expresses some relationship between two individuals.
• OWL includes representations for:
• unions and intersections of classes (sets)
• the idea that a set is a subset of another
• the idea that two sets are disjoint
• the idea that two sets are the same set
• the idea that two instances are the same instance
• Properties can by symmetric (like "sibling") or transitive (like "equals")
• A property can be "functional", or a function in a mathematical sense. If p is functional, and you assert that p(x)=y and p(x)=z, then the reasoning engine will conclude that y=z.
• One property can be declared to be the inverse of another.
• One can declare a property to have specific classes (sets) as its domain and range.

It would be really nice if, at this point, I had some brilliantly illustrative examples of OWL hacking ready to include here. Hopefully those will be forthcoming.

Autosci talk at Bar Camp Boston

Yesterday I had fun giving a talk on the automation of science at Bar Camp Boston. I was very fortunate to (A) have very little to say myself, so that I quickly got out of the way for others to discuss, and (B) have some very smart people in the room who got the idea immediately, some of them able to give the scientist's-eye view of this idea.

Discussion centered around a few topics. One was how comprehensive a role would computers play in the entire scientific process. There seemed to be consensus that computers could easily identify statistical patterns in data, could perform symbolic regression in cases of limited complexity and not too many variables, but that in the creation of scientific theories and hypotheses, there are necessary intuitive leaps that a machine can't make. Personally I believe that's true but I imagine that computers might demonstrate an ability to make leaps we can't make as humans, and I have no idea what those leaps would look like because they would be the product of an alien intelligence. If no such leaps occur, at least the collection of tools available to human scientists will hopefully have grown in a useful direction.

Another topic was the willingness of scientists to provide semantic markup for research literature. Only those expert in the field are qualified to provide such markup since it requires an in-depth understanding of the field as a whole, and the paper's reasoning process in particular. It's also likely to be a lot of work, at least initially, and there is as yet no incentive to offer scientists in exchange for such work. The notion of posting papers on some kind of wiki and hoping that semantic markup could be crowd-sourced was quickly dismissed. Crowd-sourcing doesn't work when there is a very precise correct answer and the number of people with that answer is very small.

There has been a lot of Twitter traffic around Bar Camp Boston, and I was able to find a few comments on my talk afterward. It looks like people enjoyed it and found it stimulating and engaging, so that's very cool. It turned out to be a good limbering-up for an immediately following talk on Wolfram Alpha. I found one particularly evocative tweet:

Has anyone approached a CS journal to have their content semantically marked up? #BCBos @BarCampBoston

Thinking about that question, I realized that computer science is the right branch of science to begin this stuff, and that the way to make it most palatable to scientists is to publish papers that demonstrate how to do semantic markup as easily as possible at time of publication (not as a later retrofit), how a scientist can benefit himself or herself by doing that work, and how to do interesting stuff with the markup of papers that have already been published. My quick guess is that some sort of literate programming approach (wiki) is appropriate. So lots to think about.

If you attended my talk, thanks very much for being there. I had a lot of fun, and hope you did too.

Jena: Node versus RDFNode

The Jena code has two representations for nodes in an RDF graph. One is the class Node, which has several subclasses: Node_Variable, Node_Literal, Node_URI, etc. The other is the interface RDFNode, which has many subinterfaces: Literal, Resource, Property, etc.

These two node representations have very different roles and very different idiomatic usages, and this doesn't appear to be spelled out in the Jena documentation anywhere. RDFNode is in the com.hp.hpl.jena.rdf.model package, where Node is in the com.hp.hpl.jena.graph package, but I don't think the packaging by itself is a big enough hint.

The Jena tutorials mostly talk only about the RDFNode variants, usually instantiating them by calling a "create" method on the Model. The poorly documented distinction between RDFNode and Node extends to the distinction between Model and Graph, and between Statement and Triple.

Since this information didn't appear in the documentation, we need to look at the Jena mailing list to find it.

A key difference between Resource and Node is that Resources know which model they are in, and Nodes are general. That's what makes resource.getProperty() work. Now in a query that is not a concept that has any meaning in the general case and patterns can span graphs.

We have found that Model/Statement/RDFNode (the API) works as an application interface but it's not the right thing for storage abstractions and the Graph/Triple/Node (the SPI) works better where the regularity is more valuable. That is, we have split the application-facing design from the sub-system-facing design.

So an instance of RDFNode is associated with a specific Model, where an instance of Node is free-floating, and is used to build Rules, which are also model-independent. The two representations can be connected by URIs. If you have a Node and a Model, and you want the corresponding RDFNode, do this (or use createProperty or createLiteral as needed):

Resource r = model.createResource(uri1);

and if you have an RDFNode, you can do this to get a Node:

Node uriNode = Node.createURI(
        ((Resource)rdfNode).getURI());

So I can understand that there are two very different appropriate interfaces for writing Jena apps and for interfacing to a storage system. What I don't get is why I would ever see the latter while writing an application. If I define a Rule, I need to deal in Nodes. Presumably this is because I've been constructing Rules programmatically rather than just reading them in from a file. Maybe I should stick with the latter.

Playing with the Jena semantic web framework

I've begun tinkering with Jena, a semantic web framework written in Java. It embodies a lot of ideas and technologies that were once considered AI or expert systems, and which I neglected at the time (1980s).

• Jena homepage: http://jena.sourceforge.net/
• Docs: http://jena.sourceforge.net/documentation.html
• Javadoc: http://jena.sourceforge.net/javadoc/index.html

The semantic web frames a body of knowledge as a collection of three-word sentences called triples. These can be diagrammed as a directed graph such as the one below.

The corresponding three-word sentences appear below, written in N3, a human-readable formal language used by the semantic web community.

@prefix :  <#> .
:Cat :has :Fur .
:Bear :has :Fur .
:Cat :is-a :Mammal .
:Bear :is-a :Mammal .
:Mammal :has :Vertebrae .
:Whale :is-a :Mammal .
:Whale :lives-in :Water .
:Mammal :is-a :Animal .
:Fish :is-a :Animal .
:Fish :lives-in :Water .

In Jena, a Model is one of these things. Having constructed it (or having loaded it from either a file on the internet or a file on your computer), you can apply rules that allow you to draw conclusions. So let's step through that proecess. First we need to read in the file.

private static final String baseUri =
    "file:///home/wware/wware-autosci/" +
    "semweb/java/simpleNet.n3#";
private static void modelReadFile(String filename,
                                  Model model) {
    try {
        File f = new File(filename);
        FileReader fr = new FileReader(f);
        model.read(fr, baseUri);
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    }
}

To print the contents of a model, we can use the SPARQL query language, which looks a lot like SQL.

private static void printModel(Model model) {
    String queryString = 
        "SELECT ?x ?y ?z " +
        "WHERE {" +
        "    ?x ?y ?z . " +
        "}";
    Query query = QueryFactory.create(queryString);
    QueryExecution qe =
      QueryExecutionFactory.create(query, model);
    ResultSet results = qe.execSelect();
    ResultSetFormatter.out(System.out, results, query);
    qe.close();
}

and we'll call that method from our main method. I personally find it appalling that the graph above fails to recognize that fish have vertebrae, so we'll add a triple for that.

public static void main(String[] args) {
    Model model = ModelFactory.createDefaultModel();
    modelReadFile("simpleNet.rdf", model);
    model.createResource(baseUri + "Fish")
         .addProperty(model.createProperty(
                         baseUri + "has"),
                      model.createResource(
                         baseUri + "Vertebrae"));
    printModel(model);
}

and the RDF file that imports the model was translated from the N3 above, using CWM.

<rdf:RDF
xmlns="file:///home/wware/wware-autosci/semweb/java/simpleNet.n3#"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#">
    <rdf:Description rdf:about="#Bear">
        <has rdf:resource="#Fur"/>
        <is-a rdf:resource="#Mammal"/>
    </rdf:Description>
    <rdf:Description rdf:about="#Cat">
        <has rdf:resource="#Fur"/>
        <is-a rdf:resource="#Mammal"/>
    </rdf:Description>
    <rdf:Description rdf:about="#Fish">
        <is-a rdf:resource="#Animal"/>
        <lives-in rdf:resource="#Water"/>
    </rdf:Description>
    <rdf:Description rdf:about="#Mammal">
        <has rdf:resource="#Vertebrae"/>
        <is-a rdf:resource="#Animal"/>
    </rdf:Description>
    <rdf:Description rdf:about="#Whale">
        <is-a rdf:resource="#Mammal"/>
        <lives-in rdf:resource="#Water"/>
    </rdf:Description>
</rdf:RDF>

There is a Model.write(OutputStream) method, so we can write a model directly to a file instead of stepping through the triples explicitly.

So how about some actual reasoning? We should be able to conclude that a cat is an animal, and has vertebrae. This will require that we define two rules of inference, rule1 ("is-a" is transitive) and rule2 (a member of a species has the things the species has).

String rules =
        "[ rule1: (?x " + baseUri+"is-a ?y) " +
                 "(?y " + baseUri+"is-a ?z) -> " +
                 "(?x " + baseUri+"is-a ?z) ] " +
        "[ rule2: (?x " + baseUri+"is-a ?y) " +
                 "(?y " + baseUri+"has ?z) -> " +
                 "(?x " + baseUri+"has ?z) ]";
Reasoner reasoner = new
    GenericRuleReasoner(Rule.parseRules(rules));
reasoner.setDerivationLogging(true);
InfModel inf =
  ModelFactory.createInfModel(reasoner, model);
printModel(inf);

Simply creating the InfModel is enough to draw all the relevant inferences. The Reasoner's setDerivationLogging method tells the model to remember the derivations that led to any new conclusions, and these derivations can be examined for debugging purposes.

PrintWriter out = new PrintWriter(System.out);
for (StmtIterator i = inf.listStatements();
             i.hasNext(); ) {
    Statement s = i.nextStatement();
    for (Iterator id = inf.getDerivation(s);
             id.hasNext(); ) {
        Derivation deriv = id.next();
        deriv.printTrace(out, true);
    }
}
out.flush();

Bayesian nets in RDF, and how to update them

I've banged my head on this for a couple of days and feel close to a solution. The graph looks like this.



Each random boolean variable gets a node, the causal relationship between them gets a node, and each variable gets a probability.
The math for updating probabilities is a little tricky, but in a fun and interesting way, so I enjoyed banging on that. At some point I'll tackle more involved cases where there aren't simply two random boolean variables, but that's the logistically simple case that exposes most of the concepts involved. Kinda like the Drosophila of Bayesian inference.

"""Let A and B be random boolean variables, with A being an

unobservable cause and B being an observable effect, and Pr(B|A) and

Pr(B|~A) are given. This might be the case if the situation has some

structure that dictates the conditional probabilities, like a 6.432

problem, or it just might be empirical.

From these we can compute probabilities for the four cases.

P11 = Pr(B^A) = Pr(A) Pr(B|A)

P10 = Pr(~B^A) = Pr(A) (1-Pr(B|A))

P01 = Pr(B^~A) = (1-Pr(A)) Pr(B|~A)

P00 = Pr(~B^~A) = (1-Pr(A)) (1-Pr(B|~A))

Treat (Pr(B|A), Pr(B|~A)) as one piece of information, and Pr(A) as a

separate independent piece of information. The first piece reflects

your beliefs about the machinery connecting A to B, and the second

reflects your beliefs about the likelihood of A, so these are

legitimately separate concerns.

If we observe that B=1, then we want to replace Pr(A) with our

previous estimate for Pr(A|B), which is given by our old numbers as

P11/Pr(A) = P11/(P11+P01), and this becomes our posterior probability

for A."""

class Link1:

def __init__(self, PrBgivenA, PrBgivenNotA):

self.PrBgivenA, self.PrBgivenNotA = PrBgivenA, PrBgivenNotA

def updatePrA(self, PrA, bvalue):

p11 = PrA * self.PrBgivenA

p10 = PrA * (1. - self.PrBgivenA)

p01 = (1. - PrA) * self.PrBgivenNotA

p00 = (1. - PrA) * (1. - self.PrBgivenNotA)

# print p11, p01, p10, p00

assert 0.999 < p11 + p01 + p10 + p00 < 1.001

assert PrA - 0.001 < p10 + p11 < PrA + 0.001

if bvalue:

# Pr(A|B)

newPrA = p11 / (p11 + p01)

else:

# Pr(A|~B)

newPrA = p10 / (p10 + p00)

assert 0.0 <= newPrA <= 1.0

return newPrA

link = Link1(0.6, 0.27)

PrA = 0.5

print PrA

for i in range(5):

PrA = link.updatePrA(PrA, 0)

print PrA

for i in range(10):

PrA = link.updatePrA(PrA, 1)

print PrA

Inference engines and automated reasoning

An inference engine is a computer program that reasons, using some form of knowledge representation.

This can be done with propositional logic or first-order logic, assuming each proposition is completely unambiguous and is either 100% true or 100% false. These simplistic engines are fun little exercises in programming but in real-world situations, reasoning usually needs to consider ambiguities and uncertainties. Instead of simply being true or false, propositions may be likely or unlikely, or their likelihood may be something to be tested or determined. Some elements of some propositions may be poorly defined.

In the unambiguous binary case, it's typical to express rules for generating new propositions as if-then rules with variables in them. We call these production rules because they are used to produce new propositions.

If X is a man, then X is mortal.

Given the statement "Socrates is a man", we

• match the statement to the rule's IF clause
• take note of all variable assignments: X=Socrates
• plug assignments into the THEN clause: "Socrates is mortal"
  

Obviously this isn't rocket science, but even without handling uncertainty, it will still be useful if scaled to very large numbers of propositions, as in the semantic web.

How to handle uncertainty? This can be done by representing knowledge as a Bayesian network, a directed graph where the edges represent the influences and dependencies between random variables. There is a good tutorial about these online. Here's an example from the Wikipedia article where the probability of rain is an independent variable, and the sprinkler system is usually off if it's raining, and the grass can get wet from either rain or the sprinkler.

There are at least two open-source inference engines that work with Bayesian networks. One is SMILE, another is the OpenBayes library for the Python language. OpenBayes allows you to update the state of your knowledge with a new observation.

Suppose now that you know that the sprinkler is on and that it is not cloudy, and you wonder what's the probability of the grass being wet : Pr(w|s=1,c=0). This is called evidence...

ie.SetObs({'s':1,'c':0})

and then perform inference in the same way... The grass is much more likely to be wet because the sprinkler is on!

Here is a list of many more Bayesian network libraries, and another list. There is also a nice tutorial on Learning Bayesian Networks from Data, the process of taking a bunch of data and automatically discovering the Bayesian network that might have produced it. Another Bayesian reasoning system is BLOG.

Bayesian logic (BLOG) is a first-order probabilistic modeling language under development at MIT and UC Berkeley. It is designed for making inferences about real-world objects that underlie some observed data: for instance, tracking multiple people in a video sequence, or identifying repeated mentions of people and organizations in a set of text documents. BLOG makes it (relatively) easy to represent uncertainty about the number of underlying objects and the mapping between objects and observations.

Are production rule systems and Bayesian network systems mutually compatible? I don't yet know. Do Bayesian networks adequately represent all important forms of uncertainty or vagueness that one might encounter in working with real-world data? I don't know that either. Are there other paradigms I should be checking out? Probably.