Research proposal in Artificial Intelligence: Sheaf theory, fuzzy sets and knowledge representations

I've decided to put my rough-draft research proposal up, somewhat on a whim. Any comments, questions and suggestions are most welcome!

Narrow AI and the local-to-global problem

Many AI systems have been written which can solve a very restricted class of problems by understanding a very restricted domain of knowledge or “micro world”; SHRDLU is an important early example of this. Other examples include expert systems (e.g. medical diagnosis systems, chess playing AIs) which work well in a specific, narrow domain. Unfortunately, no AI system has made the transition from understanding a narrow, limited micro world to understanding the large, unlimited knowledge environment of the real world.

This indicates to me that current AI techniques are good at solving narrow problems, but that no-one has a workable way of patching them together to cope with very large, potentially unrestricted problem spaces.

Sheaves in mathematics

I am interested in applying a mathematical technique to solving this problem. In advanced mathematics, many objects are defined by locally attaching some kind of structure to a topological space, for example in algebraic geometry with the study of schemes. The unifying notion here is that of a sheaf on a topological space: a presheaf is a map which assigns a particular kind of structure (for example a ring, a group, a set, etc) to each open set of an open cover, and to each inclusion of open sets, a restriction map. A sheaf is a presheaf such that any consistent assignment of local structure yields a unique global structure (this is known as the gluing axiom). Sheaves can be defined in more generality, for example on a site, and they can be categorified to form stacks. The category of sheaves on a space (or on a site) forms a topos, so in fact sheaves can be manipulated using the rules of intuitionistic logic (manipulations in intuitionistic logic are valid in any topos). See [3].

Knowledge representations should be sheaves

Current (neat) knowledge based AI systems use first order predicate logic (FOPL) to represent knowledge, store facts about the world as axioms in FOPL, and derive new knowledge from old by searching for proofs of statements. [4]

I would like to investigate the possibility of defining knowledge bases for AI systems using sheaf theory: specifically, I want to represent knowledge as a sheaf of sets of statements in FOPL on a topological space. See the final section of this proposal for details.

This is partially motivated by the above discussion of the efficacy of current techniques in narrow problems but not in more general ones and the formal similarity that this has to the situation in mathematics described above. I also draw inspiration from the fact that present attempts to define so called upper ontologies (for example Cyc or SUMO) are meeting the problem that there doesn’t seem to be any acceptable “upper” or “global” ontology which suits all applications. [8], [9]. This is a problem if one thinks that knowledge bases should be globally defined sets of FOPL statements. But if one considers knowledge to be a sheaf of (for example) sets of FOPL statements defined on a topological space, then the lack of a global upper ontology is simply the statement that the knowledge sheaf has no global sections. In mathematics, many important sheaves have no (nontrivial) global sections.

The problems of defining real-world categories in terms of FOPL statements (for example using a set of necessary and sufficient conditions) has long been criticized in cognitive science and the philosophy of mind. Everyday categories like “chair”, “motorcycle” are impossible to encode in this way, and has led to philosophers of mind talking about real-world objects belonging to “fuzzy categories”. Lakoff’s Hedges are particularly interesting here [6]. Attempts to define logics which make this notion precise go back to the 1960s. This line of thought has spawned various fuzzy logics, for example logics taking truth values in the interval [0,1], see [5], [7], which in turn led to more general fuzzy logics and fuzzy sets, and to some applications in control of systems.

Sheaf theory and “Fuzzy sets”

I was encouraged in my line of thinking when I discovered the recent work of Ulrich Hohle, [1], [2] wherein a large part of fuzzy set theory is shown to be sheaf theory “in disguise”. The mathematical content of Hohle’s papers shows that fuzzy sets are sheaves on a topological space defined by the lattice of truth values.

I would consider Hohle’s papers [1], [2] a setting off point for my research, along with the standard references on knowledge based AIs. [4]

Things to do

• Read some relevant existing literature on Fuzzy Sets and fuzzy logic, for example the many publications of Zadeh, also read Hohle’s second paper. [2]
• Formalize the construction of a sheaf of FOPL systems; this will involve working out what the restriction maps should be, etc.
• Perhaps try sheaves of propositional calculus, or of semantic networks (these being strictly simpler), or even of directed, labeled graphs.
• Work out what kind of topological space we want, and how to represent it on a machine. I would also like to study the properties of finite and countable topological spaces. I would also consider whether sheaves on a site are more appropriate to this application
• I would want to try and lift all of the standard algorithms and procedures from ordinary FOPL knowledge bases to the sheafified case. This would include the “TELL” algorithm to add a new piece of knowledge and the “ASK” algorithm to query the KB. Work out how to go about proving statements in a sheaf of FOPL systems.
• Hand-coding the underlying topological space that these sheaves are constructed upon isn’t a scalable option. An automated method would be required. I have some ideas as far as this is concerned involving analysis of large corpuses of text to form a suitable topological space.

A specific example of sheaf-based knowledge representation

To define a sheaf-based knowledge representation, we need two mathematical objects:

(a) A topological space T defined by a basis B of open sets which correspond to domains of knowledge

(b) A category C such that the elements of ob(C) are some suitable knowledge representation, for example directed, labeled graphs (also known as semantic networks or conceptual graphs within the AI community [4]), and for A, B objects of C, Hom(A,B) is the set of homomorphisms suitable to that representation format. In the case of directed, labeled graphs, one would want directed graph homomorphisms.

It is an AI/data mining problem to construct the above. Given these, a (directed, labeled graph) knowledge sheaf is a functor

F: O(T) --> C

Where O(T) denotes the usual partially ordered set of open sets of T, regarded as a category, such that F satisfies the usual sheaf conditions given in, for example, [3].

Defining the sheaf F requires us to choose a homomorphism of graphs for each inclusion of domains of knowledge (open sets of T).

References

1. Fuzzy sets and sheaves. Part I Basic concepts - U Höhle - Fuzzy Sets and Systems, 2007

2. Fuzzy sets and sheaves. Part II - U Höhle - Fuzzy Sets and Systems, 2007

3. Sheaves in Geometry and Logic: A First Introduction to Topos Theory (Universitext) by Saunders MacLane, Ieke Moerdijk

4. Artificial Intelligence: Modern Approach - by Stuart J. Russell, Peter Norvig

5. Fuzzy sets - LA Zadeh - Fuzzy Sets, Fuzzy Logic, and Fuzzy Systems, 1965

6. Hedges: A study in meaning criteria and the logic of fuzzy concepts
   G Lakoff - Journal of Philosophical Logic, 1973

7. Commonsense reasoning based on fuzzy logic
   LA Zadeh - Proceedings of the 18th conference on Winter simulation, 1986

8. Suggested Upper Merged Ontology (SUMO) - http://www.ontologyportal.org/

9. Representation as a Fluent: An AI Challenge for the Next Half Century – A. Bundy, F McNeill - IEEE INTELLIGENT SYSTEMS, 2006

Black Belt Bayesian: Rapture of the Nerds, NOT

Steven has an excellent post up on Black Belt Bayesian: Rapture of the Nerds, NOT. It's nearly a year old now, but it is so important that I want to draw people's attention to it.

"The idea of a technological singularity is sometimes derided as the Rapture of the Nerds, a phrase invented by SF writer Ken MacLeod [update: this isn’t true, see his comment] and popularized by SF writers Charlie Stross and Cory Doctorow. I can take a joke, even a boring old joke that implies I’m a robot cultist, but it irks me when jokes become a substitute for thinking... " [continue reading]

"It would be tragic if, by thinking of some subjects as inherently religious, we let the religious impose their terms on our understanding of the world."

Letter from Utopia: inspiration for exam term

As the exam crisis from hell is setting in, I took a few moments to read some of Nick Bostrom's Letter from Utopia:

Have you ever known a moment of bliss? On the rapids of inspiration, maybe, where your hands were guided by a greater force to trace the shapes of truth and beauty? Or perhaps you found such a moment in the ecstasy of love? Or in a glorious success achieved with good friends? Or in splendid conversation on a vine-overhung terrace one star-appointed night? Or perhaps there was a song or a melody that smuggled itself into your heart, setting it alight with kaleidoscopic emotion?

...

If you have experienced such a moment, experienced the best type of such a moment, then a certain idle but sincere thought may have presented itself to you: “Oh Heaven! I didn’t realize it could feel like this. This is on a different level, so very much more real and worthwhile. Why can’t it be like this always? Why must good times end? I was sleeping; now I am awake.”

Yet behold, only a little later, scarcely an hour gone by, and the softly-falling soot of ordinary life is already piling up. The silver and gold of exuberance lose their shine. The marble becomes dirty.

...

Quick, stop that door! Look again at your yellowing photos, search for a clue. Do you not see it? Do you not feel it, the touch of the possible? You have witnessed the potential for a higher life: you hold the fading proof in your hands.

Utopia may be a nonsensical notion (it would be a real shame if there were a best state of existence; for what would there be left to do when one achieved it?), but the idea of a world which compares to ours as ours does to the world of medieval or prehistoric times certainly seems realistic. And we are the ones who will make it happen! (or fail to do so).

************************************************************************************************************

I found the following piece of academic inspiration on John Baez's site:

In our acquisition of knowledge of the Universe (whether mathematical or otherwise) that which renovates the quest is nothing more nor less than complete innocence. It is in this state of complete innocence that we receive everything from the moment of our birth. Although so often the object of our contempt and of our private fears, it is always in us. It alone can unite humility with boldness so as to allow us to penetrate to the heart of things, or allow things to enter us and take possession of us.

This unique power is in no way a privilege given to "exceptional talents" - persons of incredible brain power (for example), who are better able to manipulate, with dexterity and ease, an enormous mass of data, ideas and specialized skills. Such gifts are undeniably valuable, and certainly worthy of envy from those who (like myself) were not so "endowed at birth, far beyond the ordinary".

Yet it is not these gifts, nor the most determined ambition combined with irresistible will-power, that enables one to surmount the "invisible yet formidable boundaries" that encircle our universe. Only innocence can surmount them, which mere knowledge doesn't even take into account, in those moments when we find ourselves able to listen to things, totally and intensely absorbed in child's play.

Can anyone guess who this is from? (without cheating!) I'll give you a clue: I've been studying the work of this man for the past few months, and he is considered to be one of the (if not the) most influential mathematicians of the late 20th century.

You Can Face Reality

What is true is already so.
Owning up to it doesn't make it worse.
Not being open about it doesn't make it go away.
And because it's true, it is what is there to be interacted with.
Anything untrue isn't there to be lived.
People can stand what is true,
for they are already enduring it.
-- Eugene Gendlin

The open-source person?

Follow-up to: Friendly AIs and RPOPs, Artificial Intelligence vs. Brain-Computer Interfaces

Over on Accelerating Future, IConrad writes:

You’re thinking of the mind as a software problem rather than as a hardware problem. One simple way to ensure Friendliness in a human is to ensure that empathy is augmented as much as — or more so than — intelligence. And as there is a neurological basis for empathy, that’s a fairly safe approach.

hmmm. I’m not entirely convinced ;-0!

But presumably he's saying something like this: it’s easy to make a human behave well: just add more empathy neurons/mirror neurons! I suspect that there is probably truth to this. But, on the other hand, you’re tinkering with an evolved, messy system. How do you know what will actually happen if you put, say, more mirror neurons into someone’s brain, past the maximum that any previous human has had? What happens when you do this at the same time as interfacing them with a computer? I suspect that the answer to the question:

“what will happen to the patient if we perform highly speculative neuro-intervention XXX”

is likely to be split evenly between

“the patient will go mad”

and

“nothing happens”

with perhaps some very tiny probability of something pleasant happening. This is typical of what happens when you interfere with a very complicated system that you don’t understand. Of course, neuroscientists will accrue more and more knowledge about the human brain over time (at what rate? who knows!), so as time goes on, our understanding of the system will go up, and the probability of a nice outcome will increase.

Now I ought to add, for balance, that AGI is not without problems. AGIs may become very powerful before they really understand what we humans consider valuable in life. I’ve discussed the pros and cons of making a putative superintelligent system more or less like a human mind here.

I think that a good compromise solution might be to try to understand the human mind using brain scanning techniques, and then to implement a human mind fully in software, from scratch, with no copying from any one particular human involved. This would effectively be an open source person, and would have several benefits IMO:

1. The open-source person wouldn’t have any hidden personality traits that went in unnoticed, the open-source person’s values and personality could be mutually agreed upon by all interested parties [perhaps even by an international treaty]. This would encourage people to co-operate and negotiate, rather than to sneakily stab everyone else in the back. See, for example, Bill Hibbard's excellent paper Open Source AI for some of the potential benefits of the open source method in this context.

2. Since there is no evolved system, no neurons, no brain involved, you don’t have a massive complexity/mess issue: one can cream off the finer points of the human mind without all of the messy implementational errors that evolution will have introduced.

3. Ethics committees will be loathed to approve intervention in an actual person's physical brain, but they probably won't mind so much if one simply scans a lot of people's brains.

On an unrelated note, I'm likely to be posting quite erratically over the next few months as I have some fairly important exams coming up. You can subscribe to the Transhuman Goodness Feed to avoid wasting time checking the site when I'm too busy to post, and to avoid missing out on posts when I'm busy posting stuff to take my mind off the exams!

Artificial Intelligence vs. Brain-computer interfaces

This is a comment on Michael Anissimov's Accelerating Future post:

It seems to me that AGI is the easier, and probably safer path to superintelligence.

Many people have spoken about how BCI will be easy because the brain is already there: as if nature has done most of the work for you, all you have to do is plug an extant brain into an extant computer, maybe tweak it a bit, and hey presto!

But look at it this way: would you try to build an aeroplane by grafting your latest pair of wings to the arms of a human? It was tried: it didn’t work. Why not? Well, one can look at the first successful attempts at flight using a human/machine hybrid (which required a much more advanced machine than the first machine used in machine-only flight). It turned out that the existing human body was simply not optimized for doing the job required of it (poor power to weight ratio).

The human brain contains about 10^12 neurons, which we can think of as dots on a graph, and 10^15 axons, which are connections between them. Imagine a graph with 10^12 dots, and roughly 1000 edges per dot… It’s not a pretty thought for a scientist. It’ll be a complete mess: evolved systems always are. Most people on this blog have probably heard about how your esophagus crosses your windpipe unnecessarily, leading to the danger of choking because evolution cannot look ahead, and mistakes get frozen in. Imagine that, multiplied by 10^15.

Now it may be possible to interface this mess with a computer, but because of the messyness on the human brain side, things WILL go wrong. Things like, for example, psychological disorders in the human concerned, or perhaps irreversible brain damage. (not to mention purely implementational risks like the risk of infection, which was a big worry for Kevin Warwick when he did some interfacing)

We worry about friendly AI, but how much more difficult will friendly BCI be? You interface the first 10 people with a computer, they all go mad. Person no.11 seems fine, until you realize too late that she has been acting essentially like an uFAI.

*****************************************************************

IConrad likes the idea of the brain being “fuzzy”, I say it’s a “mess”. I suppose two people can look at the same system and see it in different lights.

I don’t worry very much about the feasibility (or otherwise) of various BCI techniques. If they work, they work, and I don’t think I have enough information right now to know one way or another.

What worries me is the probability of things going nasty: unfriendly BCI. Now, unfriendly AGI is a distinct possibility too, so in order to argue against BCI, I have to argue that on balance, the failure modes of BCI are more serious than those for AGI. This is, given our state of ignorance today, a tall order.

Arguments about “throwing big rocks” etc seem to apply equally to BCI and AGI as far as I can see. It seems likely that the same defense works in both cases: the AGI/BCI-person is cleverer than you are, so they’ve thought of a counter strategy that is simply beyond your intellectual reach. Saying that you can kill a BCI enabled supervillain with a nuke is a bit like saying you can defeat Gary Kasparov at chess if you could just get his king on its own with your queen and your rook…

Here’s what I can think of:

1. if you’re doing BCI, you have to choose one person who will get augmented (or perhaps a small group who will get augmented). This means that you have a strong incentive for people to fight and squabble over who gets to be augmented before you’ve even started.

2. BCI is likely to be dangerous for the human concerned. This means that, on average, cautious people will not want to go first; the first generation of BCI patients will self-select for recklessness.

3. The messyness of the human brain means that you will not be able to have a provably friendly BCI. You can’t do software verification on someone’s brain.

4. Similarly, you cannot do open-source BCI: well, I presume there will be no way to make someone’s mind open source (although if one could do that, then I’d be very interested…)

Some of Eliezer's most important Posts on Overcoming Bias

This page is intended to be a continuously updated list of what I think the most important of Eliezer Yudkowsky's posts on Overcoming Bias are. For those who are not reading/have not read Eliezer's posts on Overcoming Bias, the idea is that, before considering the problems of creating friendly AI (and perhaps other problems related to accelerating technological change), we need to do a bit of a mental "spring clean" - we need to become more rational.

What does "rational" mean? Well, that's what the posts are about.

I've been reading Overcoming Bias for a while, and it is a goldmine of utterly essential insights. However, like a real goldmine, there are some bits that are absolute solid gold, buried in a lot of vaguely interesting ore (which the dedicated rationalist may have time to sift through: a full list of Eliezer's Overcoming Bias posts is being kept by Tom on Accelerating Future).

In my humble opinion, the following posts are absolutely essential reading for anyone. Even if you have no interest in transhumanism, artificial intelligence or ethics they are still solid gold material. The choice of posts is entirely mine, and I take full responsibility for anything important that I've left out. I am open to suggestions for other key posts!


***************************************************************************


The Bottom Line: - If you read nothing else here, read this post -"Your effectiveness as a rationalist is determined by whichever algorithm actually writes the bottom line of your thoughts. If your car makes metallic squealing noises when you brake, and you aren't willing to face up to the financial cost of getting your brakes replaced, you can decide to look for reasons why your car might not need fixing. But the actual percentage of you that survive in Everett branches or Tegmark worlds - which we will take to describe your effectiveness as a rationalist - is determined by the algorithm that decided which conclusion you would seek arguments for. In this case, the real algorithm is "Never repair anything expensive." If this is a good algorithm, fine; if this is a bad algorithm, oh well."

Making Beliefs Pay Rent (in Anticipated Experiences): - Most people I talk to about philosophy do not get this, which is depressing because you'd think it is fairly basic stuff - "Above all, don't ask what to believe - ask what to anticipate. Every question of belief should flow from a question of anticipation, and that question of anticipation should be the center of the inquiry. Every guess of belief should begin by flowing to a specific guess of anticipation, and should continue to pay rent in future anticipations. If a belief turns deadbeat, evict it."

Mysterious Answers to Mysterious Questions: - Another excellent post on basic rationality - " The greater lesson lies in the vitalists' reverence for the elan vital, their eagerness to pronounce it a mystery beyond all science. Meeting the great dragon Unknown, the vitalists did not draw their swords to do battle, but bowed their necks in submission. They took pride in their ignorance, made biology into a sacred mystery, and thereby became loath to relinquish their ignorance when evidence came knocking."

Hold Off On Proposing Solutions: - Once I'd read this, I started taking note of how quickly people (including me) proposed solutions to problems; the results were shocking - "Traditional Rationality emphasizes falsification - the ability to relinquish an initial opinion when confronted by clear evidence against it. But once an idea gets into your head, it will probably require way too much evidence to get it out again. Worse, we don't always have the luxury of overwhelming evidence. I suspect that a more powerful (and more difficult) method is to hold off on thinking of an answer. To suspend, draw out, that tiny moment when we can't yet guess what our answer will be; thus giving our intelligence a longer time in which to act."

The Logical Fallacy of Generalization from Fictional Evidence: "When I try to introduce the subject of advanced AI, what's the first thing I hear, more than half the time?

Oh, you mean like the Terminator movies / the Matrix / Asimov's robots!

And I reply, Well, no, not exactly. I try to avoid the logical fallacy of generalizing from fictional evidence. "

Stranger than history - Read this and realize how strange the year 2108 is going to be

Guardians of the Truth: "When you are the Guardian of the Truth, you've got nothing useful to contribute to the Truth but your guardianship of it."

Initiation Ceremony: - This little story is contains, at its core, a very important message, which I repeat here -
"Yes, I want to know," said Brennan.
"Know what, exactly?" whispered the figure.
Brennan's face scrunched up in concentration, trying to visualize the game to its end, and hoping he hadn't blown it already; until finally he fell back on the first and last resort, which is the truth:
"It doesn't matter," said Brennan, "the answer is still yes."