Ugur Demir
email: ugurdemir@itu.edu.tr

Esam Ghaleb
email: ghalebe@itu.edu.tr

Hazım Kemal Ekenel
email: ekenel@itu.edu.tr

A Face Recognition Based Multiplayer Mobile Game Application

Keywords: face recognition, multiplayer mobile game, DCT, LBP, SVM

In this paper, we present a multiplayer mobile game application that aims at enabling individuals play paintball or laser tag style games using their smartphones. In the application, face detection and recognition technologies are utilised to detect and identify the individuals, respectively. In the game, first, one of the players starts the game and invites the others to join. Once everyone joins the game, they receive a notification for the training stage, at which they need to record another player's face for a short time. After the completion of the training stage, the players can start shooting each other, that is, direct the smartphone to another user and when the face is visible, press the shoot button on the screen. Both the shooter and the one who is shot are notified by the system after a successful hit. To realise this game in real-time, fast and robust face detection and face recognition algorithms have been employed. The face recognition performance of the system is benchmarked on the face data collected from the game, when it is played with up to ten players. It is found that the system is able to identify the players with a success rate of around or over 90% depending on the number of players in the game.

Introduction

Mobile applications have become more common and popular with the advances in smartphone technologies. They have also become one of the main segments of the digital entertainment. Many successful mobile gaming companies have emerged recently with very high market values. Most of these games require users' focus and attention, isolating them from the real world. However, mobile games can also be designed to provide entertaining human-human interaction experience. In this way, instead of isolating the users from the real world, mobile game applications can convert a smartphone to a tool that allows users to interact with the others in a fun way. With this motivation, in this study, we designed a mobile game application that enables individuals play paintball or laser tag style games using their smartphones 1 . The application benefits from computer vision and pattern recognition technologies, specifically, face detection and recognition to detect and identify the players. In order to have real-time processing capability, which is required for the game, we have employed fast and robust face detection and recognition algorithms.

The developed game consists of two main components, server and mobile application. The server application regulates the game rules and players' network stream. In addition, server application contains the face recognition module. The game application sends camera frames that contain players' faces to the server. Thus, mobile application contains only network and face detection module. At the beginning of the game, players join a game session, which is created by one of the players. After all the players are attended, training stage is started by the server. Mobile applications gather player images as training data and sends them to the server. Each player collects different player's face data. When server application receives all of the training data, it extracts the features and trains the classifiers. Afterwards, the game starts and players attempt to shoot each other. If camera detects a face, while a player is shooting, it sends the detected face image to the server application. The server application assigns an identity to the received face image by using trained classifiers, and then broadcasts the necessary information to the mobile devices. The flow diagram of the game is shown in Fig. 1.

The rest of the paper is organised as follows. In Section 2, the server application architecture is introduced. In Section 3, design of the mobile application is explained. In Section 4, proposed face recognition methods and classifiers are stated. Tests and experimental results are presented in Section 5. Finally, conclusions and future work are given in Section 6. Server application that controls the game flow is the main part of the system and consists of three core modules, which are network module, game flow control module, and face recognition module. All of these core modules work collectively during a game session. Network module's main purpose is receiving the commands and images from mobile devices, and then deciding to what information should be broadcasted to players. All of the mobile devices connect to the server over a TCP socket before starting to play. Server always listens to the TCP port for incoming client data, which is represented with JSON format. It creates and runs a new thread called network thread for each connected mobile device. These threads manage the network operations. Network module does not interfere the game flow logic. It is only responsible to transfer the received data to game flow module and transmit resulting data to relevant clients. This abstraction enables us to design a more robust multiplayer game server.

Game flow control module executes the client's orders delivered by network module, which are based on the game rules. This module decides to execute necessary function calls depending on the client's request. If an image is received, it is transferred to face recognition module and results are evaluated. Player scores are calculated by this module. If a player shoot another player, game flow control module tells network module to notify these players.

Face recognition module handles training and classification tasks in the server. It has two stages in its life cycle; training and classification. In the training part, face recognition module collects player images and generates a multi-class classifier for each mobile device. We assume that players do not shoot themselves. Thus, each classifier recognise all the players in a game session except the player, who owns the mobile device. After the training stage, flow control module starts the game. Then classification stage takes control in face recognition module. In this stage, player images are queried to determine, which player's face image it is. All modules and server application are implemented in Java programming language. In the face recognition module, OpenCV library Java port is used.

Mobile Application

Mobile game application contains user interface and communication module, which delivers user commands and listens for incoming server data. At first, devices send a connection request to the server, when a player starts the game application. If the connection is successfully established, a user menu, which shows the game options, appears on the screen. Then, player can join or create a game lobby via this menu to start the game.

After starting the mobile game application, a thread called communication thread is started to run by the application. Communication thread listens the incoming server data during the application life-cycle to broadcast the necessary data to the application screens, which player interacts with. We apply observer pattern to achieve this scheme. In the observer pattern, objects that display the data is isolated from the object that stores the data and storage object is observed to detect changes on data [START_REF] Cooper | Java Design Patterns: A Tutorial[END_REF]. Observer pattern is suitable for communication module of the game due to its architecture. Communication thread listens and stores the data, so it represents the observable object in the system. Application screens, which is called Activity in Android SDK [START_REF]Android SDK Activity[END_REF], stand for the observer object in observer pattern. Server sends state changes via TCP sockets to communication thread and activities observe the communication thread for any data changes. Fig. 2 shows the network architecture. Activities in the application register themselves to observe communication thread before starting and unregister before closing. Thus, communication thread transfer the data to only relevant activities and modules. Observer activities filter and parse the received data and display to user. Mobile application flow consists of three main step; joining the game, collecting the training data, and playing. One player, called creator, creates a game lobby and waits for the other players join the existing lobby. Creator player can see the entered players on the application screen and start, when there are at least two players in the lobby including creator.

After the creator starts the game, the game lobby is configured in the server and server sends a command, which tells training session must be started, to all players. In the training stage, players' face images are collected via smartphones' cameras. Collected images are sent to the server for training. When all players send the images and the training is completed, server starts the game and sends start game command to players' devices. Main game screen basically consists of camera preview and an aim marker. If a player presses the shoot button and the aim marker overlays with a player's face at the same time, detected face image is sent to the server. Server analyses the face image and sends the information about who shoots which player to the corresponding players. Fig. 3 shows same screenshots from the mobile game screen.

Face Recognition

Face recognition process consists of the following steps: face detection, feature vector extraction and classification as shown in Fig. 4. In face recognition, the first step is to detect a face in a given frame. In this study, Viola-Jones face detection method is used [START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF]. We benefit from the available OpenCV implementation of this approach [START_REF]OpenCV Android SDK[END_REF]. Fig. 5 shows sample detected faces. Please note the illumination and view variations that pose challenges for the application.

For feature extraction from face images Discrete Cosine Transformation (DCT) and Local Binary Pattern (LBP) are implemented. These two representation methods are proven to be fast and robust in previous studies [START_REF] Ahonen | Face Description with Local Binary Patterns: Application to Face Recognition[END_REF][START_REF] Ekenel | A robust face recognition algorithm for real-world applications[END_REF]. DCT is popular for being a fast and efficient transformation, mainly used for data compression, due to its capability to represent data in a compact form. As a result, this makes DCT a suitable approach for mobile applications. In this paper, to extract a feature vector from a given image, DCT was applied as explained in reference [START_REF] Ekenel | Analysis of local appearance based face recognition: Effects of feature selection and feature normalization[END_REF]. The images are first resized to have 64 × 64 pixel resolution and then divided to nonoverlapping blocks. Each block has 8 × 8 pixel resolution. Then DCT is applied on these local blocks. Following this process, zig-zag scanning is used to order the DCT coefficients. For each block, M features are picked and normalised. These local features are then concatenated to form the overall feature vector of the image. This obtained feature vector represents the given image. In the implementation M is set to 5, making the resulting DCT feature vector of the length equal to 5 × 8 × 8 = 320.

LBP is widely used for face feature extraction and it has been proven to be very effective and successful approach for many tasks such as face recognition and face verification. In LBP, for every pixel in gray level image, it assigns a label to it, based on its neighborhood [START_REF] Ahonen | Face Description with Local Binary Patterns: Application to Face Recognition[END_REF]. In this study, first the face image is resized to 66 × 66 pixel resolution -two additional pixels due to the operations at the image boundaries-, then divided to nonoverlapping blocks of 8 × 8 pixel resolution. For each pixel in a block, the pixel is compared to each of its 8 neighbours and its corresponding LBP code is assigned. Since the 8 neighborhood is considered, a 256-bin histogram of LBP codes is computed. To reduce the dimensionality, the subset of LBP codes, called the uniform patterns, are used [START_REF] Ahonen | Face Description with Local Binary Patterns: Application to Face Recognition[END_REF][START_REF] Shan | Facial Expression Recognition Based on Local Binary Patterns: A Comprehensive Study[END_REF][START_REF] Choi | Age estimation using a hierarchical classifier based on global and local facial features[END_REF]. A uniform pattern contains a two or less number of transitions from zero to one or vice versa. As a result, the patterns that has more than two transitions are aggregated into a single bin in the LBP histogram besides the other uniform patterns, reducing the histogram size to 59 bins. The obtained histograms from local blocks are concatenated into a single feature vector that represents the entire image. The resulting LBP feature vector's length equals to 8 × 8 × 59 = 3776.

Following feature vector extraction from the face images, the application employs multi-class classifiers, either Support Vector Machine (SVM) or K-Nearest Neighbor (KNN) classifiers. In SVM the used kernel function is radial basis function and constraint parameter is set to 0.5 [START_REF] Burges | A Tutorial on Support Vector Machines for Pattern Recognition[END_REF]. In KNN, K is set to 1 and the L1 and L2 distance metrics are used.

In order to asses the face recognition system's performance, a face database is generated using the developed mobile game application. For these evaluations ten images for training and ten images for test are collected from twelve players. Samples from training and testing data sets are shown in Fig. 6. The variations in facial expression, head pose, and illumination results in a very challenging task. DCT and LBP are used for feature extraction, respectively, and the extracted features are then classified by SVM or KNN. In the tests, we change the number of players in the game from two to ten players and examine the performance for each number of players in the game. For each number of players in the game, we form ten different player combinations and the recognition rates are calculated as the average of these ten different combinations in order to have a reliable measure for the system performance.

Experiments on the Standard Data Set

In the first experiment, the evaluation is conducted using the collected data set without doing any data manipulation for additional sample generation. The results of this experiment are plotted in Fig. 7(a). As shown in the figure, the horizontal axis represents the number of the players in the mobile game application, who must be classified, while the vertical axis shows the correct classification rate, which is the average over ten different player combinations. The performance curves give the results for different combination of classification and feature extraction methods. As can be observed from the figure, using LBP features, the best performance is achieved. There is no significant performance difference, when using SVM or KNN. As the number of players in the game increases, the obtained performance decreases, however this decline is slight and the system performance stays around 90% when using LBP features.

Experiments on the Extended Data Set

In the experiments on the extended data sets, two different scenarios are applied. In these scenarios, either training data set or test data set is extended. In the first scenario, the purpose is to enrich the training data set. As a result, the collected 10 image for training are manipulated to generate 900 images using mirroring, translation and rotation. This extended data set is used for training, while test data set remains as it is. The obtained results are shown in Fig. 7(b). As shown in the performance curve, enriching training data set has improved the recognition rate. Especially, the LBP+SVM combination consistently performs at 100%. However, since SVM's training complexity depends on the square of the amount of samples, that is, it has a complexity of O(mn 2 ), where m is the dimension of the feature vector and n is the amount of training samples, it is not feasible to use it in this scenario. In the second scenario, the training data set is used as it is, however, this time the test data set is extended and enriched by operations, such as translation, rotation and mirroring. As a result, the collected ten images for test are extended to 60. Since the testing has to be done in real time, this number is far less than the number of additional samples generated for training in the first scenario. Sample generated test images are shown in Fig. 8(a). The performance curve for this experiment is shown in Fig. 8(b). Only the KNN classifier is used for this experiment due to its ease of use in decision fusion among different test samples. Similar to the case in the first scenario, the performance improves when using the enriched test data set.

Conclusion

The developed mobile game application is a proof of concept for a successful application of computer vision and pattern recognition technologies to convert a smartphone to a tool that enables human-human interaction in an entertaining way. The game allows users to play paintball or laser tag style games with their smartphones. Face detection and recognition technologies have been employed to detect and identify the players in the game. The implemented practical and realtime face recognition system is benchmarked within the scope of the application. When using LBP features with ten players in the game, around 90% performance is obtained. SVM and KNN provided similar results. The application is found to be entertaining by the users. It also inspires users about how these technologies can be used in the future. However, we experienced a problem about the usability of the system. It was observed that players keep their smartphones at the face level in order to see the screen, which causes occlusion on the face. To solve this problem, we plan to work on occlusion robust face detection and recognition. In addition, we also plan to design a physical mechanism that can be used in the game to plug the smartphone to, so that the players can have a sufficient distance from their smartphones, while playing.

Fig. 1 .

 1 Fig. 1. Multiplayer Mobile Game Application Flow Diagram

Fig. 2 .

 2 Fig. 2. Mobile Application Flow Diagram

Fig. 3 .

 3 Fig. 3. Sample Screenshots from the Mobile Application

Fig. 4 .Fig. 5 .

 45 Fig. 4. Face Recognition Process

Fig. 6 .

 6 Fig. 6. Samples from (a) the Training Data Set, (b) the Testing Data Set

Fig. 7 .

 7 Fig. 7. (a) Results when ten images are used for training and test stages, (b) results using extended training data set

Fig. 8 .

 8 Fig. 8. (a) sample generated test images, (b) results using extended testing data set

A demo video of the system can be found at http://web.itu.edu.tr/ekenel/facetag.avi

Acknowledgement

This work was supported by the Avea Labs Research Grant, TUBITAK project no. 113E121; and a Marie Curie FP7 Integration Grant within the 7th EU Framework Programme.


Esperance Mwamikazi
email: esperance.mwamikazi@umoncton.ca

Philippe Fournier-Viger
email: philippe.fournier-viger@umoncton.ca

Chadia Moghrabi
email: chadia.moghrabi@umoncton.ca

Robert Baudouin
email: robert.baudouin@umoncton.ca

A Dynamic Questionnaire to Further Reduce Questions in Learning Style Assessment

Keywords: dynamic adaptive questionnaire, classification, learning styles, Myers-Briggs Type Indicator, psychological types

The detection of learning styles in adaptive systems provides a way to better assist learners during their training. A popular approach is to fill out a long questionnaire then ask a specialist to analyze the answers and identify learning styles or types accordingly. Since this process is very time-consuming, a number of automatic approaches have been proposed to reduce the number of questions asked. However the length of questionnaire remains an important concern. In this paper, we address this issue by proposing T-PREDICT, a novel dynamic electronic questionnaire for psychological type prediction that further reduces the number of questions. Experimental results show that it can eliminate 81% more questions of the Myers-Briggs Type indicators questionnaire than three state-of-the-art approaches, while predicting learning styles without increasing the error rate.

Introduction

Knowing the learning style of learners is important to ensure enhanced and personalized interactions with teachers. Various studies established that presenting information in a manner that is adapted to the student's learning style facilitates learning (e.g. [START_REF] Felder | Understanding student differences[END_REF][START_REF] Graf | Adaptivity in Learning Management Systems Focusing on Learning Styles[END_REF]).

Two main approaches are used to carry out learning style or type assessment: the first approach consists of examining the learner's interaction with the system [START_REF] Felder | Understanding student differences[END_REF][START_REF] Ortigosa | AH-questionnaire: An adaptive hierarchical questionnaire for learning styles[END_REF]. The second approach entails using a standard questionnaire that is filled out by an individual before a specialist examines the responses and establishes the corresponding learning style.

Even though these approaches can correctly identify the learning type of a learner, they still suffer from various shortcomings. Using the first approach entails that an initial random learning style is assigned to the learner, implying that if the initial guess is wrong, the system will offer wrong interactions with the learner and that could have negative impact on learning. In addition, the interaction will persist until enough data is stored so that ideal learning style can be established [START_REF] Ortigosa | AH-questionnaire: An adaptive hierarchical questionnaire for learning styles[END_REF]. The second approach has various limitations as well. First, the questionnaires tend to be long and time consuming. For instance, Myers-Briggs Type indicator questionnaire has more than 90 questions. Second, the fact that questionnaires are long implies that the person filling the questionnaire might be demotivated to reply to the questions with enough attention [START_REF] Ortigosa | AH-questionnaire: An adaptive hierarchical questionnaire for learning styles[END_REF] which might lead to abandoning the test, skipping questions, answering falsely, etc. Consequently, an incorrect learning style might be adopted [START_REF] García | Evaluating Bayesian Networks' Precision for Detecting Students' Learning Styles[END_REF]. The third limitation of this approach is that in order to assign a learning style, there is a need for a specialist to analyze the learner's answers to questions.

To address these limitations, several approaches [START_REF] Mwamikazi | An Adaptive Questionnaire for Automatic Identification of Learning Styles[END_REF][START_REF] Nokelainen | Bayesian Modeling Approach to Implement an Adaptive Questionnaire[END_REF][START_REF] Barhoumi | Simplification du questionnaire MBTI par apprentissage automatique en vue de faciliter l'adaptabilité des logiciels de formation en ligne[END_REF] have been proposed to automatically reduce the number of questions asked to learners in an effort to identify their learning styles or psychological types. For example, Q-SELECT [START_REF] Mwamikazi | An Adaptive Questionnaire for Automatic Identification of Learning Styles[END_REF] is an adaptive electronic questionnaire that uses association rules to predict part of the answers and hence shorten the questionnaire by up to 30%. However, even when applying these approaches, the length of questionnaires remains a concern. Therefore, an important research question is "could a new method be designed to further reduce the number of questions asked?"

In this paper, we answer this question positively by proposing a dynamic electronic questionnaire T-PREDICT that further reduces the number of questions and automatically recognizes the psychological types with high accuracy.

The rest of the paper is organized as follows. The Myers-Briggs Type Indicator model is presented in section 2. Section 3 discusses related work on adaptive questionnaires. Section 4 and 5 respectively present the proposed electronic questionnaire and the experimental results. Finally, section 6 draws the conclusions.

Myers-Briggs Type Indicator (MBTI)

The Myers-Briggs Type Indicators (MBTI) is a well-known personality assessment model that has been used for over three decades. It uses Carl Jung's personality type theory to categorize individuals into four dimensions. Each dimension consists of two opposite preferences that depict inclinations and reveal dispositions in personal mindsets and techniques of making decisions [START_REF] Boyle | Myers-Briggs Type Indicator (MBTI): Some psychometric limitations[END_REF].

The E-I dimension (extraverted-introverted) centers its attention on establishing whether a person's approach is influenced by the outward environment such as other objects and individuals, or it is internally-oriented. The S-N dimension seeks to measure sensing-intuitiveness, illustrating the perception approach of an individual. As per the T-F dimension, thinking implies coherent reasoning and decision making processes while feelings influence personal, objective, and value oriented approach. The J-P dimension involves either a judging attitude and quick decision-making or perception that demonstrates more patience and information gathering prior to decision-making. Given these four dimensions, an individual's personality type is therefore designated by a four-letter code: While a number of the preferences may be dominant, others are likely to be secondary and can be easily subjected by other dimensions. For instance, the J-P dimension influences the two function preferences namely T or F versus S or N [START_REF] El Bachari | Design of an Adaptive E-Learning Model Based on Learner's Personality[END_REF].

Though the Myers-Briggs Type Indicator questionnaire has been used widely for a long time, it has some limitations. Its hypothetical and numerical imports are restricted to some extent by the use of dichotomous preference items [START_REF] Francis | The Relationship between MBTI and the Eysenck Personality Questionnaire among Adult Churchgoers[END_REF]. In addition, the MBTI questionnaire contains numerous questions, a number which may put off some users. As a result, they may choose to answer the questionnaire without paying much thought or attention to the choices thus raising doubts on the reliability of the assessment [START_REF] Pittenger | Measuring the MBTI and coming up short[END_REF]. Reducing the number of questions in a questionnaire has been a way to increase its efficiency [START_REF] Ortigosa | AH-questionnaire: An adaptive hierarchical questionnaire for learning styles[END_REF][START_REF] Mcsherry | Increasing dialogue efficiency in case-based reasoning without loss of solution quality[END_REF].

Related work

Some major challenges in building an e-learning system that can adapt itself to a learner is giving it the capability of changing the type, the order, or the number of questions presented to the learner [START_REF] Ortigosa | AH-questionnaire: An adaptive hierarchical questionnaire for learning styles[END_REF][START_REF] Mwamikazi | An Adaptive Questionnaire for Automatic Identification of Learning Styles[END_REF][START_REF] Abernethy | An optimization framework for adaptive questionnaire design[END_REF][START_REF] Chen | Personalized e-learning system using item response theory[END_REF]. For instance, McSherry [START_REF] Mcsherry | Increasing dialogue efficiency in case-based reasoning without loss of solution quality[END_REF] reports that reducing the number of questions asked by an informal case-based reasoning system minimized frustration, made learning easier and increased efficiency.

Various methods have been suggested in order to minimize the number of questions that are required to establish the learning style or preference of an individual. The AH questionnaire [START_REF] Ortigosa | AH-questionnaire: An adaptive hierarchical questionnaire for learning styles[END_REF] uses decision trees to reduce the questions and categorize the students as per the Felder-Silverman theory of learning styles. From an experiment that had 330 students, it was likely to anticipate the learning styles with precision of up to 95.71% while only asking four or five questions among the eleven questions that are applied in each dimension.

EDUFORM is a software used for adaptation and dynamic optimization of questionnaire propositions for online profiling of learners, which was proposed by Nokelainen et al. [START_REF] Nokelainen | Bayesian Modeling Approach to Implement an Adaptive Questionnaire[END_REF]. The tool, that uses Bayesian modeling as well as abductive reasoning, minimized the questionnaire items by 30% to 50% while retaining an error rate of 10% to 15%. These results showed that shortening questionnaires does not detrimentally influence the correct categorization of individuals.

In previous work [START_REF] Barhoumi | Simplification du questionnaire MBTI par apprentissage automatique en vue de faciliter l'adaptabilité des logiciels de formation en ligne[END_REF], two methods based on back-propagation neural networks and decision trees were proposed to predict learning types and reduce the number of questions asked in the MBTI questionnaire. We refer to these methods as Q-NN and Q-DT, respectively. The general experimental method tries to identify questions that are less influential in determining the learning types. These questions are then eliminated from the questionnaire and the learning types are predicted. This process is repeated until a maximum error rate of 12% is achieved. In an experimental study, that had 1,931 filled questionnaires, the Q-NN method clearly identified and eliminated 35% of the questions while establishing the learning preferences with an error rate of 9.4%. On the other hand, Q-DT eliminated 30% of the questions with an error rate of 14%.

Recently, we presented an alternative approach to reduce the number of questions in MBTI questionnaire [START_REF] Mwamikazi | An Adaptive Questionnaire for Automatic Identification of Learning Styles[END_REF]. This approach (Q-SELECT) comprises three modules: [START_REF] Felder | Understanding student differences[END_REF] an answer prediction algorithm, (2) a dynamic question selection algorithm and (3) an algorithm to accurately predict a person's learning style based on both user supplied and predicted answers. The two first modules rely on association rules between answers from previous users. The third module predicts learning types using a neural network. An experimental study with the same 1,931 MBTI filled questionnaires has shown that Q-SELECT reduces the number of questions asked by a median of 30% with an average error rate of 12.1%. The main advantage of Q-SELECT compared to Q-NN and Q-DT is its adaptability, i.e. the ability to ask a variable number of questions and to reorder them depending on the user answers, thus providing a personalized questionnaire to each user.

Reducing the MBTI questionnaire by up to 35% still leaves around 60 questions. This paper presents T-PREDICT, a new dynamic approach to further minimize the number of questions in MBTI questionnaires while predicting learning types with a comparable error rate.

Reducing the number of questions might bring to mind algorithms for dimensionality reduction such as PCA, ICA [START_REF] Jolliffe | Principal Component Analysis 2nd ed[END_REF]. However, these methods would have reduced the same number of questions for all users as in Q-NN. Our choice was to continue our experiments with a dynamic user-adaptive approach. This choice was later confirmed by our results from T-PREDICT. We were sometimes able to predict the learning type with as little as six questions out of 92 but with a median of 11 questions.

Another popular theory that deals with questions and answers is Item Response Theory (IRT) [START_REF] Demars | Item response theory[END_REF]. It has been applied in education and psychology to assess an underlying ability or trait using a questionnaire. To apply IRT, users answers need to be collected and analyzed. Using a technique such as factor analysis, a model (e.g. logistic function) is created for each question to represent the amount of information provided by each answer about the latent trait. The quality of the generated models varies depending on the data available. When a model does not fit well a question, this latter is typically removed, replaced or rewritten [START_REF] Weinhardt | An item response theory and factor analytic examination of two prominent maximizing tendency scales[END_REF]. Applying IRT can be very time-consuming, since for each modification, more data may need to be collected to update models and human intervention is required to analyze questions and tweak models. Furthermore, IRT does not provide means for user adaptability. In contrast, our proposal is automatic and user-adaptive in all steps: selecting important questions, reordering them, and later predicting learning types.

4

The Electronic Questionnaire

The proposed electronic questionnaire T-PREDICT comprises two major components: a question sorting algorithm and a learning type prediction algorithm. The philosophy behind this division is that some questions might be more important than others i.e. their answers could easily classify the learners in one or the other personality type. Hence, the sorting algorithm sorts the questions by their ability to discriminate between classes, while the prediction algorithm uses them in this preferential order. An additional module is developed to dynamically select parameters needed for the prediction algorithm.

4.1

The question sorting algorithm

The MBTI questionnaire evaluates each dimension (EI, SN, TF, and JP) by a distinct subset of questions. Thus, we split the questionnaire into the four sets of questions representing these dimensions. Each dimension consists of two opposite preferences, hence the need to classify individuals into one of these two preferences (classes). Since our goal is to reduce the number of questions asked, it is crucial to recognize which questions are more important for identifying the preferences. We define the importance of a question as its ability to discriminate between the two classes. Let q be a question and A(q) = {a 1… a m } be the set of possible answers to this question. Let T be a training set of filled questionnaires such that each questionnaire belongs to one of the two classes. For any answer a i (1 ≤ i ≤ m), let N 1 (a i ) and N 2 (a i ) respectively be the number of questionnaires in T containing the answer a i that belong to the first class and the second class. The discriminative power of the answer a i is denoted as DA(a i ) and defined as

N 1 (a i ) / N 2 (a i ) if N 1 (a i ) > N 2 (a i ) or N 2 (a i ) / N 1 (a i ), otherwise.
Intuitively, it represents how many times one class is larger than the other for individuals having answered a i , and thus how this answer helps to discriminate between the two classes. The discriminative power of a question q is denoted as DQ(q) and defined as DQ(q) = ∑ / |T|. The proposed adaptive questionnaire initially calculates the discriminative power of each question in the training set T and sorts them accordingly (see Fig. 1 for the pseudocode). The next subsection describes how the adaptive questionnaire asks the questions by decreasing order of discriminative power and predicts the preference (class) of each individual using the provided answers.

QUESTION_SORT (a training set T, a list of questions Q, a set of possible answers A) 1. FOR each question q Q 2.

FOR each possible answer a i A(q) 3.

SCAN T to calculate N 1 (a i ) and N 2 (a i ). [START_REF] García | Evaluating Bayesian Networks' Precision for Detecting Students' Learning Styles[END_REF].

IF N 1 (a i ) > N 2 (a i ) THEN DA(a i ) := N 1 (a i ) / N 2 (a i ). 5.
ELSE DA(a i ) := N 2 (a i ) / N 1 (a i ). 6.

END FOR

7.

DQ(q) = ∑ / |T|. 8. END FOR 9. SORT Q such that q a appears before q b if DQ(q a ) > DQ(q b ), for all questions q a ,q b Q. 10. RETURN Q.

Fig. 1. The question sorting algorithm

4.2

The learning style prediction algorithm

The learning style prediction algorithm (see Fig. 2) automatically identifies the preference of a user in a given dimension based on supplied answers and their similarity to answers from previous users. The algorithm takes as input a training set of filled questionnaires T, the list of questions Q for the dimension, sorted by their discriminative power (see section 4.1), a maximum number of questions to be asked maxQues-tions (by default set to |Q|), and two additional parameters minMargin and minQ that will be defined later.

PREDICT (a training set T, a list of questions Q sorted by their discriminative power, a maximum number of questions to be asked maxQuestions, a minimum margin between classes minMargin, a minimum number of questionnaires to be matched minQ) 1. U := ∅.

2. FOR each question q i Q until maxQuestions have been asked 3.

ASK q i to the user and store the provided answer in U.

4.

S 1 := S 2 := 0. 5.

FOR each questionnaire X T such that U X 6.

IF X is tagged as class

:= Y 1 + C(X, U). ELSE Y 2 := Y 2 + C(X, U). 13. IF Y 1 > Y 2
THEN RETURN "class 1". ELSE RETURN "class 2".

Fig. 2. The learning type prediction algorithm

The algorithm first initializes a set U as empty to store the user answers. Then, a loop is performed to ask the questions to the user in decreasing order of their discriminative power. Each provided answer is immediately added to U. Then, the algorithm attempts to make a prediction by scanning through the set T to count how many users have the same answers as the current user and belong to class 1 or belong to class 2, i.e. S 1 = |{X | X T U X X is tagged as class 1}| and S 2 = |{X | X T U X X is tagged as class 2}|. Two criteria must be met to make this prediction. First, the number of filled questionnaires, from the training set T, matching the answers of the current user should be higher or equal to a pre-set threshold (minQ), i.e. S 1 + S 2 ≥ minQ. Second, there should be a large enough difference between S 1 and S 2 in order to make an accurate prediction. This difference is defined as |S 1 -S 2 | ≥ minMargin, where minMargin is also a pre-set threshold. If both conditions are met, a prediction is made. The prediction is class 1 if S 1 > S 2 , and class 2 otherwise. If no prediction can be made, the algorithm continues with other questions, one at a time, until it is able to make a prediction.

After maxQuestions questions have been exhausted and no prediction was possible with the exact matching, a prediction is made by considering an approximate match between the present user answers and questionnaires from the training set T. A questionnaire X T approximately matches U if it shares at least |U|/2 answers with it. The number of answers common to X and U is denoted as C(X, U) and defined as C(X, U) = |X U|. Let Y 1 and Y 2 be the sets of all questionnaires from T that approximately match U and are tagged as class 1 or class 2. The prediction is class 1 if Y 1 Y 2 . Otherwise, it is class 2.

The parameters selection algorithm

As mentioned earlier, the prediction algorithm needs two preselected parameters minMargin and minQ. These parameters are not global. They are dynamically selected as per number of questions asked. The PARAMETERS_SELECT algorithm (see Fig. 3) attempts to select the best values for these parameters exhaustively by simulating predictions and calculating the corresponding precisions on a test set of filled questionnaires TS by using a training set T.

PARAMETERS_SELECT (a training set T, a test set TS, a list of questions Q= {q 1 , q 2 ,…q n } sorted by their discriminative power, a target precision TargetPrecision, and the two upper bounds maxMargin and maxQ) 1. GlobalPrecision :=0. 2. RequiredPrecision := TargetPrecision 3. P := ∅. 4. RemainingQuestionnaires := TS. 5. FOR each q k Q and k := 1, 2…n 6. bestScore := 0. 7.

bestParameters := (0, 0, 0). 8.

bestResult := (0, 0, 0). 9.

FOR each combination of values i, j, α such that i :=1, 2… maxQ and j := 1, 5,… maxMargin and α := 0.5, 0.6 … 0.9 10.

Predict a class for each questionnaire X RemainingQuestionnaires using the first k questions and the training set T. Set parameters minQ := i, minMargin := j for the k th question, while keeping the best previously found parameters for questions 1 to k-1. Let predicted k be the set of questionnaires where a prediction was performed and precision k be the precision. 11.

score := precision k α + |predicted k | (1-α). 12.

IF score > bestScore AND precision k ≥ RequiredPrecision THEN 13.

bestParameters := (k, i, j).

14.

bestScore := score. 15.

bestResult := (k, predicted k , precision k ). [START_REF] Demars | Item response theory[END_REF].

END IF 17.

END FOR 18.

P: = P {bestParameters}. 19.

GlobalPrecision := GlobalPrecision +|bestResult.predicted| .precision 20.

RemainingQuestionnaires := RemainingQuestionnaires \ bestResult.predicted.

21.

RequiredPrecision := (|TS| TargetPrecision -GlobalPrecision ) / RemainingQuestionnaires 22. END FOR 23. RETURN P.

Fig. 3. The parameter selection algorithm

The algorithm proceeds by considering each question from Q in the order that they will be asked by the PREDICT algorithm (in descending order of discriminative power). For every question q k considered, all combinations of values i and j for parameters minQ and minMargin in their respective intervals [1, maxQ] and [START_REF] Felder | Understanding student differences[END_REF]maxMargin] are tested. For each combination, a certain number of predictions NbPredictions k are obtained with a corresponding precision precision k . The combination of values i and j that is considered the best is the one maximising the function score (i,j) = α precision k + NbPredictions k (1-α), where α is a constant varied in the [0.5, 0.9] interval. The weight α is used to calibrate the relative importance of the precision and the number of predictions on the selection of parameter values.

Furthermore, an additional constraint is that the best combination needs to have a precision higher than a moving threshold RequiredPrecision. For the first question, this threshold is equal to a pre-set minimum precision TargetPrecision. For any subsequent question q k , the required precision is recalculated to take into account the precisions obtained with previous questions (called GlobalPrecision k ). The reason is that if a high precision is obtained for the previous questions, it is possible to accept a lower precision for the next questions, while maintaining a global precision above TargetPrecision. The global precision is calculated by weighting the previous precisions with their corresponding number of predictions. Formally, the global precision is defined as: GlobalPrecision k = ∑ . The required precision for the k th question is calculated as:

RequiredPrecision k = (|TS| Target Precision -GlobalPrecision k ) / |RemainingQ|
, where RemainingQ is the number of unpredicted questionnaires. When the algorithm terminates, it returns a list P of triples of the form (k, y, z) indicating that parameters minMargin and minQ should be respectively set to values y and z for the k th question to establish a prediction with a global precision not below TargetPrecision.

Experimental Results

Two experiments were performed. The first one compares the performance of the learning type prediction algorithm T-PREDICT with other methods. The second one assesses the influence of question sorting and limiting the number of questions in T-PREDICT. A database of 1,931 MBTI filled out questionnaires were supplied for experimentation by Prof. Robert Baudouin, an expert of the MBTI technique at Université de Moncton. The number of samples used for training was 1,000 while 931 were used for testing. The proposed dynamic questionnaire T-PREDICT is implemented using Java. The goal of the experiments was to ask as few questions as possible while automatically identifying learning types with a minimum precision of 88 %, i.e. a maximum error rate of 12%. This is the same error rate that was used in Q-SELECT [START_REF] Mwamikazi | An Adaptive Questionnaire for Automatic Identification of Learning Styles[END_REF], thus allowing a more precise comparison base. Parameters used were automatically selected by the parameters selection algorithm (see section 4.4). It varied minQ and minMargin, for each question, in the [0.01, 0.15] and [0.1, 0.9] intervals respectively and returned their optimal values to be used by the type prediction algorithm. These predictions were done for each of the four MBTI dimensions.

5.1

Comparison with other methods

The first experiment compared the median number of questions asked in each dimension with results obtained by three specialized methods that have been specifically developed to reduce the number of questions for MBTI. These methods are based on back-propagation neural networks (Q-NN) [START_REF] Barhoumi | Simplification du questionnaire MBTI par apprentissage automatique en vue de faciliter l'adaptabilité des logiciels de formation en ligne[END_REF], decision trees (Q-DT) [START_REF] Barhoumi | Simplification du questionnaire MBTI par apprentissage automatique en vue de faciliter l'adaptabilité des logiciels de formation en ligne[END_REF], and association rules (Q-SELECT) [START_REF] Mwamikazi | An Adaptive Questionnaire for Automatic Identification of Learning Styles[END_REF]. Table 1 shows the number of questions asked per dimension, as compared to the original higher number, and the corresponding error rates. Note that the T-PREDICT line shows that the number of questions asked for EI, SN, TF and JP dimensions were 2 out of 21 questions, 4 out of 25 questions, 2 out of 23 questions, and 3 out of 23 questions respectively. The corresponding error rates obtained were 10.7% for EI, 13% for SN, 10.3% for TF and 13.1% for JP. Thus, maintaining a weighted average error rate of 12.1% for the four dimensions, which is practically the pre-set error rate of 12% mentioned earlier. All dimensions for the four compared methods maintained error rates below 13.1% except the TF and JP dimensions for the Q-DT, which respectively had error rates of 16.3% and 13.7%. Overall, T-PREDICT asked a median of only 11 questions, out of 92 questions, to predict learning types with an average error rate of 12.1%, while Q-SELECT, Q-NN, and Q-DT asked 62, 60, and 64 questions to achieve error rates of 11.4%, 9.4%, and 14% respectively. In sum, the number of questions was greatly reduced by T-PREDICT while maintaining a very comparable error rate. Since the above table presents median numbers of questions asked, one might wonder how the actual numbers of questions asked are distributed. For example, Table 2 shows the distribution of questions asked for the SN dimension. Note that 34% of individual learning types were predicted using just one question, a cumulative 76% were predicted using four questions, and the remaining 24% were predicted using more questions. All 100% of the predictions were possible with at most thirteen questions. However, the error rate increases to 25% when thirteen questions are used. This is due to the fact that after the maximum number of questions (maxQuestions) has been exhausted, predictions are made by approximate matching. Note that some questions, such as the second question in Table 2, did not generate any additional predictions. These are the questions where the two established criteria necessary to make a prediction, as set by the prediction algorithm, were not met.

Influence of sorting and limiting number of questions

The following experiment assesses the influence of two optimizing strategies on error rate and median number of questions asked, these are (1) sorting questions by discriminative power and (2) limiting the maximum number of questions asked. T-PREDICT results were compared with a modified version that does not sort questions (UT-PREDICT). Moreover, the maximum number of questions asked (MaxQuestions) was varied from one to all questions. Table 3 shows the obtained results for the SN dimension. Results for other dimensions were similar, although not shown due to space limitation. It can be observed that the median number of questions is higher and that the error rate is much higher when the questions are unsorted. For example, Table 3 shows that T-PREDICT had an error rate of 13% using a median of 4 questions, while UT-PREDICT used 5 questions with an error rate of 17.84%, when MaxQuestions = 13. It can also be noticed that limiting the maximum number of questions to 13 gave the lowest error rate (13 %).

Conclusion

Filling questionnaires for learning style assessment is a very time-consuming task, which might lead to abandoning the test, skipping questions, answering falsely, etc.

To address this issue, various approaches have been proposed to reduce the size of questionnaires. In this paper, we have presented a novel dynamic electronic questionnaire T-PREDICT to further reduce the number of questions needed for learning type identification. It comprises three modules: a question sorting algorithm, a prediction algorithm and an automatic parameter selection algorithm. Experimental results with 1,931 filled questionnaires for the Myers Briggs Type Indicators show that our novel approach asked a median of only 11 out of 92 questions to predict learning types, with an average error rate of 12.1%, while previous approaches Q-SELECT [START_REF] Mwamikazi | An Adaptive Questionnaire for Automatic Identification of Learning Styles[END_REF], Q-NN and Q-DT [START_REF] Barhoumi | Simplification du questionnaire MBTI par apprentissage automatique en vue de faciliter l'adaptabilité des logiciels de formation en ligne[END_REF] asked between 60 and 64 questions to achieve error rates between 9.4% and 14%. Another defining characteristic of T-PREDICT is its ability to ask a variable number of questions, thus providing an automatic personalized questionnaire to each user, like Q-SELECT but unlike Q-NN, Q-DT, PCA and IRT that apply the same reduction to all users.

  {ISTJ, ISFJ, INFJ, INTJ, ISTP, ISFP, INFP, INTP, ESTP, ESFP, ENFP, ENTP, ESTJ, ESFJ, ENFJ, ENTJ}.

  1 THEN S 1 := S 1 +1. ELSE S 2 := S 2 +1.

	7.	IF S 1 + S 2 ≥ minQ AND |S 1 -S 2 | ≥ minMargin THEN
	8.	IF S 1 > S 2 THEN RETURN "class 1". ELSE RETURN "class 2".
	9. END FOR
	10. Y 1 := Y 2 := 0.
	11. FOR each questionnaire X T such that C(X, U) ≥ |U|/2
	12.

IF X is tagged as class 1 THEN Y 1

Table 1 .

 1 Median number of questions asked by T-PREDICT per dimension, compared to other methods.

Table 2 .

 2 Distribution of questions asked by T-PREDICT for the SN dimension

		EI	SN	TF	JP	Total
		(21 quest.)	(25 quest.)	(23 quest.)	(23 quest.)	(92 quest.)
	T-PREDICT	2	4	2	3	11
	Avg. error rate	10.7%	13%	10.3%	13.1%	12.1%
	Q-SELECT	14	16	14	18	62
	Avg. error rate	9.9%	11.8%	12%	11.7%	11.4%
	Q-NN	14	16	16	14	60
	Avg. error rate	8.3%	10.9%	9.3%	8.9%	9.4%
	Q-DT	14	17	17	16	64
	Avg. error rate	12.8%	13.1%	16.3%	13.7%	14%

Table 3 .

 3 Influence of MaxQuestions and sorting questions by discriminative power on error rate and median number of questions asked

	Parameter	Median number	Average	Median number	Average
	MaxQuestions	of questions	error rate	of questions	error rate
		(T-PREDICT)	(T-PREDICT)	(UT-PREDICT)	(UT-PREDICT)
	1	1	32,8%	1	32,8%
	2	2	32,8%	2	32,8%
	3	3	18,1%	3	28,0%
	4	4	18,1%	4	32,3%
	5	4	15,4%	5	20,8%
	6	4	18,4%	5	22,6 %
	7	4	16,3%	5	20,0%
	8	4	14,7%	5	21,4%
	9	4	14,5%	5	17,9%
	10	4	15,0%	5	19,2%
	11	4	14,0 %	5	17,9%
	12	4	13,7%	5	19,2%
	13	4	13,0%	5	17,8%
	14	4	13.9%	5	19.6%
	25	4	15.1%	5	18.3%


Alexey Potapov

Vita Batishcheva

Maxim Peterson
email: maxim.peterson@gmail.com

Limited Generalization Capabilities of Autoencoders with Logistic Regression on Training Sets of Small Sizes

Keywords: autoencoders, logistic regression, overlearning, generalization, image categorization

Deep learning is promising approach to extract useful nonlinear representations of data. However, it is usually applied with large training sets, which are not always available in practical tasks. In this paper, we consider stacked autoencoders with logistic regression as the classification layer and study their usefulness for the task of image categorization depending on the size of training sets. Hand-crafted image descriptors are proposed and used for training autoencoders in addition to pixel-level features. New multi-column architecture for autoencoders is also proposed. Conducted experiments showed that useful nonlinear features can be learnt by (stacked) autoencoders only using large training sets, but they can yield positive results due to redundancy reduction also on small training sets. Practically useful results (9.1% error rate for 6 classes) were achieved only using hand-crafted features on the training set containing 4800 images.

Introduction

Classes of patterns in pattern recognition are rarely linearly separable, and nonlinear methods should be used. Classical nonlinear methods of pattern recognition can be treated as linear methods operating in some extended feature space. However, these methods use fixed sets of nonlinear transformations to map initial features into new space, and these transformations can be inappropriate to separate classes in a specific task. Thus, learning appropriate nonlinear features (or data representations in general) is the central problem in pattern recognition and particularly in its application to computer vision (e.g. [START_REF] He | Unsupervised Feature Learning by Deep Sparse Coding[END_REF]). One modern approach to learn such features is deep learning.

Deep learning exploits the fact that adding extra hidden layers in a multi-layer classifier helps to learn more complex features and to improve their representational power [START_REF] Le Roux | Representational Power of Restricted Boltzmann Machines and Deep Belief Networks[END_REF][START_REF] Gregor | Deep AutoRegressive Networks[END_REF]. The key problem here is to train such classifiers. Earlier, training of shallow feed-forward networks with the back-propagation algorithm yielded better results than training deep networks with it, since bottom layers are difficult to train because of exponentially quick gradient vanishing, so these layers usually correspond to random (not useful or even harmful) nonlinear feature mappings. Successful training of such networks was achieved [START_REF] Hinton | A Fast Learning Algorithm for Deep Belief Nets[END_REF][START_REF] Bengio | Greedy Layer-Wise Training of Deep Networks[END_REF][START_REF] Ranzato | Efficient Learning of Sparse Representations with an Energy-Based Model[END_REF] with the help of consequent unsupervised pre-training of each hidden layer, and use of supervised training afterwards.

However, successful supervised training of multi-layer perceptrons (resulting in a very low 0.35% error rate on the MNIST benchmark) was also achieved recently [START_REF] Ciresan | Deep Big Simple Neural Nets Excel on Handwritten Digit Recognition[END_REF]. The way of achieving this is remarkable. It consists in intensive training of perceptrons using relevantly (with affine and elastic image deformations) transformed patterns. Even overlearning is avoided in spite of extremely large number of neurons (free parameters), because "the continual deformations of the training set generate a virtually infinite supply of training examples" [START_REF] Ciresan | Deep Big Simple Neural Nets Excel on Handwritten Digit Recognition[END_REF]. One can also see [START_REF] Lecun | MNIST handwritten digit database[END_REF] that many good results for MNIST are obtained using similar deformations of training patterns and convolutional nets, which additionally exploit shift invariance. It is obvious, that if one substitutes non-image patterns for training such classifiers, their results will be rather poor. Thus, this is not an appropriate way to learn (problem-specific) invariant features, which are not known a priori.

Necessity of extremely large (with account for deformations of training patterns) training sets indicates that deep networks don't really generalize, but only approximate invariants. Moreover, classifiers with many free parameters appear to be better than with fewer parameters. It can be compared with approximation of exponent with polynomials (or some other basis functions). Very many points should be used to get precise approximation with very complex model, but only few points are enough for exact generalization (if one has means to represent and find it). At the same time, humans have capabilities to learn complex invariant features from few examples [START_REF] Tenenbaum | How to Grow a Mind: Statistics, Structure, and Abstraction[END_REF]. Thus, interesting question consists in learning capabilities of deep networks on small training sets, that is, whether they are able to learn useful representations from such sets.

Here we analyze this question on example of (stacked) autoencoders with logistic regression as the classification layer applied to the task of image categorization. Pixellevel and hand-crafted features are used for experiments.

Autoencoders

We selected stacked autoencoders as the unsupervised layers with logistic regression as the classification layer. Single autoencoder has input, hidden, and output (reconstruction) layers. The input layer accepts a vector

N ] 1 , 0 [ ∈ x of dimension N, which is transformed to activities of neurons of the hidden layer ) ( b Wx y + = s , d ] 1 , 0 [ ∈ y
, corresponding to new features (hidden representation), where W is a d×N matrix of connection weights, b is a bias vector, and s is the activation (sigmoid) function. Activities of neurons of the last layer are calculated similarly as

) ( b y W z ′ + ′ = s , N ] 1 , 0 [ ∈ z
. Autoencoders differ from other feed-forward networks in that they are trained to minimize difference between x and z (for patterns from a training set), that is W' is the matrix of the reverse mapping. W' is frequently taken as W T . One can calculate gradient of the reconstruction error relative to connection weights and bias vectors and to train the autoencoder using stochastic gradient descent.

In the case of stacked autoencoders, each autoencoder on the next level takes outputs of the hidden (not reconstruction) layer of the previous autoencoder as its input performing further nonlinear transformation of constructed latent representation of the previous level. Each next autoencoder is trained after training its preceding autoencoder. Outputs from the hidden layer of the last autoencoder are passed to the supervised feed-forward network.

Multinomial logistic regression computes probabilities of a pattern to belong to different classes based on softmax applied to linear combinations of features.

∑ = ′ ′ ′ + + = = C c c T c c T c b b c y p 1 ) exp( ) exp( ) , | ( x w x w W x , ( 1
)
where x is the input vector, c is the class index, C is the total number of classes, W is the weight matrix composed by C vectors w c , b c are biases. Parameters of the classifier are learnt using stochastic gradient descent minimizing negative loglikelihood.

One common modification is denoising autoencoders [START_REF] Vincent | Extracting and composing Robust Features with Denoising Autoencoders[END_REF], in which reconstruction during training is calculated using patterns with introduced noise, but reconstruction errors are calculated relative to initial patterns without this artificial noise. Thus, a denoising autoencoder learns to reconstruct a clean input from a corrupted one. This is a way to deform input patterns efficiently increasing the training set size, but in the least problem-specific fashion.

We introduce some additional modifications into denoising stacked autoencoders. One modification consists in that only the last (regression) layer is trained in the supervised fashion. This helps to check usefulness of unsupervised features.

The second modification (which is to be compared with the basic version) consists in constructing multi-column autoencoders. Multi-column deep neural networks were already used (e.g. [START_REF] Cireşan | Multi-Column Deep Neural Network for Traffic Sign Classification[END_REF]), but each column in such networks is usually trained as a separate deep network, and predictions of all columns are then averaged. In our modification, the number of columns corresponds to the number of classes. Each column is trained for its own class to produce some non-linear features. These features are then gathered and passed as the input to the logistic regression layer.

Image Features

We took the task of image categorization for investigating behavior of autoencoders. In this task, images can vary considerably, and special hand-crafted features are usually used, that doesn't eliminate necessity to learn non-linear features, especially when different hand-crafted features are combined.

We used three types of image features for image description: color histograms, edge direction histogram (EDH) [START_REF] Vailaya | On Image Classification: City Images vs. Landscapes[END_REF] and Haralick's textural features based on graylevel co-occurrence matrices (GLCM) [START_REF] Haralick | Textural Features for Image Classification[END_REF].

Color features are built as concatenation of three 1D histograms calculated for LAB components. Histogram for each component contains N c =32 bins, so the total size of the color vector is 3N c =96.

In order to build an edge direction histogram we apply Deriche filtration [START_REF] Deriche | Using Canny's Criteria to Derive a Recursively Implemented Optimal Edge Detector[END_REF] at the first step. Then we get an assessment of orientation distribution by computing the direction of gradient vector at local maximums of gradient magnitude. Initial range of edge orientation angles [0°, 360°) is quantized to N q bins (we use 72 bins). The last bin in histogram represents the amount of image pixels that don't belong to edges. Finally, because of possible difference in image sizes, all bins are normalized by corresponding values [START_REF] Vailaya | On Image Classification: City Images vs. Landscapes[END_REF] , /

) ( ) ( ]; 1 , 0 [ , / ) ( ) ( p q q q edge N N N N i N i i EDH EDH EDH EDH = - ∈ = , (2)
where ) (i EDH -value in bin i of the histogram, N edge is total amount of edge points in the image, N p is total number of pixels.

Unfortunately EDH gives no information about location of contours on the image plane, so we tried to compensate this by splitting image into K parts (K=3) and computing the histogram for each of them. Thus, the EDH descriptor size is

K(N q +1)=219.
The last part of our image descriptor is computed from normalized GLCM. Cooccurrence matrices represent texture properties, but they are inconvenient for matching two textures, because of big number of elements, thus we used five features of normalized GLCM C d , proposed in [START_REF] Haralick | Textural Features for Image Classification[END_REF]:

• angular second moment:

( )

∑∑ i j j i, 2 d C ;
• entropy:

( ) ( ) ∑∑ - i j j i j i , log , d d C C ; • contrast: ( ) ( ) ∑∑ - i j j i j i , 2 d C ;
• inverse difference moment:

( ) ∑∑ - + i j j i j i 1 , d C ;
• correlation:

( )(
) ( )

j i i j j i j i j i σ σ µ - µ - ∑∑ , d C
, where µ i , µ j , σ i , σ j are the means and standard deviations of rows and columns of C d , d is a displacements vector, for which co-occurrence matrix is computed (we used D options of d for each image).

In order to consider color information, initial RGB images were transformed to HSV representation, so GLCM was computed for hue, saturation and value components, which in turn were preliminarily normalized to fit [0, 255] range. The size of modified GLCM descriptor (five GLCM based features for each of H, S and V component for 5 displacement vectors and 3 directions) appeared to be 5×3×5×3=225.

Thus, the image descriptor is constructed by concatenation of LAB histogram and modified EDH and GLCM parts. The total size of the image descriptor is 96+219+225=540. Reduced descriptor containing only two sets of features (96+219=315 features) was also considered for comparison.

Experiments

We conducted experiments with the neural networks composed of autoencoders and logistic regression layer described above. Logistic regression with and without autoencoders was tested separately using RGB values of pixels (on images rescaled to sizes of 64x64, 28x28, and 20x20) and hand-crafted descriptors as initial features on these two databases (three training sets). Results are presented in table 1.

It can be seen that hand-crafted features are not always very informative. Reduced image descriptors (315 features) gave worse results and enhanced descriptors (540 features) gave similar results in comparison with pixel-level features on DB1. However, for more complex image classes (DB2) these features yield better results, and results are greatly improved (in contrast to pixel-level features) with increase of the size of training sample. Of course, pixel-level features contain more information, but it is clearly seen that classes under consideration are not linearly separable in this feature space (but better linearly separable in the space of hand-crafted features), so one might expect that autoencoders would help to improve recognition rate for pixellevel features more than for hand-crafted features. However, conducted experiments showed that this assumption is not correct. The results are presented in table 2 It appeared to be very difficult to train autoencoders in the case of pixel-level features and small training sets. Too small or too large number of training epochs leaded to recognition of all patters as belonging to one same class. The best achieved error rates for DB1 and DB2 (using 10 training images per class) are 0.418 and 0.601 correspondingly with the use of multi-column autoencoder with one layer containing 1000 neurons (with 20x20x3=1200 inputs). That is, autoencoders failed to learn useful features from small amount of raw data, and they only didn't ruined initial features in fortunate cases.

Training multi-column one layer autoencoders on 800 per class DB2 images resulted in 0.353 error rate (one-column autoencoders gave 0.383 error rate), which is much better than the error rate of the logistic regression on pixel-level features, but is much worse than the error rate of the logistic regression on hand-crafted features. That is, some useful nonlinear features were learnt, but they were worse than both (reduced and enhanced) hand-crafted features. It should be noted that we also tested autoencoders on the MNIST database with 50000 training images, and they considerable reduced error rate relative to the logistic regression (from 8% to 2% only for two layers and can be reduced further) even without using convolution autoencoders or additional image transformations during training. This implies that more complex nonlinear features indeed can be learnt by autoencoders, but this result can be achieved in the case of very low variability of patterns and using large training sets.

Autoencoders trained using patterns represented by hand-crafted features appeared to be more useful (see table 2). The achieved error rate (~9%) for the scene classification task with 6 classes is rather high (e.g., in [START_REF] Vailaya | On Image Classification: City Images vs. Landscapes[END_REF], 6% error rate is achieved while distinguishing only two classes -city and landscape images, and 9% error rate is achieved for forest-mountain-sunset classification), so this result is interesting by itself.

However, it is also interesting to compare results in tables 1 and 2. In the case of hand-crafted features, larger improvement is achieved in the case of small training sets. In the case of pixel-level features, results are opposite implying that nature of this improvement may be different. Possibly, dimension reduction of linear features has stronger influence in the first case (and this is achievable on small training sets), while only construction of nonlinear features helps to increase recognition rate in the second case (and this requires large training sets).

Consider also results in fig. 3456. In all cases, error rates vary insignificantly for a wide range of hidden layer sizes. Best results are achieved on intermediate sizes, while the error rate rapidly increases for small hidden layers (in which too much information is lost), and gradually increases with the number of hidden neurons exceeding the number of features meaning that reduction of features redundancy is more useful than construction of complex nonlinear approximation on small training sets. It can also be seen that multi-column autoencoders outperform one-column autoencoders on more difficult image classes (DB2) and have similar performance on simpler classes. Although multi-column autoencoders contain much more hidden neurons, they don't suffer from overlearning more than one-column autoencoders (with the same number of neurons per column).

Finally, stacked autoencoders were tested. However, they yielded very small decrease of the error rate. For example, multi-column autoencoders with two layers (400, 300) helped to decrease the error rate from 0.329 to 0.324, and for one-column autoencoders the error rate decreased from 0.323 to 0.319 on DB1. One might expect that multi-level autoencoders will be more useful in the case of pixel-level features and larger training sets, but adding the second layer was unsuccessful resulting in increase of the error rate from 0.353 to 0.373. Possibly, larger training sets or training image deformations are necessary for multi-level autoencoders to learn useful complex features.

Conclusion

Stacked autoencoders with logistic regression layer for classifying images were considered. Original modification of multi-column autoencoders was proposed. Their performance was evaluated on pixel-level features and special hand-crafted image descriptors. These descriptors were composed of color, gradient and texture features. Tests were conducted on two data sets -cat breeds and image categories (city, indoor, forest, mountains, beach, flowers).

Training on hand-crafted features appeared to be much more successful than on pixel-level features (without introducing deformations of training images). Error rates of 9.1% and 35.3% were achieved on the training set containing 4800 images for the task of recognizing 6 image categories using hand-crafted and pixel-level features correspondingly. Thus, only hand-crafted features yielded practically usable results. Training autoencoders on small (10 patterns per class) samples using pixel-level features failed. In contrast, it stably improved (in comparison with single logistic regression) recognition rate in the case of hand-crafted features.

From the gathered experimental data one can conclude that useful nonlinear features can be learnt by (stacked) autoencoders only using large training sets, since these networks don't recover true underlying regularities in data, but approximate them by complex (multi-parametric) models. Most positive effect from usage of autoencoders on small training sets is possibly connected with redundancy reduction, and not with construction of nonlinear features. Thus, some principal ways of efficiently extracting nonlinear representations of patterns from small training sets or constructing some general representations (similar to the proposed hand-crafted image descriptors which are applicable for recognizing different image categories) are required.

  For experiments, two training sets were constructed. Variability of images in these training sets was different. The first set (DB1) contained heads of cats of 5 breeds -European Shorthair, British Shorthair, Exotic Shorthair, Burmese, Abyssinian; examples of two of them are presented in fig. 1. The second set (DB2) contained images of 6 categories -city, flowers (garden), indoor, mountains, forest, sea (beach); see fig. 2. DB1 was composed of 330 images, from which small training set was extracted with 50 (10 per class) images. DB2 was composed of 6000 images, and experiments with two training sets containing 60 (10 per class) and 4800 (800 per class) images were conducted.

Fig. 1 .

 1 Fig. 1. Examples of images from two classes (breeds of cats) of DB1.

Fig. 2 .

 2 Fig. 2. Examples of images from two classes (categories of scenes) of DB2.

Fig. 3 .Fig. 4 .Fig. 5 .Fig. 6 .

 3456 Fig. 3. Error rates of one-layer autoencoders of different hidden layer sizes with logistic regression layer on DB1 (540 features)

Table 1 .

 1 . Recognition error rates of the logistic regression classifier

		DB1	DB2	DB2
		(10 per class)	(10 per class)	(800 per class)
	Hand-crafted	0.356	0.505	0.118
	features (540)
	Hand-crafted	0.436	0.535	0.188
	features (315)
	64x64x3	0.361	0.620	0.583
	28x28x3	0.382	0.598	0.580
	20x20x3	0.401	0.615	0.571

Table 2 .

 2 Best recognition error rates of the autoencoders with logistic regression classifier

		DB1	DB2	DB2
		(10 per class)	(10 per class)	(800 per class)
	Hand-crafted	0.323	0.41	0.091
	features (540)
	Hand-crafted	0.359	0.445	0.122
	features (315)
	20x20x3	0.418	0.601	0.353

Acknowledgements

This work was supported by the Russian Federation President's grant Council (MD-1072.2013.9) and the Ministry of Education and Science of the Russian Federation.


Morten Goodwin

Anis Yazidi

A Pattern Recognition Approach for Peak Prediction of Electrical Consumption

Keywords: Peak Prediction, Energy Consumption, Classification

Predicting and mitigating demand peaks in electrical networks has become a prevalent research topic. Demand peaks pose a particular challenge to energy companies because these are difficult to foresee and require the net to support abnormally high consumption levels. In smart energy grids, time-differentiated pricing policies that increase the energy cost for the consumers during peak periods, and load balancing are examples of simple techniques for peak regulation. In this paper, we tackle the task of predicting power peaks prior to their actual occurrence in the context of a pilot Norwegian smart grid network. While most legacy studies formulate the problem as time-series-based estimation problem, we take a radically different approach and map it to a classical pattern recognition problem using a simple but subtle formulations. Among the key findings of this study is the ability of the algorithms to accurately detect 80% of energy consumption peaks up to one week ahead of time. Further, different classification methods have been rigorously tested and applied on real-life data from a Norwegian smart grid pilot project.

Introduction

Changes in the consumers electrical power consumption influences demand peaks, which are difficult to predict due to their seemingly random occurrence. This is because consumption peaks are consequences of aggregated and collective behaviour of several customers, and are influenced by many external factors. A simple example of typical consumer's behavioral influence is when people turn on their heater when the weather is cold. When multiple consumers do this at the same time it, which is natural since a drop in temperature affects them all, the aggregated behavior causes a peak in the overall electrical consumption. However, since there are many factors other than temperature that influences a user electrical consumption, it is far from trivial to foresee what the consumption will be and in turn predict high loads.

Both consumption peaks and peak supplies cause challenges for electrical service providers because they need to design their grid for the maximum potential load. This is crucial since energy scarcity has severe consequences such as power outages. An alternative approach to over dimensioning electrical grids for the absolute maximum potential consumption peaks is evening out the peaks with peak controlling methods. The difficulty lies in that to control consumption, smart grid systems need know peaks prior to their occurrence, and there is no existing method that can accurately do so. There is however no doubt that the existence of such a method would help power companies, such as Agder Energy, to design intelligent strategies for reducing the overall consumption. The overall impact of successful peak prediction is enabling for electrical grids with less load and in turn collectively less energy usage.

This paper addresses predicting electrical power consumption peaks in small communities where there are no external data available, such as weather predictions or detailed customer data. This contributes to a crucial part of larger smart grid energy system which performs load balancing and avoids energy over-supply to keep grid voltage at an acceptable level. The peak prediction algorithms are meant to be used in a smart grid installation to: (1) Automatically turn off smart electrical appliances. (2) Automatically ask consumer power cells to be turned on. (3) Carry out local level load balancing. Hence, a potential peak at one customer household will avoid contributing to an overall demand peak in the system. This is a realistic scenario and such algorithms are planned to be part of Smart Village neighbourhood in Arendal, Norway. This is particularly difficult as peaks are influenced by complex behaviour and typically occur in abnormal situations. Further, since this is planned to be installed in a new Smart Village neighbourhood, there is no external data available. We do not have access to other data such customer behavior, and since this is a small relatively secluded area weather reports is expected to have an equal impact on all customers and is therefore not particularly valuable 4 . The latter is different most approaches in the literature [START_REF] Feinberg | Load forecasting[END_REF].

Our main contributions in this paper are: In contrast to most other approaches, mapping peak detection into a two-labelled classification problem using statistical terms. We further test it out with data from a real Norwegian pilot smart grid project, and are able to get results in line with state-of-the-art with relatively simple classification algorithms.

This paper is organised as following. Section 2 formally defines the problem to be solved as a two-labelled classification problem. Section 3 continues with the most relevant development in the area from two research areas: peak prediction/detection and rare item classification. The data used in these experiments are described in section 4 and the methods used for peak predictions are described in section 5. Section 6 continues with the results and findings from these methods. Finally, conclusion and future work is outlined in section 7.

Problem setting

The goal of this research is to predict load peaks prior to their occurrence. Formally, given a time sequence t let p(t i , n) be a statistical function asserting whether t i is a peak where t i ∈ t and n tells the extremity of the peak as following:

p(t i , n) =      peak if t i > µ + n * σ not peak otherwise (1)
where µ and σ are the arithmetic average and standard deviation of t, and n is a number defined as the extremity of the peak. Thus, a value is defined as a peak if it has a value more than n times the standard deviation above the mean value. Is it possible to predict the output from p(t i , n) using only part of the sequence occurring prior to t i (t <i ∈ t)? Hence, the peak detection problem is deducted to a standard two-labelled classification problem. This is less trivial than most two-labelled classification problems because the peaks are rare and "abnormal". Rare abnormalities are particularly hard to predict. In layman's terms: Is it possible to predict future load peaks using only past data on electrical consumptions? 5

State-of-the-art

This section presents the most relevant research in the area of peak prediction. Section 3.1 presents the research on prediction electrical loads, and section 3.2 presents research on classifications when there is a skewed division of labelled data -i.e. classification when the positive labels are so few that it has a significant negative impact on the classification results.

Electrical consumption prediction

Many methods for load forecasting is available in the literature [START_REF] Feinberg | Load forecasting[END_REF][START_REF] Campbell | Methodologies for load forecasting[END_REF][START_REF] Weron | Modeling and forecasting electricity loads and prices: A statistical approach[END_REF][START_REF] Mohsenian-Rad | Optimal residential load control with price prediction in real-time electricity pricing environments. Smart Grid[END_REF]. Common for many of these is a reliance on some sort of third-party data for predictions and/or try to predict the actual power load. There are obvious similarities between peak prediction and load forecasting, but the objective is notably different.

A common approach is to use linear regression models in combination with other factors such as heat data. This is shown very useful to predict short-term peak loads [START_REF] Goia | Functional clustering and linear regression for peak load forecasting[END_REF][START_REF] Pardo | Temperature and seasonality influences on spanish electricity load[END_REF] and annual loads [START_REF] Wang | An annual load forecasting model based on support vector regression with differential evolution algorithm[END_REF]. This research uses various functional linear regression models and support vector regression for the actual prediction, and clusters the data and assign one regression model per cluster.

Another common approach of load forecasting is to find a similar day based on the available data, such as weather reports, and assume that similar days have similar loads. Most relevant for this work is hierarchical two-step classifiers used for short-term load forecasting [START_REF] Ilić | Hybrid artificial neural network system for short-term load forecasting[END_REF] which first predicts the "type of day" then an hourly forecast.

Some work exists without reliance on third party data with the assumption that the data has some internal structure than can be learnt. 6 Perhaps most well known is the use of evolutionary algorithms and fuzzy logic approach to predict hourly peaks from one to seven days ahead [START_REF] Yang | A new short-term load forecasting approach using self-organizing fuzzy armax models[END_REF],wavelet transformation techniques to accurately forecast power consumptions about 4 hours ahead of time [START_REF] Annamareddi | A simple hybrid model for short-term load forecasting[END_REF] and short-term predictions using exponential smoothing methods [START_REF] Taylor | An evaluation of methods for very short-term load forecasting using minute-by-minute british data[END_REF]. Further, other machine learning techniques been attempted such as non-linear curve-fitting [START_REF] Zhang | Forecasting with artificial neural networks:: The state of the art[END_REF][START_REF] Suganthi | Energy models for demand forecastinga review[END_REF] and Support Vector Machines (SVM) [START_REF] Mohandes | Support vector machines for short-term electrical load forecasting[END_REF][START_REF] Li | Study of support vector machines for short-term load forecasting[END_REF]. .

Rare item classification

Rare item classification is a field within pattern recognition where the majority of the data is impertinent, typically the normal situation, and consequently the interesting data appears much rarer. Often times even the labels to be classified are not known in advance. Further, there is an imbalance in the data available for training (a priori). Exhaustive labelling is commonly required to build up a proper training database. Both labelling and corresponding classification is inevitably costly. Much research exists on this, but, to the best of our knowledge, none of these directly address the peak prediction problem.

An effective technique when working with rare item classification is combination methods, such as hierarchical classifiers with more than one classification technique [START_REF] Kotsiantis | Handling imbalanced datasets: A review[END_REF][START_REF] Silla | A survey of hierarchical classification across different application domains[END_REF]. Generally this means organising local classifiers in an hierarchical structure and defining rules giving a global consensus. Based on techniques such as majority voting, the classifiers yields significantly better results for rare item classification than comparable algorithms, even with a flat structure [START_REF] Xiao | Hierarchical classification of emotional speech[END_REF]. Others use clever re-sampling, such as random under-and oversampling [START_REF] Kotsiantis | Handling imbalanced datasets: A review[END_REF].

Data with electrical consumption peaks

The data used in this project is from a summer cabin area in Hvaler, Norway for six weeks in mid 2012 [START_REF] Sand | Experiences from norwegian smart grid pilot projects[END_REF]. In total there are more than 7900 installations with varying degree of activity -making the data very vacillated. From each installation, accumulated hourly energy consumptions (kWh) was collected throughout the six weeks.

An examples of electrical consumption for one installation is presented in Figure 1(b). This shows averaged values of 7 days -displaying some clear trends: A rise and fall of the consumption with its highest around Norwegian dinner time and lowest at night, repeated nightly.

Figure 1(a) shows an example of consumption with peaks for a specific 24 hour period. The threshold level, n, for the peak data in Figure 1

Approach

This sections presents approaches for to predict p(t i , n). The first approach is a straightforward solution introduced for comparison purposes. This is continued with standard classification techniques inspired by similar work on load forecasting [START_REF] Goia | Functional clustering and linear regression for peak load forecasting[END_REF][START_REF] Mohandes | Support vector machines for short-term electrical load forecasting[END_REF][START_REF] Li | Study of support vector machines for short-term load forecasting[END_REF][START_REF] Chen | Load forecasting using support vector machines: A study on eunite competition 2001[END_REF]. Lastly, we present hierarchical classification solutions inspired by techniques in the literature on rate item classification [START_REF] Kotsiantis | Handling imbalanced datasets: A review[END_REF][START_REF] Silla | A survey of hierarchical classification across different application domains[END_REF][START_REF] Xiao | Hierarchical classification of emotional speech[END_REF]. All classifiers aim at predicting p (t <i , n) as close to p(t i , n) as possible.

Majority voting(c m ):Firstly, a simple majority voting classifier was implemented that counts the number of peaks in the training data and checks is there are more peaks the previous day than could be expected based on simple statistics.

Consistent peaks(c c ):Secondly, another classifier was implemented that always predict the peak equal to the previous peak value as following:

c c (t <i , d, n) = p (t <i , n) = p(t i-d , n). ( 2
)
where t i is the data to predict and d is how many hours in advance t i is. SVM(c l ,c p ):The purpose of the SVM is to create a function, linear(c l ) or polynomial(c p ), that separates data that results in peaks from the data that does not. Upon predicting p(t i , n) the vector space consists of a defined number of points prior to t i ∈ t, namely t <i . Each individual point in t <i is then a separate dimension. Two variants of SVM are implemented; The linear SVM approach is defined as c l (t <i , d, n), while the polynomial is defined as c p (t <i , d, n), GMM(c g ):GMM is a classifier known for handling outliers well [START_REF] Jain | Statistical pattern recognition: A review. Pattern Analysis and Machine Intelligence[END_REF]. It has, to the best of our knowledge, not been used for load or peak prediction previously.

It has however been used for many other classification applications with success, and is specially suited for rare item classification. Similar, to the SVM classifiers, when classification of t i with GMM we populate the vector space with points prior to t i (t <i ). This classifier is defined as c g (t <i , n).

Two variants of hierarchical classifiers are presented: Hierarchical and Hierarchical with Consistent Peaks. They both use a flat approach similar to variants in the literature [START_REF] Xiao | Hierarchical classification of emotional speech[END_REF] -namely straightforward combinations of the other classifiers.

Hierarchical (c h1 ): The hierarchical classifier is simply a combination of the linear SVM and GMM similar to the common practice in the literature as following: [START_REF] Uguroglu | Robust Learning with Highly Skewed Category Distributions[END_REF][START_REF] Huang | Clover: a faster prior-free approach to rare-category detection[END_REF].

7 c h1 (t <i , d, n) = c l (t <i d, , n) | c g (t <i d, n) (3)
Hierarchical with Consistent Peaks (c h2 ): An additional classifier was created utilizing the data from the consistent peaks (see equation 2). This extends equation 3 as following.

c h2 (t <i , d, n) = c l (t <i , d, n) | c g (t <i , d, n) | c c (t <i , d, n) (4)

Experiments

This section presents empirical results from running the predictive algorithms introduced in section 5. In line with common practice in the field [START_REF] Yang | A new short-term load forecasting approach using self-organizing fuzzy armax models[END_REF], we present predictions starting from one hour into the future and up to 7 days (168 hours). Section 6.1 presents a comparative experiments when n set to 1 -predicting moderate peaks. Additionally, section 6.2 shows the behaviour when varying n -making the peaks to detect more extreme -influences the algorithms.

All results presented in this chapter use a vector size of 24. 8Further, several metrics exists to evaluate information retrieval approaches. This paper promotes classification methods that favour false positives over false negatives. This is because a false positive, predicting a peak that is not present, has significantly less consequences than not predicting peaks which are present. Thus, high recall is much more sought after than high precision.

Predicting small consumption peaks

This section presents peak predictions with n in equation in p(t i , n) (equation 1) set to 1. This is the most straightforward approach where peaks are defined as simple values larger than the standard deviation.

Figure 2(a) and 2(b) show the recall and precision of the applied algorithms. These figures all show predictions 1 to 168 (7 days) into the future with n set to 1. This means that each time instance in the data, the algorithms try to predict from 1 to 168 hours ahead of time and the average is shown in the graph. All pattern recognition algorithms, SVM, GMM and Hierarchical has a decrease in recall as the t increases. This means that, in line with intuition, the difficulty increases the further into the future the algorithm try to predict peaks. However, when t reaches 24 the quality of the measure increases. Hence, it is easier to predict 24 hours into the future than it is to predict other values. This suggests that people behave similarly in 24 hour cyclic intervals (cook dinner, eat, sleep at roughly the same intervals). This is supported by "Consistent peaks"-classifier is surprisingly accurate.

The figure shows that the hierarchical classifiers have an excellent recall (Figure 2(a)). Thus, these algorithms are able to detect about 80% of the peaks in the data. Further, the recall decreases as t increases for all algorithms. Hence, prediction becomes more difficult the further into the future the algorithms aim at predict. This is however less true for hierarchical classifiers and GMM than for comparative algorithms.

On the other hand, the hierarchical classifiers have a low precision (Figure 2(b)). The algorithms have many false positives (close to 80%). We can say that an hierarchical classifier is able to predict 80% of the peaks, and whenever it predicts a peak it is a 20% chance that it is an actual peak. Keep in mind that the objective of the algorithms is to favor false positives compared to false negatives false negatives having less impact in electrical power grids. Fig. 3: Recall predicting 1 to 168 hours into the future varying n

Predicting larger consumption peaks

This section presents results upon varying n in p(t i , n) (equation 1). By increasing n the peaks become more extreme and (presumably) more difficult to predict. Figure 3(a) and 3(b) show recall over time when n is set to 2 and 3. This is same setup as shown in figure 2(a) with n set to 1, but the behaviour is notably different. First and foremost, all classifiers have a decreased recall. Most notably, the SVM classifiers drop fast to a recall close to 0. In this scenario, SVM is only able to predict close to 24 hours into the future, and not very well. Consequently, the hierarchical classifiers are only slightly better than GMM -which means than SVM does not contribute much in an increased recall in the hierarchical classifiers.

The trend in Figure 2(a) (n=1) and 3(a) (n=2) is continued in figure 3(b) (n=3), but is more extreme. The SVM classifiers more quickly drops to 0 and the difference between the hierarchical and GMM classifiers are much less. Still, the best algorithms are able to reach a recall more than 70%. 9Another trend which is more visible is that the results are more chaotic which may be caused by only some of these extreme peaks are predictable, while others are not. With peaks as n increase this becomes more apparent in the data rendering more challenging results.

A conclusion to be drawn from this is that an increase in the extremities of the peaks makes the classification more difficult. However, GMM and corresponding hierarchical classifiers are still able to detect more than 70% of the peaks. All other classifiers fall short with a recall close to 0.

Conclusion and future work

This paper deals with predicting electrical consumption peaks as input to load balancing and/or smart pricing strategies. This is done in a completely new way by mapping the prediction activities into a two-labelled classification problem. Further, in contrast to most existing approaches, the features are based solely on previous consumptions, avoiding reliance on third party data for the predictions.

Several classification algorithms are implemented and successfully applied on real-life data from a Norwegian smart-grid pilot project. The most promising results are produced by a simple hierarchical classifier combining linear support vector machines, Gaussian mixture models and deterministic assumption of consistent peaks. This solution is able to detect 80% of consumption peaks up to one week ahead of time. This promising result shows the usefulness of our approach.

This paper is part of an ongoing research project aiming at a developing smart energy housing technology with peak prediction as an essential component. We plan to carry out the following research: Comparison with additional classifiers, such as graph based classification approaches and more advanced hierarchical classifiers. We also plan to include weather information data as commonly done in the literature in order to improve the prediction results. Most importantly, this work is planned to be used in the scheduled Smart Village Skarpnes with 40 passive houses.

Fig. 1 :

 1 Fig. 1: Consumption patterns and peaks

Fig. 2 :

 2 Fig. 2: Recall and precision for predicting 1 to 168 hours into the future with n set to 1

The authors acknowledge that a change in temperature will influence electricity usage and in turn yield peaks. However, if there is an over all energy usage increase for all customers, techniques such as local load balancing will have limited value.

Note that is very different from the seemingly similar peak detection (positive outlier detection). For outlier detection it is possible calculate whether ti is an outlier using ti itself.[START_REF] Hodge | A survey of outlier detection methodologies[END_REF]

This is the same assumption we have in this paper.

Note that the decision rule is simpler than most other setups.

Several experiments were carried out with various vector sizes concluding with a vector size of 24 units. These results are not crucial to the understanding of the approach and therefore omitted.

The trend continues when increasing n even further. This is deliberately left out of the paper since this does not contribute to further insight of the algorithms.

Acknowledgements

This project is partially funded by Agder Regional Research Fund with the project "Grid Operation and Distributed Energy Storage: Potential for improved grid-operation efficiency" and the Norwegian Research Council funded project "Electricity Usage in Smart Village Skarpnes". These projects are carried out together with University of Agder, Teknova, Agder Energi Nett and Eltek. Data is collected through the external DeVID project. 10