Showing posts with label Scientific. Show all posts
Showing posts with label Scientific. Show all posts

Thursday, June 23, 2011

Knowledge-based Programming to Knowledge Representation: The Basic Tasks

We continue from the earlier post. As in the earlier post, much of this post content are taken from Franz Baader's lecture notes (freely available on the web) of which I claim no authorship whatsoever.

Knowledge-based programming can be generalized into an area called knowledge representation. More precisely, a prerequisite for knowledge-based programming is that the relevant knowledge needs, in some way, to be represented symbolically, and thus stored in a machine/computer. Obviously, the way knowledge is represented should enable a machine, or in this case, a general problem solver to process it and answer the queries given to it. Again, following Franz Baader's lecture notes, the following are the important subtasks in knowledge representation:

  1. knowledge acquisition;
  2. symbolic representation;
  3. working with and applying the represented knowledge.

Knowledge acquisition

Knowledge acquisition is a difficult task because essentially, knowledge that we would like to represent is human's knowledge. After all, the notion of knowledge makes much more sense when discussed within human context; it is arguably absurd to talk about knowledge of a table, knowledge of a stone, knowledge of a bird (well it may have something that resembles knowledge, but strictly speaking, we would call it instinct, rather than knowledge), or knowledge of a book (a book may contain knowledge, though in the end what it contains is human's knowledge).

There are various ways to acquire knowledge about the application domain which is needed to solve the relevant problem, for example, by interviewing experts, mining documents, etc. Obviously, this implies that we have to start from a very informal, imprecise, and incomplete description of the domain to a more formal, machine processable specification. This topic is a very broad research area that overlaps with many other research area including learning and knowledge engineering. For our discussion, we will not deal with this issue explicitly.  The reader are recommended to look at other literatures which can be easily found online. From now on, we simply assume that we have a way to acquire knowledge in an effective manner.

Symbolic representation

There are several meaning of the word "representation" if we look into dictionary. We do not intend to discuss them in details, but rather, we understand that representation indicates a connection between things in the real world and things that we use to depict them. For our discussion, symbolic representation is actually a depiction or description of some real world entity that is symbolic in nature. In the research area of knowledge representation and reasoning, the following questions are discussed [Baader, 2005].

  • What is the exact connection between the symbolic representation and the real world entities it is supposed to describe?
  • What formalism is used to represent the knowledge?
  • What is the meaning (semantics) of the chosen formalism?

These questions give rise to a plethora of formalisms, methods, techniques, approaches, whatever --- you name it, to represent knowledge. In a more general sense, knowledge representation can be classified into ones which are symbolic and ones which are not. The latter includes artificial neural network or connectionist systems and evolutionary computation. The other approaches like fuzzy systems and statistical-based systems, although heavily non-symbolic in nature, can be integrated with symbolic approaches in a rather seamless manner. The third question above is, in particular, frequently not applicable (at least in a rather straightforward way) to non-symbolic approaches like artificial neural network. It is undeniable that such systems do work and solve problems in applications robustly and efficiently. However, such systems typically lack semantics. For example, take any artificial neural network system which has been trained for some period of time to classify documents according to their topics. Presumably, the weights of connections between neurons in that system represent the knowledge necessary to perform the classification correctly. Unfortunately, there is no way for us to understand what is the relationship between certain configuration of numerical weights of connections between neurons and the fact that document A has topic X or document B has topic Y.  Such a gap is very difficult to close, despite the efforts that have been made so far, e.g., research in neural-symbolic integration (see e.g., the  7th International Workshop on Neural-Symbolic Learning and Reasoning (NeSy'11), or the "Perspective of Neural Symbolic Integration" book).

For the purpose of our discussion here, we would only concern ourselves with symbolic based systems, more specifically, logic-based knowledge representation (LBKR) systems.  Aside from the above three questions, research in LBKR also investigates the expressivity aspect, i.e., the adequacy of the expressive power of the chosen formalism. The question of expressive power essentially asks what statements can be formulated and what cannot within a given formalism which is restricted to the representational means defined for it. The more expressive a formalism is, the more knowledge can be presented. Of course, such a formalism can be considered adequate only when all the relevant knowledge can be presented. As an example, the sentence

There exists no prime number that is greater than every other prime number

cannot be adequately expressed using propositional Boolean logic that only uses connectives like conjunction (AND), disjunction (OR) and negation (NOT). This example illustrates that the expressive power of propositional logic formalism is not adequate to express the above sentence. On the other hand, it is also a common question to ask whether all of the representational means attributed to the formalism are really needed, that is, whether some of the representational means is redundant. For example, in propositional Boolean logic, it is sufficient to use only conjunction and negation to express all statements that can be expressed using propositional Boolean logic. In other words, the disjunction operator is redundant in the presence of conjunction and negation.

On the semantics, LBKR systems are expected not to depend solely on any procedural semantics. This means that the semantics should never depend on particular programs that are built to do whatever tasks which are assigned to the systems. If this is the case, then the semantics, i.e., the meaning, of knowledge would change if the program is changed. Instead, they should have declarative semantics, hence separating the representation and the programs that are used to process it. A declarative semantics essentially consists of an abstraction of the world that we want to represent together with a mapping from any symbolic expression allowed in the formalism to an element in the abstraction. Such an abstraction is often stated in a form of a set or other algebraic structures. Representational means of the formalism usually allows us to build more complex symbolic expressions from simpler ones. Thus, the mapping given by the semantics typically associates the representational means with some operations on the abstraction. In addition, declarative semantics specifies a notion of "truth" which is used to determine whether a symbolic expression is true in the world induced by the abstraction. Moreover, the relationship between representational means and operations on the abstraction allows for the "truth" of a symbolic expression to actually be computed.

Working with and applying the represented knowledge

LBKR systems, in addition to the above requirements, should allow users to do some kind of manipulation in the form of [Baader, 2005]:

  • adding new knowledge to existing knowledge bases;
  • removing knowledge from a knowledge base;
  • accessing the explicitly stored knowledge;
  • accessing the implicitly stored knowledge

The above activities can be viewed as knowledge management activities which similarly exist for database systems. In fact, in some sense, a (relational) database system can be considered as a form of knowledge-based system. This fact can be easily seen if we see a database as a set of relation which can be expressed as simple first-order logic statements. Also, queries to a database, say stated using SQL, are actually first-order logic statements whose truth are tested against the relations in the database. The feature that a standard database system lacks is the ability to access implicitly stored knowledge. This feature implies that a LBKR system should be able not only to retrieve knowledge that is stored explicitly, but also to deduce implicit knowledge that is implied by the explicitly stored knowledge. Such a feature is called inference mechanism or inference procedure. Referring to my earlier post on "Classical Programming vs. Knowledge-based Programming: Example", the general problem solver mentioned there would be realized here as inference mechanisms. As an example, we use the one from that post; consider the following knowledge base:

[sourcecode language="ruby" light="true" wraplines="false"]

directly-connected(a,b).
directly-connected(a,c).
directly-connected(b,d).
directly-connected(b,e).
directly-connected(c,e).

connected(x,y) if directly-connected(x,y).
connected(x,y) if directly-connected(x,z) and connected(z,y).

[/sourcecode]

Here, directly-connected(a,b) is  explicit knowledge because it is explicitly stated in the knowledge base above, whereas directly-connected(a,c) is implicit knowledge because it is implied and not explicitly stated by the knowledge base.

Wednesday, June 22, 2011

Classical Programming vs. Knowledge-based Programming: Example

Continuing from my last post, let me give you an example on how classical programming differs from knowledge-based programming (the example is taken from Prof. Franz Baader's lecture notes). Consider the acyclic graph in the picture below.

With regards to the above acyclic graph, we would like to solve the following problem: given to node $latex x$ and $latex y$ in the graph, determine whether these two nodes are connected.

In the classical programming, this problem can be solved by giving a procedure that gives you precisely the desired answer, namely "yes" if  both nodes are connected, and "no" otherwise. This procedure might be something like this:

[sourcecode language="ruby" light="true" wraplines="false"]

procedure connected(x,y)
if x = a then
if y = b or y = c then
return true
else
return (connected(b,y) or connected(c,y))
else
if x = b then
if y = d or y = e then
return true
else
return false
else
if x = c then
if y = e then
return true
else
return false
else
return false
[/sourcecode]

It is straightforward to see that if we ask whether $latex e$ is connected to any node, the answer would be false. Now, what if the graph is changed, say by adding a new node $latex f$ and an edge from $latex e$ to $latex f$? Of course, the above procedure will return the wrong answer when we ask whether $latex e$ is connected to $latex f$. We might have to modify the whole program to incorporate this new case.

On the other hand, the knowledge-based programming will solve the above problem in a different way. First, the graph, i.e., the problem description and its restrictions are specified explicitly as the knowledge about graph and the meaning of "connected". For example, the following knowledge base gives a correct description of the graph and the "connectedness" between nodes in the graph.

[sourcecode language="ruby" light="true" wraplines="false"]

directly-connected(a,b).
directly-connected(a,c).
directly-connected(b,d).
directly-connected(b,e).
directly-connected(c,e).

connected(x,y) if directly-connected(x,y).
connected(x,y) if directly-connected(x,z) and connected(z,y).

[/sourcecode]

Next, against the above knowledge base, we give the following query:

[sourcecode language="ruby" light="true" wraplines="false"]

connected(a,b)?

[/sourcecode]

To answer the above query, we simply run a general problem solver and get the answer. Thus, classical programming focuses more on "how" to obtain the solution, while knowledge-based programming would focus more on "what" the solution would be like.

In practice, this distinction may not be as strict as what the example illustrated. Classical programming typically also allows parts of the program to contain the data structures that describe the problem specification, whereas some knowledge-based programming applications encode the knowledge about application in the program using procedural rules.

In knowledge representation and reasoning, one of the main research theme is about formulating and specifying languages that allow users to express knowledge symbolically and developing algorithms which can perform as a general problem solver for queries by users to the knowledge base.

Wednesday, July 20, 2005

Nach Berlin ...

It's been almost a month since my last post. In the meantime it's been a quite busy time for me. Right now is the exam time. I still have two more exams to go, on 28th July and 2nd August. All are written exams. I'm afraid that they will be notoriously difficult, especially on Advanced Logic, since Dr. Nauber that will make the exam questions and checking our answers.

Besides above, from 1st until 3rd July, I was in Berlin for a DAAD scholarship holders meeting. It's an annual meeting organized for DAAD's foreign scholarship holders that in Germany. All scholarship holders whose scholarship period begins at the earliest in the winter semester of last year, are invited for this kind of gathering.

DAAD grants (new) scholarships for about 15000 foreign students a year, thus it's impossible to hold this meeting in one location for all scholarship holders in the entire Germany. Usually the organizers from DAAD organize several meetings for scholarship holders in the neighboring region. In my case, it is for us who reside in Sachsen, Sachsen-Anhalt, Brandenburg, Mecklenburg-Vorpommern and of course the city Berlin itself.

I had a nice time for three days in Berlin, though I admittedly missed my wife, seeing some of my friends invited together with their families. But nevertheless, I enjoyed the programs and the change of scenery from the usually not-so-crowded Dresden. As usual, the program consisted not only of sessions with our mitarbeiter/in from DAAD, but also some lectures. Well I was a little bit disappointed since all of the topics were really closely related with Computer science, but at least there was a lecture that was quite interesting, given by Prof. Raymond J. Dolan from Department of Imaging Neuroscience, University College, London. It's about "Emotion, Feeling and Empathy".

There are two interesting things that he argued, first that women are more inclined to empathy than men. This is especially towards other person that gives bad/unfair treatment to the subject. The experiment proceeded by giving some doses of pain to the unfair person, in the present of a woman/man subject. He argued that although women are unfairly treated, they still show considerable empathy towards the unfair person, i.e., parts of the brain that are active are the area which is closely related to the processing of empathy/simpathy. Meanwhile, men exhibit no activity in that area, but more to the area that is related to anger. Hehehehe I don't really want to delve to the meaning of this, I'll just leave the conclusion to you... :).
The second was the respond to my question to him about the differences between children that are raised by "good" families and "bad" families. What I mean here is that parents are encouraged to give examples of good behavior, including being compassionate to others. And it can be seen that if the parents give this good behavior as examples for their children, it can be expected that the children will have the same tendency after growing up. On answering, he said that still empathical feelings cannot be trained, e.g. by giving examples to children. What we really do is not training empathy, but instead of simpathy. He pointed out subtle difference between those two. Being simpathy is a cognitive process. This means that we can see its realization in the form of good behavior. Meanwhile, empathy is really a feeling inside. You cannot judge a person's empathy from his/her behavior. For example, giving a help to others does not necessearily imply there's empathical reason behind it.

OK, ok, enough about this psychological things, it turns out that Prof. Dolan's wife is a Malaysian. After the lecture we chatted about a few things, and when he understood that I am an Indonesian, he just exclaimed, "really? are you from Jakarta? I'd love to go to Jakarta but haven't got the chance. You know, my wife is from Malaysia. I'll introduce her to you later". I thought it's just for hospitality, but it's not. Later when I went with city tour session to Einstein exhibition, I met him again in the exhibition and this time he really introduced his wife to me.

By the way, this year is exactly a century after Einstein published his most famous quartet of papers on theoretical physics (which one of them was the special relativity), shattering the very foundation of classical Newtonian physics. No wonder, especially in Berlin, this year is celebrated as The Einstein Year, and I was lucky enough to be able to visit Berlin at the time of the exhibition. I even bought a book... :D. I mean this book:

This is nicely done by Denis Brian. It reveals a quite deep account on some aspect of Einstein's private life, which has been obscured to public before. I just finished the half of it, but I recommend this to whomever interested in Einstein. Since Einstein's role in zionism is not small (this might be a rather sensitive topic for some), you can also see and judge by yourself, how zionism means to Einstein. Besides that, it also includes one of thing that was previously obscured: Einstein's pleasure in the company of women and the existence of his illegitimate daughter.

Besides Empathy and Einstein, actually there's a good news for me. DAAD granted an extension to my scholarship for another year. Yayy, this means, hopefully I will be able to bring my wife here in Dresden. Well it's indeed hard to live our life a part from each other. We do really miss each other .. :((.

Thursday, April 21, 2005

Paper...

Barusan baca artikel di http://www.cnn.com/2005/EDUCATION/04/21/academic.hoax.ap/index.html

Ceritanya, Jeremy Stribling, Max Krohn and Dan Aguayo, tiga orang mahasiswa MIT bikin program komputer yang men-generate secara otomatis paper ilmiah tentang ilmu komputer. Hebatnya (atau konyolnya?) iseng-iseng mereka submit di sebuah konferensi internasional, hasilnya... ACCEPTED!!
Padahal papernya bener-bener nggak karuan isinya (at least seperti yang dibilang oleh CNN), dan at least juga saya percaya nih isinya emang nggak karuan. Coba lihat ke:
http://pdos.csail.mit.edu/scigen/
Itu program bikinan Jeremy Stribling dan temen2-nya, buat bikin paper macam yang diberitain di CNN tadi. Coba masukkan nama Anda, terus klik "Generate".
Taadaaa!! Dapat deh satu paper bidang ilmu komputer... :D. Kalo lihat judulnya doang sih meyakinkan... tapi kalo lihat isinya, buat orang yang ngerti ilmu komputer pasti langsung tau kalo paper hasil buatan mesin itu bener-bener ngaco.... :D.
Kalau gini panitia konferensinya pasti ngasal. Kemungkinan besar sih paper yang mereka terima nggak pernah bener2 dibaca... lirik judulnya sekilas terus langsung terima aja... *geleng-geleng kepala*