Prenex Normal Form

In First Order Predicate Logic ( FOPL ), one can represent an expression using the operators

For any X, Expression

Exists X such that Expression.

Where Expression is a logic expression , either a predicate or a combination of logic operators and other expressions.

In order to represent an Expression in Prenex Normal Form, one must do some transformation. For an expression to be in Prenex Normal Form, all the "Any" and "Exists" Logical operators must precede a whole stand-alone expression. For example, expression

(Any X in P(X) ) Or ( Exists Y in Q(Y)) it''s not in Prenex Normal Form.

Expression

(Any X in ( P(X) and Q (Y) ) ) is in Prenex Normal Form .

Prenex Normal Form is useful in Knowledge representation for obvious reasons: memorizing in computer memory, specific attributes: We evaluate first the "Any"/"Exists" operators and the following expression can be substituted to simple expression.

To convert a normal expression to Prenex Normal Form, we consider the following transformation rules:

( Any X in Expr) or (Another_Expr) changes to (Any X in ( Expr or Another_Expr )) with mentioning the fact that X has no free appearances in Another_Expr ( if free they are renamed to another free variable )

( Any X in Expr) and (Another_Expr) changes to (Any X in (Expr and Another_Expr )) with same mentioning.

The same rules apply to Exists operator.

Association rule Mining

Let''s say we want to mine some data for our supermarket, given as example previously.

A customer from a supermarket buys several products. This are categorical data. Let''s say he buys Honey, Milk, Sugar, Bread. We want to determine if other customers buy these items ( or part of them ), and if it''s possible to tell that one or more of these products determines the others. In other words, if for example a customer buys Milk and Sugar, it will also buy Honey and Bread.

First of all let''s see what other customers bought:

Customer 2: Milk, Paper, Honey

Customer 3: Sugar, Honey, Milk, Beer

Customer 4: Beer, Chips, Bread

Customer 5: Milk, Honey, Bread

We define an association rule as two related parts of an item set, such that first part determines the second part.

Example : Milk -> Sugar, Honey.

An itemset is a set of items such that each item is present only once.

For a given itemset, one can create multiple association rules.

An association rule has a support and a confidence. The support is defined as the number of customers ( transactions ) that bought all the items in the item set divided by the total number of transatctions. The confidence is defined as the number of transactions that include the first part of the association rule and the second part divided by total number of transactions that include the first part.

The support for our rule Milk -> Sugar, Honey is 2/5 e.g. 40 %. This is because Customer 1 and 3 have in their itemsets all the 3 items from our rule, and the total number of transactions is 5.

The confidence for our rule is 2/4 e.g. 50 % , because there are 4 customers that have Milk and only 2 which have Milk and Sugar, Honey.

For our rule we can say that buying Milk determines the buying of Sugar and Honey with a support of 40 % and a confidence of 50 %.

Parameter evaluation in programming languages

How does parameter evaluation influences programming?

First of all how are possible evaluations?

Method 1: Evaluate each parameter at a time and then pass the result to the next level ( called function for example ). In this case parameters are send by value.

Method 2: Send the parameters as they are, and let the next level evaluate them, if necessary. In this case parameters are send by name.

At first glance, there is not an important difference, however, looking closer we may notice:

- Sending parameters by name implies a bigger stack because all calls need to store partial results and all unapplied parameters

- Sending parameters by name implies having evaluation at a later time, which in state-full programming languages/environments this may bring up some problems. On stateless situations evaluation time is non significant.

- Sending parameters by value may bring unnecessary computations because we may not need the evaluation of certain parameters.

Here is an example written in C programming language

int myFunc( int parameter)

{

return 0;

}

 

In this case the evaluation of parameter, in the case of the call myFunc( someOtherFunc(some params )), computing the parameter value is useless.

Lets say someOtherFunc does the following:

int someOtherFunc( some params )

{

while (1) ;

return 0;

}

In this case, evaluation by value will have a serious problem because program will never end.

However, evaluation by name will end in a normal fashion because there is no need to call someOtherFunc.

Stateless programming languages can fully take advantage of this lazy-evaluation, but on state-full situations, someOtherFunc may change environment so it''s evaluation can become mandatory.

The C programming language uses applicative evaluation, which is by value, while functional programming languages like Haskell use lazy-evaluation.

Knowledge representation Concepts part 1

What is knowledge? In our colloquial thinking, it''s something that "we know" , mostly information.

For computers, this might not be as easy as it seems. Knowledge can be split in some categories:

- Common sense knowledge: We know that if we throw a rock on a window, it will break. Can a computer actually know this if we tell him about the window and the rock? Does the computer realize that the rock will eventually fall down to the earth ? In common sense, we have a lot of knowledge that we take for granted, like physics laws, which may not be as intuitive for computers as they are for us. To give a computer a "common sense knowledge" implies a lot of factors that we may or may not be aware of. In computer decision process, minor things can be of extreme importance.

- Logic knowledge: We know that if we add one apple to another apple we obtain two apples. This is quite logical and it''s appliance can be extended for various problems and situations. This is also fair to implement in a computer knowledge database.

Computers cannot have a full set of common sense knowledge. How can we implement a basic system that can be extended so that computer share a bit of our understanding? One idea is too use a rule-based system.

If thrown(rock, window) then break(window)

Actions, predicates, simple logic can be useful in such situations.

Objects can be implemented into classes, actions can move from one state to another.

However, knowledge representation is a very important part in having a basic start for creating an artificial intelligence and designing a system that will respond fast to stimuli and give an adequate response as well.

Get more Joomla!® Templates and Joomla!® Forms From Crosstec