Dizan Vasquez
email: dizan.vasquez@inria.fr

Novel Planning-based Algorithms for Human Motion Prediction

Human motion prediction from visual tracking is a challenging problem with a wide array of applications such as robotics, video surveillance and situation understanding. Recently, planning-based methods -which assume that people move by planning over a cost function-have emerged as one of the most promising alternatives. Nevertheless, state of the art planning based algorithms have shortcomings regarding their computational complexity and ability to predict for arbitrary time intervals. This paper addresses these shortcomings by leveraging alternative planning techniques (Fast Marching Method) and formulating efficient algorithms for goal estimation and full spatiotemporal prediction with lower complexity than comparable approaches. In preliminary experiments, the proposed method significantly outperforms the accuracy of the current state-of-the-art approach while reducing the computation time by a factor of 30 using a parallel version of our algorithm.

I. INTRODUCTION

In recent years, mobile robotics has seen an important shift in the way it considers humans. People are no longer seen as mere inanimate obstacles to avoid, but as essential environmental elements to interact and collaborate with. Moreover, in most cases, the safety, comfort and, in general, the well-being of people should take precedence over the robot's task. Hence, in order to successfully cohabit with humans, robots require models to estimate people's future position and velocity and plan their own motion accordingly. This has motivated the emergence of a significant number of motion prediction approaches in the last ten years [START_REF] Lefèvre | A survey on motion prediction and risk assessment for intelligent vehicles[END_REF]. The problem has also been widely studied by the computer vision community in areas such as video surveillance [START_REF] Morris | A survey of vision-based trajectory learning and analysis for surveillance[END_REF] and multiple object tracking [START_REF] Gong | Multi-hypothesis motion planning for visual object tracking[END_REF].

A closer look at the literature shows that proposed methods actually address different sub-problems. For instance, Goal Estimation [START_REF] Ferrer | Bayesian human motion intentionality prediction in urban environments[END_REF] focuses on determining the final place in the environment that an agent aims to reach. In this paper, we address the problem of estimating the agent position at specific future times, which we will henceforth call Spatiotemporal State Prediction (Fig. 1). Previous approaches belonging to this category differ on the kind of variables which they take into account: while early work was primarily based on kinodynamic variables [START_REF] Zhu | A stochastic algorithm for obstacle motion prediction in visual guidance of robot motion[END_REF], later approaches introduced further elements such as: interaction with other dynamic agents [START_REF] Kuderer | Featurebased prediction of trajectories for socially compliant navigation[END_REF], [START_REF] Kim | Predicting pedestrian trajectories using velocity-space reasoning[END_REF]; typical motion patterns [START_REF] Bennewitz | Learning motion patterns of people for compliant robot motion[END_REF], [START_REF] Vasquez | Growing hidden markov models: a tool for incremental learning and prediction of motion[END_REF]; static features of the environment such as walls [START_REF] Ziebart | Planning-based prediction for pedestrians[END_REF], [START_REF] Kitani | Activity forecasting[END_REF]; or all of the previous factors [START_REF] Yamaguchi | Who are you with and where are you going?[END_REF], [START_REF] Elfring | Learning intentions for improved human motion prediction[END_REF]. This paper is close in spirit to the planning-based approach of Ziebart and Kitani [START_REF] Ziebart | Planning-based prediction for pedestrians[END_REF], [START_REF] Kitani | Activity forecasting[END_REF] which extends Markov Decision Processes to predict motion assuming a static environment with known destinations. Our paper addresses two drawbacks of those works: their high computational complexity and their limited capability to predict for a specific time. Our general contribution is a motion prediction framework enabling any cost-to-go planning algorithm to represent the uncertainty related to human motion. Our specific contributions are:

1) A simple and efficient goal estimation procedure based on the gradient of the local cost-to-go function. 2) A sound mechanism to fuse the output of different spatiotemporal state predictors based on "Bayesian Fusion with Diagnosis" [START_REF] Pradalier | Expressing bayesian fusion as a product of distributions: Applications in robotics[END_REF]. 3) Two spatiotemporal motion models: one based on the agent's velocity and the other on its estimated goal. 4) Experimental validation of our approach against a stateof-the-art algorithm using tracking data from the VIRAT data set [START_REF] Oh | A large-scale benchmark dataset for event recognition in surveillance video[END_REF].

The rest of this paper is structured as follows: Sec. II describes the ideas behind planning based approaches and the current bottlenecks motivating our work; Sec. III describes our general probabilistic model and other theoretical contributions; experiments and their results are presented in Sec. IV; finally, we present our conclusions and outlook in Sec. V.

II. PLANNING-BASED PREDICTION APPROACHES

Planning-based approaches are built around the assumption that people and other intelligent agents, when they move, minimize a cost function which depends on the context. Thus, if the cost function and the context are known, future motion may be predicted using the vast arsenal of existing motion planning algorithms.

Besides its intuitive appeal, one of the main advantages of this assumption is that it lays down a sound theoretical framework to deal with the different variables which may be considered relevant to human motion. Nonetheless, this formulation implies at least two underlying challenges: (a) the trade-off between the computational cost of motion planning algorithms and the real-time requirements of many applications; and (b) the difficult problem of expressing the cost function and tunning its parameters.

This paper focuses on the first challenge and assumes that the cost function is known a priori1 . This choice is motivated by our intended application, autonomous robot navigation, where opportune predictions are critical to plan safe motion. Such real-time requirements are also important for other applications such as motion tracking.

We will focus our discussion on the work of Kitani et al. [START_REF] Ziebart | Planning-based prediction for pedestrians[END_REF], [START_REF] Kitani | Activity forecasting[END_REF] which, from our point of view, summarizes the state of the art on planning-based prediction. The interested reader is referred to [START_REF] Morris | A survey of vision-based trajectory learning and analysis for surveillance[END_REF], [START_REF] Lefèvre | A survey on motion prediction and risk assessment for intelligent vehicles[END_REF] for comprehensive reviews of motion prediction approaches from the computer vision and robotics perspectives.

The works of Ziebart and Kitani are based on the use of a Markov Decision Process (MDP) defined over a regular discretization (i.e. grid) of the agent's workspace in order to infer goals and predict motion. They model cost as a linear combination of features (presence of obstacles, kind of terrain, etc.) which encode the context and may be extracted from camera images using semantic segmentation approaches. They apply Inverse Reinforcement Learning to estimate the combination weights which, in theory, can then be used to compute the cost for a different environment without further learning. Despite its generality, this approach has the following important drawbacks concerning prediction: (a) its high computational complexity due to the use of an iterative inference algorithm requiring an unbounded, but usually consequent, number of iterations; (b) its limited ability to predict the state for a specific time: temporal predictions are only addressed in [START_REF] Ziebart | Planning-based prediction for pedestrians[END_REF], where they propose a method that, essentially, assumes that all agents move at the same speed; and (c) they assume that, while moving, agents are not able to change their intended destination.

Despite these drawbacks, this approach -which we will henceforth denote as MDPMP (Markov Decision Process Motion Prediction)-is very attractive because of its use of a unified formalism for both planning and uncertainty modeling. With this paper, we aim to propose an alternative which keeps these advantages while addressing the corresponding weaknesses.

III. PROPOSED APPROACH

Our approach aims to propose solutions to the three stated weaknesses of MDPMP, namely:

1) High computational complexity. This is dealt with by using the Fast Marching Method (FMM) [START_REF] Tsitsiklis | Efficient algorithms for globally optimal trajectories[END_REF], [START_REF] Sethian | Fast marching methods[END_REF] an efficient deterministic planning algorithm which computes the cost-to-go to a given location for every cell of a grid representing the agent's workspace. This grid is then used in a novel goal prediction algorithm (Sec. III-B) and to produce a path-like prediction equivalent to the output of MDPMP (Sec. III-D).

2) Limited ability to model the temporal evolution along

the predicted path: this is addressed through the use of a velocity-dependent probabilistic motion model which is used to estimate a probability distribution of the future agent's position (Sec. III-C). This is then fused with the cost-based model proposed in Sec. III-D to produce a full spatiotemporal prediction (Sec. III-E). 3) Constant-goal assumption. We propose a gradient-based goal prediction approach (Sec. III-B) which does not rely on filtering, making it capable of quickly recognizing intended destination changes as they happen. In the rest of this section, we describe our global probabilistic model and the notation used throughout this document.

A. Probabilistic model and Notation

In its most basic form, state prediction aims to compute the probability distribution of the future agent's position knowing the current one (Fig. 1). This may be expressed as:

P ( ⃗ X t+H | ⃗ X t ), H > 0 (1)
where ⃗ X t and ⃗ X t+H are vectors in R 2 representing the agent's positions at times t and t + H (i.e. current and future positions). H is often called the prediction lookahead or time horizon.

The proposed approach augments this basic model with the following variables: Having defined our six variables (including ⃗ X t , ⃗ X t+H ) we may now describe the Joint Probability Distribution (JPD) of our global model (Fig. 2):

• Velocity ⃗ V t ∈ R 2 : The agent's velocity at time t. • Goal G t ∈ 1, • • •
P ( ⃗ Xt, ⃗ Xt+H , ⃗ Vt, Gt, IV , IC ) = (2)
P ( ⃗ Xt)P ( ⃗ Xt+H ) (3)
×P (Gt)P ( ⃗ Vt| ⃗ Xt, Gt) (4) ×P (IV | ⃗ Xt, ⃗ Xt+H , ⃗ Vt) (5) ×P (IC | ⃗ Xt, ⃗ Xt+H , Gt) (6)
The JPD can be seen as the composition of four different models:

• The position priors (3), modeled as uniform probability distributions over the agent's workspace. • Goal Prediction (4), described in Sec. III-B.

• The Velocity-based prediction model [START_REF] Zhu | A stochastic algorithm for obstacle motion prediction in visual guidance of robot motion[END_REF], described in Sec. III-C • The Cost-based prediction model [START_REF] Kuderer | Featurebased prediction of trajectories for socially compliant navigation[END_REF], described in Sec. III-D It is straightforward to apply Bayesian inference to predict the future state from the current state and velocity (setting

I V = I C = 1): P ( ⃗ X t+H | ⃗ Xt, ⃗ Vt, I V , I C ) = 1 Z P (I V = 1| ⃗ Xt, ⃗ X t+H , ⃗ Vt) × |G| ∑ g=1 P (Gt = g)P ( ⃗ Vt| ⃗ Xt, Gt = g)P (I C = 1| ⃗ Xt, ⃗ X t+H , Gt = g) ( 7
)
where Z is a normalization variable. The remaining subsections describe the individual submodels of Eq. (2).

B. Goal Prediction

Our Goal Prediction model is based on the use of a planning approach to compute the minimum cost-to-go C ⃗ Xi→Gg from a given position ⃗ X i to a given goal region G g in the environment. For grid-based representations of the agent's workspace and non-uniform cost functions, Dijkstra's algorithm is often used to compute the cost-to-go from every cell to a given region. Such approach is very efficient, having run-time complexity of O(n log n), where n is the number of cells in the grid. However, Dijkstra's algorithm suffers from severe aliasing problems (i.e. digitization bias) due to its coarse discretization on the number of directions (usually four or eight). Instead, we use the Fast Marching Method [START_REF] Tsitsiklis | Efficient algorithms for globally optimal trajectories[END_REF], [START_REF] Sethian | Fast marching methods[END_REF] which is much more accurate while keeping the same run-time complexity.

In addition to the cost-to-go for every goal, our approach also computes, for every cell in the grid, the unitary gradient vector ∇Gt of the cost-to-go function using second order differences and normalizing the result. Since we assume that neither the costmap nor the set of existing goals change, it is possible to compute all these values during the initialization stage of the algorithm, instead of doing it at every time step.

Our goal prediction approach is based on the assumption that the orientation of an agent aiming to reach goal G t , is normally distributed around the optimal direction, given by the negative gradient vector. This yields the following model:

P ( ⃗ V t | ⃗ X t , G t ) = N ( ⃗ V t ; µ G ( ⃗ X t , ⃗ V t ), Σ 2 G ) (8)
where N denotes the normal distribution, the covariance Σ 2 G is a system parameter expressing the sensibility to misalignments, and the mean value:

µ G ( ⃗ X t , ⃗ V t ) = -∇Gt ( ⃗ X t ) ⃗ V t (9)
is the optimal direction multiplied by the velocity's norm as a way of penalizing higher speeds which will lead to the object getting farther away from the goal when the vectors are misaligned. This model may be seen as a predictive version of the approach proposed in [START_REF] Treuille | Continuum crowds[END_REF] for crowd simulation. An advantage of using the cost-to-go gradient is that, as opposed to MPDMP, it is possible to represent time-varying goals. On the other hand, this means that our approach does not rely on filtering, potentially making it less robust to noise. In practice, however, velocities are often computed upstream (i.e. by the tracking algorithm) using some sort of filter, considerably limiting this problem.

C. Velocity-Based Model

As its name indicates, the velocity-based model predicts the future position on the basis of the current position and velocity. It assumes that the agent will keep its current speed and that the total distance D( ⃗ X t , ⃗ X t+H ) it will travel during the time horizon is normally distributed, with mean:

µ D ( ⃗ V t ) = H ⃗ V t ( 10
)
So that the full model is:

P ( ⃗ X t+H | ⃗ X t , ⃗ V t ) = N ( D( ⃗ X t , ⃗ X t+H ); µ D ( ⃗ V t ), σ 2 D ) (11)
where σ 2 D is a model parameter expressing the uncertainty on the predicted distance and D(•) is the cost-corrected distance, which accounts for the fact that minimum cost paths avoid high-cost regions of the environment.

For a homogeneous cost function, the corrected distance is just the Euclidean distance, and the distribution is shaped as a circle centered in the current position ⃗ X t (Fig. 3b).

and sound solution to this precise problem, which may be summarized as follows: for every fused model, we introduce a binary consistency variable with the following semantics: a value of one means that our model is consistent with the observed data and a value of zero means that it is not.

What is more relevant in our case, is that it provides a straightforward way of fusing the models by simply multiplying them together, as illustrated by Fig. 3.

In order to apply it to our particular model, we simply recast [START_REF] Kitani | Activity forecasting[END_REF] as:

P (I V = 1| ⃗ Xt, ⃗ Vt, ⃗ X t+H ) = N ( D( ⃗ Xt -⃗ X t+H ); µ D ( ⃗ Vt), σ 2 D ) (16)
which is the parametric form for [START_REF] Zhu | A stochastic algorithm for obstacle motion prediction in visual guidance of robot motion[END_REF].

Similarly, for [START_REF] Pradalier | Expressing bayesian fusion as a product of distributions: Applications in robotics[END_REF]:

P (I C = 1| ⃗ Xt, Gt, ⃗ X t+H ) = N ( C ⃗ Xt→ ⃗ X t+H →Gt ; µ C ( ⃗ Xt, Gt), σ 2 C ) (17)
which is the parameteric form for [START_REF] Kuderer | Featurebased prediction of trajectories for socially compliant navigation[END_REF].

Given that both I V and I C are binary variables, the corresponding expressions for I V = 0 and I C = 0 may be obtained by subtracting the above probabilities from one. In our case, however, this is not necessary, since we simply set both variables to one querying the model to indicate that the model is consistent (which we believe it is) as indicated in Eq. [START_REF] Kim | Predicting pedestrian trajectories using velocity-space reasoning[END_REF].

IV. EXPERIMENTS

We have conducted a preliminary comparison of our approach against MDPMP using the data set provided by Kitani [19] which is a subset of the one used in [START_REF] Kitani | Activity forecasting[END_REF], which comes from the VIRAT ground video surveillance data set [START_REF] Oh | A large-scale benchmark dataset for event recognition in surveillance video[END_REF]. The published data contains 14 trajectories extracted from video recorded in a parking lot (Fig. 4). It includes the following information:

• Trajectories, obtained from a visual tracker and consisting of sequences of agent positions. Positions have been projected into the floor plane. In order to smooth them and compute velocities, we have post-processed this data by applying a standard Kalman filter. The resulting sequences have the form:

D i = {( ⃗ X 1 , ⃗ V 1 ), • • • , ( ⃗ X Ti , ⃗ V Ti )}
where T i is the total number of points in trajectory i. • Cost functions, the current reward values of the static environment are computed as a linear combination of Fig. 4. Two examples of our results on the VIRAT data set(one per row). First column: video sample. Second column: reward heat map and five predicted trajectories sampled from each approach (blue for MPDMP, magenta for the proposed approach). Third column: MPDMP forecast distribution heat map. Fourth column: Proposed approach forecast distribution heat map. The white line in columns 2 through 4 correspond to the actual trajectory followed by the agent.

features which encode the context. The features have been obtained by post-processing the output of a semantic segmentation algorithm [START_REF] Munoz | Stacked hierarchical labeling[END_REF] on the floor-projected input images. The weights have been learned using an inverse reinforcement learning approach described in [START_REF] Kitani | Activity forecasting[END_REF]. Finally, since our algorithm requires strictly positive cost values, the real-valued reward grid has been converted by applying the following identity:

C ij = 1/(ϵ + R ij -min l,m∈grid R lm ) (18)
Where C ij and R ij are the cost and the reward values of cell i, j and ϵ is a small regularization value (0.1 in our experiments) to avoid division by zero.

A. Implementation Details.

We have implemented the proposed approach in Python and C++. We have also developed an OpenCL-based GPUaccelerated version of the approach which, in our experiments, reduces the computation time by a factor of 5. For our algorithm, parameter values have been set by trial-anderror: Σ 2 G = 0.2 and σ 2 C = 30. For MPDMP, we have used the code and parameters provided by the authors [START_REF] Kitani | Activity forecasting data set[END_REF].

We are currently cleaning up our code and it will be made publicly available at the time of the final version of this paper, if it is accepted.

B. Evaluation metrics.

The forecast distribution obtained in MPDMP is equivalent to the cost-based model of eq. 14 and both can be interpreted as representing the probability of an agent visiting a given cell when traveling from its current pose towards a destination. In our experiments, we aim to evaluate the accuracy of these distributions by comparing them against the actual observed motion. This is done by taking, for every trajectory in the data set, the start and end position and using the respective algorithms to compute the forecast distributions (third and fourth columns of Fig. 4), which are then compared against the complete input trajectory using the following metrics:

• Negative log-loss (NLL): measures the expected loglikelihood of a trajectory given the model. In the case of MPDMP, it is computed as:

N LL(Di) = E π( ⃗ V | ⃗ X) [ -log ∏ t π( ⃗ Vt| ⃗ Xt) ] (19)
while, for our approach, it is computed from eq. 8 as:

N LL(Di) = E P ( ⃗ V | ⃗ X,G) [ -log ∏ t P ( ⃗ Vt| ⃗ Xt, Gt) ] (20)
in order to have a fair comparison with the 8-action MPDMP policy, we have discretized P ( ⃗ V t | ⃗ X t , G t ) into 8 values at intervals of π 4 rad, with the initial angle aligned with the local gradient vector ∇Gt ( ⃗ X t ). • Modified Hausdorff Distance (MHD) [START_REF] Dubuisson | A modified hausdorff distance for object matching[END_REF]: used by Kitani et al. as an estimation of the distance between two trajectories. • Position negative log likelihood (PNLL): a distanceonly spatial evaluation criterion like the MHD has the drawback that a high-cost trajectory and a low-cost one which are equidistant to the reference trajectory would have the same score. In order to address this problem, we propose to use the PNLL, defined as:

P N LL(Di) = EF [ -log ∏ t F ⃗ X t ] (21)
which is the expected value of the normalized forecast distribution F -obtained by normalizing the respective forecast/cost-based model grid-and F ⃗ Xt denotes the value of the cell containing ⃗ X t . • Time: the required time to compute the forecast distribution, excluding all precomputed values. Since we have no parallel version of MPDMP, we are using the sequential version of our algorithm in order to be fair.

C. Results.

Our results, summarized in Table I, show that, in our experiments, the proposed approach outperforms MDPMP's accuracy while requiring considerably less computation time. Moreover, the computed p-values indicate that our results are significant, with the possible exception of the MHD metric, whose score is slightly higher than the our assumed significance level of 0.05. The accuracy difference may be better understood by looking at Fig. 4. We can see that our approach yields forecast distributions which are relatively wide, while MPDMP probabilities are much more less spread out. In consequence, they yield bad NLL and PLL scores when the actual trajectory is not in the narrow high-probability band. For instance, we can see that the actual agent trajectory of row one in Fig. 4 cannot be explained by the MPDMP forecast distribution, while in the proposed approach it has a low but significant probability. Similarly, in the second example we see that MPDMP completely excludes the possibility that the agent passes in front of the vehicle (lower part of the image), which is not the case for the proposed approach.

There is, however, at least one case in which our approach does not perform as well as MPDMP. It happens when the agent suddenly becomes partially obstructed or the other way around, leading to wrong velocity estimates which, given our algorithm's lack of filtering, are immediately reflected in the prediction. Yet, this problem is often corrected after a couple of frames.

Finally, we would like to stress out that these are preliminary results. Notably, we need to conduct further experiments to assess the respective differences concerning goal estimation.

V. CONCLUSIONS This paper has introduced a novel approach for motion prediction allowing for full spatiotemporal prediction of human motion. Experimental results are very promising with our approach consistently outperforming the state-of-the-art alternative in terms of accuracy. As for computational cost, the sequential version of our algorithm ran 6 times faster than MPDMP while the speed up was of 30 times for the parallel version.

Current work focuses in two main aspects: (a) peforming more extensive experiments on real robots and evaluating goal prediction; and (b) improving the cost-based model, in particular by using a lognormal distribution instead of a normal one in order to take into acount the fact that, by definition, no trajectory may have a cost-to-go that is inferior to the optimal. Future work will follow three main directions: (a) extending the framework to realize costmap learning à la Inverse Optimal Control; and (b) take advantage of the very fast prediction times (10ms per prediction for the parallel version) in order to address the more complex and realistic case of agent interaction.

Fig. 1 .

 1 Fig. 1. Example of spatiotemporal state prediction for a single agent, indicating its current and future position after 8 seconds (green and yellow boxes) as well as the predicted position probability and its maximum value (blue box).

Fig. 2 .

 2 Fig. 2. Graphical model of the proposed JPD. For prediction, the observed variables are the current position and velocity (yellow nodes) the output variable is the predicted position (orange node), latent variables include the goal (gray node) and the consistency variables (blue nodes).

  , |G|: The agent's intended goal at time t. The time sub-index indicates that we assume that the agent may change its intentions while it is moving. |G| is the total number of goals.

• Velocity model consistency variable I V ∈ 0, 1: A binary variable indicating whether our velocity model is consistent with the real velocity of the agent. As explained in Sec. III-E, this kind of variable is part of the "Bayesian Fusion with Diagnosis" formalism.

• Cost model consistency variable I C ∈ 0, 1: Another consistency variable for model fusion indicating whether our path cost model is consistent with the real cost incurred by the agent.

TABLE I METRIC

 I SCORES (LOWER IS BETTER)

	Metric	MDPMP Proposed	p-value
	NLL	1.38	0.83	6.8 × 10 -5
	MHD	25.04	20.62	5.1 × 10 -2
	PNLL	16.08	9.82	5.4 × 10 -4
	Time	0.2 s	0.03 s 1.5 × 10 -11

For an example of cost function modeling and learning, we refer the reader to[START_REF] Ziebart | Planning-based prediction for pedestrians[END_REF].

An alternative to a normal distribution is discussed in Sec. V

For non-homogeneous cost-functions, we assume that the agent will cover a shorter distance if the average cost of its path is higher than that of its current position, but it will keep its speed otherwise:

where L is the side of a grid's cell, C ⃗ Xi→ ⃗ Xj is the cost to go from ⃗ X i to ⃗ X j , and M( ⃗ X i ) is the value of the costmap at ⃗ X i .

D. Cost-Based Model

Our cost-based model aims to compute the probability that an agent passes through position ⃗ X t+H when traveling from its current position ⃗ X t to a goal G t . The key hypothesis is that this probability depends on the total cost of the trajectory C ⃗ Xt→ ⃗ X t+H →Gt . In particular, we assume trajectories to be normally distributed around the optimal cost 2 :

according to the following expression:

where σ 2 C is a model parameter which regulates the width of the path towards the goal.

The cost of the path that goes from ⃗ X t to G t passing through ⃗ X t+H may be efficiently computed thanks to the triangle's inequality as the sum of the two partial costs:

Since the first term has been precomputed (c.f. Sec. III-B), we only need to compute the second one. Assuming that costs are symmetrical (i.e.

Xi ), this only requires executing the planning algorithm once per prediction step for the entire grid.

E. Model Fusion

As they are formulated, both the cost-based model of Sec. III-D and the velocity-based one of Sec. III-C have the same dependent (i.e. left-side) variable, making it impossible to put them together in a joint probability decomposition. Bayesian Fusion with Diagnosis [START_REF] Pradalier | Expressing bayesian fusion as a product of distributions: Applications in robotics[END_REF], provides an elegant


Konstantin M Golubev
email: gkm-ekp@users.sf.net

Overview of AI Research History in USSR and Ukraine Up-to-date Just-In-Time Knowledge Concept

Keywords: artificial intelligence, USSR, Ukraine, adaptive learning, just-intime knowledge, general knowledge machine, electronic knowledge publishing

This paper contains a short description of AI history in USSR and in Ukraine. It describes also a state-of-the-art approach to intellectual activity support called Adaptive Learning based on the Just-In-Time Knowledge concept. It's kind of the Artificial Intelligence and Knowledge Management fusion.

Introduction

The history of computing and Artificial Intelligence in particular in URSS and Ukraine is not widely known. One reason is the publication language which was mainly Russian. As not a historian by profession, but taking part in this research, we wish to share with the lecturers the contribution of remarkable people and ideas born in Soviet times in a hope that it could be interesting and inspiring.

It is followed by a description of the General Knowledge Machine Group research work, based on the previous experience and a new insight. It represents an original approach to knowledge presentation and learning developed in Kiev, Ukraine. Described by some as the "Soviet Alan Turing," Sergey Lebedev had been thinking about computing as far back as the 1930's, until interrupted by war. In 1946 he was made director of Kyiv's Institute of Electrical Engineering. After the second war some stories of "electronic brains" in the West began to circulate and his interest in computing re-vived. Initially, Lebedev's superiors were skeptical, and some in his team felt working on a "calculator"-how they thought of a computer-was a step backward compared to electrical and space systems research. Lebedev pressed on regardless, eventually finding funding from the Rocketry department and space to work in a derelict former monastery in Feofania, on the outskirts of Kyiv.

Work on MESM got going properly at the end of 1948 and, considering the challenges, the rate of progress was remarkable. Ukraine was still struggling to recover from the devastation of its occupation during WWII, and many of Kyiv's buildings were in ruins. The monastery in Feofania was among the buildings destroyed during the war, so the MESM team had to build their working quarters from scratch-the laboratory, metalworking shop, even the power station that would provide electricity. Although small-just 20 people-the team was extraordinarily committed. They worked in shifts 24 hours a day and many lived in rooms above the laboratory. MESM ran its first program on November 6, 1950, and went into full-time operation in 1951. In 1952, MESM was used for top-secret calculations relating to rocketry and nuclear bombs, and continued to aid the Institute's research right up to 1957. By then, Lebedev had moved to Moscow to lead the construction of the next generation of Soviet supercomputers, cementing his place as a giant of European computing. As for MESM, it met a more prosaic fate-broken into parts and studied by engineering students in the labs at Kyiv's Polytechnic Institute". [START_REF] Teilhard De Chardin | La place de l'homme dans la nature[END_REF] "Lebedev's interest in the digital computer engineering was not accidental. During the first 20 years of his creative career (until 1946) Lebedev worked in the field of power engineering and he constantly faced the necessity to do complex calculations. He successfully tried to automate them using analog devices, but quickly realized that the abilities of these techniques were limited.

His scientific work started with the vacuum tube machines that carried out ten thousands operations. At the time they were supercomputers. Computers M40 and M50, created in 1958 and 1959, were the most fast-acting computers in the world. With the advent of semiconductors and magnetic elements S.Lebedev switched to the elaboration of the second generation supercomputers. The 1967 BESM-6, with a million of operations per second efficiency, was manufactured for 17 years. The best computer facilities in the USSR were equipped with this machine. The BESM-6 took a worthy place in the world computer building. In 1972 London Museum of Science bought the machine to save it for the history. Lebedev's bright scientific career was concluded with construction of the supercomputers based on integrated circuits (microchip) devices that managed millions operations per second. Two of them after update are still in use in anti-missile and anti-airplane defense systems. Every computer was a new step in computer engineering. Every next one was more productive, more reliable and suitable in exploitation. The main principle of machines construction was paralleling of the calculation process. In MESM and BESM they used arithmetic parallel devices for this purpose. In M-20, M-40 and M-50 external devices worked in parallel with a processor. Conveyer calculation method (Lebedev called it water-pipe) was introduced into BESM-6. In the following computer models they used multiple processors and other improvements. All the machines projected under Lebedev's direction were on big serial production in the USSR.

The pioneering work of Lebedev contributed into the formation of powerful computer industry. The Institute of Precision Mechanics and Computer Engineering Academy of Science of the USSR, headed by Lebedev, became the leading one in the country. In 1950s -1970s its achievements were as significant as ones of the American company IBM.

Characterizing scientific attainments of S.Lebedev, the President of National Academy of Science of Ukraine Boris Paton stressed out: "We would always be proud that in our very Academy of Science of Ukraine, in our beloved Kiev, the Lebedev's talent unfolded to become a prominent scientist in the field of computer engineering and mathematics, and the largest computer-based systems. He founded the famous school of thought in the field of computer science in Kiev. V.Glushkov carried on his work. And now we have productive V.Glushkov Institute of Cybernetics, NASU, one among the largest in the world.

One of Lebedev's wonderful qualities was his care of and trust to the youth. He put them in charge of solving the most difficult problems. He possessed an outstanding pedagogical talent. A lot of his disciples became prominent scientists. They developed their own scientific schools.

His whole life is a heroic example of the devotion to science and to his people. He always aspired to combine noble science with practice and engineering tasks.

He lived and worked in the period of stormy development of electronics, computer engineering, rocket production, space exploration and atomic energy. Being a patriot of his country, Lebedev participated in the biggest projects of I.Kurchatov, S.Korolyov and M.Keldysh, who created a reliable shield for the Motherland. In all these works the computers constructed by Lebedev played a special role.

His prominent works will enrich the treasury of the world science and technology, and his name will stand together with the names of the greatest scientists forever."

Due to the Lebedev's extraordinary modesty and classified nature of the significant part of his works, it is very little known in the western countries about this genius scientists. Until the end of 1990s there were almost no substantial publications. In the 1995 book "Computer Pioneers" by John Lee, which contains over 200 biographies of the scientists, Lebedev's name is not mentioned.

Only on 95th birthday anniversary his achievements were recognized abroad. He was recognized as a pioneer of computer engineering with a medal from the International Computer Society. He greatly influenced many other fields of theoretical computer science (including the theory of programming and artificial intelligence) as well as its applications in USSR. The significance of scientist's work is not always recognized fully by contemporaries. Real evaluation appears much later, when the scientific results and the expressed ideas are verified by the time. The prominent contribution of Victor Glushkov into mathematics, cybernetics and computer engineering was highly appreciated when he was still alive. But with the time passing by, it became evident that in the process of his creative activity he managed to stay ahead of time and oriented his Institute of Cybernetics of the Academy of Science of the Ukrainian SSR, which he founded and supervised, for the transition from computer engineering to computer science, and then -to information technologies (IT). V. Glushkov became a founder of this incredibly important field of science and technologies in Ukraine and in the former URSS. He has trained the necessary cohort of experts and created a powerful scientific school in this field.

The term "information technologies" appeared in science in the last years of XX century. Earlier the terms "informatics" or "computer engineering" were used, that defined narrower problem circle. Being high technologies, information technologies cover wide range of scientific, design, technological and industrial directions: design and construction of computers, periphery devices, elemental base, network equipment, system software, elaboration and creation of automated and automatic numeric systems of different destination and their application software. All these directions have been developed since 1960-70s in the Institute of Cybernetics of the Academy of Science of the Ukrainian SSR, created in 1962 by V. Glushkov". [START_REF]Development of Computer science and technologies in Ukraine[END_REF] Author of this paper was working for the Institute of Cybernetics in 1980-86 and has started then General Knowledge Machine project. "The sphere of interests of outstanding surgeon Nikolai Mihailovich Amosov included not only medical problems, but also general human cognition problems. General system approach to understanding human nature has been reflected in the scientific directions initiated by N.M.Amosov in various areas of cybernetics: modeling of physiological functions of human organism (physiological biocybernetics), modeling of cognitive and psychological human functions (psychological biocybernetics), and modeling a man as a social creature (sociological biocybernetics). All these research directions have been represented in the Department of Biocybernetics founded in the Institute of Cybernetics by V.M.Glushkov and N.M.Amosov in 1961. Nikolai Mikhailovitch Amosov was the scientific leader of the Department since 1988.

In 1964 Nikolai Mikhailovitch Amosov formulated a hypothesis on the information processing mechanisms of the human brain. Within this hypothesis he expressed his system-level observations on the brain's structure and the mechanisms that are made operational by a human's mental functions. Of principal importance was the fact that it was not the separate structures, mechanisms or functions (such as memory, perception, learning and so on) that became the simulation object, but the brain of the human as a social being -the brain of homo sapiens. Such was the main idea of the monograph "Modeling of Thinking and of the Mind ", published in 1965, which for a couple of decades became the "bible" for several generations of Department's researchers (and not only for them).

The ideas, which N.M.Amosov put forward in his book "Modeling of Thinking and of the Mind" were further developed in his subsequent works "Modeling of Complex Systems ", "Artificial Intelligence ", "Algorithms of the Mind " and "Human Nature ".

On a theoretical level, two main features characterize the research of Amosov School.

The first feature is that not an individual neuron, but a set of neurons organized in a particular way -neuron assembly -is considered to be the core functional element of a neural network, its "principal character ". Given this, the neural network appears now as a structure consisting of a multitude of interacting assemblies, each of which corresponds (and this is a very important point) to some individual image or concept out of a set of images and concepts that participates in forming integrative mental functions realized by the brain. That is, this set participates in the thought process. Thus the neural network turns out to be a network with semantics (a special kind of a semantic network). The origins of the present approach can be traced to the early works of a well-known physiologist D.Hebb, whose main study was published as early as in 1949.An important characteristic of this kind of network is that all of its elements at any point in time are active to some degree. The magnitude of this activity varies in time, reflecting the interaction of concepts represented by the network's nodes.

The second feature of Amosov school research concerns the introduction of the notion of a specific system for reinforcement and inhibition (SRI) to scientific use. This system is an integral neural network attribute, and it plays a role comparable to that of functions of attention in the thought processes in network functioning. The idea of SRI is entirely original. He was Head of International UNESCO Artificial Intelligence Laboratory and Head of "Intellectual Systems" division of Russian Academy of Sciences.

Pospelov was a founder of Russian (Soviet) Artificial Intelligence Association (www.raai.org).

The small parts from a paper "Universal Scales to Systems of Communicating Contextual Systems" by Irina Ezhkova are quoted [START_REF] Ezhkova | Universal Scales to Systems of Communicating Contextual Systems[END_REF].

"It was more than four decades ago when Dmitry Pospelov began his inspiring study of the Semiotic Systems, Situated Logics, Universal Scales and Spaces. His interest in psychology and neurology, in mathematical logics and fuzzy sets, in linguistics and behavior sciences had been stimulated the blossoming tree of a broad Russian school of AI. His typical way of approaching constructive model was formalized as a cortege, or train (or even a simple list) of elements, each of which then may be represented well in a traditional way. This reflected his original flexibility, profound vision and interdisciplinary views. His major works were on the study of bioelectrical phenomena in the cortex of large hemispheres in norm and pathology. Livanov first applied the methods of the mathematical analysis to bioelectrical fluctuations in the cortex of the brain. He was one of the founders of electroencephalography in the USSR. It shows the functional significance of individual frequency components of the EEG and the role of the spatial distribution of them by the cortex of large hemispheres. Theoretical research and methodological techniques developed by Livanov, are used for the diagnosis of diseases in neuropsychological clinic, are used in the space and aviation medicine. He was awarded 4 orders and medals. His work on spatial organization of cerebral processes is described in [START_REF] Livanov | Spatial Organization of Cerebral Processes[END_REF].

The small description of the paper by V. N. Dumenko "The phenomenon of spatial synchronization of the brain potentials in a broad frequency band 1-250 Hz" is quoted in [START_REF] Dumenko | The phenomenon of spatial synchronization of the brain potentials in a broad frequency band 1-250 Hz[END_REF] "The article dedicated to the centenary of academician Mikhail Nikolaevich Livanov briefly outlines the history of development of his original concept of the functional significance of the brain potential's spatial synchronization phenomenon as a possible way of studying systemic organization of the brain electrical activity. The new parameter of "space" introduced into neurophysiology by M. N. Livanov made it possible to research the earlier unknown aspect of the brain activity. Livanov's ideas have been developed in many studies of the late decades of the XX century. In the review, much attention is given to specific functional significance of this phenomenon in a broad frequency band 1-250 Hz, especially, during instrumental learning. Energy (power spectra) and coherent-phase characteristics of cortical potentials in traditional (1-30 Hz), gamma-(30-80 Hz) and high-frequency (80-250 Hz) bands are compared. The problem of linear and nonlinear processes in the organization of the brain potentials is mentioned". [START_REF] Ezhkova | Universal Scales to Systems of Communicating Contextual Systems[END_REF] All these people's works influenced and inspired the creation and activity of General Knowledge Machine Research Group.

General Knowledge Machine Research Group

General Knowledge Machine Research Group was founded in 1986 in Kiev, Ukraine, as informal institution by mathematicians and IT experts. It counts 11 members including sponsors, developers and thinkers. The author of this paper has generated initial ideas, coordinates activities and plays all roles needed for the show.

Just In Time Knowledge Concept

The term "JIT Knowledge" was introduced in the paper "Traditional + Adaptive learning = broad way to knowledge" by K.M. Golubev [START_REF] Golubev | Traditional + Adaptive learning = broad way to knowledge[END_REF] Knowledge is can be considered a set of holistic items directing our behavior including descriptions of typical situations and proposed actions. We should learn continuously to be able to apply our knowledge in present and in the future. In a case of knowledge items traditional search engines are inefficient due to impossibility to distinguish knowledge items from full text.

General Knowledge Machine works on an intelligent e-knowledge base engine for any kind of knowledge-based applications supporting effective knowledge presentation, precise knowledge search, adaptive learning and immediate consulting.

Example of Learning processes.

Dialog Professor -student during an exam:

Prof.: You are looking very worried. Any problems with exams questions? Stud.: Oh, no! Questions are OK. It is the answers that I worry about.

Traditional learning.

Traditional learning is based on a linear process, when students must learn all proposed knowledge, topic by topic. After that students must pass exams to get acknowledgement from professors that they acquired the related knowledge. There are many exams, sometimes very difficult, having significant influence on the life of students. But all this very hard work does not guarantee that students have all or even greater part of knowledge needed to solve problems which arise in their post-school activity, in the real world life.

Adaptive Learning.

Adaptive Learning is based on a concept called Just-In-Time Knowledge (JIT-Knowledge). Total amount of external sources of knowledge, even in the specific areas, becomes greater all the time. It is not possible, taking into account limitations of human brain, to learn it with Traditional Learning, topic by topic. It means that in reality significant part of knowledge is not used by anyone, and many problems are not solved because no one learns needed knowledge. The Electronic Knowledge Publishing based on General Knowledge Machine power, called GKM-EKP technology, allows to find and to learn knowledge relevant to existing problems. Based on the general knowledge concept using approach developed by Academician of USSR M.N.Livanov E-knowledge system may be easily incorporated into any kind of information system due to support of wide range of data input and output sources It may be used for Adaptive Learning applications, based on the Just-In-Time Knowledge concept

Steps of intellectual activity

The expert's activity is similar to work of Mr. Sherlock Holmes [START_REF] Breughel | Renaissance painting from[END_REF], and consist in following tasks:

 Observation  Producing propositions, based on a knowledge  Elimination of impossible propositions  Selection and verification of the most appropriate propositions Thus, if we want to help human intellect, to make it more powerful and more creative, we should make a knowledge machine which could assist during these steps. Let's name demands to such a machine.

demands to Knowledge Machine.

Step 1 -Observation.

1. Knowledge machine should have maximum possible information about a case before a judgment.

Step 2 -Producing propositions, based on knowledge.

2. Knowledge machine should possess maximum possible knowledge in a sphere of implementation.

3. Knowledge machine should possess no excessive knowledge, should have nothing but the tools which may help in doing work.

4. Getting indication of the course of events, knowledge machine should be able to guide itself by other similar cases which occur to its memory.

5. Knowledge machine should have an ability to take into account not only descriptions of situations in its memory but results as well, providing a possibility to reconstruct a description from a result, i.e. if you told it a result, it would be able to evolve what the steps were which led up to that result.

6. Possessing information about the great number of cases, knowledge machine should have an ability to find a strong family resemblance about them, i.e. to find templates of typical cases.

7. Knowledge machine should have an ability to explain the grounds of its conclusion.

8. Knowledge machine should arrive at the conclusion for a few seconds after getting a description of case. 9. Knowledge machine should focus on the most unusual in descriptions of situations.

Step 3 -Elimination of impossible propositions.

10. Knowledge machine should have an ability to point out all impossible propositions.

Step 4 -Selection and verification of the most appropriate propositions.

11. Knowledge machine should estimate a level of a confidence of its propositions.

We think that there are many possible solutions for estimation, but we have developed our own Proposition Value Index, based on idea of member of USSR Academy of Science M. N. Livanov from Russia that the essence of memory associations is a spatial-temporal coherence of narrow-band periodical oscillations of central neurons sets activity (see [START_REF] Dumenko | The phenomenon of spatial synchronization of the brain potentials in a broad frequency band 1-250 Hz[END_REF]).

AI expert systems and neural networks.

Expert system, as we understand, is based on the idea of decision tree, when, with every answer to a program's question, a direction of moving through a tree changes until a final leaf (decision) will be reached [START_REF] Alty | Expert systems. Concepts and examples[END_REF].

 So not all possible questions will be asked, and not maximum information will be received.  The key elements are decision rules, but no knowledge itself. Not a word about the thousands of other similar cases, about typical cases.  As we see, expert systems originally were designed to be deduction machines. But it is not very reliable to entrust to machine deciding what is absolutely impossible. We think that more fruitful approach is to show what reasons to consider some hypotheses as impossible. And only man should make the final decision.

It is not amazing that development and implementation of a successful expert system is very hard work, because experts cannot think, as a rule, in terms of decision trees, and the mathematical theory of probability have a little in common with a feeling of a confidence of an expert.

Neural network is based, as we know, on the idea of teaching of set of elements (neurons), controlling conductivity between them (see [START_REF] Hinton | Learning in parallel networks[END_REF]). Teaching is going under control of expert, which defines whether attempt is successful. This is more merciful towards expert -nobody is trying to make him feel himself deficient asking: what is the probability of this conclusion when that parameter's value is present. But there are some difficulties, not outdone yet.

 A neural network is oriented on decision rules rather than on knowledge itself. So there are no thousands of other similar cases in memory of neural network.  A neural network cannot explain reasons of own conclusion in terms that people can understand. So it is very hard to verify its activity and, therefore, to believe.

An expert system is an example of a 'top-down' approach when particular instances of intelligent behavior selected and an attempt to design machines that can replicate that behavior was made. A neural network is an example of 'bottom-up' approach when there is an attempt to study the biological mechanisms that underlie human intelligence and to build machines, which work on similar principles. GKM-EKP technology is based on principles uniting both 'top-down' and 'bottomup' approaches.

Building Knowledge Machine

And if we could build a knowledge machine satisfying 11 demands, it should mean that we could introduce a new kind of publishing -publishing of knowledge itself.

How to build such a knowledge machine?

Famous experts in Artificial Intelligence (AI) Alan Newell and Herbert Simon, developers of General Problem Solver, proposed to define memory elements as rules called 'Productions' of the following type 'If-Situation-Then-Action'. We have a right to suppose, taking into account this definition and opinion of Mr. Sherlock Holmes, that big part of knowledge consists of following 3-parts elements:

(Description of real problem-Name-Action-Result), that is called a concrete knowledge, or (Description of template of problem-Name-Action-Result), that is called an abstract knowledge (we think that this kind of knowledge appears of a concrete knowledge for a long lifetime).

Let's consider the following example. It is a try to develop a knowledge machine for pictures authors' recognition assistance. We pick up a fragment from "Renaissance painting from Brueghel to El Greco" by Lionello Venturi [START_REF] Oshe | A role of operative memory in solving of tasks of visual interpolation of linear intervals[END_REF].

"Like the Florentines, a Parma artist Francesco Mazzola (1503-1540), known as Parmigianino (i.e. little Parmesan), tended to the use of abstract forms, but, less doctrinaire in his abstractionism than such man as Rosso and Pontormo, he achieved a fragile grace and delicacy, reminiscent of Raphael and Corregio. His universal popularity contributed largely to the spread of mannerism in Europe.

The Madonna of the Long Neck (Uffizi, Florence) illustrates to perfection of his aesthetic. Here elegance replaces beauty and the somewhat abstract treatment of the figure gives it an immaterial charm. His sfumato, his discreet allusions to reality, the elongation of proportions and the sinuous movement of his figures were enthusiastically followed up by many painters in the second half of Cinquecento." [START_REF] Oshe | A role of operative memory in solving of tasks of visual interpolation of linear intervals[END_REF] Let's try to formalize it in a form (Description of template of problem-Name-Action-Result), because it is an abstract knowledge.

Description of problem consists of sentences that we call description signs.

"Tendency to the use of abstract forms; Fragile grace and delicacy; Elegance replaces beauty; Sfumato; Elongation of proportions; Sinuous movement of figures" Name "Possible author is Francesco Mazzola (Parmigianino) from Parma, Italy (1503-1540)."

Action and Result

Description of action consists of sequence of sentences that we call action signs. In our case there are no action signs. Description of result consists of sequence of sentences that we call result signs. In our case result sign could be: "Possible author is Francesco Mazzola (Parmigianino) from Parma, Italy (1503-1540)."

Step 1 -Observation

We gather all description signs from all elements of knowledge eliminating synonyms and duplicates, and numerate signs and their grades. Signs numeration sequence doesn't matter. As a result we get a chapter of problem's description input form called Step 2 -Producing propositions, based on knowledge Initially, we should numerate Name parts of knowledge elements that will be used as propositions, just for convenient reference. It will look like:

1. Francesco Mazzola (Parmigianino) from Parma, Italy (1503-1540) ... Every proposition is accompanied with a list of numbers of signs and grades from problem's description input form.

Getting the most possibly full description of problem, we could build a list of elements of knowledge with the most similar descriptions. It could be presented in a menu-like list of propositions, sorted according to indexes, which present value index depended on degree of similarity.

The highly valuable propositions Index Number Proposition 90 % 1) Francesco Mazzola (Parmigianino) from Parma, Italy (1503-1540) ... We have developed our own Proposition Value Index, based on ideas of member of USSR Academy of Science M. N. Livanov (see [START_REF] Dumenko | The phenomenon of spatial synchronization of the brain potentials in a broad frequency band 1-250 Hz[END_REF]).

Step 3 -Elimination of impossible propositions So there's a possibility to verify manually -are there any objections against our favorite propositions?

Step 4 -Selection and verification of the most appropriate propositions

If we choose some proposition from list to get additional information, we should get a list of signs on which proposition is based and its description. In our case, if we select the proposition:

Results

Early versions of General Knowledge Machine were developed for UNIX, MS-DOS, Windows operating systems. The latest version supports all platforms of GNU compiler options (any Windows, Linux, UNIX ...).

There are working products which can be presented to experts in corresponding areas.

Products were tested in various environments -business, medicine, arts. Papers were published in Russia, Italy and UK. The work was featured in the 2006-2007 Edition of the Marquis Who's Who in Science and Engineering as a pioneer research.

Conclusion and Perspectives

Some people say about a crisis of Artificial Intelligence. But is this crisis of human intellect? Of course, not. May be it's a crisis of human self-confidence. In the beginning there were many promises to built machines more intelligent than people. And those machines should use advanced principles of work, much better than obsolete human intellect [START_REF] Golubev | Traditional + Adaptive learning = broad way to knowledge[END_REF]. Instead of help to human intellect there were attempts to replace it. But those, who read works of academician V. Vernadsky from Ukraine [START_REF] Schank | The quest to understand thinking[END_REF], E. Le Roy [START_REF] Vernadsky | The Biosphere[END_REF] and P. Teilhard de Chardin from France [START_REF] Mcmenamin | Les origines humaines et l'evolution de l'intelligence[END_REF], know that the main result of evolution on Earth is creation of Noosphere -a sphere of intellect. And, in this case, it is very interesting what can be called an intellect, but is based on other principles than developed by evolution?

2 URSS

 2 Excerpts and pictures from Website called "Development of Computer science and technologies in Ukraine" are included by permission from the International Charity Foundation for History and Development of Computer Science and Technique ICFCST http://www.icfcst.kiev.ua/MUSEUM/LEBEDEV/L_life.html

Fig. 1 .

 1 Fig.1. Sergey Lebedev (source ICFCST)

Fig. 1 .

 1 Fig. 1. MESM and team members in 1951. From left to right: Lev Dashevsky, Zoya Zorina-Rapota, Lidiya Abalyshnikova, Tamara Petsukh, Evgeniy Dedeshko (source ICFCST)

  Glushkov has founded a Kiev-based Chair of Theoretical Cybernetics and Methods of Optimal Control at the Moscow Institute of Physics and Technology in 1967 and a Chair of Theoretical Cybernetics at Kiev State University in 1969. The Institute of Cybernetics of National Academy of Science of Ukraine, which he has created in 1962, is named after him.

Fig. 4 .Fig. 5 .

 45 Fig.4. Cybernetic Center NASU planned by V.Glushkov in 1972 was organized in 1992. The main organization -V.Glushkov Institute of Cybernetics of the National Academy of Science

Fig. 2 .

 2 Fig. 2. Dmitry Pospelov. Head of International UNESCO Artificial Intelligence Laboratory. Head of "Intellectual Systems" division of Russian Academy of Sciences (source ICFCST)

Fig. 3 .

 3 Fig. 3. Mikhail N. Livanov, the Soviet physiologist, academician of the Academy of Sciences of the USSR (source ICFCST)

( 1 .

 1 Descriptions signs). The second part of problem's description input form chapter (2.Actions signs) consists of action signs, arranged in a way similar to description signs. The third part of input form chapter (3.Results signs) consists of result signs, arranged in a way similar to description signs. Problem's description input form. 1.Descriptions signs 1.Tendency to the use of abstract forms ... 2.Actions signs None 3.Results signs 200.Possible author is Francesco Mazzola (Parmigianino) from Parma, Italy (1503-1540) …

90 % 1

 1 Francesco Mazzola (Parmigianino) from Parma, Italy (1503-1540), Then we would get the following: Proposition was made according to the following signs 4.Sfumato. ... Francesco Mazzola (Parmigianino) from Parma, Italy (1503-1540) Tendency to the use of abstract forms ... And we have a possibility for additional verification. Knowledge system on Renaissance Painting may be found at Web address: http://gkm-ekp.sf.net/IVP-Portal.html

2.2 Victor Glushkov. Institute of Cybernetics Founder Fig. 3. Victor Glushkov (source ICFCST)

	Its legend states: "Sergei Alekseyevich Lebedev 1902-1974.
	Developer and designer of the first computer in the USSR. Founder of the Soviet
	computer building".[10]
	Victor Glushkov (August 24, 1923 -January 30, 1982) was the founding father of
	information technology in the Soviet Union (and specifically in Ukraine), and one of
	the founders of Cybernetics. He was born in Rostov-on-Don, Russian SFSR, in the
	family of a mining engineer. He was graduated from Rostov State University in 1948,
	and in 1952 has proposed solution to the Hilbert's fifth problem and defended his
	thesis in Lomonosov Moscow State University.
	In 1956 he has started working in a computer science field in Kiev as a Director of
	the Computational Center of the Academy of Science of Ukraine.

2.4 Dmitry Pospelov. Russian Artificial Intelligence Association Founder

  Using this system allows to introduce a direction component into neural network information processing, and, what is very important, to use value characteristics of information in organizing this processing.Dr.Alexander Kasatkin, Dr.Lora Kasatkina International Research and Training Center of Information Technologies and Systems of National Academia of Sciences of the Ukraine[START_REF]Development of Computer science and technologies in Ukraine[END_REF]

Table 1 .

 1 Comparison of AI Expert Systems and Electronic Knowledge Systems

	AI Expert Systems	Electronic Knowledge Systems
	Intended to replace human experts	Intended to assist human intellect

http://gkm-ekp.sf.net


Mieczyslaw Owoc
email: mieczyslaw.owoc@ue.wroc.pl

Pawel Weichbroth

Mieczysław Owoc

Paweł Weichbrot

Validation Model for Discovered Web User Navigation Patterns

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Evolution of designing and developing Web sites from static to dynamic approach has enabled easy updates. Furthermore, intensive development and proliferation of WWW network resulted in other new modeling methods. It's obvious -being recognized and visited in the Web means that the content is up-to-date and satisfies its visitors. Widespread scope of content topics shared and presented on the Web site affects the size and depth level of its structures. This results in negative impression of presented content and weaker usability.

Usability of delivered informat ion and knowledge depends on dynamically created user profiles as a result of Web min ing and particularly user navigation patterns discovery process. Knowledge acquired fro m web server log files in order to generate navigation patterns embraces useful as well as non-relevant association rules and has to be validated. Therefore the ultimate goal of this research is presentation of the method allowing for generated knowledge refinement.

These are very specific features of Web Mining procedures: temporal and massive data input, big differentiation of user types. They have direct impact on generated knowledge about website content and forms and in turn should be considered in Knowledge Validation (KV) framework. List of constrains useful in knowledge validation processes includes: page-view duration, total session time, include and exclude items, support and confidence and time and date. All the mentioned constraints should be considered as potential criteria of discovered knowledge about web surfer navigation patterns. On the other hand the considered constraints are useful in search space reduction in a case of frequent files. Actually the application supporting the discussed problem with mentioned above constraints has been implemented.

The paper is structured as follows. After presentation of related work, crucial definitions essential for this survey are proposed. Results of prepared experiments consisting of relationships between components are demonstrated in the next section. Crucial procedure for formulat ing knowledge discovery in such environment is investigated later. The paper ends with itemizing of conclusions and considering future research.

RELATED WORKS

Reco mmendation systems help to address informat ion overload by using discovered web users navigation patterns knowledge gained fro m web server log files. A problem for association rule recommendation systems (RS) is placed in dataset. It is often sparse because for any given user visit or object rank, it is difficult to find a sufficient number of co mmon items in mult iple user profiles. As a consequence, a RPS system has difficu lty to generate recommendations, especially in collaborative filtering applications.

In [START_REF] Sarwar | Application of Dimensionality Reduction in Recommender System -A Case Study[END_REF] to solve above problem, some standard dimensionality reduction techniques were applied due to improved performance. This paper presents two different experiments. Sarwar et al. have exp lored one technology called Singular Value Deco mposition (SVD) to reduce the dimensionality of recommender system databases. The second experiment compares the effectiveness of the two recommender systems at predicting top-n lists, based on a real-life customer purchase database fro m an e-Co mmerce site. Finally, results suggest that SVD can meet many of the challenges of recommender systems, under certain conditions.

Ad hoc exclusion of some potential useful items can be one of known deficiencies of this and other reduction of dimensions solutions hence they will not appear in the final results. Two solutions that address this problem were proposed by Fu et al. in [START_REF] Fu | M ining navigation history for recommendation[END_REF]. The first solution assumes to rank all the discovered rules based on the degree of intersection between the left-hand side (antecedent) and active session of the user. Then, the SurfLen (client-server system) generates the top k recommendations. In addition to deal with sparse datasets -if users browsing histories intersect rarely, the system is unable to produce recommendations -the algorithm for ranking association rules was presented. The second solution takes advantage of collaborative filtering. The system is able to find "close neighbors" who represent similar interest to an active user. Then, based on that, a list of reco mmendations is generated.

Many collaborative filtering systems have few user ranks (opinions) compared to the large number of available documents. In this paper [START_REF] Sarwar | Using filtering agents to improve prediction quality in the GroupLens research collaborative filtering system[END_REF], Sarwar et al. define and implement a integration model for content-based ranks into a collaborative filtering. In addition, metrics for assessing the effectiveness filter bots and a system were identified and evaluated.

In the paper [START_REF] Lin | Efficient Adaptive-Support Association Rule M ining for Recommender Systems[END_REF], Lin et al. a collaborative recommendation system based on association rules framework was proposed. The framework provides two measures for evaluating the association expressed by a rule: confidence and support. Moreover, the system generates association rules among users as well as among items.

DEFINITIONS

The web site space can be considered as universe U which consists of a sequential sets (P i ) where i =1...M. Each of sets P i corresponds to unique user session where as each element of P i is user's request for single page shared by a web site. We consider only such subsets A of P i (A⊆P i ⊆U) which appeared often enough. The frequency of subset A is defined as support (or support ratio) denoted as support(A)=|{i ; A⊆P i }| / M. A "frequent" set is a set which support satisfies the minimu m support value, denoted as minsupport. It is a user dependent value, often defined as cut-off as well.

We developed and applied an Apriori-like algorithm to mine frequent itemsets that is based on level-wise search. It scans a database recursively -a growing collections A are generated using smaller collections, especially the subsets of A of cardinality |A|-1, called hipersubsets. Formally, a set B is a h ipersubset of a set A if and only if ∃ a∈A A=B∪{a}.

An association rule is an imp lication of the form A→B, where B⊆P i ⊆U and A ∩ B = ∅. The support of a rule is the percentage sessions in P that contains A ∪ B. It can be seen as an estimate of the probability Pr(A∪B). The rule support is computed as follows: support(A→B) = support(A∪B) / M. The confidence of a rule A→B is the percentage of sessions in P that contain A also contain B. It can be seen as an estimate of the conditional probability Pr(B\A). The rule confidence is computed as follows: confidence(A→B) = support(A∪B) / support(A). Confidence of the disjoint couple of sets {A,B} can be read B under the condition A. If its value exceeds an arbitrarily determined level of min imu m confidence (also defined by user), denoted as minconfidence, the pair {A,B} will express an association rule A→B.

Given a session data set D, the problem of min ing association rules is to discover relevant (or strong) association rules in D which satisfy support and confidence greater than (or equal) to the user-specified minimu m support and min imu m confidence. Here, the keyword is "relevant" (or "strong") which means, taking into account a user's point of view, association rule mining process is complete.

Theorem 1: Each subset of the frequent set is a frequent set. Proof 1: Let A be an arbitrary frequent set and B⊆A be a subset of A. The set A is frequent, thus support(A)=|{i ; A⊆P i }| / M ≥ minsupport. Since B is a subset of A, we have that A⊆P i ⇒ B⊆P i , thus support(B) = |{i ; B⊆P i }| / M ≥ |{i ; A⊆P i }| / M ≥ minsupport. Therefore the set B is also frequent which ends the proof.

Theorem 2:

If A→B ∪ C is a relevant association rule (A, B, C -pair wise distinct), then also A→B, A→C, A∪B→C and A∪C→B are relevant association rules.

Proof 2: Let A→B ∪ C be an user-relevant association rule. Then minconfidence ≤ confidence(A,B∪C) = support(A∪B∪C) / support(A).

Let us consider A∪B ⊆ A∪B∪C. Having in mind theorem 1, we get

support(A) ≥ support(A∪B) ≥ support(A∪B∪C). As a result, confidence(A,B) = support(A∪B) / support(A) ≥ support {A∪B∪C} / support(A) ≥ minconfidence. The set {A∪B} is frequent, so A→B is a relevant association rule. On the other hand, confi- dence(A∪B,C) = support(A∪B∪C) /support(A∪B) ≥ support {A∪B∪C}/support(A)
≥ minconfidence, because of a frequency of a set A∪B∪C, A∪B→C is also a relevant association rule. Consequently, proofs for rules A→C and A∪C→B are similar.

Two additional interpretation of introduced earlier constraints should be presented: page view duration and total session time. Page view duration is calculated as a difference between the page view start time o f the next page minus the page view start of the previous page. Total session time is calculated as a sum of duration times referencing to particular elements of frequent sets without the last element.

PHASES OF WEB USAGE MINING PROCESS

Tools commonly used in data min ing are applied in Web Internet resources analysis.

The main fundamental task is pattern usage discovering available in the Internet. Such knowledge can be the basics of recommendation systems in order to improve functionality (cross-selling) and usability (easier access) to Internet portals and services.

First holistic and integrated (incl. different KDD steps) model of Web Usage Mining process was proposed by Cooley et al. in [START_REF] Cooley | Web M ining: Information and Pattern Discovery on the World Wide Web[END_REF]. Afterwards, Srivastava et al. in [START_REF] Srivastava | Web usage mining: discovery and applications of usage patterns from web data[END_REF] extended this model and apparently distinguished three phases: (1) preprocessing, (2) pattern discovery and (3) pattern analysis. This model has been widely applied -the references can be found e.g. in [START_REF] Kosala | Web mining research: A survey. Newsletter of the Special Interest Group ([END_REF][START_REF] Eirinaki | Web mining for web personalization[END_REF][START_REF] Dai | Discovery and Evaluation of Aggregate Usage Profiles for Web Personalization[END_REF][START_REF] Pierrakos | Web Usage M ining as a Tool for Personalization: A Survey[END_REF][START_REF] Facca | M ining interesting knowledge from weblogs: a survey[END_REF][START_REF] Bayir | Smart M iner: a new framework for mining large scale web usage data[END_REF][START_REF] Staś | Wykorzystanie algorytmów mrowiskowych w procesie doskonalenia portali korporacyjnych[END_REF][START_REF] Rigou | M ining for Web Personalization[END_REF]. This model is complex and practice-oriented solution of solving problem of knowledge discovery fro m Web data repositories. The following particular tasks are subordinated to the mentioned phases. It allows for clear defining of user requirements fro m its point of view including data format and expected analysis results. However it seems to be reasonable to extend the model by data collect ion (see Fig. 1). During this phase data sources are defined based on data entry type and the same selection of necessary variables necessary variables including planned analysis are performed.

Fig. 1. Extended Web Usage M ining process

Two dimensions can be defined in this model: e.g.:

• phase -definition of data-oriented actions (tasks),

• object -definition of data types.

The whole process consists of the four phases; first three can be considered as machine-aided while the last one is human -expert oriented. In this frames, similarly to CRISP-DM, specialized tasks are separate. We can distinguish four phases in web usage mining process: In the next section, we refer to each phase briefly, emphasizing the most important issues which can be seen as a part of knowledge validation challenge. ◊ time of the session, ♠ session ID, ○ user ID, □ service ID, ⌂ subservice ID, ♣ html file ID.

EXPERIMENTS ON REAL WEB SOURCES

In our research, we used a web server log file wh ich covers five hours of system activity -fro m 2PM to 7PM on 29th December 2008. We also want to notice the fact that dedicated solutions (e.g. scripts, services) on the Web Server side were imp lemented. They were intended to reduce globally useless data (e.g. spiders activity). In this case, we can determine that in the phase of data collection, some preprocessing tasks took(or have taken) p lace.

Data preprocessing

We used Linu x operating system to operate on the raw data. To carry out this phase, a simple script in awk language was implemented to process the log files. Firstly, fro m six available variables just two were selected (♠ ♣) and separated from others. Secondly, these two were sorted accordingly to the session time (◊) and session identifier (♠). Thirdly, the sessions, where only one html page was requested by the users, were deleted fro m the log files. In such way, there were 2.132.581 unique sessions observed which would be taken into account in our experiments. The size of the log file was reduced from 4.018.853 KB to 512.934 KB. Again, it can be noticed that necessary tasks which typically had to be performed in the second phase were very limited. In addition, the source data was supplemented with text files which contained dictionaries corresponding to the URL name (e.g. 724 denotes to [www]). Finally, the processed file had the following format (session id, URL name):

• 8654 [www] • 8654 [sport.html]
• 8654 [ga mes.ht ml]

5.3

Pattern discovery

In this phase, frequent Web users' access patterns are discovered from sessions. A few algorith ms have been proposed to discover frequent itemsets. During the literature study of KDD, we came across the algorithms such as AprioriAll [START_REF] Agrawal | M ining Sequential Patterns[END_REF], GSP [START_REF] Srikant | M ining Sequential Patterns: Generalizations and Performance Improvements[END_REF], SPADE [START_REF] Zaki | SPADE: An Efficient Algorithm for M ining Frequent Sequences[END_REF], PrefixSpan [START_REF] Pei | M ining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach[END_REF], ItemsetCode [START_REF] Ivancsy | Frequent pattern mining in web log data[END_REF].

We have decided to use Apriori algorith m, although it is not the most efficient and recent one. It is suitable solution for our problem since we can make it more efficient by pruning most of the candidate sequences generated in each iteration. This can be done because of given constraints and requirements. We cannot assume that for every subsequent pair of pages in a sequence the former one must have a hyperlin k to the latter one. The justification of that assumption is the fact that we do not have full access to the Web Server repository. Some files could have been deleted, moved to the archives or simp ly changed by the provider. On the other hand, the frequency of content update can be seen as very high -we have to keep in mind that approximately 7 million users per day visit this Web portal. So, it is obvious that the content hosted on the portal must be up-to-date. Furthermore and what seems to be the most important, the engine of recommendation system is able to generate links directly on web pages and does not require knowledge of inner-oriented structure and relationships of individual web pages.

Let P = {p 1 , p 2 , ... , p m } be a set of web pages, called items. Database D represents a set of reconstructed sessions S = {s 1 , s 2 , ... , s n }. Each session s n is a subset of P where s n ⊆ P, called itemset. We implemented Apriori algorithm (Algorith m 1) where input is a database of sessions D and output is a set of frequent sequences L.

(1) L 1 = find_frequent_1-itemsets(D); [START_REF] Fu | M ining navigation history for recommendation[END_REF]

for (k = 2; L k-1 = Ø; k++) { (3) C k = apriori_gen(L k-1 ); (4)
for each transaction T ∈ D (5)

C t = subset(C k , t); [START_REF] Srivastava | Web usage mining: discovery and applications of usage patterns from web data[END_REF] for each candidate c ∈ C t [START_REF] Kosala | Web mining research: A survey. Newsletter of the Special Interest Group ([END_REF] c.count++; } (8)

L k = {c ∈ C k | c.count ≥ min_sup} } (9) return L = ∪ k L k procedure apriori_gen(L k-1 : frequent(k -1) -itemsets (1) for each itemset l 1 ∈ L k-1 and (2) for each itemset l 2 ∈ L k-1 (3) if(l 1 [1] = l 2 [1]) ∧ (l 1 [2] = l 2 [2]) ∧ ... ∧ (l 1 [k -2] = l 2 [k -2]) ∧ (l 1 [k -1] < l 2 [k -1]) (4) then { (5) c = 1 1 ⊠ l 2 ; (6) if has_infrequent_subset(c, L k-1 ) then (7) delete c; (8) else add c to C k ; } (9) return C k ; procedure has_infrequent_subset(c: candidate k-itemset); L k-1 : frequent(k -1)-itemsets; (1) for each(k -1)-subset s ∈ c (2) if s ∉ L k-1 then (3)
return True else [START_REF] Lin | Efficient Adaptive-Support Association Rule M ining for Recommender Systems[END_REF] return False;

As a result the program returns frequent sequences with support for each. A simple example of a three element sequence is given below.

[www];[info]/science/item.html;[info]/wo rld/item.html; 0,02011 Interpretation of this particular sequence may be exp ressed in these words: "Over 2 percent of anonymous users between 2PM and 7PM on 29 th December 2008, first requested access to the home page, next opened science section then world section".

Based on the set of frequent sequences L we are able to generate sequential association rules (SAR). In this scenario, a simple algorith m was developed (Algorithm 2). Let R = { r 1 , r 2 , ... , r m }be a set of SAR. In each rule antecedent (body of the rule, left side) and consequent (head of the rule, right side) must not be replaced. In other words, it guarantees the precise order of each element in the sequence. Also, a user is requested to provide the minimu m confidence (minconfidence) threshold.

(1) R={} [START_REF] Fu | M ining navigation history for recommendation[END_REF]

for all I ∈ L do (3) R = R ∪ I → {} (4) C 1 = {{i} | i ∈ I}; (5) k:= 1; (6)
while C k ≠ {} do [START_REF] Kosala | Web mining research: A survey. Newsletter of the Special Interest Group ([END_REF] //extract all consequents of confident association rules (8)

H k := {X ∈ C k | confidence(I \ X ⇒ X, D) ≥ min_conf} (9)
//generate new candidate consequents [START_REF] Pierrakos | Web Usage M ining as a Tool for Personalization: A Survey[END_REF] for all

X, Y ∈ H k , X[i] = Y[i] for 1 ≤ i ≤ k -1 and X[k] < Y[k] do (11) I = X ∪ {Y[k]} (12) if ∀J ⊂ I, |J| = k : J ∈ H k then (13) C k+1 = C k+1 ∪ I (14) end if (15)
end for [START_REF] Agrawal | M ining Sequential Patterns[END_REF] k++ (17) end while [START_REF] Zaki | SPADE: An Efficient Algorithm for M ining Frequent Sequences[END_REF] //cumulate all association rules [START_REF] Pei | M ining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach[END_REF]

R := R ∪ {I \ X → X | X ∈ H 1 ∪ ⋯ ∪ H k } (20) end for
The set of sequential association rules R is achieved as a result. We give a simple example of such results, based on previously given frequent sequence. r 1 :{www};{science.html}→{world.ht ml}; 0,02011; 0,964 r 2 :{www}→{science.html}{world.ht ml}; 0,02011; 0,652 r 3 :{www}→{science.html}; 0,0305; 0,00209 r 4 :{www}→{world.ht ml}; 0,0294; 0,00152 Interpretation of the first rule may be expressed in these words: "There is a 96,4% chance that a user who visited {www} and {science.html} pages, after them would also visit {world.html}". In other words, the value of confidence ratio shows degree of rule reliability.

In this way we have shown that attractiveness of discovered knowledge is evaluated by two measures: support and confidence ratio. They are both specified by a userit guarantees a definitive result.

Results of pattern analysis

The aim of the research was to discover frequent sequences which represent web user navigation paths. In first iteration the level of support and confidence ration was respectively 0,01 and 0,9. Table 2 shows top ten (taking into account the highest support, denoted by percentage) one element frequent itemsets. For instance, human interpretation of such knowledge might be exp ressed in these words: "Over 27 percent of sessions include a page enabling user to log on the email service".

Entire volu me of frequent sequences draws picture of the most popular content of the web portal. First conclusion which arises fro m this analysis to divide and group discovered knowledge to two different categories: (1) service-oriented and (2) content-oriented. First category relates to the hosted services via the web portal like email, advertisements, auctions, games, video on demand, dates. Second category relates to the shared content like information, news and plots. In this kind of the web portal, we are not able to recommend anything on the home page unless we violate user's privacy. On the other hand, keeping in mind high level of usability and visibility, the objects' arrangement should remain static. Therefore service-oriented content will not be considered to be recommended. Also, over 60% of d iscovered knowledge concerns users' actions while using email service. As an examp le let us deliberate on sequence below:

• [www];[email]/login.ht ml;[email]/ inbox.html;[email]/new- message.html;[email]/ logout.html
Such knowledge is useless for recommendation engine since it simp ly presents obvious and feasible actions during common session, restricted to single service. In this case, we decided to decrease the confidence ratio to four additional levels: 0,8; 0,7; 0,6 and 0,5. Table 3 shows the volume of discovered sequential association rules for five different levels of confidence ratio. min imu m confidence: ◊ 0.9 □ 0.8 ○ 0.7 θ 0.6 ⌂ 0.5

It can be noticed easily that simple and apparent indication has occurred -on every lower level of confidence the number o f ru les have increased. Finally, for 0,5 confidence more than 1710 rules were discovered. These 1138 ru les (difference between 0,5 and 0,9 confidence) are not likely to bring further knowledge of web data usage. Nevertheless, some interesting itemset groups were observed which will be added to knowledge base. An examp le o f useful sequence is presented below: At this point, previously undiscovered knowledge shall be reviewed and compared to that, which is already stored in knowledge base. Moreover, if discovered knowledge was transferred to knowledge base and its resources are engaged by recommendation engine, we are able to track the process of knowledge validation. It means that two measures recall and precision will determine degree of knowledge adequacy. In other words, we are able to determine quality of reco mmendations produced by the system.

Another step, which is possible to undertake and promises to discover new rules, is to decrease the value of the min imu m support. There is no general instruction with suggested value in any scenario. It is a subjective issue and relies on expert intuition and experience. In the next two iterations, we set up the value of minimu m support respectively on 0,05 and 0,001. In our opin ion it should be compro mise between timeconsumption and hardware requirements constraints. min imu m support: ◊ 0.01 □ 0.005 ○ 0.001

The program was executed under Eclipse environment with Java version 1.6.0 on IBM PC x86 co mputer with an Intel Core2 Quad processor 2.4 GHz and 2 GB Random Access Memory. Execution times are 55 minutes, 2 hours 30 minutes and 28 hours 16 minutes respectively to lower value of the minimu m support. The determination of the factors influencing on the effectiveness of algorithm covers an remarkab le research question. Unfortunately, we are not able to put forward straightforward answers.

Let us examine new sequences discovered throughout these two independent iterations. Though, we only focus on the set (○) because it is a superset of the other two sets (◊ and □). First of all, we can notice a enormous growth -almost 14 times larger set of frequent sequences was discovered, when value of minimu m support was set up on 0,001 co mparing to 0,01. This fact is worth deep consideration however our attention would be focused on the longest nine-items sequences which one of them is presented below: We asked ourselves: was it necessary to decrease value of minimu m support having in mind program time-consumption? Even some portion of discovered knowledge might be useful, there is a great risk that it would become inadequate. This situation happens when the content update is very often. Discovered sequences are not longer available to reach because its items (represented by links) are simp ly replaced by others.

In our approach we anticipated the last step which can help to discover relevant knowledge fro m web server log files. The assumption is simple: the domain expert shall determine service-o riented itemsets and any other irrelevant items and exclude them fro m the data. Then, the data is preprocessed again and process of web usage mining starts one more. Preliminary experiments have confirmed presented model in the next section.

A CONCEPT OF A VALIDATION PROCEDURE

In this section, we present an iterative model for discovering and validating web user navigation patterns. General assumptions of this procedure are as follo ws:

• Input data are the results of the previous described steps (data are collected then preprocessed to allow for discovering patterns). • The procedure consists of four steps where defined confidence and support parameters are changed in order to exclude irrelevant sets. • A domain expert is responsible for the validation generated knowledge base. He plays crucial role in order to exclude irrelevant sets -furthermore called also as an user. • The procedure is iterative what denotes active participant of the expert on different steps of validation with possibility of starting the procedure from the beginning. The graphical fo rm of the procedure is presented in Figure 2. In the first step, initial values for min imu m support and confidence are set by a user. Next, the pattern discovery process is performed and thus analyzed and evaluated by a user. Positively assessed knowledge is put into the knowledge base fro m where inference engine produces a list of recommendations to active user sessions. The effectiveness of this process can be measured by two metrics: recall and precision. Therefore the knowledge base is validated by them, expressing the degree of its adequacy. If the values of metrics are not satisfied, in the second step the confidence value is decreased.

Fig. 2. Iterative model for discovering and validating web user navigation patterns

Similarly, in the third step, a user can decrease the minimu m support value. If even in this case, values of evaluation metrics are not satisfied, a user specifies additional constraint by excluding sets which are irrelevant. If results are not satisfactory, the process can be started from the beginning.

CONCLUSIONS

In this paper, we introduced an interactive a user-driven model which addresses problem of validating web user navigation patterns. Experiments performed on web

Knowledge Validation

server file logs show that the model is useful and in some circu mstances can be used in large-scale web site environments. Conclusions based on our presented results can be divided into two groups. In the first group we have the confirmat ion of the general properties of the method of association rules, and detailed observations of Agrawal and Srikant algorith m and its implementation in the form of application.

Thanks to the cut-off at the level of support we discovered only the strong association rules. The number and size of the discovered association rules increase with the growth of the minimal support ratio. Cutting off the irrelevant sets of frequent factor support was imp lemented to be done at first, so that level has decisive influence on the uptime. Confidence factor, which determines the level at which the second cut-off is made after pruning of low-level support sets, has a significant impact on the final number of the rules, but the change of this factor does not affect the uptime. Nu mber of the elements of the association rules determines the strength of correlation (the more elements in the antecedent of a rule, the correlation is weaker, the more elements in the consequent of a rule, the correlation is stronger). This, in addition to the actual values of support and confidence, has a decisive influence on ordering rules in the final results.

The second group of the conclusions concerns the study -particular data that have been examined and usage of a mult istage pruning. The primary study revealed structure of the portal. In particu lar, there were ext racted two independent services which have extremely strong, static navigation paths. These services have their own audience and introduce artifacts which hinders the proper analysis. Furthermore, the hierarchical structure of informat ion service is reflected in the ext racted association rules.

Despite the relatively slight reduction in the size of data, allows to significantly reduce the parameters in the secondary study and obtain more relevant knowledge. In summary, the mult istage pruning seems to be accurate for use in the analysis that uses method of association rules. In addition, the method itself seems to give satisfactory results in discovering web users' navigation paths.

1 .

 1 Data collection, usage data can be collected fro m various sources like Web Server (e.g. log files), Client side (e.g. cookie files) or pro xy servers. 2. Data preprocessing, this phase concerns raw data files which often includes web server log files. There can be distinguish following tasks: (a) data cleaning and filtering, (b) de-spidering, (c) user identificat ion, (d) session identification and (e) path completion. 3. Pattern discovery, it can be seen as the data min ing step when comparing to KDD. The following methods and techniques can be applied: (a) statistical techniques, (b) association rules, (c) sequential patterns, (d) clustering and (e) classification. 4. Pattern analysis, where domain expert evaluates discovered knowledge and optionally does performance assessment. If necessary, some modeling methods and techniques can be applied, such as clustering and classification.

1. Set up support and confidence 2 . 3 .support threshold 4 .

 234 Decrease confidence threshold Decrease Determine and exclude irrelevant sets

Table 1 .

 1 In Web Usage Mining the major sources of data are Web Server and application server log files. We only used Web Server log files which are a set of Web users' activity record, reg istered by onet.pl -one of the most recognized Web portals in Poland. Web Server log files contain full history of access requests to files, shared on the Web Server. Usually, http server vendors apply Common Log Format (CLF) to the log files associated with http protocol service. This format was developed by CERN andThe data format of Web Server log files is specific in onet.pl (see Tab. 1) and includes seven variables. Sample entries, which represent Web users' activity, are presented below. The structure of raw Web Server log files.

	Data	Data	Pattern	Pattern
	Collection	Preprocessing	Discovery	Analysis
	Web Server	Preprocessed	Rules &	Interesting
	&Data Files	Data	Patterns	Knowledge

Table 2 .

 2 Itemsets and its support

	Itemset	Support	Itemset	Support
	www	78.48%	email/logout.html	14,09%
	email/login.html	27.08%	email/folder/delete.html	10,80%
	email/folder.html	25.49%	sport/football/news.html	10,22%
	info/world/item.html	20.27%	sport/formula one/news.html	9,88%
	email/folder/open.html	15,01%	info/homeland/item.html	9,18%

Table 3 .

 3 The volume of SAR

				Number of SAR
				Confidence
	Number of items	◊	□	○	θ	⌂
	2	65	79	95	118	142
	3	169	197	254	349	430
	4	196	225	315	480	585
	5	114	132	209	328	407
	6	28	32	68	111	146
	total	572	665	941	1386	1710

Table 4 .

 4 Frequent sequences for three different minimum support values.

			Frequent sequences
			Quantity		Change (◊=100)
	Number of items	◊	□	○	□	○
	1	64	103	276	61%	331%
	2	167	307	1522	84%	811%
	3	177	438	3279	147%	1753%
	4	418	338	3768	-19%	801%
	5	40	154	2625	285%	6463%
	6	14	44	1193	214%	8421%
	7	0	6	373	-	-
	8	0	0	73	-	-
	9	0	0	5	-	-
	total	880	1390	13114	58%	1390%