Wei Wang

Sylvain Gombault
email: sylvain.gombault@enst-bretagne.fr

Detecting Masquerades with Principal Component Analysis Based on Cross Frequency Weights

In this paper, several cross frequency weights are used for extracting attributes of audit events. Principal Component Analysis (PCA) are then employed to discover the interrelationships and dependencies among features in a large number of variables and also to reduce the high dimensionality of these variables. Command data are used in the experiments for masquerade detection and the results demonstrate the effectiveness and efficiency of the method.

Introduction

Masquerades are people who impersonate other people on a computer [START_REF] Schonlau | Computer Intrusion: Detecting Masquerades[END_REF]. Masquerading can be a serious threat to the security of computer systems. However, user behavior varies widely and masquerades are usually difficult to be detected. Extracting important features from user behavioral data, therefore, is crucial for effective masquerade and intrusion detection.

Almost all the existing work in anomaly masquerade and intrusion detection considered two probabilistic attributes of activities in computer systems, namely, the transition attributes (e.g., [START_REF] Yeung | Host-based intrusion detection using dynamic and static behavioral models[END_REF][START_REF] Forrest | A sense of self for Unix processes[END_REF][START_REF] Wang | Modeling program behaviors by hidden Markov models for intrusion detection[END_REF]) and the frequency attributes (e.g., [START_REF] Liao | Using text categorization techniques for intrusion detection[END_REF][START_REF] Wang | Profiling program and user behaviors for anomaly intrusion detection based on non-negative matrix factorization[END_REF][START_REF] Wang | Profiling program behavior for anomaly intrusion detection based on the transition and frequency property of computer audit data[END_REF][START_REF] Wang | A Novel Intrusion Detection Method Based on Principal Component Analysis in Computer Security[END_REF][START_REF] Wang | Distances measures for anomaly intrusion detection[END_REF]) of audit data. Schonlau et al. [START_REF] Schonlau | Computer Intrusion: Detecting Masquerades[END_REF] attempted to detect masquerades by building normal user behavioral models using truncated command sequences. Experiments with six masquerade detection techniques [START_REF] Schonlau | Computer Intrusion: Detecting Masquerades[END_REF]: Bayes one-step Markov, Hybrid multi-step Markov, IPAM, Sequence-Match, Compression and Uniqueness, were performed and compared. The first five methods are mainly based on the transition information of user command data.

There are many issues to be resolved in masquerade and intrusion detection. First, a computer system in daily operation can produce massive data streams. Fast processing of typically high dimensional audit data is thus essential for a practical Intrusion Detection System (IDS) so that actions for response can be taken as soon as possible. However, intrusion detection methods considering the transition attributes of audit data usually require much time to train the models and to detect intrusions. Intrusion detection methods only taking account of frequency information can improve some real-time performance but cannot achieve good detection accuracy [START_REF] Wang | Profiling program behavior for anomaly intrusion detection based on the transition and frequency property of computer audit data[END_REF] and this is not enough for a practical IDS.

Second, most of current masquerade and intrusion detection methods utilize the first-order statistics for detection (e.g., [START_REF] Liao | Using text categorization techniques for intrusion detection[END_REF]). However, many masquerades and intrusions in information systems manifest themselves by the correlation changes. The detection methods ignoring the coherent relations and dependencies of variables usually resulted in high false positive rates.

In this paper, we propose a masquerade and anomaly intrusion detection method with Principal Component Analysis (PCA) based on frequency weights that not only consider the frequency information of events in each sequence of audit data, but also consider the distribution of the event in the whole data. The weights are originally from information retrieval and were known as tfidf (term frequency -inverse document frequency). Plain Term Frequency (TF), Mean tfidf (Mtfidf ) and LOG tfidf (LOGtfidf ) are used in this paper for feature transformation. PCA is then used for masquerade detection based on the cross frequency weights. PCA is employed to discover the interrelationships and dependencies among features in a large number of variables by using the second-order statistics in the variable of audit data. Moreover, PCA condenses the valuable information in a large number of variables into a smaller set of dimensions so that the data can be largely reduced for real-time masquerade and intrusion detection.

Detecting masquerades with Principal Component

Analysis Based on Cross Frequency Weights 1. TF (Plain Term Frequency): Nearly all the current frequency based intrusion detection methods used Plain Term Frequency (TF) for feature transformation [START_REF] Liao | Using text categorization techniques for intrusion detection[END_REF][START_REF] Wang | Profiling program and user behaviors for anomaly intrusion detection based on non-negative matrix factorization[END_REF][START_REF] Wang | Profiling program behavior for anomaly intrusion detection based on the transition and frequency property of computer audit data[END_REF][START_REF] Wang | A Novel Intrusion Detection Method Based on Principal Component Analysis in Computer Security[END_REF][START_REF] Wang | Distances measures for anomaly intrusion detection[END_REF]. It can be defined as tf ij = f ij .

Mtfidf (Mean term frequency -inverse document frequency): Mtfidf

has been widely used in information retrieval and we use this scheme for masquerade and intrusion detection. It is defined as

M tf idf ij = f ij × log n si .

LOGtfidf (LOG term frequency -inverse document frequency):

LOGtfidf is defined as LOGf idf ij = log (0.5 + f ij ) × log n si .

PCA based masquerade and intrusion detection

Given a set of observations (sequences) be x 1 , x 2 , • • • , x n , suppose each observation is represented by a row vector of length m. The average observation is defined as µ = 1 n n i=1 x i . Observation deviation from the average is defined as Φ = x i -µ. The sample covariance matrix of the data set is defined as

C = 1 n n i=1 (x i -µ)(x i -µ) T = 1 n n i=1 Φ i φ T i .
The covariance matrix C considers the first and second-order statistic of variables in audit data. Suppose (λ 1 , u 1 ), (λ 2 , u 2 ), • • • , (λ m , u m ) are m eigenvalue-eigenvector pairs of the sample covariance matrix C. We choose k eigenvectors having the largest eigenvalues. Often there will be just a few large eigenvalues, and this implies that k is the inherent dimensionality of the subspace governing the "signal" while the remaining (m -k) dimensions generally contain noise [START_REF] Duda | Pattern Classification[END_REF]. The dimensionality of the subspace k can be determined by k i=1 λi m i=1 λi ≥ α [START_REF] Duda | Pattern Classification[END_REF], where α is the ratio of variation in the subspace to the total variation in the original space. We form a m × n matrix U whose columns consist of the k eigenvectors. The representation of the data by principal components consists of projecting the data onto the k-dimensional subspace according to the rules

y i = U T (x i -µ) = U T φ i [10].
A test data vector x i that represents a test sequence of data can be projected onto the k-dimensional subspace according to the rules. The distance between the test data vector and its reconstruction in the subspace is simply the distance between the mean-adjusted input data vector Φ = x-µ and φ f = UU T (x-µ) = Uy. If the test data vector x is normal, the test data vector and its reconstruction will be very similar and the distance between them will be very small [START_REF] Duda | Pattern Classification[END_REF]. As PCA seeks a projection that best represents the data in a least-square sense, we use the squared Euclidean distance to measure the distance between these two vectors ε = φ -φ f .

In anomaly detection, ε are characterized as anomaly indexes. If ε is above a predetermined threshold, then the test data x is classified as normal. Otherwise it is treated as anomalous.

3 Testing results

Data set

The command data sets collected by Schonlau et al. [START_REF] Schonlau | Computer Intrusion: Detecting Masquerades[END_REF] are used in our experiments for masquerade detection. The command data consists of user names and the associated command sequences (without arguments). 50 users are included with 15000 consecutive commands for each user, divided into 150 blocks of 100 commands. The first 50 blocks are uncontaminated and used as training data. Starting at block 51 and onward, some masquerading command blocks, randomly drawn from outside of the 50 users, are inserted the command sequences of the 50 users. The goal is to correctly detect the masquerading blocks in the user community. The data are available at http://www.schonlau.net/intrusion.html.

Testing results

In the experiments, we first convert each block of data into a feature vector based on the three weights. PCA is then used for masquerade detection. We use the same threshold for all the users and there is no updating during the training and detection steps in our experiments. α was set as 99.99% in the experiments. Receiver Operating Characteristic (ROC) curves are used to evaluate the masquerade detection performance. The ROC curve is the plot of Detection Rates (DR)against False Alarm Rates (FAR).

For evaluating the performance of different weights, we plot ROC curves of the results shown in Fig. 1 base on PCA method with plain TF, Mtfidf and LOGtfidf weights. It is easily observed from the figure that LOGtfidf and Mtfidf are much better than TF in terms of detection accuracy. In details, LOGtfidf is little better than Mtfidf. Using the cross frequency weights significantly improves the detection accuracy.

Results comparison

To facilitate comparison, we also used Chi-square distance test (also called as X 2 test) for masquerade and intrusion detection as it is typical for considering the first-order statistic of audit data.

Competitive approaches

1. Chi-square distance test: For a given test vector x, the X 2 test statistic is given by X 2 = m i=1 xi-ti ti , where x i is the i-th variable in the test vector x and t i is the averaged i-th variable of all the training vectors. The distance of a test vector x from the center of the normal data population can be measured by X 2 test and are considered as anomaly index for the test vector.

When the m variables are independent and m is large (e.g., greater than 30), the X 2 statistic follows approximately a normal distribution according to the central limit theorem [START_REF] Duda | Pattern Classification[END_REF]. We compute the mean and standard deviation of the X 2 population as X 2 and σ X 2 and set a threshold based on a zone of some combinations of X 2 and σ X 2 , e.g., [X 2 -βσ X 2 , X 2 + βσ X 2 ], where β is a variable parameter. For a test sequence x, if its anomaly index is outside of the zone, it is then classified as abnormal. 2. Existing approaches in the literature: As mentioned in Section 1, Schonlau et al. [START_REF] Schonlau | Computer Intrusion: Detecting Masquerades[END_REF] used six methods to detect masquerades based on the same data sets. We also used NMF for masquerade detection.

Results comparison

From Fig. 2 (a), it is observed that PCA method outperforms the Chi-square test method using the same LOGtfidf weight for masquerade detection. This may show that considering the first and second-order statistic of audit data can improve detection accuracy compared to only using that of first-order statistic. Fig. 2 (b) shows the results for PCA method and Chi-square method by using the LOGtfidf weight along with the results from another 7 methods in [START_REF] Schonlau | Computer Intrusion: Detecting Masquerades[END_REF][START_REF] Wang | Profiling program and user behaviors for anomaly intrusion detection based on non-negative matrix factorization[END_REF]. It is observed that PCA method achieves the best results among the other 7 methods. By using the same PCA method, the LOGtifidf weight improves the detection results with 23.6% than plain frequency TF based on the same data set. PCA method improves the detection results with 29.3% than Chi-square test. Using the cross frequency weights are essentially more effective than only using the plain frequency attributes of audit data for masquerade intrusion. In addition, the computation cost of cross frequency weights is almost as the same as that of the plain frequency and is low overhead. In this way, the detection accuracy can improve a lot while the computation expense almost does not increase so that an effective IDS can be developed for real-time detection. The PCA method using the first and second-order of audit data can also improve the detection accuracy compare to only using that of the first-order statistic.

We have tested our method on command data for masquerade detection. The testing results are promising in terms of detection accuracy and computation expense. We believe that our work has some contributions to the masquerade and intrusion detection areas as well as IT service management. In the future work, we plan to implement the method onto practical network environments for real-time detection. Finding more effective weights for extracting valuable features of audit data and combining the frequency attributes with the transition information of audit data are also being investigated to achieve lower false alarm and missing alarm rates.

2. 1

 1 Feature transformation with frequency weight schemes Thefrequency weight schemes are described below and the notation and terminology used in this paper are listed in Tab. 1.

Fig. 1 .

 1 Fig. 1. ROC curves for PCA method with various different frequency weights

Fig. 2 .

 2 Fig. 2. (a): ROC curves for PCA and X 2 test method using LOGtfidf weight; (b): ROC curves for PCA method using LOGtfidf weight along with the results from other 7 methods

Table 1 .

 1 The

notation and terminology n Total number of sequences in the observation data set m Total number of distinct events in the observation data set fij Frequency of event i in sequence j ni Number of times that event i appears in the observation data set si Number of sequences containing event i X Test sequences T Training sequences in the observation data set


Antoine Pigeau

Olivier Aubert

Yannick Prié

Success prediction in MOOCs A case study

Success prediction in Massive Open Online Courses (MOOCs) is now tackled in numerous works, but still needs new case studies to compare the solutions proposed. We study here a specific dataset from a French MOOC provided by the OpenClassrooms company, featuring 12 courses. We exploit various features present in the literature and test several classification models.

INTRODUCTION

Multiple models and data mining methods for learner success prediction in a Massive Open Online Courses (MOOCs) are proposed by many works in the literature [START_REF] Gardner | Student success prediction in MOOCs[END_REF], with different conclusions about which model provides the best performance. The quality of the results seems to highly depend on the input dataset, and on the selected or computed features. Generalization of the methodology for success prediction seems now ongoing [START_REF] Gardner | Student success prediction in MOOCs[END_REF], but we still need new case studies to improve the accuracy and insights obtained by these methods.

This work presents a case study on a new dataset, provided by OpenClassrooms, a major online courses french company. We test several models using classification algorithms and sequence-based approaches, such as process and pattern mining. Our study aims at enriching previous results obtained for different datasets published in the literature.

Our first contribution in this work is the comparison of 8 classification models. Random Forest, AdaBoost, Support Vector Machine (SVM), logistic regression and neural networks are first applied, followed by sequence-based approaches: an LSTM neural network, a process mining method and a proposal of a solution based on a sequence mining method. The second contribution consists in experimental results obtained from a new dataset for a success prediction task. While most papers only focus on 1-5 courses [START_REF] Gardner | Student success prediction in MOOCs[END_REF], we use here 12 different courses from the same platform.

The remainder of this paper is organized as follows: section 2 surveys previous work related to success prediction. Section 3 presents the dataset used for the experiments with details on the raw data used to compute features. Section 4 describes features obtained from the literature and their adaptation to our context. Section 5 presents the classification methods that we applied. The result of our experiments are detailed and discussed in section 6. We conclude by summarizing our work and drawing perspectives in section 7.

RELATED WORK

Prediction of dropout or success in MOOCs is carried out in numerous works [START_REF] Gardner | Student success prediction in MOOCs[END_REF]. The goal is to improve the performance of the learners by detecting a possible failure in advance. Such a detection could for instance lead to a teacher intervention to increase the learner engagement in the course.

The input data for such a prediction is based either on assignments [START_REF] Taylor | Likely to stop? predicting stopout in massive open online courses[END_REF][START_REF] Koprinska | Students at risk: Detection and remediation[END_REF][START_REF] Feild | Improving student performance using nudge analytics[END_REF][START_REF] Tomkins | Predicting post-test performance from online student behavior: A high school MOOC case study[END_REF][START_REF] Sweeney | Next-term student performance prediction: A recommender systems approach[END_REF] or clickstreams [START_REF] Ren | Predicting performance on MOOC assessments using multi-regression models[END_REF][START_REF] Ng | Modelling the way: Using action sequence archetypes to differentiate learning pathways from learning outcomes[END_REF][START_REF] Mukala | Learning analytics on coursera event data: A process mining approach[END_REF][START_REF] Boroujeni | How to quantify student's regularity?[END_REF]. Social activities can also be included to assess the learner engagement in a course [START_REF] Taylor | Likely to stop? predicting stopout in massive open online courses[END_REF][START_REF] Koprinska | Students at risk: Detection and remediation[END_REF][START_REF] Tomkins | Predicting post-test performance from online student behavior: A high school MOOC case study[END_REF].

Classification methods rely on common approaches such as linear regression, logistic regression, K-nearest neighbors, random forests, decision trees, support vector machines, hidden Markov models and neural networks. Because the course context is different for each study, it is hard to determine which model will be the best for a prediction task. Support vector machine is the best method obtained for [START_REF] Tomkins | Predicting post-test performance from online student behavior: A high school MOOC case study[END_REF] while random forest performs better in [START_REF] Sweeney | Next-term student performance prediction: A recommender systems approach[END_REF]. The conclusion of [START_REF] Taylor | Likely to stop? predicting stopout in massive open online courses[END_REF] states that prediction performance depends more on the features computed than on the model. Several temporal data mining methods are proposed in the literature [START_REF] Gardner | Student success prediction in MOOCs[END_REF][START_REF] Ng | Modelling the way: Using action sequence archetypes to differentiate learning pathways from learning outcomes[END_REF][START_REF] Mukala | Learning analytics on coursera event data: A process mining approach[END_REF]. Recurrent neural networks are assessed for dropout detection and experiments conclude that LSTM recurrent networks present the second best results in [START_REF] Wang | A nonlinear state space model for identifying at-risk students in open online courses[END_REF] (where a Nonlinear State Space Model is slightly better). [START_REF] Mukala | Learning analytics on coursera event data: A process mining approach[END_REF] proposes a solution based on process mining to emphasize a correlation between the way learners browse the course and their performances. Other approaches use sequence mining algorithms to predict learner skills [START_REF] Ng | Modelling the way: Using action sequence archetypes to differentiate learning pathways from learning outcomes[END_REF].

In the present work, we test some of the common shallow methods proposed in the literature, as well as neural network approaches. We also explore a solution based on process mining, and propose one based on sequence mining. For all these algorithms, we assess a large set of features adapted from the literature.

INPUT DATA

OpenClassrooms is a MOOC platform that provides courses in various domains, from art and culture to computer science. All courses are freely accessible anytime, and paid services are proposed for supplementary features such as online help and certificates of achievement. Courses are generally composed of texts, videos or e-books that users can browse, read or download after a registration process. Based on the properties proposed in [START_REF] Gardner | Student success prediction in MOOCs[END_REF], these courses can be characterized as follows:

• massive, open and online: thousands of learners can follow the courses freely. Paid access is provided to get an access to a tutor or a completion certificate; • no-stakes: the learner can complete a course without certification or credit; • asynchronous: learners are free to register, browse the content, or complete a course. There is no constraint on dates for enrollment or assignments. This point is important and has an impact on the choice of features used as input for the prediction model; • heterogeneous: learners have various motivations and mostly come from francophone countries since courses are in french.

In this study, we are considering a dataset covering 12 courses in the domains of programming languages, project management and startup creation. The two leftmost columns of table 1 present for each course its name and the total number of learners that followed it, from 2014 to 2016.

The provided courses are composed of static web pages and quizzes/assignments, and do not contain any video. A course is composed of chapters, divided in sections, and of exercises based on quizzes and assignments. To succeed in a course, a learner must obtain an average grade on all exercises higher than 70/100 (the exercises are quizzes automatically graded).

The input format of learner activity is a clickstream dataset. Each access to a resource is recorded as one event in a log file. The granularity of the retrieved events varies among different courses. Apart from Audace Entreprendre, Node JS, XML and Java (in bold in table 1), which are traced at the section level, all courses present a chapter granularity.

The first step applied on the raw dataset consists in segmenting the learners' sequences of events into sessions. This session detection step aims to enrich some features related to the learners' regularity, the duration, or the number of events in the working sessions. The learners' sessions are determined from the raw sequences with the method proposed in [START_REF] Sadallah | Towards reading session-based indicators in educational reading analytics[END_REF], where a session is defined as a delimited and sustained set of pages visited by the same user within the duration of one particular visit to a particular website. Once sessions are determined, a cleaning task is performed: learners with only one session and no exercise attempt are removed. We associate this behaviour to learners that want to check the content of the course and do not really intend to follow it.

Discussion with the OpenClassrooms company about their needs lead us to define two groups for our goal of success prediction:

• passing group: set of learners that obtained an average grade equal to or higher than 70/100 for a course; • failing group: set of learners that did not obtain an average grade higher than 70/100. This group contains all the learners that either quit the course or completed all exercises but failed to obtain a grade higher than the 70/100 validation threshold.

Our choice for the terms "Pass / Fail" is based on [START_REF] Gardner | Student success prediction in MOOCs[END_REF], where it is defined that A student typically passes a course if they meet or exceed an instructor-specified overall grade threshold; otherwise they fail.

The two rightmost columns of table 1 present the number of learners in each group for the 12 courses of the dataset, after the cleaning step. As commonly encountered in MOOC contexts, these groups are clearly unbalanced: on average, the passing group represents 15% of the learners. Courses of table 1 are ordered according to the percentage of passing learners.

FEATURES

Table 2 presents our candidate features set. This set regroups an adaptation of the best features identified in [START_REF] Taylor | Likely to stop? predicting stopout in massive open online courses[END_REF][START_REF] Ren | Predicting performance on MOOC assessments using multi-regression models[END_REF][START_REF] Whitehill | Beyond prediction: First steps toward automatic intervention in mooc student stopout[END_REF][START_REF] Chen | Dropoutseer: Visualizing learning patterns in massive open online courses for dropout reasoning and prediction[END_REF][START_REF] Nagrecha | Mooc dropout prediction: Lessons learned from making pipelines interpretable[END_REF] and a set of regularity features proposed in [START_REF] Boroujeni | How to quantify student's regularity?[END_REF].

We needed to adapt some of the features due to differing contexts for our MOOC.

Several options are possible to generate features depending on the considered machine learning approach:

• basic features: features are computed for the whole considered period (after x weeks of the course for instance). These features do not evolve with time; • temporal features: features are computed for successive time periods in order to emphasize their evolution all along the course. The period commonly used in the literature seems to be one week [START_REF] Gardner | Student success prediction in MOOCs[END_REF]; • temporal features with stacking: similar to the previous method but each feature of a period is stacked with the previous one. Practically, it consists in adding the values of week n with those of week n+1.

PREDICTION TASK

In this section, we present different classification methods tested for our prediction task of passing/failing. We start with the baseline methods commonly applied for this kind of task and then detail a process mining approach and our proposal based on a sequence mining solution.

Baseline approaches

In order to compare our results with other available works in the literature, we experimented with the following methods: Random Forest, AdaBoost, SVM, logistic regression, dense neural network and LSTM neural network.

A first step of feature selection is necessary for logistic regression and SVM models. We rely here on a wrapper method with a forward selection to emphasize the best features. A subset of features is iteratively built, starting from an empty set and adding one by one the features that best improve our model's accuracy for the whole set of courses. The process is stopped when accuracy does not increase anymore.

Except for LSTM neural network that directly relies on a sequence of features, other methods can deal with several types of input features: basic features, temporal features and temporal features with stacking. We test each possibility in our experiment, to determine in what measure this choice impacts the performance of the prediction.

Process mining approach

Process mining was initially a method to analyze business processes for process discovery, process conformance checking and process improvement. In the context of online courses, this method proposes to study the behavior of learners during a course, by emphasizing common paths in course resource navigation.

The classifier for our prediction task is built from the outputs of process discovery and conformance checking methods. Our process discovery relies on the Heuristic Miner algorithm [START_REF] Der Aalst | Process Mining: Data Science in Action[END_REF]. This algorithm is robust, and deals with the majority of common problems in process detection. Models for failing and passing are built with this algorithm for each course. Our conformance checking solution relies on an algorithm based on an alignment method [START_REF] Der Aalst | Process Mining: Data Science in Action[END_REF]. Our prediction task is carried out by computing the fitness of a learner on both failing and passing models, and affecting him to the group with the best fitness.

The input dataset of a process mining algorithm is a set of traces, where each trace represents the sequence of activities of one learner. In our context, an activity is an access to a resource and is defined with the id of this resource. Because the grades and the duration of each access are lost, a categorization step is carried out on each event of a learner's trace. It consists in updating the resource ids (the activity) as follows: for an exercise id, the new id depends on success or failure. For a chapter/section, the new id depends on the duration spent on the resource, using 3 classes of short/medium/long durations.

Sequence mining approach

With this approach, our goal is to determine whether different groups of learners present distinct frequent sub-sequences of events in their traces.

Our first step is to build the passing model (by retrieving the frequent sequence on only the passing learners) and the failing model. We rely on the VMSP algorithm to generate the maximal frequent sequences on both groups. Note that all sub-sequences of a maximal sequence are also frequent sequences, thus we still obtain all the frequent sequences.

Our second step is to compute a similarity score between a model and a learner's sequence. Our proposal consists in tessellating the new learner sequence with the larger frequent sub-sequences of the models. Practically, we try to map each frequent sequence on the learner sequence. The mapping obtained is used to compute a similarity score:

1. for a frequent sequence of length n in the model, generate all k-grams with k between 2 and n; 2. map all k-grams one by one on the learner sequence, keeping the mapping with the larger k-gram; 3. repeat the steps 1-2 for all frequent sequences; 4. for each item position of the learner sequence, a score is computed as the length of the longer k-gram that maps this position. The similarity score is then obtained by summing up all these positions' scores.

The input dataset for this method is similar to the one used for our process mining approach. Each learner's event is categorized with our previous method (see section 5.2).

EXPERIMENTS

For all the following experiments, a cross validation 80% train -20% test is carried out 10 times on each course separately. For the neural network approaches, the training set is divided into a train set, a validation set and a test set. Input features are standardized. The computation of temporal features is carried out by grouping the sessions into 7 days periods. For each period, all features, except the regularity ones, are computed.

Neural networks present the advantage of avoiding the laborious feature selection step, but still need some tuning for determining a correct architecture with its optimization parameters. Our first task was to assess several candidate architectures, varying the number of layers and units. Our prediction tasks were carried out on all courses and results were aggregated. The best accuracies were obtained with the following parameters: [Dense Layer of 512 units, Dropout layer, Dense Layer of 256 units, Dropout layer, Dense layer of 1 unit with a sigmoid activation].

A similar search was carried out for the architecture of the LSTM solution, leading to the following parameters: [LSTM layer of 32 units, Dense layer of 1 units with a sigmoid activation]. The input of the LSTM algorithm, a time series, was computed as follows: each session is considered as a time step. For a specific learner, the input features for time t is computed with the learner t th session and each element of a learner's time step is stacked with its previous element (a padding is applied to provide the same time's series length for each learner).

Finally, in order to assess our prediction at different time steps of the learning process, classification tasks are tested on truncated versions of the sequences. Experiments provide results for 25%, 50%, 75% and 100% of learner's sequence length (number of events).

In the following, the best features for random forest, logistic regression, SVM and AdaBoost models are first presented. Second, the results of the prediction task are detailed for each model.

Best features selection

The best features obtained for the shallow methods are presented in table 3. The best features for SVM and logistic regression are obtained with the wrapper method described in section 5.1. Best features on each course were computed with a 10 times 80%-20% cross validation, leading to a score for each feature depending on its ranking. These scores were then aggregated among the courses. For random forest and AdaBoost, the weights provided by the learning algorithms have been used. For each method and sequence length, we selected the features with the best scores until a sudden drop appeared (the elbow method).

Clearly, the number of best features decreases with the increase of the sequence length available for the classification task, leading to the sole use of marks (feature marks) for full length. The marks feature is obviously pertinent for all sequence lengths.

If we ignore marks, random forest, logistic regression and SVM seem more related to inter-activity periods features while AdaBoost is associated to activity features. The best features concern mainly the marks, the activity intensity and the activity intensity between assessments. No regularity feature appears in the best features list for any model.

In the following, the aggregated best features obtained for SVM and logistic regression models are used to provide the results of our prediction task.

Best models

Table 4 presents the aggregated accuracies obtained for each model on each course separately, with basic features, temporal features and temporal features with stacking.

Each row is associated to a model and the columns present the sequence length used to fit the model (25%, 50%, 75% and 100%). The sub-columns (A., P., F.) stand for All, Pass and Fail, respectively for the overall accuracy, the accuracy for the passing learners and the accuracy for the failing learners.

Among the shallow classification methods, the Adaboost and logistic regression models present the more balanced results on both the passing and failing groups: Adaboost seems more reliable to detect the failing learners while the logistic regression model performs better on the passing group. The Random Forest solution provides good results on balanced courses but clearly fails on very unbalanced ones (see the 28% accuracy on the passing group). The SVM model presents results similar to the logistic regression model, except for the passing learner accuracies which are clearly lower.

Compared to the best shallow models, the dense neural network presents a poor performance on passing learners and does not significantly outperform failing learner prediction. In our opinion, the lack of passing learners for each course in the train set does not enable to fit appropriately the parameter of the network. The LSTM model provides a result similar to the dense neural network, but with a higher computation cost. Hence we do not recommend these neuralbased models in our context.

The process mining model presents very low scores. Our explanation is that the graphs generated by the heuristic miner algorithm on the two learner groups (passing and failing) contain the same navigation paths. Traces for passing or failing learners can then be replayed on both graphs with a good fitness.

A similarly bad result is also obtained with the sequence mining model. It can be explained by the fact that frequent sequences of failing learners are short and almost all included in the frequent sequences of the passing learners. Passing frequent patterns are more numerous and longer (longer patterns involve an increase of the similarity score between a model and an input learner trace). It is then more likely to find a better similarity between a learner sequence and the passing learner model. Our conclusion for the process and sequence mining approaches is that passing and failing learners do not present a discriminant behavior on the way they browse the courses.

The second and third parts of table 4 present the average accuracies when temporal features are used for the input dataset of the models, without and with stacking. Compared to the results obtained with the basic features, the results with the temporal features with and without stacking are lower for all models on all sequence lengths, with a clear drop on the accuracies of the passing learners. To conclude, the temporal features do not provide any improvement in our experiments.

To summarize, our experiments show that shallow models present the best results for our dataset. Among them, Ad-aBoost and logistic regression present the best results respectively for the failing group and the passing group. Another observation is that contrary to several experimental results [START_REF] Ng | Modelling the way: Using action sequence archetypes to differentiate learning pathways from learning outcomes[END_REF][START_REF] Mukala | Learning analytics on coursera event data: A process mining approach[END_REF], our temporal data mining approaches (temporal features, LSTM, process mining and sequence mining solutions) do not perform well on our data set. Our conclusion here is that no difference can be found in the way learners access the course resources.

CONCLUSION

The objective of our work was to assess several solutions for predicting success in the context of Massive Online Open Courses, using a new dataset provided by the OpenClassrooms company, a major online course enterprise in France.

From our experimental results, we reached the following conclusions:

• failing and passing learners do not seem to present differences in the way they browse a course. Neither specific paths nor specific patterns are identified with our proposed solutions to discriminate between passing and failing learners; • best features depend on the model used for the prediction tasks; • temporal features do not increase the performance of the prediction task; • the best models to detect failing and passing learners are respectively based on AdaBoost and logistic regression solutions.

A short term perspective work is to apply the same prediction tasks on other MOOC datasets, in order to validate our previous conclusions in other learning environments.

Table 1 :

 1 Number of learners per group for each course of the OpenClassrooms dataset, after cleanup. The first column presents the total number of learners and the two last ones detail the number of passing and failing learners.

	Name	# users	# pass	# fail
	Java	7761	34 (0%)	7727 (100%)
	XML	855	10 (1%)	845 (99%)
	Ionic	960	46 (1%)	914 (99%)
	Rubys	149	5 (3%)	144 (97%)
	Node JS	2227	81 (4%)	2146 (96%)
	Arduino	2487	115 (5%)	2372 (95%)
	Bootstrap	8402	727 (8%)	7675 (92%)
	Audace Entr.	225	26 (12%)	199 (88%)
	JavaScript	8105	1803 (22%) 6302 (78%)
	Gestion Projet	1808	666 (36%)	1142 (64%))
	Twitter	817	328 (40%)	489 (60%)
	Web	7947	3502 (44%) 4445 (56%)

Table 2 :

 2 Features used for our experiments: this set is composed of features identified in our litterature review, adapted to the characteristics of our dataset (* indicates the features defined by a set of values).

	Category	name	description	abbrev.
		total duration	total time spent on the course	totalDuration
		window duration	time spent from the first event to the last	windowDuration
			one
		linearity	ratio between the number of correct transi-	linearityRatio
			tions, w.r.t. the structure of the course and
			the number of transitions in the sequence
	Activity	# events per resource	# of accesses per resource	#eventPerR
		duration per resource	total time spent on each resource	durationPerR
		average duration per resource	avg duration spent on each resource	avgDurationPerR
		average session duration	avg duration of user sessions	avgSessionDuration
		average # events in session	avg number of events in each user session	avg#eventSession
		median of intertime	median of the time spent between sessions	medianInterTime
		duration before assessment *	time spent before each assessment	durationBeforeA
		# events before assessment *	# of events before each assessment	#eventBeforeA
		# sessions before assessment *	# of sessions between each assessment	#sessionBeforeA
	Inter-	# events per day before assessment *	average number of events per day between	#eventPerDayBeforeA
	activity		each assessment
	periods
		# sessions per day before assessment * avg # of sessions per day between each as-	#sessionPerDayBeforeA
			sessment
		time since last event *	time without activity after 1, 2,. . . , n	timeSinceLastEvent
			weeks (n=7 weeks in our experiment)
		PDH	measure of user activity concentration	PDH
			around a particular hour of the day
		PWD	measure of user activity concentration	PWD
			around a particular day of the week
		WS1	measure of how user regularly works on the	WS1
			same weekdays
		WS2	measure of similar distribution of workload	WS2
			among weekdays, in different weeks
	Regularity	WS3	similarity of time spent on each day of the	WS3
			week for different weeks
		FDH	measure of the repetition of hourly pat-	FDH
			terns of activity over days
		FWH	measure of the repetition of hourly pat-	FWH
			terns of activity over weeks
		FWD	measure of the repetition of the daily pat-	FWD
			tern of activity over weeks
	Assignment	marks *	all marks obtained for each quiz	marks

Table 3 :

 3 Best features for the different sequence lengths for random forest, AdaBoost, SVM and logistic regression models. This result is an aggregation of the best features obtained on each course separately. For each model and sequence length, features are ordered from most to least pertinent.

	Sequence	Random forest	AdaBoost		SVM			Logistic regression
	length
	25%	marks,	durationPerR,	marks,		marks,	#eventPerR,	#eventPerR,	marks,
		#sessionPerDayBe-	avg#eventSession,	#sessionPerDayBe-	durationBeforeA, #ses-
		foreA, #eventBeforeA,	durationPerR, avgDura-	foreA, durationBeforeA	sionBeforeA,	#event-
		avgDurationPerR	tionPerR					PerDayBeforeA
	50%	marks, #sessionPerDay-	marks,	avgDura-	#eventPerR,	marks,	#sessionBeforeA,
		BeforeA, #eventPerDay-	tionPerR, durationPerR,	#eventBeforeA, #event-	#eventPerR,	marks,
		BeforeA		#eventPerR		PerDayBeforeA		#eventBeforeA
	75%	marks, #sessionPerDay-	marks,	avgDura-	marks, #eventPerDay-	marks, #eventPerR
		BeforeA, #eventPerDay-	tionPerR, durationPerR	BeforeA, #eventPerR,
		BeforeA				#sessionBeforeA
	100%	marks		marks		marks			marks

Table 4 :

 4 Accuracies of the different models tested. A., P. and F. stand respectively for All, Pass and Fail

				25%			50%			75%			100%
			A.	P.	F.	A.	P.	F.	A.	P.	F.	A.	P.	F.
		Random forest	91% 28% 96%	93% 36% 96%	94% 47% 96%	98% 77% 98%
		AdaBoost	91% 41% 94%	93% 48% 95%	94% 59% 96%	99% 96% 99%
		SVM	88% 61% 90%	91% 64% 92%	92% 69% 93%	98% 89% 99%
	Basic	Logistic Reg.	88% 66% 89%	91% 71% 91%	93% 84% 93%	99% 100% 99%
	features	Dense NN	91% 37% 94%	93% 47% 95%	94% 59% 95%	98% 82% 99%
		LSTM	90% 38% 93%	91% 47% 93%	93% 55% 95%	97% 78% 98%
		Process mining	66% 47% 64%	72% 49% 71%	67% 54% 65%	64%	54%	58%
		Seq. mining	24% 85% 13%	24% 88% 9%	22% 95% 5%	18% 100% 0%
		Random forest	92% 9% 99%	92% 11% 99%	92% 12% 98%	92% 11% 99%
	Temporal features	AdaBoost SVM Logistic Reg.	90% 42% 94% 88% 60% 90% 87% 58% 91%	92% 46% 95% 89% 65% 90% 91% 67% 92%	92% 46% 96% 92% 72% 92% 92% 76% 92%	95% 55% 98% 99% 87% 99% 99% 90% 99%
		Dense NN	89% 36% 93%	90% 41% 93%	92% 48% 94%	94% 59% 96%
	Temporal features with stacking	Random forest AdaBoost SVM Logistic Reg. Dense NN	89% 16% 97% 91% 43% 94% 91% 66% 93% 89% 64% 90% 88% 36% 92%	90% 22% 98% 92% 47% 95% 87% 23% 95% 90% 61% 92% 83% 18% 88%	91% 24% 97% 93% 51% 96% 91% 57% 92% 92% 76% 92% 79% 17% 82%	92% 29% 96% 97% 67% 99% 91% 61% 92% 98% 91% 98% 78% 18% 83%


Karine Amis Cavalec

Nicolas Le Josse
email: nicolas.lejosse@enst-bretagne.fr

Karine Amis
email: karine.amis@enst-bretagne.fr

Christophe Laot
email: christophe.laot@enst-bretagne.fr

Efficient Frequency-Domain MMSE turbo equalization derivation and performance comparison with the Time-Domain counterpart

teaching and research institutions in France or abroad, or from public or private research centers.

Efficient frequency-domain MMSE turbo equalization derivation and performance comparison with the time-domain counterpart

Introduction

Wireless digital communications are about to take the place of wired applications. To overcome the need for an increasing volume of information through a band limited transmission medium, a solution is to use multiple antennas at both sides of the communication link. Space Time Bit Interleaved Modulations [START_REF] Tonello | On Turbo Equalization of Interleaved Space-Time Codes[END_REF] have thus been proposed to achieve high spectral efficiency transmissions over frequency selective channels. Bit interleaved Modulation consists in cascading an information binary digit encoder, an interleaver and a modulator. For ST-BICM, modulated symbols are spatially splitted into n T substreams, where n T denotes the transmit antenna number. Each substream is sent from its corresponding antenna. Provided the channel is frequency selective, such a transmission scheme combines spatial, frequency and time diversities. The receiver has to be thought so as to take fully advantage of the available diversity. The Maximum Likelihood A Posteriori receiver achieves this goal but its computational cost is too high and makes its implementation impossible. The MMSE turbo equalization principle [START_REF] Glavieux | Turbo Equalization over a frequency selective channel[END_REF][START_REF] Wang | Iterative (turbo) soft interference cancellation and decoding for coded CDMA[END_REF][START_REF] Tüchler | Minimum mean squared error equalization using a priori information[END_REF] enables to derive low complexity receivers that can achieve optimal performance. It has been extended and applied to detect single carrier ST-BICM. In [START_REF] Chtourou | A New Class of Iterative Equalizers for Space-Time BICM over MIMO Block Fading Multipath AWGN Channel[END_REF][START_REF] Wautelet | MMSE-Based Turbo Receiver for Space-Time BICM Over Frequency-Selective MIMO Fading Channels[END_REF][START_REF] Abe | Space-Time Turbo Equalization in Frequency-Selective MIMO Channels[END_REF], the MMSE equalization is carried out in the time domain.

Nevertheless, frequency-domain processing has retained more attention to be an effective mean for reducing computational complexity. Frequency domain approaches for MMSE turbo equalization are proposed in [START_REF] Tüchler | Linear time and frequency domain turbo equalization[END_REF][7] [START_REF] Chtourou | Low Complexity Frequency Domain Turbo Equalizer for STBICM over MIMO ISI Channel[END_REF] for SISO and MIMO systems respectively. More precisely, The filtering equations, derived in the time-domain, are converted to the frequency-domain by taking advantage of the circular convolution property of the channel impulse response and the data symbols enabled by inserting a cyclic prefix at the beginning of each transmitted packet. The resulting structure includes only one filter in succession of a soft interference canceller.

In [START_REF] Kalbasi | Layered Space-Time Receivers for Single-Carrier Transmission with Iterative Frequency-Domain Equalization[END_REF], the authors propose an interesting frequencydomain equation derivation for an iterative BLAST receiver. In the spirit of [START_REF] Kalbasi | Layered Space-Time Receivers for Single-Carrier Transmission with Iterative Frequency-Domain Equalization[END_REF] and based on the approach of [START_REF] Laot | Low Complexity MMSE Turbo Equalization : a possible solution for EDGE[END_REF], we derive a Turbo equalizer for ST-BICM by optimizing the feedback and feedforward filters directly in the frequencydomain. In that sense, this paper improves the derivation of the previous approach [START_REF] Tüchler | Linear time and frequency domain turbo equalization[END_REF][7] [START_REF] Chtourou | Low Complexity Frequency Domain Turbo Equalizer for STBICM over MIMO ISI Channel[END_REF].

In systems that communicate over large delay spread channels, it is well understood that TD MMSE turbo equalization provides comparable performance when configured with a high impulse response length filter. However a performance comparison between the frequency-domain MMSE turbo equalizer and its time-domain counterpart, for which the filter length has to be properly and efficiently chosen, has never been proposed yet. In this paper, we consider the problem of finding the TD filter achieving the best compromise between minimum impulse response length and performance.

In section II, we describe the MIMO transmission scheme and particularly the frame structure adaptation to frequency domain equalization. In section III, the turbo equalizer equations are derived and in section IV, simulation results show the receiver efficiency in comparison with that of the corresponding MMSE equalizer in the time-domain. In this section the TD filter length choice is pointed out.

MIMO system description

Notations

In the following, considering a matrix A, A •,i denotes the i th column of A and A j,• denotes the j th row of A. A T is the transpose of A and A † is the Hermitian transpose of A. If {x(n)} is a symbol sequence of size N , {X(p)} denotes its N -Discrete Fourier Transform.

Transmission model

We consider a MIMO system consisting of n T transmit antennas and n R receive antennas. Information binary digits are first encoded thanks to a non recursive convolutional code before being interleaved. Interleaved coded bits are then modulated and passed through a serial to parallel converter. Each of the n T resulting symbol streams is sent from one of the n T transmit antennas. We denote s i (p) the p th symbol transmitted from the i th transmit antenna. The modulation size is denoted M and m is defined as m = log 2 (M ).

In case of a frequency selective channel, the received data result from the convolution of the channel impulse response and the data symbols. Frequency-domain receiver requires that the time domain convolution of the two finitelength sequences be equivalent to the product of their Discrete Fourier Transform coefficients. This is true only if the transmitted frame structure enables the convolution to be circular. This is achieved by inserting a cyclic prefix (the last ν symbols are reported at the beginning of the sequence) or extending each finite-length sequence by a known word [START_REF] Benvenuto | On the comparison between OFDM ans Single Carrier modulation with a DFE using a frequency domain feedforward filter[END_REF]. In this paper, each substream symbols are splitted into packets of size N and a cyclic prefix of size ν is inserted at the beginning of each packet. At the receiver side, the cyclic prefix is suppressed before operating the N -DFT.

Let us denote h j,i (z) =

L-1 l=0 h j,i (l)z -l the Ztransform of the channel impulse response between transmit antenna i and receive antenna j. The complex AWGN noise coefficients on receive antenna j are denoted b j (n). Assum-ing perfect carrier and time synchronisation, the samples received on receive antenna j can be written as follows.

r j (n) = nT i=1 L-1 l=0 h j,i (l)s i (n -l) + b j (n) (1)
After the cyclic prefix extraction, {r j (n)} is splitted into packets of length N . A N -DFT is applied on each block. We thus obtain

N vectors R(p) of size n R whose expression is R(p) = H(p)S(p) + B(p) (2)
where

R(p) = [R 1 (p) • • • R nR (p)] T , S(p) = [S 1 (p) • • • S nT (p)] T , H(p) = H j,i (p) 1≤i≤n T 1≤j≤n R with {H j,i (p)} the N -DFT of {h j,i (l)}.

Statistical property assumptions

We assume that the interleaver depth is sufficient to ensure that information binary digits entering the modulator are independent and identically distributed. Denoting them α k , an additional hypothesis is Pr(α k = 1) = 1 2 . Taking into account a QAM or PSK modulation, the modulated symbols s i (n) have zero mean and the cross-correlation matrix coefficients are given by

E[s i (n)s q (n -k)] = σ 2 s δ k,0 δ i-q,0 (3)
where δ k,0 is the Kronecker symbol.

Complex noise samples are supposed to be independent, identically distributed of zero mean and variance σ 2 b .

Frequency-Domain Turbo Equalization

The turbo equalization principle [START_REF] Douillard | Iterative correction of inter symbol interference : Turbo equalization[END_REF] consists in repeating the equalization and decoding processes by exploiting information available at the decoder output in the equalizer. In the proposed receiver scheme, the equalization is operated in the frequency domain whereas the decoding process is carried out in the time domain.

Information exchange principle

The decoder provides the equalizer with A Posteriori Probabilities for the encoded binary digits that can be used to compute a soft estimate of transmitted symbols. We denote L D Out (q) the Logarithm of Likelihood Ratio for the q th encoded bit available at the decoder output. {L D Out (q)} are interleaved and provided to the equalizer input to estimate the Inter Symbol Interference (Co and Inter Antenna) and take it into account in the decision value computation. Let us denote si (n) a soft estimate of s i (n). The samples si (n) are computed using the regression curve theory, i.e. taking the conditional expectation. More precisely, si

(n) = E[s i (n)|{L E In (q)}],
where {L E In (q)} corresponds to the interleaving of {L D Out (q)}. Moreover as in [START_REF] Laot | Low Complexity MMSE Turbo Equalization : a possible solution for EDGE[END_REF], si (n) are assumed to be independent and identically distributed of zero mean and variance denoted σ 2 s . If S denotes the modulation constellation, using the bit to symbol conversion

{α i (t)} mn≤t≤m(n+1)-1 ∈ {0, 1} m ↔ s i (n) ∈ S, (4) we can write si (n) = s∈S s Pr(s i (n) = s|{L E In (q)}) (5)
= s∈S {α k }↔s s m(n+1)-1 t=mn Pr(α i (t) = α k |{L E In (q)}) (6)
with

Pr(α i (k) = α|{L E In (q)}) = 1 2 1+(2α-1) tanh( L E In (t) 2
) .

(7) where α i (k) corresponds to the t th binary digit in the interleaved coded binary sequence. One can prove [START_REF] Laot | Low Complexity MMSE Turbo Equalization : a possible solution for EDGE[END_REF] that

E[s i (n)s q (n -k)] = σ 2 s δ k,0 δ i-q,0 (8)
E[s i (n)s q (n -k)] = σ 2 s δ k,0 δ i-q,0
Both properties are used in the equalizer equation derivation.

Frequency domain equalizer equation derivation

Based on the approach in [START_REF] Glavieux | Turbo Equalization over a frequency selective channel[END_REF], the proposed equalizer consists of a feedforward and feedback MMSE filters in the frequency domain. We denote { Si (p)} the N -DFT of {s i (n)}. The equalizer computes Ŝi (p) from R(p) and { Sq (p)} 1≤q≤nT . More explicitly, Ŝi (p) is given by

Ŝi (p) = W i,• (p)R(p) -Q i,• (p) S(p) (9)
where W i,• (p) denotes the n R length row vector of the pth feedforward filter frequency coefficients and Q i,• (p) is the n T length row vector of the pth feedback filter coefficients such that its diagonal elements in the time domain is equal to zero: q i,i (0) = 0, i.e.

N -1 p=0 Q i,i (p) = 0.
To obtain the matrices W(p) and Q(p), we minimize the mean square error between Ŝ(p) and S(p) under the constraint

N -1 p=0 Q i,i (p) = 0 for each index i.
The Lagrangian resolution of this optimization problem provides us with the following equations :

G(p) = (1 - σ 2 s σ 2 s ) nT q=1 H •,q (p)[H •,q (p)] † + σ 2 b σ 2 s I nR ( 10
)
β i = 1 N N -1 p=0 [H •,i (p)] † G(p) -1 H •,i (p) (11)
µ i = β i 1 + σ 2 s σ 2 s β i (12) W i,• (p) = (1 - σ 2 s σ 2 s µ i )[H i,• (p)] † G(p) -1 (13) Q i,• (p) = W i,• (p)H(p) -µ i e i ( 14
)
where e i is a n T length vector with coefficient in position i equal to one and the other ones equal to zero. In [START_REF] Abe | Space-Time Turbo Equalization in Frequency-Selective MIMO Channels[END_REF][START_REF] Tonello | On Turbo Equalization of Interleaved Space-Time Codes[END_REF][START_REF] Tüchler | Minimum mean squared error equalization using a priori information[END_REF][START_REF] Wang | Iterative (turbo) soft interference cancellation and decoding for coded CDMA[END_REF][START_REF] Yee | Comparison study of Single-carrier and Multi-carrier modulation using iterative based receiver for MIMO system[END_REF]], estimation of s(n) is based on MMSE linear estimation requiring the computation of second order statistics at each signalling instant using the information delivered by the decoder. This approach provides a more accurate estimation of s(n) at the expense of a higher complexity [START_REF] Laot | Low Complexity MMSE Turbo Equalization : a possible solution for EDGE[END_REF][START_REF] Tüchler | Minimum mean squared error equalization using a priori information[END_REF]. Note that, after some mathematical developpements, we can obtain an equalizer structure equivalent to that of [3][7], i.e a soft interference canceler followed by a MMSE linear filter in frequency-domain.

Analysis of the equalizer output

Considering the expression of R(p) and equations [START_REF] Laot | Low Complexity MMSE Turbo Equalization : a possible solution for EDGE[END_REF][START_REF] Le Josse | Performance Validation for MMSE Turbo Equalization in ST-BICM Systems[END_REF][START_REF] Al Dahir | Finite Length MIMO Decision Feedback Equalization for Space Time Block Codes Signals over Multipath-fading Channels[END_REF][START_REF] Tonello | On Turbo Equalization of Interleaved Space-Time Codes[END_REF][START_REF] Tüchler | Linear time and frequency domain turbo equalization[END_REF], one can easily obtain an equivalent expression of the equalizer output :

Ŝi (p) = µ i S i (p) + Q i,• (p)(S(p) -S(p)) + W i,• (p)B(p) (15)
Therefore one can write ŝi (n) = µ i s i (n) + η(n) where η(n) corresponds to the residual ISI and the noise. Indeed due to the constraint on {Q i,i (p)}, η(n) and s i (n) are independent. We assume that η(n) is a complex gaussian noise. We can prove that η(n) is a zero mean random variable of variance σ 2 η equal to σ 2 s µ i (1µ i ). Therefore a direct approximation of the conditional density probability function of ŝi (n) is

p ŝi(n)|si(n) (x) = 1 πσ 2 η exp - |x -µ i s i (n)| 2 σ 2 η ( 16
)

Soft symbol to binary digit conversion

We define the extrinsic information delivered by the decoder by

X D Out = L D Out -X D In . X D Out (q) is independent from X D
In (q) which is delivered by the equalizer. Therefore it will be used as a valuable a priori piece of information in the soft symbol to binary digit converter. We denote X E

In the interleaved sequence of X D Out . Assuming that α i (mn + k) corresponds to the position q in the serial binary stream (i.e before the modulation and the serial to parallel conversion), the Logarithm of Likelihood Ratio for the q th binary digit is given by :

L E Out (q) = ln( s∈S|α k =1 p ŝi(n)|si(n) (x) Pr(s i (n) = s|X E In ) s∈S|α k =0 p ŝi(n)|si(n) (x) Pr(s i (n) = s|X E In ) ) (17)
The symbol to binary digit converter output is defined as the extrinsic information extracted from L E Out (q) and independent of X E In (q).

X E Out (q) = L E Out (q) -X E In (q) (18)
X E Out is desinterleaved giving X D In . X D
In becomes the new decoder input.

The whole receiver structure is summarized in Fig. 1.

Lower bound of the turbo equalizer performance

A lower bound of the iterative equalizing and decoding process can be obtained by feeding the equalizer with perfect decoder output. It consists in considering S(p) equal to S(p) in ( 9) and taking X E In (q) = γ[2α i (mn + k) -1] where α i (mn + k) corresponds to the q th binary digit in the interleaved coded sequence and γ is a constant of high value. The so-called genie FD MMSE turbo equalizer supresses multi-antenna interference and intersymbol interference for each transmit antenna, from the received signal. Assuming soft demapping without a priori knowledge, we can accurately predict asymptotic performance at the frequencydomain equalizer output following the proposed approach in [START_REF] Le Josse | Performance Validation for MMSE Turbo Equalization in ST-BICM Systems[END_REF]. Simulations are shown in section IV to confirm the purpose.

Simulation results

This section is dedicated to the simulation result presentation. Before introducing the parameters, we define the Signal to Noise Ratio and its expression as a function of

E b
N0 . E b is the average energy necessary to transmit an information binary digit and N 0 is the unilateral power spectral density function of the gaussian noise.

Signal to Noise Ratio definition

According to (3), the average total transmitted power per channel use is given by P s = n T σ 2 s . Defining a super symbol as

s(n) = [s 1 (n) • • • s nT (n)] T ,
and its duration T , and denoting E s the average energy necessary to transmit a super symbol, we can write E s = P s T . On the other hand, if R c is the coding rate, the following equality holds:

E s = n T mR c E b .
If the reception low-pass filter is the square root of a raised cosinus filter, the average gaussian noise power is equal to P b = N0 T . Furthermore P b = σ 2 b . As a consequence, the average signal to noise ratio per receive antenna is

ρ j = E[ nT i=1 h ji 2 ] P s n T P b = mR c E b N 0 E[ nT i=1 h ji 2 ] ( 19
)
where

h ji 2 = L-1 l=0 |h ji (l)| 2 .

Turbo equalizer performance over an ISI channel

The simulation context is the same as in [START_REF] Chtourou | A New Class of Iterative Equalizers for Space-Time BICM over MIMO Block Fading Multipath AWGN Channel[END_REF]. We consider a MIMO system with n T = n R = 2. The information sequence length is 506. The convolutional code has a coding rate of 1 3 and its octal polynomial representation is (133, 145, 175). Binary coded digits are pseudo-randomly interleaved before being 8-PSK modulated. We consider that the interleaver depth is sufficient to ensure information binary digits entering the modulator are i.i.d. Simulations have shown that taking higher interleaver size does not improve the bit error rate. Then symbols are splitted into packets of size 256. A cyclic prefix is added at the beginning of each packet. We assume that channel impulse responses between two transmit and receive antenna pairs are uncorrelated and consist of two paths separated by a symbol duration and of equal average power. h ji (z) = h ji (0) + h ji (1)z -1 with h ji (l) ∼ N(0, 1 4 ) + jN (0, 1 4 ). The channel is time-invariant over a symbol packet duration (i.e over N + ν symbols) and we assume perfect channel state information at the receiver. Assuming soft demapping without a priori knowledge, the bit error rate (resp. Frame error rate) after each equalization and decoding iteration is plotted as a function of E b N0 in Fig. 4.2 (resp. 3). The signal to noise ratio computation does not take into account the cyclic prefix and the trellis termination bits. The performance of the turbo equalizer with perfect a priori information from the decoder (cf. III.E) is plotted as a reference (genie-equalizer and genie-decoder). The genieequalizer performance is compared to the corresponding analytical probability of bit error developed in [START_REF] Le Josse | Performance Validation for MMSE Turbo Equalization in ST-BICM Systems[END_REF]. We observe that both curves are indistinguishable which confirm the accuracy of the proposed FD algorithm. The figure also shows that for E b N0 superior to 2 dB, the iterative process at the equalizer output reaches a steady-state after 3 iterations which matches the lower bound. On the other hand, for a BER of 10 -2 at the decoder output, there is a gap of 1.5 dB compared to the genie-aided decoder output. This is due to the fact that the BER at the equalizer output is not exactly the same as the one available at the genie-aided output and this little difference is amplified at the decoder output. Indeed the decoder is very sensitive to the reliability value level. In Fig. 3, the behaviour for FER is somehow different. The decoder performance after 6 iterations is at less than 0.4 dB from the genie-aided decoder. Considering the iterative receiver convergence, we can observe that 4 iterations are sufficient. The improvement brought by the fifth and sixth iterations is negligible.

Frequency-domain vs Time-domain MMSE Turbo equalization

A further evaluation is performed to compare the performance of the proposed algorithm with that of the corresponding TD MMSE equalizer. Refering to [START_REF] Chtourou | A New Class of Iterative Equalizers for Space-Time BICM over MIMO Block Fading Multipath AWGN Channel[END_REF][START_REF] Wautelet | MMSE-Based Turbo Receiver for Space-Time BICM Over Frequency-Selective MIMO Fading Channels[END_REF][START_REF] Kansanen | Multilevel-Coded QAM with MIMO Turbo-Equalization in Broadband Single-Carrier Signaling[END_REF], the TD MMSE equalizer consists of a soft interference canceler followed by a MMSE linear filter. It requires a sliding window, of sufficient length Nf from each antenna at the receiver to ensure optimum MSE solution. The issue is to find a value Nf that meets a compromise between performance and computation cost. The design of finite length filter in time-domain is well understood and finite length constraints can be considered under the MSE criterion [START_REF] Al Dahir | Finite Length MIMO Decision Feedback Equalization for Space Time Block Codes Signals over Multipath-fading Channels[END_REF]. We consider the same MIMO transmission scenario as in section IV. We define r = σ 2 s σ 2 s as the a priori information reliability degree. It can be seen that r = 1 (resp. r = 0), corresponds to perfect (resp. unavailable) a priori information from the decoder output. The deviation between the MSE of an equalizer using a Nf length impulse response filter and the minimum MSE is plotted as a function of Nf in Fig. 4 for different values of r and E b N0 . As shown in Fig. 4, the filter length corresponding to the inflexion point in each curve, enables the equalizer to achieve a good compromise between complexity (short filter length) and ISI reduction (long filter length). Interestingly, we observe that the effective filter length decreases while the parameter r increases. For r = 1, the MMSE equalizer is able to retrieve the whole N0 and r = 1, the ISI phenomenon dominates over the noise such that the equalizer has to invert the channel impulse response. As a consequence, a high impulse response length filter is necessary in order to avoid unstable phenomena due to finite length equalization constraints.

According to Fig. 4, using a 2L + 1 length filter enables to achieve a good compromise between computational cost and performance for E b N0 = 5dB. We thus take Nf = 2L+1 in the following. We consider the same MIMO transmission scenario as in section IV for n T = n R = 2 with respectively L = 2 and L = 10 paths and variance 1/L. The bit error rate (resp. frame error rate) after the sixth decoding iteration is plotted as a function of E b N0 in Fig. 5 (resp. Fig. 6). The performance of the turbo equalizer with perfect a priori information from the decoder is plotted as a reference. We observe that the time-domain and frequency-domain techniques perform identically in each MIMO channel configuration when Nf = 2L + 1. We can conclude that the proposed MMSE turbo is the relevant frequencydomain counterpart of the time-domain. Note that, it is seen that the genie decoder performance corresponding to L = 2 paths outperform the one respresented in Fig. 4.2 with a 1dB gain which comes strictly from the improvement due to soft demapping with a priori knowledge. The figure also shows performance improvement due to multipath diversity with the increase of channel impulse response length. Hence our system benefits from an additional diversity of order L due to the channel dispersion.

We have also considered the TD MMSE turbo equalizer performance with a low number of filter coefficients (L +1) to confirm the results in Fig. 4. As shown in Fig. 5 (resp. Fig. 6), the sixth decoding iteration corresponding to L = 2 paths is very close to that of the TD turbo equalizer with sufficient filter length. It should be noted that if asymptotic performance is the same, the TD turbo equalizer with sufficient filter length exhibits faster convergence. On the other hand, noticeable loss in performance is observed for L = 10 paths when the filter length is set to L+1. For L = 2, taking Nf equal to 3 does not degrade the performance compared to using Nf = 5. On the contrary, for L = 10, taking a 11-length filter brings a noticeable degradation in comparison with a 21-length filter. In Fig. 5, for a BER of 10 -2 at the decoder output, there is a gap of 4dB compared to the TD MMSE turbo equalizer with sufficient filter length. The same observations can be done in Fig. 6 for the FER.

Performing equalization in the time-domain requires a minimum filter length to achieve good performance at the expense of a high computational complexity for channels with severe ISI. In that case, the FD MMSE turbo equalizer seems more suitable.

Conclusions

This paper describes a frequency domain turbo equalizer for Space Time Bit interleaved coded modulation. The proposed turbo equalizer differs from previous approaches in that feedforward and feedback filters are directly derived in the frequency domain. Asymptotic performance has been shown to be consistent with the probability of bit error derived in [START_REF] Le Josse | Performance Validation for MMSE Turbo Equalization in ST-BICM Systems[END_REF]. Simulations over multipath Rayleigh block fading channels show the structure equivalence in comparison with the time-domain approach. The frequency-domain equalizer structure is independent of the channel impulse response length on contrary of the time-domain one for which the filter length has to be properly chosen so as to ensure good performance. Future work will consider computation cost reduction of the whole iterative process in the case of TD receiver, by shortening the filter length with the iterations.

Figure 1 .

 1 Figure 1. Frequency domain turbo equalizer structure

Figure 2 .

 2 Figure 2. BER as a function of E b N0 -2 Tx 2 Rx -CC(133,145,175)-8-PSK

Figure 3 .

 3 Figure 3. FER as a function of E b N0 -2 Tx 2 Rx -CC(133,145,175)-8-PSK

2 Eb/No=15dB σ 2 s = σ 2 sFigure 4 .

 2224 Figure 4. MSE as a function of Nf for various reliability information levels r = σ 2 s /σ 2 s -E b N0 = 5dB, 15dB -2 Tx 2 Rx -CC(133,145,175)-8-PSK

Figure 5 .

 5 Figure 5. BER as a function of E b N0 -2 Tx 2 Rx -CC(133,145,175)-8-PSK. 6 iterations are performed

Figure 6 .

 6 Figure 6. FER as a function of E b N0 -2 Tx 2 Rx -CC(133,145,175)-8-PSK

This work was supported in part by FT RD.