Kostas Anagnostou
email: kostasan@ionio.gr

Player Modeling using HOSVD towards Dynamic Difficulty Adjustment in Videogames

Keywords: Clustering algorithms, games, user modeling, Tensor Analysis 1

In this work, we propose and evaluate a Higher Order Singular Value Decomposition (HOSVD) of a tensor as a means to classify player behavior and adjust game difficulty dynamically. Applying this method to player data collected during a plethora of game sessions resulted in a reduction of the dimensionality of the classification problem and a robust classification of player behavior. Simultaneously HOSVD was able to perform significant data compression without significant reduction as regards to the accuracy of the classification outcome and furthermore, was able to alleviate the data sparseness problem common within data collected from game sessions.

Introduction

Designing a successful videogame depends among others on achieving a delicate balance between difficulty and user skill. Csikszentmihalyi's influential work on Flow [START_REF] Csikszentmihalyi | Flow: The Psychology of Optimal Experience[END_REF] dictates that in order to accomplish the optimal user experience, any interactive process (such as videogames) must tread constantly between two states, one of frustration and the other of boredom, never reaching any of them. Frustration in games can be the result of game challenges that are too hard for the user to achieve, while on the other hand boredom can result from game tasks that are too easy. Both states will undermine the player experience and are undesirable.

In order to avoid those two states, ideally, a videogame must constantly match the difficulty of the game challenges to the player capabilities. This entails providing the player with increasingly harder tasks, as her ability to solve those increases. Considering the huge player base, and the great variation in gameplaying experience, player capability and free time to devote to games, designing a game to satisfy many is no easy task.In an attempt to match game difficulty to player abilities, game designers have traditionally provided a "difficulty" setting. The player has to choose a priori between 3 or 4 difficulty levels (easy-medium-hard) before the game starts, with no real feeling of how well the difficulty level suits her abilities. Based on the chosen difficulty level, the game adjusts the number of enemies, enemy AI, player aim precision etc. A problem with this approach is that the user might misjudge the suitability of the selected difficulty level and her game playing experience might be thwarted by a too easy or too difficult game.Ideally, the game system should be able to monitor user performance and based on such data to accommodate for her playing abilities by adjusting the difficulty of the game to match those abilities, in order to maintain a high level of player engagement throughout. Recently, an increasing number of games, such as Microsoft's Halo Wars and SiN Episodes, are opting for a Dynamic Difficulty Adjustment (DDA) system, where the game changes the difficulty based on the runtime player performance [START_REF] Hunicke | The case for dynamic difficulty adjustment in games[END_REF] [START_REF] Adams | The Designer's Notebook: Difficulty Modes and Dynamic Difficulty Adjustment[END_REF]. DDA during game-playing can be numerical and/or structural. Numerical adjustment amounts to altering parameters such as the number of enemies, enemies' shield and weapon power and accuracy, using statistical models of player performance, in order to make the game easier or harder according to player skill [START_REF] Yannakakis | Player Modeling Impact on Player's Entertainment in Computer Games[END_REF] [START_REF] Kazemi | Metrics and Dynamic Difficulty in Ritual's SiN Episodes[END_REF]. According to Booth [START_REF] Booth | The AI Systems of Left 4 Dead[END_REF] Valve utilized such an approach be dynamically altering the location and frequency of spawn points for enemies and items in Left for Dead based on player performance. Structural adjustment on the other hand amounts to changing the structure of a game level dynamically according to player performance, using procedural level generation. Procedural level generation can be offline, i.e. before the game starts, such as in the case of Pedersen et al [START_REF] Pedersen | Modeling Payer Experience in Super Mario Bros[END_REF] who derive a statistical model of player challenge and frustration and by using evolutionary algorithms generate levels that match a particular level of player challenge. There applications on the other hand, such as Polymorph, which adjust the structure of the level during gameplay by generating sections of a level ahead of the player's movement, allowing a level to change in difficulty from start to finish in response to changes in the player's performance [START_REF] Jennings-Teats | Polymorph: dynamic difficulty adjustment through level generation[END_REF]. Yet, the basis of any approach for dynamic difficult adjustment, be it numerical or structural, offline or in the runtime, is the successful specification of the model of player behavior and performance from data gathered during gameplay. Any dynamic adjustment will made be according to this model.

Towards the extraction of the player model, in this paper we extend the work in [START_REF] Anagnostou | Data Mining for Player Modeling in Videogames[END_REF] by proposing the use of higher order singular value decomposition (HOSVD) of a tensor [START_REF] Lathauwer | A multilinear singular value decomposition[END_REF] for classification of a player, in order to maintain a high level of engagement. The suggested algorithm uses HOSVD to compute a small set of basis matrices that span the dominant subspace for each class of players. The basis matrices are then used to describe unknown players/games. Furthermore, the proposed methodology is able to exploit sparse data, such as the task at hand, where numerous games are difficult to be collected. This algorithm is closely related to SIMCA [START_REF] Wold | Pattern recognition by means of disjoint principal components models[END_REF] and PCA. Experimental results show interesting outcomes that deal with both increased classification accuracy and data compression.

Throughout recent years, tensor methods have been successfully applied to problems in pattern recognition and other areas. Tensors are known to be multidimensional or multimode matrices. In a plethora of real world pattern recognition applications, the data have a multidimensional structure and it is then somewhat unnatural to organize them as matrices or vectors. As an example, consider a video segment. Each image is a two-dimensional matrix of integers and together with images from different time frames the data constitute a third order tensor (three-dimensional data matrix). While most Machine Learning algorithms require data to be reformed as vectors, in many circumstances, it is beneficial to exploit the collected data without destroying its inherent multidimensional structure.

Methodology

The video game used for data collection was based on the Space Debris prototype developed at Ionian University. It is a top-down scrolling space action game in which the player has to defend Earth against waves of incoming alien invaders. The user can utilize a variety of weapons as well as the environment to eliminate the advancing menace.In this prototype, the action takes place within the confines of a single screen in which alien ships scroll downwards. There are two kinds of enemy spaceships, the cargo which is slow and has a stronger shield that can withstand more laser blasts and the fighter which is fast and easier to destroy. The cargo ship will maintain its course and will not attack the player except when she is directly in front of it. On the other hand the fighter ship has a more aggressive behavior and will alter its course in order to hunt and attack the player. At the end of each level, the user has to confront a large boss space ship which is equipped with strong shields and has more lethal weapons. The player's ship has a shield that can absorb enemy blasts. When this reaches zero, the player loses a life. When all three available lives have been lost, the game ends. The player wins only if she destroys the boss ship at the end of the level.

The game environment is littered with floating asteroids which can be used as a weapon against enemy ships. In their default state the asteroids do no interact (i.e. collide) with any of the game spaceships. In order to do so, an asteroid has to be "activated", i.e. hit by a player weapon. The asteroids never destroy the player's ship on collision. Also floating are shield and life power-ups which the user can use to replenish her ship's shield and increase lives.

The following list enumerates the types of weapons available to the player  A laser cannon which can used to shoot alien ships. The laser canon is weak and about 2-3 successful shots are required to destroy an enemy ship (except for the boss ship which requires many more). The laser can also be used to "activate" an asteroid and deflect it towards an enemy ship.  An asteroid-grab ray, which can capture any asteroid in the player's ship area, activate and hurl it, slingshot-like, towards an enemy ship.  A blast wave which centers on the player's ship position and expands outwards in a circular fashion, activating all asteroids in the expanding area. The activated asteroids will destroy any enemy ship they collide with.  A freeze wave, which centers on the player's ship position and expands outwards in a circular fashion, immobilizing all asteroids in the expanding area. An immobilized asteroid can act as a shield to enemy fire and can be activated and set in motion at any time, and guided towards enemy ships

The game design specifies the use of two main weapon mechanics: direct enemy ship destruction using the laser and indirect destruction through an activated asteroid. Table 1 summarizes the balance of the two mechanics (laser vs activated asteroid) in terms of enemy destruction effectiveness. This dichotomy between ease of use (laser) and effectiveness (activated asteroids) creates a choice for players to either use the fast but ineffective laser to kill enemies or to be more tactical and efficient by directing asteroids towards them. The first weapon mechanic is easier to use but not as efficient because each enemy ship's shield can withstand many laser hits. The second weapon mechanic is slightly harder to use, but highly efficient since the asteroid will destroy any enemy ship on its trajectory that happens to collide with.Based on the choice of game tactic, we initially assume two player types: The action-player which favors weapon simplicity over efficiency, and the tactical-player which favors weapon efficiency over ease of use.For those reasons we chose to use, as an input device, a videogame controller, and more specifically the standard Xbox360 controller which can be connected to a PC via a USB port, instead of a keyboard. The Xbox controller, as well as other videogame controllers, features 4 symmetrical buttons (labeled A, B, X and Y) which we use to map each of the 4 weapons, reducing the effect of weapon choice bias.

The video game was developed using XNA Game Studio 3.1, on the Windows XP platform. During gameplay, we recorded automatically, with a new code module developed especially for the game, a large set of parameters that describe the way each player approaches the game, be it in an action or more tactical style.

Data collection consisted of a single session in which 210 students from the Ionian University and the University of the Aegean played the game 4 times each (840 records in total). In addition to the player behavior data collected for each player we recorded the player gender, and whether or not he/she is an experienced game player. The sample population consisted of 150 males and 60 females. 66,67% of the male users were regular videogame players, and 26,6% of males had some game playing experience while only 0,66% had no experience at all. 50% of the female users had some game playing experience and 40% in the sample set of females had no experience at all 10% of female users declared themselves as experienced players.

For each game we collected a record of data illustrated in Table 2.

Introduction to Tensors

Informally speaking, an N th order tensor is an object with N indices. The "dimensions" of a tensor will be also referred to as modes. Vectors and matrices can be considered as first and second order tensors, respectively. Within the framework of this article, the order is defined as N = 3. Therefore, for reasons of simplicity, most of the theoretical issues concerning tensors shall be stated for third order tensors noted as:

K J I     
, where I,J,K are integers greater than zero. The dimensionality of the vector space

K J I    is I*J*K.
The aforementioned notation can be straightforwardly generalized to include further dimensions. It is clear that a tensor of order 0 is a scalar, while a tensor of order 1 is a vector and a tensor of order 2 is a matrix. Most of the notation used is borrowed from data mining and especially from data warehousing literature, therefore, readers familiar to such concepts could comprehend more effortlessly since the definitions used follow many of the data cubes notions. Treating tensors as multidimensional arrays is a convenient way of processing high-dimensional data, since we are also interested in extracting arrays of lower dimensionality. A vector can be extracted along any mode, forming a fiber. Furthermore, when a single plane from an order-𝑟 tensor on any mode is extracted, a matrix known as a slice is produced. Slices and fibers of a third order tensor are illustrated in Fig. 1 and Fig. 2, respectively.

Proposed algorithm

For reasons of computational complexity, we have emphasized throughout the whole design and experimental phase to 3 rd order tensors, since considering a tensor that contained at once all the 19 game input parameters described in Table 2 is unrealistic. The choice of which three parameters to choose each time was based solely on the criterion of the lowest error rate in terms of classification accuracy. Figure 3 depicts tensor decomposition example for three of the most significant input features, as it turned out from the experimental section, namely Lasers, BlastWaves and Ene-miesKilledbyLasers. Features that contained numeric values were discretized into 20 bins, so that each game that was encoded as a point in a 20 20 20    space. The choice of the discretization intervals was done according to the unsupervised method of Tree-based density estimation [START_REF] Schmidberger | Unsupervised Discretization Using Tree-Based Density Estimation[END_REF]. Furthermore, each game was manually annotated, through external observation during game playing, as belonging to the tactical or the action user attitude (the class), so it is straightforward to believe that games of the training set constitute 2 well separated clusters, otherwise any other classification algorithm would perform poorly. The most representative vectors of each cluster span a subspace in 20 20 20   

. The idea behind the proposed algorithm is to construct a set of orthogonal vectors that span the dominant elements of each cluster. An unlabeled, unseen game can be classified by estimating the approximation error for each of the 2 clusters. Basis vectors are approximated using HOSVD.

Classification Algorithm

The following algorithm describes the training phase: x are unknown scalars to be determined.

Due to the fact that matrices are all orthogonal, the solution is given by:

      l i U U i A G c M

Conclusions

Modeling player behavior can be a means to understand her game-playing skills and preferences. This, in turn, can provide game developers with the tools to adjust the game challenges in order to better match the player capabilities, potentially resulting in higher engagement and user-satisfaction.In our experiments, using this robust 3mode tensor, game modeling experts could extract useful patterns and verify the actual parameters that define the problem. Using this knowledge, one can straightforwardly classify (we remind readers that the classifier is very fast in the test phase) new players according to the predefined behavior easily, based on a tutorial or introductory playing session, considering only the reduced set of attributes, a considerably faster process.

Fig. 1 .

 1 Fig.1.Slices of the (a) first (horizontal), (b) second (latteral) and (c) third (frontal) modes.

Fig. 2 .

 2 Fig.2.Fibers of the (a) first (column fibers), (b) second (row fibers) and (c) third (tube fibers) modes.

Fig. 3 .

 3 Fig.3.Illustration of a third order HOSVD decomposition considering 3 of the 19 game features. The core tensor contains concept strengths, while the projection matrices represent modeto-concept similarities.

1 for each class 2 for d=1 to 3 2

 3 Temp=A n1xn2xn3 (A n1xn2xn3 ) T /*the covariance matrix of mode-d matricization*/ 3 Set U n1xn2xn3 to be the r leading left eigenvectors of Temp 4 Upon completion of the training phase, suppose a new game G is encountered. The testing phase deals with identifying which set of orthogonal projections per class describes it best. This is actually a minimization problem: c denotes the class.  l denotes the projected training examples per class and  c i

Table 1 .Weaponbalance

 1

	Weapon	CargoShip	FighterShip
	Laser	3 successful shots per ship	2 successful shots per ship
	Activated Asteroid	Instant death, many ships	Instant death, many ships

Table 2 .

 2 Data Collectedforeach Game

		Parameter	Description
		Time	Time required to finish the current game
		Accuracy	Percentage of player laser blasts that found a tar-
			get
		LasersAvoided	Number of enemy lasers the user avoided
		Lasers	Number of laser blasts fired by the user
		BlastWaves	Number of blast waves used
		Freezers	Number of asteroid freezers used
		Grabbers	Number of asteroid grabbers used
		KeysPerSecond	User key press rate
		Carriers	Number of enemy carriers destroyed
		Fighters	Number of enemy fighters destroyed
		KilledByLaser	Number of enemies killed by laser
		KilledByAsteroid	Number of enemies killed by asteroid
		LasersHitAsteroid	Number of user laser blasts that hit an asteroid
		LasersHitEnemy	Number of user laser blasts that hit an enemy
		LasersMissed	Number of user laser blasts that missed
		ShieldsUsed	Number of shield upgrades used
		LivesUsed	Number of life upgrades used
		BossTime	Time required to destroy the Boss ship
		Result	Whether the player won the game or not
	3	User Modeling with HOSVD

Classification by compression using HOSVD

The methodology of HOSVD can be additionally applied to compress the training set prior to the calculation of the basis matrices for the different classes. In this section, some mathematical formulations are provided, which are in a close analogy with low rank matrix approximations. The advantage is based on the fact that games from different users (action or tactical) are all projected onto one common subspace. Hence, an unknown game is only projected once, which is a substantial decrease in term of computational cost both in terms of computations and memory allocation. Furthermore, compression can also be applied to the class dimension, reducing noisy instances and creating a more compact database if one collects a plethora of gameplay data.In the training phase, a tensor D is built by using all games from the training set. They are organized in such a way that every slice contains games from the same class.

The HOSVD approach decomposes D from 4000 20 20 20

and the amount of game instances in each separate class c. Let D have the HOSVD

. Under the assumption that both r and c are significantly smaller than the original values, high compression rates could be achieved without compromising the classification robustness. In the next section, we tabulate experiments that point towards this belief.

Experimental Results

The evaluation approach dealt with identifying which triplet of all attributes described in Table ΙΙΙ best describes user models according to their behavioral patterns. The test set consisted of 840 games played by 210 different players, 150 male and 60 female.

Each game was manually annotated by the authors according to whether they belonged to the tactical or the action class. In this section, we present the classification outcome for the four best attribute triplets in relation to classification error rate, as well as results from the compression phase, concluding with some performance metrics in terms of computational cost. Up to 16 basis matrices for each class were used in the classification and 10 least square problems were solved. In each experiment, the same number of basis matrices was kept for all classes. Figures 4 to 5 depict the error rate of the two best 3-mode tensors from the available set of game input features.As can be observed the best result is provided by the tensor which models Lasers, BlastWaves and EnemiesKilledbyAsteroid attributes. The error rate is approximately 4,5% which is reached at around 12 basis matrices. In Table 4, we provide classification results from the complete dataset by using the K-Nearest-Neighbor and Support Vector Machines algorithms, two well-known approaches that have been previously used in many data mining tasks with successful outcomes.Furthemore, their error rate is almost identical to that of 3-mode tensor modeling, a fact that supports our claim that even low-mode tensors can reveal useful patterns from sparse data. Another triplet of significant results is that of Lasers-Grabbers-EnemiesMissed. The error rate is slightly higher than that of the previous case and again it is achieved when the number of basis matrices increases from 11 to 13. The same principle applies to the other two attribute triplets. From the above figures, we can conclude that a plethora of attributes, initially considered as important, such as the time required to kill the Boss (BossTime), the number of cargo (Carriers) and fighter (Fighter) ships the player has destroyed etc., do not seem to play an important role in deciding whether a player's style is tactical or action-oriented. Furthermore, the Laser attribute is very important since it is present in the top-3 of the 3-mode tensors as regards to error rate.


Carl Barton
email: carl.barton@kcl.ac.uk

Emilios Cambouropoulos
email: emilios@mus.auth.gr

Costas S Iliopoulos

Zsuzsanna Lipták
email: zsuzsanna.liptak@univr.it

Melodic String Matching Via Interval Consolidation And Fragmentation

Keywords: melodic pattern matching, string matching, pitch intervals

In this paper, we address the problem of melodic string matching that enables identification of varied (ornamented) instances of a given melodic pattern. To this aim, a new set of edit distance operations adequate for pitch interval strings is introduced. Insertion, deletion and replacement operations are abolished as irrelevant. Consolidation and fragmentation are retained, but adapted to the pitch interval domain, i.e., two or more intervals of one string may be matched to an interval from a second string through consolidation or fragmentation. The melodic interval string matching problem consists of finding all occurrences of a given pattern in a melodic sequence that takes into account exact matches, consolidations and fragmentations of intervals in both the sequence and the pattern. We show some properties of the problem and an algorithm that solves this problem is proposed.

Introduction

As vast amounts of audio recordings, MIDI files and sheet music become available on the web, efficient Music Information Retrieval (MIR) methods are indispensable for organising and accessing this data, not only in terms of metadata but primarily in terms of musical content (content-based MIR). Most current MIR applications are still in early stages of development and are, usually, not robust, general, or efficient enough.

One key problem that hampers attempts to build reliable and robust systems is the lack of explicit structural information in musical data (lack of the equivalent of words or phrases in language). Content-based MIR systems commonly operate on primitive descriptors extracted from audio or on the elementary musical surface (i.e. sequences of note symbols), and do not have access to the kind of rich higher-level musical information that humans use when storing and accessing musical data (in a sense, it is like having text IR systems operating on mere strings of letters without spaces). Extracting musically pertinent features, especially significant repeating melodic patterns as discussed in this paper, can enormously increase effectiveness and efficiency of music information indexing and retrieval systems. Extracting melodies and rhythms from sequences is a difficult problem which has been researched in the past but generally these algorithms work just on notes in a MIDI like representation and not on pitch intervals. This leads to the problem that the methods used are not transposition invariant and can often struggle to take into account some of the natural variations that occur in music sequences.

Ornamentation, embellishment, elaboration, filling in, thinning out, and reduction are common strategies employed by composers in order to generate new musical material that is recognised as being similar to an initial (or underlying) musical pattern. This way musical unity and homogeneity is retained, whilst at the same time, variation and change occur. This interplay between repetition, variation and change makes music 'meaningful' and interesting. Musical passages are often heard as ornamented or reduced versions of other passages. Listeners are capable of discerning common elements between varied musical material primarily through reduction, i.e. identifying 'essential' common characteristics. The capacity of listeners to 'match' varied musical materials is essential to the process of identifying meaningful musical entities such as interesting motifs, themes, melodic and rhythmic patterns, characteristic harmonic progressions, and other memorable musical entities.

Pattern matching methods are commonly employed to capture musical variation, especially melodic variation [START_REF] Crawford | Pattern processing in melodic sequences: Challenges, caveats and prospects[END_REF][6] [START_REF] Hewlett | Melodic Similarity: Concepts, Procedures, and Applications[END_REF]. Dynamic programming techniques, often based on various types of edit distance, are used to find patterns in melodic strings. In this paper, we maintain that techniques using standard edit distance operations (replacement, insertion, deletion, along with consolidation and fragmentation) applied on strings of notes are limited and have inherent shortcomings. Instead, we redefine the problem of matching in a way that is appropriate for strings of melodic intervals (not notes). To this aim, we abolish the replacement, insertion and deletion operations, and retain only consolidation and fragmentation operations which are adapted to the interval domain. It is shown that this new definition of the problem of melodic matching enables more reliable matches and is also transposition invariant.

In this paper we consider the 'Melodic String Matching Via Interval Consolidation and Fragmentation' problem and give optimal algorithms that will find all occurrences of a pattern p in a text t allowing for consolidations and fragmentations.

The paper is structured as follows: In Section 1 we introduce the problem, in Section 2 we describe the problem and give preliminaries and present some important properties used in our analysis, in Sections 3-5 we give our algorithms, in Section 6 experimental results and future improvements.

The Melodic String Matching Via Interval Consolidation and Fragmentation Problem

Pattern matching methods are commonly employed to capture musical variation (especially melodic variation). Dynamic programming techniques, often based on various types of edit distance, are used to find patterns in melodic strings. The most common edit operations in melodic string matching are insertion (inserting a note), deletion (deleting of a note) and replacement (replacing a note). Mongeau and Sankoff [START_REF] Mongeau | Comparison of musical sequences[END_REF] suggest two additional operations: fragmentation (division of a note into multiple notes of the same pitch) and consolidation (combining multiple notes in a single note). The minimum number of operations that are necessary for making two strings identical is called edit distance; this distance is a measure of similarity between the two strings. In Figure 1, the first melody is transformed into the second melody if the notes indicated by an asterisk are deleted/inserted as appropriate.

-2 2 -2 -2 -1 -2 -1 1 -2 2
-4 4 -5 5 -7 7 -8 8 -7 Edit distance is usually applied to strings of pitches. This distance is problematic, however, when applied to strings of pitch intervals. The reason is that the deletion, insertion or replacement of a pitch interval in a melodic sequence changes radically the initial sequence. If for instance, a 2 semitone interval is replaced by a 3 semitone interval, the rest of the melody following this interval is transposed by 1 semitone in a remote key and thus the quality of the melody is altered drastically [START_REF] Crawford | Pattern processing in melodic sequences: Challenges, caveats and prospects[END_REF].

The use of edit distance in strings on notes (not intervals) also has some shortcomings. Firstly, in order to account for transpositions it is necessary to transpose the query to 12 different keys and search the target string twelve times. Secondly, it is difficult to define a distance threshold beyond which two strings do not match. If enough edit operations are performed any string can be made identical to any other string -such strings, however, may be very dissimilar. An appropriate distance threshold has to be determined in order for edit distance to account for plausible similarity ratings; determining such a threshold is not straightforward.

In this paper, we address the problem of melodic string matching, introducing a new set of operations that are adequate for pitch interval strings. Insertion, deletion and replacement are abolished as irrelevant. Consolidation and fragmentation are retained but adapted to the pitch interval domain (they can also be applied to durations). That is, two or more intervals of one string may be matched to an interval from a second string through consolidation or fragmentation (see table in Figure 1).

Working with intervals means melodic matching is transposition-invariant. Additionally, matching is confined by the consolidation and fragmentation operations (the only threshold necessary is the maximum number of intervals an interval may be broken down to).

Let us examine one musical example (Figure 2) in more detail. According to our proposed interval consolidation and fragmentation operations (see tables in Figure 2), the top melodic query matches fully with instances (a) and (c) in agreement with standard musical knowledge/intuition (actually the query and instance c are elaborations of instance a). The query matches partially with instance b (except for the last interval). Finally, only the first two intervals of instance d match with the first interval of the query; this is the weakest match. These match results are rather plausible according to our general musical understanding. In this same example we get quite different results in terms of the standard edit distance operations (for pitch only -query transposed in 12 different keys). The query is measured to be most similar to instance b (only one replacement for the last note), and the other three instances are equidistant to the query (four operations in each case). These results are counter-intuitive (a and c are most similar to the query, then b, and lastly d). Although it is simple to construct a dynamic programming matrix to find an alignment of the pattern with the melody, this won't find all the occurrences of the melody; an operation which is useful for musical analysis. Additionally by not using the dynamic programming approach we can avoid the problem of determining a good threshold and can reduce the high memory usage needed by such dynamic program techniques. This is our motivation for considering our problem.

Formal Definition

Let Σ ⊂ Z be a finite alphabet of integers. A string is a sequence of symbols from Σ and the set of all strings over the alphabet is denoted by Σ * . Melodic string matching is a pattern matching problem where we wish to find all occurrences of a pattern within a text. Throughout the paper the use the following notation: p represents the pattern of length m, t is the text of length n. The i -th element of the pattern (text) is denoted by pi (ti ). A factor of a word t starting at i and finishing at j is represented by t[i...j].

Melodic string matching via consolidations and fragmentation is a string matching problem where we are given a text t = t1 ...tn and pattern p = p1 , ..., pm over an alphabet . Σ The problem is to find all occurrences of p in t, where an occurrence of p can consist of three operations -equal (ti matches pj ) -consolidation (ti + ti+1 + ..ti+j matches pk ) -fragmentation (tk matches pi + pi+1 + ..pi+j ) The total number of summations allowed for a single character is bounded by a parameter . З Now we present some important properties of the problem which will be used in our analysis of the algorithm.

Lemma 1 For a pattern of size m there are O(2 m-1 ) valid combinations of the pattern, where З >= m.

Proof . We can encode pattern combinations as a bit mask, Where a 1 at position i represents a summation between i and i+1 and 0 otherwise. Where summations are bounded by З this means that a valid pattern is a binary string of length m which avoid factors 1 m-1 . So where З >= m this consists of all the binary words of length m-1, the total combinations is bounded by O(2 m-1 ).

Lemma 2 For a valid pattern combination there are O(2 n-1 ) valid occurrences at a position i in the text, where З = n.

Proof. We can make a similar argument as Lemma 1 for Lemma 2. If we encode the valid summations in the text as a bit mask. In the worst case a text and pattern of all 0s, where З = n we have O(2 n-1 ).

Lemma 3 There are at most O(n2 n+m-2 ) occurrences of a pattern of size m in a text of size n where З = n. Proof. By Lemma 1 and 2 we have at most O(2 n+m-2 ) occurrences at each position in the worst case and at n positions. Therefore O(n2 n+m-2 ) occurrences overall.

Theorem 1 It will take at least Ω(n2 n+m-2 m) in the worst case to solve the Melodic string matching problem via interval consolidation and fragmentation.

Proof. By Lemma 3 there are at most O(n2 n+m-2 ) occurrences in a string, therefore, any algorithm solving this problem will have a worst case of at least Ω(n2 n+m-2 m)if we wish to individually report every occurrence.

We present a simple binary search based algorithm. The main idea behind this algorithm is to use a binary search to identify only those sections of the text where a valid occurrence of the pattern could possibly occur. This filtering step based on the following 2 observations. Observation 1 For the pattern to occur it must occur in a section of the text that sums up to M, where M is the sum of the entire pattern. We call an interval of the text which sums to M, a submass [START_REF] Bansal | Finding submasses in weighted strings with fast fourier transform[END_REF] of size M.

Observation 2 P is a submass of s with occurrence at position (i, j) if and only if s = s1 + . . . + sj -s1 + . . . + si-1. [START_REF] Becker | Sequencing from compomers: Using mass spectrometry for DNA de-novo sequencing of 200+ nt[END_REF][START_REF] Cieliebak | Algorithmic complexity of protein identification: combinatorics of weighted strings[END_REF] Within these valid sections of the text we then need to try pattern combinations of the same length as the section. Although simple this technique means, on average, we will drastically reduce the number of pattern combinations we need to check. This filtering technique is similar to that used in the Karp Rabin [START_REF] Karp | Efficient Randomized Pattern-Matching Algorithms[END_REF] string matching algorithm where we are using a very simple hashing function. An outline of the algorithm is given below.

Step 1 Calculate the sum of every prefix of t and store them as an array called PSA [i]. Such that PSA[i] = s1 + . . . + si . We store these values as pairs (PSA[i], i) to make identifying candidate segments easier later on.

Step 2 Sort the PSA array by the first value of each pair using a stable sorting algorithm, we call the resulting array the SPSA array.

Step 3 Identify all candidate segments by performing a binary search for all submasses M in the original string, we do this for each position i in the text. For example, if PSA[i] = 15 and M = 9 we would search for 15 -9 = 14. Where there are multiple occurrences of the same number we can also do a binary search for the end position of this match. For each candidate segment we must do a further check to ensure that all reported candidates are valid, as it is possible that some impossible candidate segments are reported e.g. those segments (i, j) with j < i .

Step 4 For each candidate segment of the text we must check pattern combinations within this fixed length. Checking the pattern combinations can be done using a restricted version of the brute force method. The restricted brute force method is similar to the standard brute force technique, however, only combinations which fit exactly in the candidate section will be checked. Time taken for this depends on the number of candidate intervals identified.

Step 1 requires us to compute the prefix sum for every index which will take Θ(n) as each sum can be computed in constant time based on the sum for the previous index. Sorting the PSA array is simple and we can use any algorithm such as merge sort and this will take O(n log n). Step 3 requires us to make n binary searches to find all of the candidate areas where an occurrence of the pattern could occur. As each binary search takes O(log n) and we need to do n binary searches in total we will take O(n log n) for every binary search. Step 4 is the most time consuming step in the algorithm and in the worst case it could be up to O(2 n+m-2 ) due to the maximum number of possible matches within a candidate segment, although in practice it will be much lower as this can only occur if the pattern and text are all 0 which wouldn't happen in practice. So the total runtime of this algorithm will be dominated by the final step of the algorithm, however, as previously mentioned, in practice we wouldn't ever realise this worst case as such strings wouldn't be interesting pieces of music or interesting melodies. The algorithm correctly identifies most of the variations of the theme in its various guises. Especially, the reduced versions of the theme are successfully recognised. The original theme is recognised directly only in Variation II (match of other variations is unsuccessful as many-to-many interval interval matching is required -see discussion below). A slightly reduced version of the theme (Q1 in Figure 3) is matched to Variations I, II, and V, whereas a further reduced version (Q2 in Figure 3) is matched to Variations I, II, V and VI. The reduced queries would be matched to Variation IV if a mod12 matching of intervals was allowed (or if the first note of each measure was transposed upwards by an octave); they would also be matched to Variation III if a tolerance of +/-1 semitone is introduced (Var III is in C minor). The algorithm is quite successful is capturing quite severe alteration of the melodic material.

Results for some queries can be seen in Table 1. The table shows the number of occurrences of each pattern as identified by our algorithm for three queries (ThemeStart, Reduction1, Reduction2) and for three summation thresholds (7, 8 & 9). The query ThemeStart corresponds to the first two measures of the original theme (Orig. in Figure 3). The queries Reduction1 and Reduction2 correspond to queries Q1 and Q2 of Figure 3 respectively (but Q2 is four measures long). The spurious large numbers for larger summations depicted in the table may occur due to the presence of 0s or intervals that sum to 0 which can lead to reporting many false positives as explained in section 3. The large number of combinations found for ThemeStart may be reduced if, for instance, durations are taken into account (see below). Reduction 2 5 12 16 10 12 16 11 13 14 0 0 0 0 0 0 0 0 4 20 26 31 There are, various shortcomings in the current preliminary attempt to solve this relatively difficult melodic matching problem. Firstly, the algorithm identifies the correct instances but additionally finds in some occasions many false positives that are not significant (see table 1); this is particularly strong when the consolidation/fragmentation limit (number of summations) is large. There are various ways to deal with this issue. An obvious way is to extend matching to include duration consolidation/fragmentation (when a pitch interval is fragmented/consolidated so are the rhythmic durations fragmented/consolidated). Another way is to add extra constraints such as an overall number of fragmentations/consolidations allowed per query (similar to -approximate matching where a threshold for a valid match is γ defined as the sum of the differences over the entire match [START_REF] Crochemore | Algorithms for computing approximate repetitions in musical sequences[END_REF]).

Original

Secondly, the current implementation allows only one-to-many and many-to-one matches (that is one interval consolidated/fragmented to many intervals). This way it is unlikely that two ornamented versions of the same underlying melody can be matched (e.g. the original theme of Figure 3 with variations). The current algorithm would be more successful if ornamentations were stripped away from a query melody before applying pattern matching.

Thirdly, in the current version of the algorithm interval matching (of consolidated/fragmented intervals) is exact (i.e. intervals add up exactly to the matched interval). This may be unnecessary. It may be useful to allow some tolerance, e.g., ±1 semitone, to account for matches of patterns, for instance, in relative or parallel keys. This would be a kind of -approximate matching δ [START_REF] Crochemore | Algorithms for computing approximate repetitions in musical sequences[END_REF]. Overall, the algorithm is performing as expected and is successful in capturing melodic variation. Further testing, however, is necessary. In particular we plan to make use of precision and recall type analysis to determine the accuracy of our algorithm. As our algorithm will identifies all occurrences of a pattern it is clear that in certain situations we will identify many occurrences that are not true occurrences of the melody, so testing the precision of our algorithm will be a very important metric in determining it's effectiveness. Additionally, larger groundtruth testdata are necessary. Apart from testing, further research is required to improve it and make it more robust and reliable.

In this paper we have defined the problem of matching melodic patterns in a novel way, such that ornamentation and variation can be naturally accommodated. This new approach allows the development of new flexible transposition-invariant melodic matching techniques that can identify melodic patterns exhibiting various degrees of variation/transformation.

We have proposed one algorithmic solution to this problem and tested it on artificial and actual melodic data. We have shown that the proposed technique yields musically meaningful results. At the same time a number of potential shortcomings have been identified and discussed in the previous section. Although we have shown that the algorithm is quicker in a number of situations, it is clear that we need to perform a more thorough and rigorous experimental analysis of the algorithm. Further research is required to improve the current version and to show its full potential. The improvements proposed in the previous section are expected to increase the performance and effectiveness of the algorithm.

Figure 1

 1 Figure 1 Beginning of Toccata (a) and theme of Fugue (b) from Bach's D-minor Toccata and Fugue BWV 565. Intervals of one excerpt may be fragmented or consolidated in the other excerpt as depicted in the table.

Figure 2

 2 Figure 2 The top query matches fully with instances (a) and (c), matches partially with instance (b) except for the last interval, and, in case (d), only the first two intervals match with the first interval of the query (solid line tables indicate matches).

Figure 3

 3 Figure 3 Beginning of Theme and 6 Variations from Mozart's Sonata in A major KV331. The two queries at the top match most of the variations (see text).

Table 1

 1 Number of occurrences found in each text, for each query and summation size.


Dimitrios Kravvaris

Katia L Kermanidis

Eleni Thanou
email: elenithanou@gmail.com

Success Is Hidden in the Students' Data

Keywords: Data mining, educational, classification, support vector machines, complexity, bagging, boosting, attribute selection

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

Introduction

Our research focused on a) evaluating the success or failure of students in attending a course and b) analyzing the attributes from the dataset that we acquired in order to obtain useful information about the course. The learning procedure involved a coeducational (blended learning) training method in order for the students to obtain a computer skills certificate. Data was collected automatically using the Moodle elearning platform [START_REF] Romero | Data mining in course management systems: Moodle case study and tutorial[END_REF], [START_REF] Romero | Handbook of Educational Datamining[END_REF], which was used to implement the lesson plan from a human resources training organization.

The first objective of our study was to find the best classification model for our case. Previous researches by others [START_REF] Bresfelean | Determining students academic failure profile founded on data mining methods[END_REF], [START_REF] Hamiiliiinen | Comparison of machine learning methods for intelligent tutoring systems[END_REF], [START_REF] Zang | Investigation of web-based teaching and learning by boosting algorithms[END_REF], [START_REF] Romero | Data mining algorithms to classify students[END_REF] have shown that the prediction of student's outcome attending a specific course has been primarily done within academic institutions. A variety of algorithms such as Decision Trees, Bayesian Networks, Neural Networks, K-Nearest Neighbor and Support Vector Machines (SVM) have been used and the best value for classification accuracy did not exceed 90%. The second objective was to determine at which time point of the lesson we could satisfy the classification accuracy in order to predict the students outcome. Finally the third objective of our study was to analyze the attributes from the dataset in order to obtain useful information about the course structure and the students' profiles.

In previous work the datasets were drawn from K-12 or college students where their profiles, behaviors and goals have different characteristics from those of our study. The students' data obtained for this particular survey were provided from a Vocational Training Institution and concerned a computer skills training program in Microsoft Word. These institutions focus on training workers or those who are unemployed in an effort to enhance their existing qualifications. The characteristics and the behavior of the students that were attending a computer skills training course were not similar to K-12 or college students that were examined in previous work. With this survey we expand the research from schools and universities to companies and training institutions.

The classification done in our study used the SVM algorithm. We chose to use SVM since it is widely used within the data mining community and satisfies the objectives of our research protocol. Specifically SVM [START_REF] Romero | Handbook of Educational Datamining[END_REF] a) can create a general purpose model (as opposed to a local), b) can handle non-linear class boundaries, c) is accurate on small datasets, d) deals well with spaces where the majority of data is numerical and e) can easily be adapted directly to the current state of the user.

With regards to the attributes of the dataset we found that emphasis was placed on the monitoring time per unit instead of the total time monitoring of the course as indicated by other investigators. This is of particular importance to the learning process since the student must be connected to the platform in order to monitor the course online. The reason for this is that the systems policy makes the students unable to download the course material locally to their computers. It is clear that the time devoted to studying or reading the material is useful in an educational setting and is essential in maintaining the flow of learning. The ultimate goal of the present study is to provide the necessary information tools to teachers and course administrators in order to help students successfully complete the training course.

Dataset

Our study used one particular dataset in which the participants were certified in Microsoft Word. The dataset has 511 examples and their attributes are listed in the table 1.

The demographic attributes of our trainees were based on Age (years old) and Education (secondary or higher education). The course attributes consisted of Word01 to Word15 which dealt with monitoring time per unit, WordTheory was the time of all theory activities, WordTest was the time that the student used to complete the Microsoft Word tests and WordSum shows the summarized time that the students were connected to the Moodle platform.

The classification system used is based on two values (binary), which are Success or Failure (WordResults) of the course in question. The reason for this classification system is based on the fact that we are not concerned with the overall grade the student receives but whether or not they passed or failed the subject of interest.

Methodology

Classification method

Support Vector Machines. An important role in our research is the detailed configuration of the classification algorithm Support Vector Machines (SVM). The configuration was done using the software Weka, where it was possible to change the complexity as well as the kernel function parameters of SVM [START_REF] Hearst | Support Vector Machines, Intelligent Systems and their Applications[END_REF]. With regards to Weka the SVM uses the algorithm sequential minimal optimization developed by John C. Platt and will be referred to as SMO.

Kernel Functions. For our research purposes the kernel functions [START_REF] Burges | A Tutorial on Support Vector Machines for Pattern Recognition[END_REF] that parameterize Weka's SMO in our experiment are the following.

Radial Basis Function (RBFKernel).

Concerning the Radial Basis Function kernel [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization[END_REF], [START_REF] Scholkopf | Comparing support vector machines with Gaussian kernels to radial basis function classifiers[END_REF] the γ (gamma) parameter of Weka is represented by 1/2σ 2 in the formula below, which has a Gaussian distribution.

Pearson VII Function (Puk). The Pearson VII function has the flexibility to change from a Gaussian to that of a Lorentzian distribution or an intermediate of the two [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization[END_REF]. This flexibility gives more power especially in the representation of Puk, compared to simple linear, polynomial and RBF kernel functions. The Puk function has two parameters, namely ω (omega) and σ (sigma), as depicted in the next formula.

The ω and σ variables control the width and shape (that is the behavior of the tail) of the Pearson VII function distribution.

Polynomial (Polykernel).

Using the polynomial kernel function [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization[END_REF] one parameter can be changed and that is the exponent p as shown in the formula below, however, there is no specific rule in choosing the exponent allowing for more than one test to be performed.

Complexity. The parameter C of the SMO algorithm in Weka refers to the complexity, which determines the soft/hard margin for the SVM algorithm. The role of complexity in our survey is rather critical because the number of the examples is small and we must avoid the classification overfitting models [START_REF] Witten | Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations[END_REF]. If C is too high, then a solution with minimum error classification might be reachable, but at a high risk of overfitting, as shown below in figure 1.

Early prediction

For the part of our survey concerning the early prediction of trainee outcome, we created new datasets from the original one (Word dataset). Those new datasets consists of demographic attributes and the course attributes which dealt with monitoring time per unit, adding one attribute at a time giving us 18 datasets (dw1 to dw18). The accelerating number in datasets represents the time flow of the course per section. We proceeded with classification for each dataset and we observed the accuracy values according the course flow.

Attribute selection

For the part of our survey concerning the attribute selection of the Word dataset we used a voting principal in order to obtain results using a variety of methods. We used a combination of search and evaluation methods as shown in table 2 [START_REF] Kirkby | WEKA Explore User Guide[END_REF]. The results were statistical analyzed choosing the top six attributes (which represents 1/3 of the total number of attributes evaluated) of each combination.

Bagging and Boosting

We next focused on experiments using two classification ensemble models. First we tried to increase the accuracy of the Bagging [START_REF] Breiman | Bagging Predictors[END_REF] and Boosting (AdaboostM1) [START_REF] Han | Data Mining: Concepts and Techniques[END_REF] classifiers by using 10 iterations of the best algorithm we have found thus far, namely SVM using Puk were ω=1, σ=1 and C=14. The method gave a Bagging classification accuracy rate of 96.8689% and Boosting equal to 96.0861%.

Interestingly there was no increase in the accuracy when either Bagging or Boosting was used as shown above. This may be attributed to a high complexity C=14 and for this reason we chose to control the value of complexity (1-20). Our results showed that the accuracy rate of Bagging rose to 97.2603% when C=8 and Boosting rose to 96.2818% when C=1 (figure 4).

Using complexity C=14 lead to an extreme variation in the data as seen in figure 2, however if we choose a complexity C=8 this yielded the second best performance for the SVM (using Puk kernel function). With this adjustment in the complexity this leads to the same classification accuracy using the Bagging method equals to 97.2603%. This is a valuable tool for avoiding overfitting the classification method to the training data.

Early Prediction

According to our findings we choose for classification the following parameterization Bagging using 10 iterations of SVM (Puk , ω=1, σ=1), this particular parameterization is best suited for the type of data that we are using according to our previous experiments. In order to avoid the classifier's data overfitting, because the datasets have a small number of attributes and examples we choose a low value of complexity C=1. The datasets we examined were arranged sequentially and represent a timeline, which depicts the monitoring of the online course (e.g. the first monitored unit is represented by dw1 dataset, the first and the second unit is represented by dw2 etc.). As shown in figure 5 the classification accuracy rises significantly earlier in the timeline rather than later and we can have a high value of classification accuracy (94.9119%) when the course timeline reaches the middle of the course (dw9 dataset). In addition, to the course attributes studied we next evaluated AGE and its association with the time that students spent to successfully complete the course. Groups were separated based on their age and a statistically significant difference was observed as shown in figure 6b. From this diagram we can see that students with an age greater than 40 needs on average 38% more time to successfully get certified in a computer training course compared to students that are less than 25 years old.

Conclusions

In studying the classification of SVM using three different function kernels (Polykernel, RBFKernel and Puk) it was determined that these functions play an important role in analyzing data obtained under our experimental conditions. Based on the configuration of the complexity within the SVM algorithm and using the different kernel functions, it was observed that Puk gave the highest classification accuracy of 97.456%. The results from this study suggest that using the Bagging ensemble method was better suited for the data and gave a classification accuracy rate of 97.2603%, which was achieved with less complexity rather than using the classifier SVM alone. With this we attempt to reduce the margin of error with respect to the classification of success or failure, thus having a general model of classification for predicting trainee outcome in a computer skills training course.

Secondly studying at which time point of the lesson we could have satisfied classification accuracy for the prediction of the students outcome, we show that we can have a high value of 94.9119% for classification accuracy when the course timeline reaches the middle. This early prediction gives teachers and course administrators the time to find which students are inclined to fail in order to interfere and prevent them from failing, giving those students extra help and attention.

The last part of our study concerned the attribute selection for the Word dataset we followed a voting principal in order to obtain results from a large variety of methods. We observed that the attribute of AGE was always on the top six attributes for every attribute evaluation that was performed. We proceed with an analysis of the AGE attribute in compilation with the summarized time that students have spent in order to successfully complete the training course. We show that summarized time and AGE are increased together and we conclude that since the material of the lesson is common for students of all age, younger students successfully complete the training material in less time compared to older students.

Our results are of particular importance within the educational community, showing that both the students and the institutions can save time and money during the training process. The ability to predict with high level of classification accuracy the success or failure of the student before the end of the course, as well as selecting the most useful attributes for the attending course, strengthens the role of e-learning. These results do not only benefit the students but also benefits the teachers and administrators allowing them to improve existing online courses in an attempt to increase the successful completion of the course.

Fig. 1 .

 1 Fig. 1. The role of complexity in classification

  With regards to the above experimental setup as described in the methodology section, we set forth to explore the configuration of the SVM algorithm.Kernel Configuration. Tests were done in order to determine the best kernel function for our experimental data. In all experiments the complexity of SMO was set to 1 and a 10-fold cross validation technique was used.  Parameterization of the Polykernel function concerned the exponent p, the values of which ranged from 1 to 10, and the results exhibited a classification accuracy greater than 97.0646% for p=4.  Parameterization of the RBFKernel function concerned the γ parameter, ranging from 0.01 to 4.5, which resulted in classification accuracy greater than 96.4775% for γ=2.  Parameterization of the Puk kernel function regarded parameters ω and σ. When ω values ranged from 1 to 10000 and σ remained constant (σ =1) the results gave us the same accuracy values. However, when ω is kept constant (ω=1) and σ varies from 1 to 5 then the results vary. Finally it was determined that the highest classification accuracy was 96.4775% using the Puk kernel function when both ω and σ were equal to 1. Configuration Complexity. Based on the above findings with respect to the parameterization of the kernel functions, we kept the best results and experimented with complexity (C).

Fig. 2 .

 2 Fig. 2. Complexity parameterization

Fig. 3 .

 3 Fig. 3. Precision, Recall and Confusion Matrix

Fig. 4 .

 4 Fig. 4. Bagging and Boosting

Fig. 5 .

 5 Fig. 5. Classification accuracy per dataset

Fig. 6 .

 6 Fig. 6. SPSS results a) Attributes ranking (left) b) Mean times (right)

Table 1 .

 1 Word Dataset Attributes

	Attribute	Type	Description	Word Section
	Age	numeric	Years	-
	Education	nominal	Educational level	-
	Word01	numeric	Time in minutes	Document handling
	Word02	numeric	Time in minutes	Environment management
	Word03	numeric	Time in minutes	Write text
	Word04	numeric	Time in minutes	Manage text
	Word05	numeric	Time in minutes	Utilities
	Word06	numeric	Time in minutes	Fonts formatting
	Word07	numeric	Time in minutes	Paragraphs formatting
	Word08	numeric	Time in minutes	Pages settings
	Word09	numeric	Time in minutes	Headers & footers
	Word10	numeric	Time in minutes	Use changes
	Word11	numeric	Time in minutes	Object management
	Word12	numeric	Time in minutes	Create & manage tables
	Word13	numeric	Time in minutes	Tables formatting
	Word14	numeric	Time in minutes	Manage mass mail
	Word15	numeric	Time in minutes	Printings
	WordTheory	numeric	Time in minutes	-
	WordTest	numeric	Time in minutes	-
	WordSum	numeric	Time in minutes	-
	WordResults	nominal	Success / Failure	-

Table 2 .

 2 Search and evaluation methods for attribute selection

	Search Methods	Evaluation Methods
	Best First	cfsSubsetEval (Consider the predictive value of each attribute indi-vidually, along with the degree of redundancy among them)
	Ranker	ChiSquaredAtrributeEval (Compute the chi-squared statistic of each attribute with respect to the class)
	GreedyStepwise	ConsistencySubsetEval (Project training set onto attribute set and measure consistency in class values)
	Ranker	FIlteredAttributeEval (An arbitrary attribute evaluator on data that has been passed through an arbitrary filter)
	GreedyStepwise	FIlteredSubsetEval (An arbitrary subset evaluator on data that has been passed through an arbitrary filter)
	Ranker	GainRatioAttributeEval (Evaluate attribute based on gain ratio)
	Ranker	InfoGainAttributeEval (Evaluate attribute based on information gain)
	Ranker	OneRAtributeEval (Use OneR's methodology to evaluate attributes)
	Ranker	ReliefFAttributeEval (Instance-based attribute evaluator)
	Ranker	SVMAttributeEval (Use a linear support vector machine to deter-mine the value of attributes)
	Ranker	SymmetricalUncertAttributeEval (Evaluate attribute based on sym-metric uncertainty)


Panos Alexopoulos
email: palexopoulos@isoco.com

John Pavlopoulos

Phivos Mylonas
email: fmylonas@image.ntua.gr

Learning Vague Knowledge From Socially Generated Content in an Enterprise Framework

Keywords: vagueness, knowledge management, social web, microblogging, fuzzy ontologies

The advent and wide proliferation of Social Web in the recent years has promoted the concept of social interaction as an important influencing factor of the way enterprises and organizations conduct business. Among the fields influenced is that of Enterprise Knowledge Management, where adoption of social computing approaches aims at increasing and maintaining at high levels the active participation of users in the organization's knowledge management activities. An important challenge towards this is the achievement of the right balance between informalities of socially generated data and the required formality of enterprise knowledge. In this context, we focus on the problem of mining vague knowledge from social content generated within an enterprise framework and we propose a learning framework based on microblogging and fuzzy ontologies.

Introduction

Knowledge Management evolved over the last years to a serious management discipline that aims to enable enterprises and organizations to fully leverage their knowledge in their effort to grow more efficient and competitive. This leverage involves several key objectives such as identification, gathering and organization of existing knowledge, sharing and reusing of this knowledge for different applications and users and facilitation of new knowledge creation. Nevertheless, a dimension of enterprise knowledge that has so far been inadequately considered by the research community is that of vagueness.

Vagueness, typically manifested by terms and concepts like Tall, Strong, Expert etc., is a quite common phenomenon in human knowledge and it is related to our inability to precisely determine the extensions of such concepts in certain domains and contexts. That is because vague concepts have typically fuzzy boundaries, that do not allow for a sharp distinction between the entities that fall within the extension of these concepts and those which do not. This is not usually a problem in individual human reasoning, but it may become one, i) when multiple people need to agree on the exact meaning of such terms and ii) when machines need to reason with them. For instance, a system could never use the statement "This project requires many people to execute" in order to determine the number of people actually needed for the project.

To deal with vague knowledge, a relatively new knowledge representation paradigm that has been proposed is Fuzzy Ontologies [START_REF] Alexopoulos | IKARUS-Onto -A Methodology for Developing Fuzzy Ontologies[END_REF], extensions of classical ontologies that, based on principles of Fuzzy Set Theory [START_REF] Klir | Fuzzy Sets and Fuzzy Logic, Theory and Applications[END_REF], allow the assignment of truth degrees to vague ontological elements in an effort to quantify their vagueness. Thus, for example, whereas in a traditional ontology one would claim that ''The project's budget is satisfactory" or that ''Jane is an expert at Artificial Intelligence", in a fuzzy ontology one would claim that "The project's budget is satisfactory to a degree of 0.7" and that "Jane is an expert at Artificial Intelligence to a degree of 0.5".

Unfortunately, an important bottleneck in the process of developing and applying fuzzy ontologies for knowledge management is that of vague knowledge acquisition. This kind of bottleneck in traditional ontology development has been well documented in the literature and several approaches towards automating the knowledge acquisition process have been proposed [START_REF] Szumlanski | Automatically Acquiring a Semantic Network of Related Concepts[END_REF] [START_REF] Reichartz | Semantic relation extraction with kernels over typed dependency trees[END_REF]. In fuzzy ontologies the problem is even more acute as the high level of subjectivity and contextdependence characterizing vague information makes the accurate definition of fuzzy degrees and membership functions a very difficult task. Yet only a few automatic approaches for fuzzy ontology population have so far been proposed, with the vast majority of them being based on text mining [START_REF] Zhang | Automatic fuzzy semantic web ontology learning from fuzzy object-oriented database model[END_REF] [7] [START_REF] Chen | Research on Automatic Fuzzy Ontology Generation from Fuzzy Context[END_REF].

Contrary to above approaches, we envision the active participation of users in the vague knowledge acquisition process through a corresponding framework based on the so-called Web 2.0; a technological paradigm that facilitates and supports the active participation and collaboration of people on the Web. Our approach is inspired from works in the area of "crowdsourcing" [START_REF] Surowiecki | The wisdom of crowds[END_REF] where a large group of people solves implicitly a problem or carries out a task through proper incentive mechanisms. In our case such mechanisms are required since one of the biggest bottlenecks in typical Knowledge Management systems, where end-users are supposed to actively participate, is precisely the hurdles they encounter that discourage them for keeping involved. On the other hand, Web 2.0, where users participate in an active manner, and willingly generate new content, has been adopted by companies for their internal processes within the so-called Enterprise 2.0 framework [START_REF] Mcafee | Enterprise 2.0: The dawn of emergent collaboration[END_REF]. In particular, microblogging systems have been embraced as a way of fostering internal communication within the enterprise boundaries.

With that in mind, in this paper we propose a framework for automatic vague knowledge acquisition based on a semantically enhanced microblogging system and a fuzzy ontology learning process that acts upon the social content produced by the enterprise's people within this system.

The remainder of this paper is organized as follows: in Section 2, we introduce necessary relevant background information utilized within this work. Section 3 describes the proposed vague knowledge acquisition process. Finally, we draw our conclusions and briefly describe our future work in Section 4.

Background and Problem Setting

Vagueness and Ontologies

Vagueness as a semantic phenomenon is typically manifested through predicates that admit borderline cases [START_REF] Hyde | Vagueness, Logic and Ontology[END_REF], i.e. cases where it is unclear whether or not the predicate applies. For example, some people are borderline tall: not clearly "tall" and not clearly "not tall". In the relevant literature two basic kinds of vagueness are identified: degree-vagueness and combinatory vagueness [START_REF] Hyde | Vagueness, Logic and Ontology[END_REF]. A predicate has degree-vagueness if the existence of borderline cases stems from the apparent lack of crisp boundaries between application and non-application of the predicate along some dimension. For example, Bald fails to draw any sharp boundaries along the dimension of hair quantity while Red can be vague along the dimensions of brightness and saturation.

On the other hand, a predicate has combinatory vagueness if there is a variety of conditions all of which have something to do with the application of the predicate, yet it is not possible to make any sharp discrimination between those combinations which are sufficient and/or necessary for application and those which are not. An example of this type is Religion as there are certain features that all religions share (e.g. beliefs in supernatural beings, ritual acts etc.), yet it is not clear which of these features are able to classify something as a religion.

At this point, it should be clarified that the notion vagueness is different from inexactness or uncertainty. For example, stating that someone is between 170 and 180 cm is an inexact statement but it is not vague as its limits of application are precise. Similarly, the truth of an uncertain statement, such as "Today it might rain", cannot be determined due to lack of adequate information about it and not because the phenomenon of rain lacks sharp boundaries.

In an ontology the elements that can be vague are typically concepts, relations, attributes and datatypes [START_REF] Alexopoulos | IKARUS-Onto -A Methodology for Developing Fuzzy Ontologies[END_REF]. A concept is vague if, in the given domain, context or application scenario, it admits borderline cases, namely if there are (or could be) individuals for which it is indeterminate whether they instantiate the concept. Primary candidates for being vague are concepts that denote some phase or state (e.g Adult, Child) as well as attributions, namely concepts that reflect qualitative states of entities (e.g. Red, Big, Broken etc.). Similarly, a relation is vague if there are (or could be) pairs of individuals for which it is indeterminate whether they stand in the relation. The same applies for attributes and pairs of individuals and literal values.

Finally, a vague datatype consists of a set of vague terms which may be used within the ontology as attribute values. For example, the attribute performance, which normally takes as values integer numbers, may also take as values terms like very poor, poor, mediocre, good and excellent. Thus vague datatypes are identified by considering the ontology's attributes and assessing whether their potential values can be expressed through vague terms.

Fuzzy Ontologies and Problem Definition

A fuzzy ontology utilizes notions from Fuzzy Set Theory in order to formally represent the vague ontological elements described in previous paragraph. The basic elements it provides include i) Fuzzy Concepts, namely concepts to whose instances may belong to them to certain degrees (e.g. Goal X is an instance of StrategicGoal at a degree of 0.8 ), ii) Fuzzy Relations/Attributes, namely relations and attributes that link concept instances to other instances or literal values to certain degrees (e.g. John is expert at Knowledge Management at a degree of 0.5 ) and iii) Fuzzy Datatypes, namely sets of vague terms which may be used within the ontology as attribute values (e.g. attribute experience mentioned above). In a fuzzy datatype each term is mapped to a fuzzy set that assigns to each of the datatype's potential exact values a fuzzy degree indicating the extent to which the exact value and the vague term express the same thing (e.g. A consultant with 5 years of experiences is considered experienced to a degree of 0.6 )

The problem we wish to tackle can be defined as follows: Given a fuzzy enterprise ontology, what are the optimal fuzzy degrees and membership functions that should be assigned to its elements (concepts, relations and datatypes) in order to represent their vagueness as accurately as possible? In particular, given a fuzzy concept (e.g. CompanyCompetitor) and a set of its instances (e.g. a set of companies), we practically want to learn the degree to which each of these instances belongs to this concept (e.g. to what degree each company is considered a competitor). Similarly, given a fuzzy relation (e.g. isExpertAt) and a set of related through it pairs of instances (e.g. persons related to business areas), we want to learn the degree to which the relation between these pairs actually stands. Finally, given a fuzzy datatype (e.g. ProjectBudget) and the terms it consists of (e.g. low, average, high), we want to learn the membership functions of the fuzzy sets that best reflect the meaning of each of these terms.

Vague Knowledge Acquisition

As already discussed, vague pieces of knowledge are characterized by the existence of blurry boundaries and by high degree of subjectivity. As such, they are expected to provoke discussions, disagreements and debates among the enterprise's members. For example, it might be that two product managers disagree on what the most important features of a given product are or that two salesmen cannot decide what amount of sales is considered to be low. Our approach is based on the facilitation and recording of such discussions and disagreements, through a microblogging platform, and their utilization for determining the optimal degrees and membership functions of a fuzzy ontology representing this knowledge.

In particular, the process we propose for performing vague knowledge acquisition within an enterprise consists of the following steps:

1. Identification within the enterprise of vague knowledge and conceptual modeling of it in the form of a fuzzy enterprise ontology. 2. Setting up of a microblogging platform in which the members of the enterprise are expected to participate and perform discussions and information exchange on all aspects regarding the enterprise and its environment. 3. Detection and extraction from the user generated platform's content of vague knowledge assertions, namely statements related to the elements already defined in the fuzzy enterprise ontology. 4. Calculation for each vague assertion of a strength value based on the utilization of various characteristics of the discussions they are involved in. 5. Aggregation of these assertions and automated generation of fuzzy degrees and membership functions.

In the following paragraphs we elaborate on each of the above steps.

Vague Knowledge Conceptualization

This step involves the identification of vague pieces of knowledge within the enterprise and their conceptualization in the form of fuzzy ontological elements (paragraph 2.2). Within this work we followed the implementation described in detail in the IKARUS-Onto methodology [START_REF] Alexopoulos | IKARUS-Onto -A Methodology for Developing Fuzzy Ontologies[END_REF] which provides concrete steps and guidelines for identifying vague knowledge and conceptually modelling it by means of fuzzy ontology elements. Of course, it should be noted that, fuzzy degrees or membership functions for the above elements do not need to be defined a priori as they are expected to be automatically determined in the later stages of the process.

Microblogging Framework

Microblogging is one of the recent social phenomena of Web 2.0, being one of the key concepts that has brought Social Web to more than merely early adopters and tech savvy users. Simply put, microblogging is a light version of blogging where messages are restricted to less than a small number of characters. Yet, its simplicity and ubiquitous usage possibilities have made microblogging one of the new standards in social communication. There is already a large number of social networks and sites, with more blooming every day, that appear to have some microblogging functionalities, with Twitter1 and Facebook2 being the most famous.

Being of greater interest within the microblogging framework we examine, Twitter allows users to publish text limited to a maximum of 140 characters. On Twitter a user has to main roles, to publish tweets (writer) or to subscribe to other users and read their posts (reader). As a writer you are allowed to: 1) republish or retweet) other users posts; 2) make reference to other users within the published content (a.k.a mentions) by using the @ character before the users user name; 3) reply to another tweet, replies always start with @username (author of the tweet you are replying to); 4) include different types of resources to your post (i.e. hashtags and links); and 5) be listed by your followers. As a reader you can: 1) follow other users posts; and 2) organise into groups (lists) the users you follow.

The microblogging platform we adopt for the purposes of this work is miKrow [START_REF] Penela | miKrow: Semantic intra-enterprise micro-knowledge management system[END_REF], an intra-enterprise semantic microblogging tool that allows its end-users to share short messages expressing what are they doing, or more typically in a work environment, what are they working at. The platform works mostly like Twitter, with two important enhancements:

1. When users reply to a message they are able to denote the nature of their reply by using the predefined hashtags #support and #attack. 2. Users are also able to denote their agreement or disagreement to a message through a rating functionality (see figure 1)

These two features allows us to use the platform as an argumentation tool and capture the disagreements and debates over vague knowledge statements that may occur.

Detection and Extraction of Vague Knowledge Assertions

Vague knowledge assertions are practically statements related to the elements of fuzzy ontology. For example, the assertion "The budget for the project X is low" is related to the fuzzy datatype "ProjectBudget" while the assertion "John knows everything about ontologies" is related to the fuzzy relation "isExpertAt". Our goal is to detect and extract such assertions from the messages generated by the platform's users so that we can use them for determining the fuzzy degrees of their respective elements.

In order to achieve this, we use an in-house developed semantic annotation tool that, given a fuzzy ontology, is able to recognize such assertions within a piece of text. An important factor that contributes to higher levels of precision for this detection is the fact that microblogging messages are short. In any case, the detection process may be performed in a semi-automatic fashion where the correctness of the extracted assertions could be checked by the system's administrator.

Assertion Strength Assessment

To calculate the strength of the extracted vague assertions we consider their so-called "social context". The latter includes all messages that are directly or Given such a context, we calculate the strength of the assertions contained in it as follows:

Let a ∈ A be an assertion and M a = Incl(a) be the set of messages in which this assertion is contained. Then the strength of the assertion S(a) is given by the average strength of these messages, namely:

S(a) = 1 |M a | • ∑ mi∈Ma s(m) (1)
where s(m) denotes the strength of each message and is calculated as follows:

s(m) = w 1 • agr(m) + w 2 • sup(m) + w 3 • inf l(P ub(m)) (2)
In the above equation ( 2) w 1 , w 2 and w 3 are weights denoting the relative importance, in calculating the message's strength, of the measures agr(m), sup(m) and inf l(P ub(m)) respectively. In particular, agr(m) denotes the relative agreement on the message m based on the number of agreements and disagreements it has received by the users. Thus, it is calculated as follows:

agr(m) = |Agr(m)| -|Disag(m)| ∑ mi∈M (|Agr(m)| + |Disag(m)|) (3)
Similarly, sup(m) denotes the relative support to the message based on the number and strength of attacking and supporting messages. This support is recursively calculated as follows:

sup(m) = ∑ mi∈Att(m) s(m i ) |Att(m)| - ∑ mj ∈Sup(m) s(m j ) |Sup(m)| (4)
Finally, inf l(P ub(m)) denotes the overall influence of the user who has published the message (and thus has made the assertion). This influence is generally relevant to the number of users that follow the message publisher but also to the persons expertise on the messages topic. For that, we derive the exact influence score using Topic-Sensitive PageRank Algorithm [START_REF] Haveliwala | Topic-sensitive PageRank[END_REF] which was originally proposed for ranking web pages according to their relative importance, given a set of representative topics. In our case, in the place of pages we have users and the topics are in practice the business areas in which these users are interested or considered expert within the enterprise.

Generation of Membership Functions and Fuzzy Degrees

A fuzzy ontology may be considered as a tuple O F = {C, R, I, T, i C , i R , D}, where -C is a set of fuzzy concepts. -I is a set of instances. -R is a set of fuzzy binary relations that may link pairs of concept instances.

-i C is a fuzzy concept instantiation function C × I → [0, 1]. -i R is a fuzzy relation instantiation function R × I → [0, 1].
-D is a set of fuzzy datatypes. Each d ∈ D is itself a tuple {T, X, m} where T is the set of linguistic terms of the datatype that refer to a base variable whose values range over a universal set X and m is a function that, for each linguistic term t ∈ T , relates the values of X to a fuzzy degree.

Based on this formalization, our goal is practically to learn the functions i C and i R and m. To do that we utilize the extracted assertions along with their calculated strengths. In particular, given an instance i ∈ I and a concept c ∈ C, the related assertions form a set A i,c = {s 1 , s 2 , ..., s n } where s j is the strength of the j th assertion. Based on this set we want to determine a single fuzzy degree d for the pair {i, c}. Similarly, for two given instances i 1 , i 2 ∈ I and a relation r ∈ R, the related assertions form a similar set A i1,i2,r = {s 1 , s 2 , ..., s n }. Again our goal is to determine a single fuzzy degree d for the triple {i 1 , i 2 , r}.

For example, if i 1 = John, r = isExpertAt and i 2 = M achineLearning and we have managed to extract a number of relevant assertions, each with some strength, we want to aggregate these strengths into a single degree that denotes how expert is actually John at Machine Learning. To do that we first compute the mean value of all the strength values observed in the assertion set. Then we estimate confidence intervals and we only allow those mean values with significance level of no less than 0.05. In most cases we expect to have most assertions gathered very close to a single mean value which can then be considered as the degree of the relevant ontological statement. In case many assertions seem to be out of the confidence intervals, then that's an indication that the statement's interpretation might be context-dependent. In such a case, we may isolate these contexts by performing clustering on the assertion set.

On the other hand, for a given term t of a fuzzy datatype d ∈ D, the related assertions form a set A t,d = {(v 1 , s 1 ), (v 2 , s 2 ), ..., (v n , s n )} where v j is the actual value the term t refers to in the j th assertion (for example, in the assertion "The budget for the project X is low" v is the actual value of project X). Our goal in this case is, based on the pairs of these values and strengths, to determine the optimal function fuzzy membership function m that links them. This is a well-studied problem in the area of fuzzy expert systems and several related methods that construct such functions from training data have been proposed [START_REF] Chen | A New Method to Construct Membership Functions and Generate Fuzzy Rules from Training Instances[END_REF]. Therefore our approach involves reusing such methods in our framework and through extensive experimentation determining the optimal one for the kind of training data our microblogging platform produces.

Conclusions and Future Work

In this paper we proposed a framework for automatic vague knowledge acquisition in enterprise settings, based on a semantically enhanced microblogging system and a fuzzy ontology learning process that acts upon the social content produced by the enterprise's people. The key characteristic of our approach is the utilization of the content's social features, like the relative agreement and support that microposts enjoy or the status and influence of the users, in order to assign strengths to vague assertions.

In the future we intend to apply our framework in an actual enterprise setting and evaluate its effectiveness in acquiring vague knowledge. This evaluation will focus on two dimensions: i) the ability of the microblogging approach in producing rich social context over the vague knowledge and ii) the accuracy of the fuzzy ontology degrees and membership functions learned using this context.

Fig. 1 .

 1 Fig. 1. The miKrow microblogging platform

www.twitter.com

www.facebook.com