How to mimic our brain!

In my previous post, I tried to explain that a large knowledge base with the appropriate algorithms could mimic our brain reasoning. But what could be these algorithms?

In a naïve approach, the simplest form of reasoning program will have to:
1 - format the input facts.
2 - retrieve similar or related facts in the knowledge base.
3 - retrieve rules linked with the facts (retrieved) in the knowledge base.
4 - search for synonyms and repeat steps 2 and 3.
5 - check the incoherences in the facts and rules retrieved and mark them "check it!"
6 - make inferences between facts and rules
7 - recycle the conclusions in the step 1 (the conclusion becomes an input fact) until the conclusion matches our criteria.

This a very raw description of the different steps and algorithms required to mimic our brain reasoning. I will detail each steps in the future posts.

When Knowledge size matter.

We are able to estimate the risk to receive the fruit on our head because our observations accumulated since our childhood. As young kid without any knowledge about the gravity we know that any object between our fingers will fall when we will release the object. Later, we will know that fruits in the tree fall when it is windy or when the fruits are ripe. If a program has this knowledge too, logically it will be able to estimate the risk to receive the fruit. The reasoning will be a succession of inferences. For example, the database contains these facts and rules (the probability that the fact is true is indicated in percent):

1 - 100% - A pear is a fruit.
2 - 100% - A pear grows in the top of a tree.
3 - 100% - The top of a tree is above the ground surface.
4 - 100% - A thing above the ground surface falls when released.
5 - 100% - A pear is a thing.
6 - 80% - A fruit is released when is ripe.
7 - 60% - A pear is ripe on October.
8 - 100% - We are on October.

The inferences are:

(1,6 => 9) A pear is a fruit + A fruit is released when is ripe = A pear is released when is ripe.

(9,7,8 => 10) A pear is released when is ripe + A pear is ripe on October + We are on October = A pear is released (0.8 x 0.6 x 1 = 0.48).

(4,5 => 11) Thing above the ground surface fall when released + A pear is a thing =A pear above the ground surface falls when released.

(11,10 => 12) A pear above the ground surface falls when released + A pear is released = A pear above the ground surface falls (1 x 0.48 = 0.48).

(2,3 => 13) A pear is in the top of a tree + The top of a tree is above the ground surface = A pear is above the ground surface.

(12,13 => 14) A pear is above the ground surface + A pear above the ground surface falls = A pear falls (1 x 0.48 = 0.48).

So the set of facts and rules above bring to the conclusion that a pear could fall with a probability of 48%.

This sort example shows that a software is able of reasoning but that requires an extensive and precise factual and procedural knowledge base.

But what happens when the knowledge base is incomplete, a fact is wrong or incertain , or different words are used for the same thing?

For example:

a) If the fact 6 is missing "A fruit is released when is ripe" ?

b) If the fact 7 is wrong "A pear is ripe on June" ?


c) If the fact 3 and 4 use two different terms soil and ground surface for the same thing: "The top of a tree is above the soil" and "A thing above the ground surface falls when released" ?

As for human, it will depend of the quantity of knowledge stored in the database.  

For the problem (a), the software can proceed by analogy, for instance the 2 facts below conduct to the hypothesis that a pear could fall like an apple :
- An apple falls from the tree when it is ripe.
- Apples and pears grow on tree.

For (b), the software can detect an error in the knowledge base. If for instance the knowledge base can contain these facts:
- Anjou, Bartlett, Bosc, Comice are pear varieties.
- Comice pears are harvested September through February.
- Bosc pears are harvested September through April.
- Barlett pears are harvested July through October.
So the fact (b) is illogical regarding the facts listed above and the program will warn there is an incoherence in its knowledge base and it will ask for checking of the fact (b).

For (c), the software can search a synonyms of soil and ground and then it will decide that both words design the same thing.

As a human, a program is able to support some incoherence in its knowledge base and ask to verify some weird facts.

But what kind of algorithms are required for this pseudo-human reasoning ?

To be continued...

Facts and Rules

My work to improve the dictionaries of TexLexAn, in fact its knowledge base brings me to a very basic question: What is knowledge?

We can distinguish two kind of knowledge:

The procedural knowledge or the rules to do things.
The declarative knowledge or the facts.

In the computer world, the procedural knowledge is represented by the rules-based system experts such as the online diagnosis programs, and the declarative knowledge is foundation of the databases such as the phone directory for the simplest form.

Today, the both forms of knowledge are managed by two completely different kinds of programs but our brain does not work like that! It looks evident that facts and rules are intimately mixed. There is a good reason for it; we construct our rules from ours observations (the facts). These rules can very dependent of the observations but we try generalize these rules. We call it an inductive reasoning.

We can imagine this funny thing:  In the middle of October while we are reading under an apple tree, we receive an apple on our head, so we decide to move under another tree, in fact a pear tree. Pears are not apples but we are cautious because we infer that if one apple fell down there is a chance that a pear can fall down too.  Can a program do the same hypothesis?

to be continued...

TexLexAn to classify and summarize wiki pages?

I am currently thinking about a new kind of wiki especially designed for the education. The students will be the main contributors and the main readers too. A tool able to extract some statistic concerning the text, to classify and to provide automatically a short summary will be useful for the instructor and the reader too.
I think that TexLexAn after some modification (to make it able to understand the markup language of the wiki) will be able to do the job.

If you are interested in my project of Educational Wiki (I called it "Academic Wiki"), you will find the detail of the project here: http://learnexperiment.wikidot.com/

Best answers of the most frequently asked questions

I could call it "BAMFAQ"; it is the idea to create of database of the most frequent answers to the most frequent questions. It is common to the see the same questions repeated again and again in different forums.

- The idea is to crawl the different forums and to collect all the questions and their answers, so that will be the first step.
- The second step will be a classification of the questions in order to regroup the similar questions. The classification will be unsupervised (clustering). So now, we have groups of similar questions with their answers.
- The third step will be the extraction of the 2 or 3 most frequent answers for each group of questions. Our database is almost ready, for each group of similar questions we have the 2-3 most frequent answers that we can suppose as the best answers.

Robustness of the new dictionary

The robustness of a structure of data is an important point when a large amount will have to be stored on disk for a long period of time. The current hard disk reliability is high ( 600,000 hrs < MTBF < 1,200,000 ), furthermore some array configurations of hard disks increase the overall reliability (raid 6 for instance). Anyway, the risk is non-null and it is interesting to verify if it will be possible to recover the data in case of hard disk failure.

Analyze:

Structure of each class in the dictionary: 

label_index label_name:k/S1/w1L1\TERM1/w2L2\TERM2.../wiLi\TERMi/S2/wi+1Li+1\TERMi+1..../wi+jLi+j\TERMi+j/S3/..../Sn/Wk+1Lk+1\TERMk/...

/0/Wl+1Ll+1\TERMl+1/Wl+2Ll+2\TERMl+2/...EOL

There are 3 dictionaries with the same structure for the word-unigrams, words-digrams and words-trigrams.

Hypothesis: one or a few consecutive bytes are corrupted.

- The sequence "label_index label_name:" is exactly repeated in each dictionary. It is easy to rebuilt this sequence from another dictionary by searching the closest match. If the probability is P to have a problem is this sequence and the probability is the same for each dictionary, then the probability is P³ to have an unrecoverable sequence "label_index label_name:".  P³ is a tiny probability and furthermore, it will always possible to correct manually the label_name.

- The value k can be easily computed again from the Number of terms in the dictionary / number of term in the class. So, the risk is not here.


Finally , the biggest risk comes from the list of terms of each class because it represent the largest part of the data.

/S1/w1L1\TERM1/w2L2\TERM2...
- The sequence /S_i/ takes 6 bytes, the value S_i 4 takes bytes and can be computed again by searching the next leading digram and counting the number of characters.
- The sequence /w_jL_j\ takes 6 bytes. w_j takes 2 bytes and can be roughly estimated from the previous weight w_j-1 and the next weight w_j+1 if the term of the same leading digram are sorted on the weight w. L_j take 2 bytes and is the length of the TERM_j. It can be computed again.
So, the sequence /Si/wjLj\ does not represent a big risk too.

- The chain \TERM_j/ has a variable length given by L_j + 2. In many case, this term belongs to other classes inside the dictionary, then it will be possible to retreive it by searching its closest match (lowest edit distance) inside the dictionary.

In conclusion:
This structure seems intrinsectly robust with enough redundency to recover any errors affecting one byte or a few continuous bytes.

Note: I am starting to modify the dictionaries and the programs. They will be in the new branch of the repository /branch/new_dico_struct/...  Be patient, that will take time to modify and to valid the code.

Dictionary structure: Switch between sorted and unsorted leading digrams

The computation of the jump value of each leading digrams has cost (my post of feb 17), so when the number of terms with the same leading digrams is too small, it will be more expensive to compute the jump to the next leading diagram than to compare each term.  This conclusion brings two ideas:

- The dictionary should have two structures: the terms sorted and grouped on their leading digrams when the number of terms of same digrams is important and the terms unsorted and ungrouped when this number is small.
- A calibration routine will compute the threshold value. This value will be used to decide when to switch between the two structures. This calibration will only run the first time the program is executed.

1- New dictionary structure:

label_index label_name:k/S1/w1L1\TERM1/w2L2\TERM2.../wiLi\TERMi/S2/wi+1Li+1\TERMi+1..../wi+jLi+j\TERMi+j/S3/..../Sn/Wk+1Lk+1\TERMk/...

/0/Wl+1Ll+1\TERMl+1/Wl+2Ll+2\TERMl+2/...EOL

where S1 is the length of the substring  "/w1L1\TERM1/w2L2\TERM2.../wiLi\TERMi/"
S2 is the length of the substring  "/wi+1Li+1\TERMi+1..../wi+jLi+j\TERMi+j/"
etc for S3, S4... Sn
/0/ marks the end of grouped leading digrams.

The difference with the structure presented in my post of Feb 17 are the /0/ sequence of characters. The value 0 indicates the end of the group of terms, and then a routine will have to compare each terms one by one rather to compare just the leading digram of the first term of each group of terms.

2 -New routines:

To keep the program simple, the grouping of terms with the same leading digram will be done by a third program, independently of the classifier and the learner.

Simplified flowchar:

The new program named 'smartgroup' will reorganize the dictionaries. It will be trigged after several dictionaries updates. It runs independently of Texlexan and Lazylearner.

New search algorithm:
(pseudo code, Python style with goto):

GROUP:
      While not EOL do:
         get length S of the group of digram
         if length S is 0 goto BULK
         compute the index of the next group
         get the digram of the first term
         if digram of the first term is the digram searched goto TERM
      else: goto NO_FOUND
TERM:
      while not EOL do:
         get length L of the term
         compute the index of the next term
         get the term
         if term is the term searched goto FOUND
         if index of the next term is at the end of the group goto GROUP
      else: goto NO_FOUND

BULK:
      while not EOL do:
         get the length L of the term
         compute the index of the next term
         get the digram
         if digram is the digram searched:
             get the term
             if term is the term searched goto FOUND
      else: goto NO_FOUND

FOUND:
      get the weight
      return the weight ( exit of this routine )

NO_FOUND:
      return 0 ( exit of this routine )

This algorithm is divided in three parts:
 - GROUP: jump from group of digram to group of digram when the first digram read does not match the searched digram.
- TERM: jump from term to term inside the group of same leading digram when the term does not match the searched term.
- BULK: jump from term to term as soon as the value of S is zero.


Speed optimization (multi-core processor):
The computation of the index of each group, the computation of the index of each term, and the comparison of digrams or terms can be done in parallel . The code should eliminate the race conditions ( in case the comparison is faster than the computation of the indexes ).

The next post will be about the robustness of this structure of data.