Ilias Maglogiannis

Charalampos Ioannou

George Spyroglou

Panayiotis Tsanakas

Fall Detection Using Commodity Smart Watch and Smart Phone

Keywords: Fall Detection, Smart watch, Activity Recognition, Ambient Assisted Living, Streaming data

Human motion data captured from wearable devices such as smart watches can be utilized for activity recognition or emergency event detection, especially in the case of elderly or disabled people living independently in their homes. The output of such sensors is data streams that require real-time recognition, especially in emergency situations. This paper presents a novel application that utilizes the low-cost Pebble Smart Watch together with an Android device (i.e a smart phone) and allows the efficient transmission, storage and processing of motion data. The paper includes the details of the stream data capture and processing methodology, along with an initial evaluation of the achieved accuracy in detecting falls.

Introduction

The introduction of ubiquitous and mobile systems in human centered computing pushes towards achieving availability of invisible software applications and information anywhere and anytime [START_REF] Varshney | Pervasive Healthcare[END_REF]. Applications and interfaces able to automatically process data provided by sensors, exchange knowledge and make intelligent decisions in a given context, are strongly desirable. Natural user interactions with such applications are based on autonomy, avoiding the need for the user to control every action, and adaptivity, so that they are contextualized and personalized, delivering the right information and decision at the right moment. Thus, the development of assistive applications particularly for elderly or disabled people living on their own, has gained significant attention during the last years. The aging population is a significant issue. According to a recent report published by the EU the percentage of European population over the age of 65 is expected to be over 20% in 2020 and over 30% in 2060 [START_REF]Ageing Report: Economic and budgetary projections for the 27 EU Member States[END_REF].

The detection of falls is considered an essential function in the context of such intelligent assistive applications and environments, since approximately 33% of persons over the age of 65 and 50% of persons over the age of 85 experience a fall each year [START_REF] West | Do rates of hospital admission for falls and hip fracture in elderly people vary by socioeconomic status?[END_REF]- [START_REF] Robinson | Relationship between lowerextremity joint torque and the risk for falls in a group of community dwelling older adults[END_REF]. The injuries associated with falls can have serious consequences. For example, following hip fracture, 50% of older people are unable to live independently, 25% will die within six months, and 33% die within one year [START_REF] West | Do rates of hospital admission for falls and hip fracture in elderly people vary by socioeconomic status?[END_REF]- [START_REF] Robinson | Relationship between lowerextremity joint torque and the risk for falls in a group of community dwelling older adults[END_REF].

The goal of this work is to propose an unobtrusive wearable system capable of capturing and analyzing motion data and reaching a prompt decision for activity recognition and fall detection. For this purpose, the Pebble smart watch [5] has been utilized, as it combines several positive characteristics (low price, water-resistance, user friendliness, long battery life, open SDK). The specific smart watch has a reliable built-in accelerometer to measure human movements, and a personal area network interface in order to transmit data and communicate with other devices. More details about the Pebble device are provided in Section 2.2. The processing of the motion data occurs in a nearby Android device, since the smart watch lacks the necessary computing power to perform data analysis and the wide networking interface for transmitting the fall detection information. The overall architecture of the proposed fall detection application is illustrated in Figure 1. The rest of the paper is organized as follows: In Section 2, background material and related work is provided. Next, in Section 3 the SW of the proposed application that resides in both the smart watch and the smart phone are presented, while Section 4 is devoted to an initial evaluation. Finally, Section 5 covers concluding remarks and some future research directions.

2

Background Information and Related work

Fall Detection Applications

The concept of activity recognition with focus on fall detection is relatively new; however, it is quite popular due to the vast amount of sensors that have flooded the market recently. Several research groups and R&D departments of prominent companies have developed similar applications and there already exists significant related research work in the field. A comprehensive review exists in [START_REF] Mubashir | A survey on fall detection: Principles and approaches[END_REF]. Information regarding the human movement and activity in assisted environments is frequently acquired through visual tracking of the subject's or patient's position. Overhead tracking through cameras provides the movement trajectory of the patient and gives information about user activity on predetermined monitored areas [START_REF] Doukas | Emergency fall incidents detection in assisted living environments utilizing motion, sound, and visual perceptual components[END_REF]. A different approach for collecting patient activity information is the use of sensors that integrate devices like accelerometers, gyroscopes and contact sensors. The latter approach depends less on issues like patient physiology (e.g. body type and height) and environmental information (e.g. topology of monitored site) and can be used for a variety of techniques enabling user activity recognition [START_REF] Zhang | Design of an unobtrusive wireless sensor network for nighttime falls detection[END_REF][START_REF] Noury | Monitoring behavior in home using a smart fall sensor and position sensors[END_REF]. In previous works [START_REF] Doukas | Advanced classification and rules based evaluation of motion, visual and biosignal data for patient fall incident detection[END_REF][START_REF] Doukas | An assistive environment for improving human safety utilizing advanced sound and motion data classification[END_REF] we have presented a patient fall detection system, based on such body sensors that utilized advanced classification techniques and Kalman filtering for producing post fall detection. In this work we are trying to exploit a new class of smart devices that has been introduced recently: smart watches. We have selected the Pebble smart watch as a popular representative and we present some details of its capabilities in the next section.

2.2

The Pebble Smart watch Smart-watches are wristwatches with a micro display, integrated sensors and connectivity. The intention of the manufactures of smart watches is to have a new device that displays short messages like SMS, RSS feeds or Facebook messages. The Pebble is a smart watch developed by Pebble Technology and released in 2013. It features a black and white e-paper display, a vibrating motor, a magnetometer, ambient light sensors and an accelerometer, enabling its use as an activity tracker. The Pebble is compatible with Android and iOS devices. When connected to a phone, it can receive a vibrating alert to text messages, emails, incoming calls, and notifications from social media accounts.

The watch has a 1.26-inch 144 × 168 pixel black and white e-paper display using an ultra low-power "transflective LCD" with a backlight. The communication with an Android or iOS device is implemented using Bluetooth 4.0 (Bluetooth Low Energy) protocol. An important feature of the Pebble smart watch is that it is a solid and strong construction and it has a waterproof rating of 5 atm, which means it can be submerged down to 40m. An open software development kit (SDK) is available to programmers for developing custom applications. The SDK (known also as PebbleKit) allows the two-way communication between Pebble and smartphones running iOS or Android via the AppMessage framework and includes access to the accelerometer, as well as a Javascript API.

3

The proposed system

As shown in Figure 1 (system architecture) and illustrated also in Figure 2, the proposed activity and fall detection system consists of two software modules, which work in conjunction and communicate with each other using the Bluetooth 4.0 networking interface. The first module runs on the Pebble smart watch, and it is responsible for the user interaction and the data input. The second module is executed on the android device and handles data processing and alarm management. In order the system to be fully functional, the user has to wear the Pebble watch with the fall detection application running and remains within the Bluetooth range of the android device. In case the Bluetooth device is a smart phone the user can carry the device, so it can be always within range; however, at a home setup, the android device could be a tablet, a board PC, or a set-top box.

The Pebble application

The Pebble SDK 2.0 (until release 6), does not support multitasking, thus the user wearing the Pebble device should have the fall detection app installed in the foreground. Therefore, it is not feasible to run any other application on the background or to interact with other applications. The main screen of the developed app consists of a minimal clock, so the user can be informed about the time. Also at the bottom of the main screen, there is a small text field, which displays the status of the connection with the android device. If the android device is connected with the Pebble, the text field displays "Connected -Fall Detection is Active", whereas if the Pebble is not connected, the text field displays "Disconnected -Fall Detection is not Active" (see Figure 3).

As the Pebble display shows the time, the developed application checks whether an active Bluetooth (BT) connection with the android device is established. If a connection is found, the smart watch transmits the current accelerometer data and the corresponding time stamps. In the case for some reason the Pebble smart watch is disconnected from the android device (for instance, it gets out the BT range), the Pebble application changes the visible status connection, closes the accelerometer, stops transmitting data and notifies the user with a small vibration about the change in the status of the connection. The user has to be notified immediately about the disconnection. Once reconnected, the application starts again automatically. The code that runs on the Pebble watch is written in the C programming language. A very effective feature of the SDK is the "event handler" that supports the triggering of various functions, according to the captured event. The smart watch is capable of receiving 3-axis integer (example: x1, y1, z1) motion data from the built-in accelerometer in a sampling period of 50 ms, and stores them into character array variables, separated by commas. The values are converted into character array, are then separated by commas and copied to a single character array, by using the using the standard C function, strcat(). The final string is as follows, for ten samples or 500ms: [x1,y1,z1, x2,y2,z2, x3,y3,z3, x4,y4,z4, x5,y5,z5, x6,y6,z6, x7,y7,z7, x8,y8,z8, x9,y9,z9, x10,y10,z10].

Every 500ms the Pebble converts the character array into a tuplet string dictionary, by using a characterization key. After the serialization procedure, Pebble sends the data as a single string via the BT interface, while at the same time it continues to receive and store the incoming accelerometer data. The data is then sent to the android device for further processing, according to fall detection algorithms. In case a fall is detected, the android device sends a string value (fall-alarm) to the Pebble, and the proper event handler changes the watch status from watch view and status view, into alarm view. Alarm view consists of a text field, which displays: "A fall was detected -Press any key to Cancel", the Pebble screen's backlight is active and a vibration is triggered every 500ms.

If the user presses any of the Pebble's buttons in 5 seconds after the fall is detected, the fall alarm will be set off and a cancel-alarm string value will be sent to the android device. If the user does not respond within the 5-second interval the Pebble will send a trigger-alert sting value with the proper event handler, to notify about the triggered alarm.

3.2

The Android application

The Android application has been developed in Java using the Eclipse Android Developer Tools, intended for android devices. This app is launched (in background mode), every time the user launches the app on the Pebble smart watch and vise versa.

When the app is active, whether it runs on background or on foreground, it receives data from the Pebble device. The incoming string using the same tuplet dictionary and characterization key, is converted into comma-separated integer numbers.

According to the corresponding accelerometer axis, the data is parsed into the fall detection algorithm as follows: X=

, Y=[y1,y2,y3,y4,y5,y6,y7,y8,y9,y10], Z=[z1,z2,z3,z4,z5,z6,z7,z8,z9,z10]. The implemented fall detection algorithm has been proposed in a previous work and is based on the cumulative sum (CUSUM) change detection algorithm [START_REF] Tasoulis | Statistical data mining of streaming motion data for fall detection in assistive environments[END_REF]. The CUSUM decision function, as calculated for a fall in the X-and Y-axis, is depicted in Figure 4. In case a fall is detected a fall-alarm string will be sent to the Pebble and as already mentioned if the user does not cancel the alarm within the appropriate time interval, the application will initiate an actual alarm, transmitting automatically the fall detection information as defined (i.e. via email or via a call or SMS in the case of a smart phone).

4

The system in Practice -Initial Experimental Results

The main goal of this work is to present a user-friendly and unobtrusive application for fall detection. The proposed system combines the advantages of two simple, lowcost, and widely available devices. The obvious advantages of the smart watch are the ease and comfort of use, the high quality of acquired sensor data, the minimum weight and the low power consumption characteristics. The limited computing resources are replaced by the processing power of a typical android smartphone. The proposed solution is based on the bare minimum sampling rate (i.e. 50-200 ms), in order to minimize power consumption and increase battery life. During our experiments, the Pebble smart watch was proven capable of continuous sampling for at least 30 hours. An improvement in autonomy was achieved taking into consideration the actual time and the frequency of the user's movement, in order to decrease even more the sampling rate during the sleep. That resulted in a combined 35+ hours of continuous user fall tracking with a single battery charging. A significant parameter of the CUSUM algorithm presented in [START_REF] Tasoulis | Statistical data mining of streaming motion data for fall detection in assistive environments[END_REF] is the value of the threshold for the CUSUM decision function, which determines a fall. This is symbolized as the h parameter in the specific algorithm. According to the performed experiments, a lower value for h corresponds to smaller delays in fall detection, but produces more false positives. By experimenting with the h-parameter, we tried to minimize false positive alarms, ensuring the minimum possible delay time. The results of the conducted experiments are presented in Table I.

5

Discussion and Conclusions

This paper presents a fall detection application based on the Pebble smart watch, which is capable of transmitting the built-in accelerometer readings via Bluetooth to an android device for further processing. To the best of our knowledge, this is the first integrated application developed for fall detection based on a commodity smart watch. The main advantages of the proposed application are that it is non-obtrusive, low-cost, easy to deploy and use, and suitable for processing streaming data and reaching a prompt decision. In a future work, we intend to combine contextual data of the android device (e.g. location, audio, etc.), in order to decrease false alarms and improve the accuracy of the system and add additional functionalities, such as fall severity estimation. Furthermore the same device will be used for the simultaneously assessing sleep and other vital activities.

Figure 1 .

 1 Figure 1. Architecture of the proposed fall detection application

Figure 2 .

 2 Figure 2. The proposed fall detection application SW modules

Figure 3 .

 3 Figure 3. Screenshots of the Pebble Smart watch Application in case of an idle active connection and in case of a detected fall

Figure 4 .

 4 Figure 4. Accelerometer readings and the corresponding CUSUM calculation in case of a typical fall

TABLE I

 I Number of false alarms and the delay for several values of h, for each axis

	h	2.5	3.0	3.4	3.6	3.8	4.0 5.0
		Accelerometer (X-axis)
	False Alarms	5	3	2	1	0	0	0
	Delay (ms)	0	16	46	43	10	10 10
		Accelerometer (Y-axis)
	False Alarms	7	5	4	3	3	2	0
	Delay (ms)	1	0	10	16	45	18 10
		Accelerometer (Z-axis)
	False Alarms	8	6	5	4	4	3	0
	Delay (ms)	14	18	31	10	40	45 10

Acknowledgment

The authors would like to thank the European Union (European Social Fund ESF) and Greek national funds for financially supporting this work through the Operational Program "Education and Lifelong Learning" of the National Strategic Reference Framework (NSRF) -Research Funding Program: \Thalis \ Interdisciplinary Research in Affective Computing for Biological Activity Recognition in Assistive Environments. Part of the work reported here has been out in the framework of national project Providing Integrated eHealth Services for Personalized Medicine utilizing Cloud Infrastructure (PinCloud), led by the University of Piraeus, conducted in the context of the National Strategic Reference Framework NSRF 2007-2013, Cooperation 2011 and co-funded by the European Commission.


Eleanna Kafeza
email: kafeza@aueb.gr

Andreas Kanavos
email: kanavos@ceid.upatras.gr

Christos Makris
email: makri@ceid.upatras.gr

Pantelis Vikatos
email: vikatos@ceid.upatras.gr

Predicting Information Diffusion Patterns in Twitter

Keywords: Information Diffusion, Machine Learning, Social Media Analytics

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

Introduction

Social contagion, or as it is often called word-of-mouth, is mainly based on viral marketing strategies. There is a plethora of tools in the area of social media analytics that are available to help marketers to develop a real time viral marketing strategy. A central question when developing such strategies is how information is diffused within the social network. Recently an augmenting body of research has focused on examining the nature and structure of information diffusion from the point of view of an information cascade. For example, in the case of Twitter, an information cascade is the followers of a user that retweeted the initial user message. We look into the problem of defining typical cascades and predict when they will appear in the social graph. We argue that the content of the message and the type of network diffusion are the two main dimensions that lead to robust cascade prediction.

The problem of how information spreads within social media has been examined from different perspectives in the literature. In several cases, information flow has been associated to virus contamination and a diverse set of models have been developed trying to count the spread of information [START_REF] Aral | Creating Social Contagion through Viral Product Design: A Randomized Trial of Peer Influence in Networks[END_REF], [START_REF] Guille | Information Diffusion in Online Social Networks: A Survey[END_REF], [START_REF] Wu | Information Flow in Social Groups[END_REF]. Yet, there are fundamental differences in the case of information spread as opposed to virus spread mainly because the spread is based on a network structure and is influenced by the message. For instance, it has been observed in studies [START_REF] Wu | Information Flow in Social Groups[END_REF] that social media users who are several steps afar tend not to propagate information of each other. Although probability decay models have been proposed to capture that element, it is not certain that such decay occurs in a homogenous manner. Moreover, existing studies show that large cascades are rare and usually, larger cascades are utilized in terms of width and not depth. These results are in accordance to our findings. Hence, since most cascades appear, we need a more pragmatic approach in order to predict one.

In the problem of Twitter message diffusion, we take a different approach and similarly to [START_REF] Bakshy | Social Influence and the Diffusion of User-Created Content[END_REF] we investigate the actual users diffusion. Our objective is to predict the information diffusion of users for messages related to a specific topic. Our contribution is that we present a solid method for predicting tweet cascades within the Twitter graph. We argue that not all users and their connections behave in the exact same way. We assume that there are two aspects that drive the information spread, the message itself and the network structure. So, for different message subjects different diffusion occurs. For a given subject we examine the frequencies of all possible diffusions and thus we extract some simple and basic patterns of diffusion. We then, associate the content of tweets with the propagation patterns, using linguistic analysis and machine learning techniques. Given a tweet of a user, we are then able to predict its pattern path. We do so, with very good accuracy as our results indicate. Hence given a user's tweet on a subject we predict the approximate path that the tweet will take into the Twitter graph. Moreover, we show that influential communities tend to have a diverse set of propagation patterns.

The rest of the paper is organized as follows: Section 2 is the related work. In Section 3 we present the methodology of our approach. The implementation and our results are presented in Section 4. We conclude in Section 5 where we also present our future work.

Related Work

In [START_REF] Trusov | Determining Influential Users in Internet Social Networks[END_REF], a nonstandard form of Bayesian shrinkage implemented in a Poisson regression is proposed. There, the approach identifies the specific users who most influence others' activity and does so considerably better than simpler alternatives. The authors find that for the social networking site data, approximately one-fifth of a user's friends actually influence their activity level on the site. Also, in [START_REF] Purohit | Finding Influential Authors in Brand-Page Communities[END_REF], the authors present a study towards finding influential authors in Twitter brand-page communities (many enterprises have set-up their official webpages) where an implicit network based on user interactions is created and analyzed. More specifically, author profile and user interaction features are combined in a decision tree classification framework (DT framework) and thus, a novel objective evaluation criterion is used for evaluating these features.

Another work was [START_REF] Lee | Finding Influentials Based on the Temporal Order of Information Adoption in Twitter[END_REF], where a novel method to find influentials by considering both the link structure and the temporal order of information adoption in Twitter is adopted. Recently, in [START_REF] Kempe | Maximizing the Spread of Influence through a Social Network[END_REF], the authors consider the issue of choosing influential sets of individuals as a problem in discrete optimization. The optimal solution is NP-hard for most models that have been studied, including the model of [START_REF] Domingos | Mining the Network Value of Customers[END_REF]. The framework proposed in [START_REF] Richardson | Mining Knowledge-Sharing Sites for Viral Marketing[END_REF], on the other hand, is based on a simple linear model where the solution to the optimization problem can be obtained by solving a system of linear equations. The generality of the mentioned NPhard models lies between that of the polynomial-time solvable model of [START_REF] Richardson | Mining Knowledge-Sharing Sites for Viral Marketing[END_REF] and the very general model of [START_REF] Domingos | Mining the Network Value of Customers[END_REF], where the optimization problem cannot even be approximated to within a non-trivial factor.

In [START_REF] Wang | Measurement error in network data: A re-classification[END_REF], the authors compare a wide assortment of node-level network measures (degree centrality, clustering coefficient, network constraint, and eigenvector centrality), testing their robustness to different forms of measurement error. They also investigated network-structural properties (average clustering, degree distributions) as explanations for the varying effects of measurement error. In addition, Leskovec et al. [START_REF] Leskovec | Patterns of Influence in a Recommendation Network[END_REF] deal with information cascades; they are phenomena in which an action or idea becomes widely adopted due to influence by others. They develop a scalable algorithm and set of techniques to illustrate the existence of cascades as well as to measure their frequencies. From their experiments, they found that most cascades are small, cascade sizes approximately follow a heavy-tailed distribution, the frequency of different cascade subgraphs depends on the product type and last that these frequencies reflect more subtle features of the domain in which the recommendations are operating.

In article [START_REF] Bonchi | Social Network Analysis and Mining for Business Applications[END_REF], a business process classification framework to put the research topics in a business context is employed while providing a critical perspective on business applications of social network analysis and mining. Furthermore, in [START_REF] Leskovec | The Dynamics of Viral Marketing[END_REF], authors provide some assumptions concerning epidemic models. They find that the probability of purchasing a product increases with the number of recommendations received, but quickly saturates to a constant and relatively low probability. Also, they present a simple stochastic model that allows for the presence of relatively large cascades for a few products, but reflects well the general tendency of recommendation chains to terminate after just a short number of steps; they observe that the most popular categories of items recommended within communities in the largest component reflect differing interests between these communities.

Another empirical study of user-to-user content transfer occurring in the context of a time-evolving social network in Second Life (e.g. a massively multiplayer virtual world) is presented in [START_REF] Bakshy | Social Influence and the Diffusion of User-Created Content[END_REF]. There, adoption rates quicken as the number of friends adopting increases and this effect varies with the connectivity of a particular user. Also, in [START_REF] Bakshy | Everyone's an Influencer: Quantifying Influence on Twitter[END_REF], authors find out that the largest cascades tend to be generated by users who have been influential in the past and who have a large number of followers. The authors in [START_REF] Liu | From Strangers to Neighbors: Link Prediction in Microblogs using Social Distance Game[END_REF] focused on the problem of link prediction in Microblogs and proposed the notion of social distance based on the interaction patterns. The main idea is that social networks exhibit homophily and that the agents prefer to create ties with other agents who are close to them.

In [START_REF] Guille | Information Diffusion in Online Social Networks: A Survey[END_REF], methods for identifying influential spreaders in online social networks are presented and in following, a taxonomy of various approaches employed to address diffusion modeling techniques is proposed. Finally, Peng et al. [START_REF] Peng | Predicting Information Diffusion Initiated from Multiple Sources in Online Social Networks[END_REF] introduced the basic characteristics of the diffusion process of multi-source information via real datasets collected from Digg (e.g. a social news aggregation site); in following, a mathematical model to predict the information diffusion process of such multisource news is used.

Methodology

In our model we examine information diffusion in Twitter as Tree-Patterns. Our methodology for predicting the tweet cascade is based on the linguistic and emotional content of the tweets as well as the user communication behavior. According to Twitter: "A Retweet is a re-posting of someone else's Tweet. Twitter's Retweet feature helps you and others quickly share that Tweet with all of your followers". Although ReTweets might have other forms as well (for example the use of RT in the beginning of the message denotes that it is a ReTweet), still most of the ReTweets are done according to the formal Twitter definition using the @username convention. This is the conversion we use to retrieve ReTweets. Figure 1 depicts the architecture of our system.

We represent the information cascade as a Tree-Pattern i.e. the set of nodes that retweeted the initial user tweet. Note that all of these nodes are related with the "follow" relationship since only a user's followers can retweet their message.

The Social Media Crawler takes a topic as input and retrieves the information from Twitter. It collects all the Tweets and their corresponding ReTweets on the specific topic. The Tweet Profile Extraction is the module where the Tweets are inserted and they are abstracted as vectors that contain linguistic and emotional information about the Tweet as well information regarding the user behavior as depicted through the Twitter analytics i.e. number of followers etc. The Basic Tweet-Pattern Generation is a module that creates the frequent basic Tweet Propagation Patterns. The Tweet Vector and the Patterns are the input to the Diffusion Structure Classifier that predicts the Tweet-Pattern that will be followed by a given user tweet.

The Social Media Crawler

In order to retrieve information from the Twitter graph we use a crawler topicbased sampling approach where Tweets are collected via a keyword search query. Our data source is Tweets retrieved from the Twitter through the Twitter API (e.g. Twitter4J1 ) for a specific period of time (e.g. a couple of hours). We retrieved all the Tweets that were relevant to the subject #MH370 concerning Malaysia Airlines Flight 370 disappearance. Our dataset contains 13000 Tweets that have been done by 11130 users.

The crawler is responsible for sampling and traversing the Twitter media; it also collects information regarding the users' activity. More specifically, we extract 6 basic user features which better describe user communication behavior in Twitter. The set of 6 features contain the number of Followers, the number of Direct Tweets, the number of ReTweets, the number of Conversational Tweets (e.g. if a user replies to a post), the Frequency of user's Tweets (e.g. how "often" an author posts Tweets) and last the number of Hashtag Keywords (e.g. words starting with the symbol # and can specify the thematic category of a specific Tweet) as in [START_REF] Kafeza | Identifying Personality-based Communities in Social Networks[END_REF], [START_REF] Kafeza | T-PICE: Twitter Personality based Influential Communities Extraction System[END_REF].

Generating the Tweet-Pattern

To measure how tweets propagate through the Twitter network we represent tweet propagation as a tree. The root of the tree is the user that posts the initial tweet. Every child node is a follower of the initial user that has retweeted the initial tweet. This continues recursively until there are no nodes that retweeted the initial tweet. Hence each Tweet-Tree represents all the followers that retweeted the same message as the root user.

In Figure 2 we present some Tweet-Trees returned by our crawler. As previous studies have shown and as our results have shown as well, there are no large cascades of information, and Tweet-Trees tend to be small. So, our first objective is to find a set of representative Tweet-Patterns.

We observe that isomorphic Tweet-Trees exhibit the same diffusion. Isomorphic paths have the level number of a node as invariants, the number of paths from the root to the leaves, the number of levels in the tree, the number of leaf descendants of a node and the level number of a node. In information diffusion we are interested in the spread of information. Additionally, we are interested in the number of the leaf descends and not the specific position of the subtree that these descendants come from. Therefore we represent in the same way all isomorphic Tweet-Paths, taking as their representative the left-most variant.

For example in Figure 3, we see three different Tweet-Trees. All of them exhibit the same information diffusion thus we model them choosing one representative; the one depicted in (c).

Representing Tweet-Trees as Strings

We encode the diffusion of each tweet as a string and use top-down approach to traverse the tree. The root is the tweet that has been produced by a certain user. Let k be the maximum number of different users that have posted a ReTweet from a user from the whole dataset. Hence given a root tweet, there are at most k different possibilities of diffusion for each node of the tree. The order of these possibilities depends on the depth and width of diffusion. Starting from the root we use symbols to mark the diffusion. The placement of symbols begins from root to the next level. If there is more than one node in the current level we order the created symbols in reverse lexicographic way and we put the symbols respectively.

For each node there are k different possibilities of diffusion to the next level. In total there are k m different strings where k are different possibilities of diffusion to the next level and m the max depth of the trees. We have to note that based on the above construction, isomorphic trees have the same string representation.

Identifying the Basic Tree-Patterns

We use edit distance as a metric to identify the basic tree patterns. In particular the edit distance between two strings s 1 , s 2 of size d 1 , d 2 respectively is defined as he number of symbol operations (insertion, deletion and substitution) that must be performed in order to transform one string into the other. The edit distance is equal to the cost of the alignment of the two strings that is defined as the number of character mismatches when putting the one string under the other embedding spaces in both of them in order to produce strings of equal length. The edit distance can be computed with a simple dynamic programming algorithm as it is nicely described in [START_REF] Trusov | Determining Influential Users in Internet Social Networks[END_REF]

[i -1, j] + 1, D[i, j - 1] + 1, D[i -1, j -1] + (i, j)
, where (i, j) is an indicator variable equal to 1 if s 1 [i] and s 2 [j] are different, otherwise it is 0. The needed solution is given by D[d 1 , d 2 ] and it can be produced by a simple traversal of the array from top to bottom and from left to right.

Each produced string is compared to others using a table of dynamic programming via edit distance and the frequent strings are gathered in bins. As a result of the above process, a set of basic Tweet Tree-Patterns are extracted. These frequent patterns constitute the pre-assigned labels of each tweet for the training of the classification models.

Using Linguistics to Represent the Tweet as a Vector

After having specified the basic Tweet-Patterns, we argue that given a tweet on a specific topic the diffusion basic pattern that this tweet will follow is based on the tweet content and on the user profile. Hence we represent each tweet as a vector in which we extract linguistic and emotional information as well as information regarding the user that posted the tweet.

The following are the two main characteristics that we include in the Tweet-Vector:

-Linguistic and Emotional characteristics, which are produced by the Linguistic Inquiry and Word Count (LIWC) software which produce 80 features that include linguistic and psychological use of language as well as personal concerns. -Social Media Analytics, which can be used to monitor and capture user's behavior. The Followers of a user, the number of Tweets, ReTweets, Conversations and Hashtag Keyword as well the Frequency of Tweets, are some aspects that differentiate user behavior.

Thus every tweet is represented as a vector that contains the 80 features that were extracted when the tweet was processed with LIWC for linguist extractions and the 6 social analytics metrics that represent information about the user that created the initial tweet. We predict the Tweet-Pattern based on that vector using a variety of classification algorithms. The performance is evaluated by the F-Measure metric.

As already mentioned our dataset contains 13000 Tweets that have been done by 11130 users. In these Tweets, the maximum depth of the Tweet-Tree was 4 and the maximum width was 92. Thus we verify existing results which claim that the depth of the Tweet-Tree is small and the width large [START_REF] Lee | Finding Influentials Based on the Temporal Order of Information Adoption in Twitter[END_REF]. We encode the tweet information diffusion using 92 4 different representations as previously explained. After applying the methodology presented in Section 3.2, we end-up with the following basic Tweet-Patterns: As explained in Section 3.2, the next step in our methodology is to represent the tweet as a vector based on its linguistic characteristics and its user profile as described in the analytics. We used LIWC as a tool to extract linguistic characteristics and we used Twitter analytics to extract the user profile. As a result, we created a vector of 86 characteristics, as presented in Table 1. We separated dataset to training and test set, using two approaches: a) K-Fold Cross-Validation (K=10 Fold) and b) Leave-One-Out Cross-Validation. The concept of using both techniques is that splitting with 10-Fold Cross-Validation, important information can be removed from the training set. However, the We used the WEKA library2 for the classifiers. Table 2 shows the results of F-Measure for each classifier. The classifiers that give us the best results are depicted in bold. We can observe that JRIP achieves the highest F-Measure value. In addition, the next best classifiers are J48, PART as well as RotationForest. Moreover, we see that almost all classifiers achieve an F-Measure above 60%; only one classifier achieves 61%, while the rest are above 70%. Hence the accuracy of our prediction is high which validates our hypothesis that based on the linguistic aspects of the tweet and the user analytics profile, we can predict the Tweet-Tree.

As an application of our approach, we examine the different patterns that occur in highly influential communities. Based on our previous work [START_REF] Kafeza | T-PICE: Twitter Personality based Influential Communities Extraction System[END_REF], we extract the existing communities of the graph taking into consideration the personality of the users. We rank these communities based on the number of Tweets. The first in the rank are the most influential communities i.e. the communities where most Tweets occur. We are interested in finding out the type of diffusion that occurs in these communities.

We expect that the top influential communities are those that diffuse more the information. The first Tweet-Pattern which is a node by itself does not exhibit any diffusion since the tweet was not retweeted. Hence we expect that for the influential communities the diffusion patterns should mainly be the other three. Figure 5 verifies that expectation. It shows that when ranking the influential communities in ascending order based on the number of tweets that occurred in them, then the pattern of singe tweet (diffusion class 1) occurs less to the most influential community (com1). While the rest patterns (diffusion classes 2, 3 and 4) occur more in com1 and com2 than in com3. Therefore we conclude that communities where the number of tweets is large (influential communities) have more diffusion where ReTweets occur either as in sequence or in width. Recently there has been a growing interest in the literature for examining how information is diffused in social networks especially in the case where information cascades are short and usually with small depth and large width. In our work we use existing evidence supported by our results, to show that these Tweet-Trees have specific patterns. Hence we find the representative Tweet-Tree patterns that information follows when propagated in Twitter. We argue that this Tree-Pattern information diffusion can be predicted given a user's tweet and we use linguistic and user profiling information in order to do so based on machine learning techniques. Our results show that we can predict the basic Tree-Pattern with good accuracy. Our contribution is important especially in cases where marketers are interested in identifying influential users and networks and estimate the propagation of their messages. We show that in influential networks there is a set of different Tree-Patterns that occur.

In our future work, we are interested in examining the overall propagation of information within a whole Twitter network based on our prediction methodology. Also, as a next step we will consider time as a factor that influences the information diffusion.

Fig. 1 .

 1 Fig. 1. System Architecture of the Tweet Prediction Pattern System

Fig. 2 .

 2 Fig. 2. Examples of Tweet-Trees

Fig. 3 .

 3 Fig. 3. Isomorphic Tweet-Trees that represent the same information Diffusion

Fig. 4 .

 4 Fig. 4. The Basic Tweet Patterns

Fig. 5 .

 5 Fig. 5. Information Diffusion in Top Communities

  in time d 1 * d 2 . More specifically a two dimensional table D of size d 1 * d 2 is defined where D[i, j] is equal to the edit distance between s 1 [1 . . . i] and s 2 [1 . . . j] and can be expressed as the minimum of D

Table 1 .

 1 The Characteristics of the Tweet Vector

	Features	# Description
	LIWC	80 4 general descriptor categories (total word count, words per sen-
		tence, percentage of words captured by the dictionary, and per-
		cent of words longer than six letters), 22 standard linguistic
		dimensions (e.g., percentage of words in the text that are pro-
		nouns, articles, auxiliary verbs, etc.), 32 word categories tapping
		psychological constructs (e.g., affect, cognition, biological pro-
		cesses), 7 personal concern categories (e.g., work, home, leisure
		activities), 3 paralinguistic dimensions (assents, fillers, nonflu-
		encies), and 12 punctuation categories (periods, commas, etc)
	Twitter Metrics 6 Followers, Tweets, ReTweets, Conversations, Frequency, Hash-
		tag Keywords

Table 2 .

 2 F-Measure for each Classifier

	Classifiers	F-Measure
	AdaBoost	0.71
	IBK	0.71
	J48	0.88
	JRip	0.89
	Multilayer Perceptron	0.81
	Naive Bayes Classifier	0.61
	PART	0.88
	RotationForest	0.88
	SMO	0.77
	Leave-One-Out Cross-Validation technique evaluates the classification perfor-
	mance based on one sample.

Twitter4J library: http://twitter4j.org/en/index.html

Weka toolkit: http://www.cs.waikato.ac.nz/ml/weka/


Manuel Roveri
email: manuel.roveri@polimi.it

Francesco Trovò
email: francesco1.trovo@polimi.it

An Ensemble of HMMs for Cognitive Fault Detection in Distributed Sensor Networks

Distributed sensor networks working in harsh environmental conditions can suffer from permanent or transient faults affecting the embedded electronics or the sensors. Fault Diagnosis Systems (FDSs) have been widely studied in the literature to detect, isolate, identify, and possibly accommodate faults. Recently introduced cognitive FDSs, which represents a novel generation of FDSs, are characterized by the capability to exploit temporal and spatial dependency in acquired datastreams to improve the fault diagnosis and by the ability to operate without requiring a priori information about the data-generating process or the possible faults. This paper suggests a novel approach for fault detection in cognitive FDSs based on an ensemble of Hidden Markov Models. A wide experimental campaign on both synthetic and real-world data coming from a rock-collapse forecasting system shows the advantages of the proposed solution.

Introduction

Distributed sensor networks represent an important and valuable technological solution to monitor and acquire data from an environment, a cyber physicalsystem or a critical infrastructure system (e.g., water, gas, electric or transport networks). Unfortunately, distributed sensor networks working in (possibly harsh) real-working conditions may suffer from permanent or transient faults, thermal drifts or ageing effects affecting both the embedded electronic boards and the sensors. Fault Diagnosis Systems (FDSs), which are able to detect, identify, isolate and possibly accommodate faults, have been widely studied in the related literature [START_REF] Isermann | Fault-diagnosis systems[END_REF][START_REF] Venkatasubramanian | A review of process fault detection and diagnosis: Part i: Quantitative model-based methods[END_REF]. These systems revealed to be particularly effective in several different application domains provided that a priori information about the system model or the possible faults is (at least partially) available.

Recently, cognitive FDSs have been introduced, representing a novel and promising approach for fault diagnosis [START_REF] Demetriou | Incipient fault diagnosis of dynamical systems using online approximators[END_REF][START_REF] Farrell | Using learning techniques to accommodate unanticipated faults[END_REF][START_REF] Trunov | Automated fault diagnosis in nonlinear multivariable systems using a learning methodology[END_REF][START_REF] Alippi | A cognitive fault diagnosis system for distributed sensor networks[END_REF][START_REF] Alippi | A "learning from models" cognitive fault diagnosis system[END_REF]. The distinguishing features of these FDSs are the capability to work without a priori information about the process or the possible faults (which are learned directly from data) and the ability to exploit temporal and spatial dependencies in the acquired datastreams to improve the diagnosis of faults. Fault detection is obviously a key aspect in cognitive FDSs and, among the available techniques in the cognitive FDSs literature, we focus on the change detection test (CDT) based on a Hidden Markov Model (HMM) suggested in [START_REF] Alippi | An hmm-based change detection method for intelligent embedded sensors[END_REF]. This HMM-CDT revealed to be particularly effective in detecting faults affecting real-world monitoring applications (e.g., environmental monitoring [START_REF] Alippi | An hmm-based change detection method for intelligent embedded sensors[END_REF] or water transport network [START_REF] Alippi | An ensemble approach to estimate the fault-time instant[END_REF]) in the scenario of networked intelligent embedded sensors or distributed sensor networks. Unfortunately, the detection abilities of this CDT are influenced by the initial conditions of the HMM training algorithm, possibly leading to suboptimal HMM parameters estimations [START_REF] Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF].

In this paper, we propose an ensemble-of-models approach for cognitive fault detection based on HMMs, leading to a novel Ensemble HMM-based CDT (EHMM-CDT). More specifically, the proposed EHMM-CDT relies on a set of HMMs configured on the same training set, but with different randomly generated initial conditions for the HMM training algorithm. The ensemble approach aims at weakening the dependency of the HMM-CDT from the random initial conditions, hence providing better detection abilities. Interestingly, the possibility to combine different models to improve the generalization ability of a single model has been widely studied in the literature (mainly in the regression and classification scenarios) and effectively applied to different application fields [START_REF] Zhou | Ensemble methods: foundations and algorithms[END_REF][START_REF] Krogh | Statistical mechanics of ensemble learning[END_REF][START_REF] Perrone | When networks disagree: Ensemble methods for hybrid neural networks[END_REF]. Recently, ensembles of models have been successfully considered in time series prediction [START_REF] Wichard | Time series prediction with ensemble models[END_REF][START_REF] Zhang | Time series forecasting using a hybrid arima and neural network model[END_REF] and on-line missing data reconstruction [16]. Moreover, an ensemble of HMMs within a Bayesian framework for parameter estimation has been derived in [START_REF] Mackay | Ensemble learning for hidden markov models[END_REF], while an algorithm for training HMM in the ensemble framework was presented in [START_REF] Davis | Comparing and evaluating hmm ensemble training algorithms using train and test and condition number criteria[END_REF]. Remarkably, for the first time in the literature, in this paper we suggest an ensemble of HMMs for fault detection and we describe and evaluate two different aggregation mechanisms. In the experimental section, the proposed EHMM-CDT has been compared with the HMM-CDT: the advantages provided by the proposed solution have been evaluated both on synthetic and real datasets coming from a rock-collapse forecasting system.

The paper is organized as follows: Section 2 describes the problem formulation, while Section 3 summarizes the HMM-CDT suggested in [START_REF] Alippi | An hmm-based change detection method for intelligent embedded sensors[END_REF]. Section 4 details the proposed ensemble approach for cognitive fault detection, while Section 5 shows the experimental results.

Problem Formulation

Let us consider a distributed sensor network acquiring scalar measurements -or datastreams -from a time invariant dynamic system whose model description is unavailable. Without loss of generality we focus on the relationship between two datastreams; the extension to multiple or multivariate datastreams is straightforward, e.g., see [START_REF] Alippi | A cognitive fault diagnosis system for distributed sensor networks[END_REF].

The unknown relationship P between the two streams of data is modeled by a Single-Input Single-Output (SISO) linear time invariant (LTI) predictive model belonging to a family M parametrized in θ ∈ D ⊂ R p , where D is a C 1 compact manifold in R p and p ∈ N is the dimension of θ. For instance, SISO or Singleoutput/Multiple-input linear predictive models [19] and Reservoir Computing Networks [START_REF] Schrauwen | An overview of reservoir computing: theory, applications and implementations[END_REF] are viable options for the choice of M. In this paper, we consider linear SISO one-step-ahead predictive models: ŷ(t|θ) = f (t, θ, u(t), . . . , u(t -τ u ), . . . y(t -1), . . . , y(t -τ y )) , ∀t ∈ N [START_REF] Isermann | Fault-diagnosis systems[END_REF] where ŷ(t|θ) ∈ R is the prediction provided at time t, f : N×R p ×R τu ×R τy → R is the approximating function in predictive form, u(t) ∈ R m and y(t) ∈ R are the model input and output at time t, respectively, and τ u and τ y are the orders of the input and output, respectively.

Under mild assumption on P, M and the estimation procedure of θ over a finite dataset Z N = {(u(j), y(j))} N j=1 , it holds that [19]:

lim N →∞ √ N Σ -1 2 N ( θ -θ o ) ∼ N (0, I p ) ( 2
)
where θ is the estimated parameter vector, θ o is the parameter optimizing the structural risk in M, Σ N is a properly defined covariance matrix and I p is the identity matrix of order p. Interestingly, Equation ( 2) assures that, given a sufficiently large N , the estimated parameter vector θ follows a multivariate Gaussian distribution with mean θ o and covariance matrix Σ N . Moreover, this result remains valid even when P / ∈ M, i.e., a model bias ||M(θ o ) -P|| = 0 is present. This justifies the use of LTI models, even when the dynamic system under investigation P is non-linear.

The HMM-based Change Detection Test

The aim of this section is to summarize the key points of the HMM-CDT suggested in [START_REF] Alippi | An hmm-based change detection method for intelligent embedded sensors[END_REF], representing the core element of the proposed EHMM-CDT. Under the formulation presented in Section 2, the use of a HMM ruled by a mixture of Gaussian (GMM) over a sequence of parameters θs is the natural solution to model the functional relationship presented in Equation ( 1) in the parameter space. More formally, a HMM [START_REF] Elliott | Hidden Markov Models[END_REF] can be defined as a tuple H = (S, A, π), where S = {S 1 , . . . , S s }, s ∈ N is the indexed set of the states, each of which has an emission probability defined by a GMM,

A ∈ R s×s , A = [a ij ], s i=1 a ij = 1 ∀j ∈ {1, .
. . , s} is the transition matrix, i.e., a ij is the transition probability from state i to state j and π ∈ [0, 1] s , with

s i=1 π i = 1, is the initial distribution probability over S.
The idea underlying the HMM-CDT is to analyse the statistical behaviour of θs over time: when the statistical pattern of the estimated parameters does not follow what learned during an initial training phase, a change in the relationship is detected. Thus, the HMM-CDT relies on an initial parameter vector sequence Θ L = ( θ1 , . . . , θL ) estimated on a faulty-free training set Z M , where θj is estimated on a subsequence Z j,N = {(x(h), y(h))} j h=j-N +1 of the training sequence, j ∈ {N, . . . , M }, L = M -N + 1 (i.e., overlapping windows of length N ). The parameter sequence Θ L is used to train a HMM Ĥ, aiming at capturing the statistical behaviour of the estimated parameter vectors θt s in nominal conditions (without any change/fault). Then, during the operational phase, the statistical affinity between the estimated parameter vectors θt s and Ĥ is assessed by looking at the HMM loglikelihood: changes in the relationship expressed by Equation ( 1) are detected by inspecting the likelihood of θt with respect to Ĥ. More specifically, given a sequence Θ t,k = ( θt-k+1 , . . . , θt ), i.e., the last k consecutive parameter vectors at time t, a HMM Ĥ provides an estimates on how well the sequence follows Ĥ by means of the computation of the loglikelihood:

l( Ĥ, Θ t,k ) = log Pr( θt-k+1 | Ĥ) + t-1 h=t-k+1 log Pr( θh+1 | θh , Ĥ). ( 3
)
If the relationship does not change over time, the loglikelihood l( Ĥ, Θ t,k ) is comparable with the one computed during the training phase on a validation set

Z O = {(x(j), y(j))} O j=M +1 .
Otherwise, in case of variations in the relationship, l( Ĥ, Θ t,k ) decreases, since Θ t,k is no more compatible with the statistical model characterized by Ĥ. Further details about the HMM-CDT can be found in [START_REF] Alippi | An hmm-based change detection method for intelligent embedded sensors[END_REF][START_REF] Alippi | A cognitive fault diagnosis system for distributed sensor networks[END_REF].

Ensemble of HMM for Fault Detection

One of the key aspects of the HMM-CDT is the estimation of a HMM on Θ L , aiming at characterizing the nominal state. The state-of-the art training algorithm for HMMs is the Baum-Welch (BW) algorithm [START_REF] Baum | A maximization technique occurring in the statistical analysis of probabilistic functions of markov chains[END_REF], which aims at finding the maximum likelihood estimates of the HMM parameters given Θ L . Nonetheless, BW algorithm does not provide any guarantee about the convergence to the global maximum of the likelihood function [START_REF] Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF]. Since the BW algorithm requires a random initialization of the parameters, different HHMs can be obtained by repeating the training phase with different randomly initialized parameters on the same training sequence. Hence, a viable solution to weaken the effect of the initialization procedure on the HMM-CDT would be to repeat the BW algorithm and select the HMM guaranteeing the largest likelihood on a validation set. Unfortunately, as pointed out in [START_REF] Mackay | Ensemble learning for hidden markov models[END_REF], this solution may lead to overfit the training sequence Θ L (and this is particular evident for reduced training sets), leading to false positive detections (false alarms) during the operational phase.

In this work, we suggest an ensemble approach for fault detection (EHMM-CDT) based on a set E = {H 1 , . . . , H e }, e ∈ N of HMMs, where e is the ensemble cardinality. The main point of the proposed solution is that the HMMs H i ∈ E are trained on the same training set Z M with different initialization points of the BW algorithm. This ensemble approach allows to weaken the influence of the initial conditions of the HMM training algorithm, providing a better generalization ability and, consequently, better detection performance.

The proposed EHMM-CDT is detailed in Algorithm 1. To characterize the nominal state we rely on a training set Z M , assumed to be change-free. We estimate the parameter vectors θj s on overlapping windows of N data Z t,N , t ∈ {N, . . . , M }. Without loss of generality, we assume a step of one sample between

A(t) = A mean (l(H 1 , Θ t,k ), . . . , l(H e , Θ t,k ))) = e i=1 l(H i , Θ t,k ) e A(t) = A min (l(H 1 , Θ t,k ), . . . , l(H e , Θ t,k ))) = min i∈{1,...,e} l(H i , Θ t,k )
where A mean computes the average value of the loglikelihoods, while A min takes into account their minimum. The last step of the EHMM-CDT training phase is the computation of the threshold l min on a validation set Z O (Line 15), which is computed as follows:

l min = l -C l - min h∈{M +k,...,O} A(h) (4)
where l =

O h=M +k A(h) O
and C > 1 is a user-defined coefficient factor. During the operational phase, when the aggregated loglikelihood decreases below l min , a change in the statical behaviour of P is detected by the EHMM-CDT. More in details, as soon as a new sample (u(t), y(t)) , t > M + O is available, the algorithm estimates a new parameter vector θt on Z t,N (Line 17). The likelihoods for the ensemble of HMMs, i.e., l(H i , Θ k,t )∀H i ∈ E, are computed (Line 20) and then aggregated, according to the aggregation mechanism A (Line 22). Afterwards, the aggregated likelihood A(t) is compared with the threshold l min to asses if a change in P is detected (Line 23). In case of a change, an alarm is raised and the detection time T = t is returned (Line 24), otherwise the algorithm keeps on monitoring data coming from P.

While ensemble approaches are generally able to increase the generalization ability of single models, they are characterized by an increased computational complexity, that in this case scales linearly with the number of HMMs e. Two comments arise: 1) The most time consuming part of the EHMM-CDT refers to the HMMs training (the loglikelihood computation is much more lighter than training). Interestingly, the training phase is performed only once during the initial configuration of the cognitive FDS, while during the operational life only the likelihoods are computed. In addition, in scenarios where networked embedded systems are operating, the training of HMMs could be performed in a centralized high-powerful unit, leaving only the computation of likelihoods directly at the low-power distributed units of the network. 2) In scenarios where the fault detection ability is a relevant activity, the increase in the complexity induced by the ensemble approach is well compensated by the decrease in false and missed alarms and detection delays, as shown in the experimental section.

Experimental Results

To evaluate the performance of the proposed EHMM-CDT we considered both synthetic (Application D1) and real data (Application D2), coming from a rock collapse forecasting system deployed in Northern Italy. In both applications, we considered a faulty free dataset divided into training (to create E), validation (to learn l min ) and test sets (to evaluate the performance). In the last one we injected five different kinds of abrupt permanent fault at time t:

-A1-A3: y(t) = y(t) + ∆ a • a max , ∀t > t, ∆ a ∈ {0.1, 0.2, 0.3} (additive fault); -M : y(t) = y(t) • (1 + ∆ m ), ∀t > t, ∆ m = 0.3 (multiplicative fault); -S: y(t) = y( t), ∀t > t (stuck-at fault);
where a max = max j∈{1,...,M } y(j) -min j∈{1,...,M } y(j).

As regards the model family M, we considered SISO LTI AutoRegressive with eXogenous input (ARX) models, whose orders are chosen through a model selection procedure (i.e., minimizing the mean square one-step-ahead prediction error on a validation set). The HMMs are configured by considering batches of N = 100 samples, loglikelihood window length k = 10 and exploring s ∈ {3, . . . , 6} and the number of models in each GMM ∈ {1, 2, 4, 8, 16, 32}. The cardinality of the ensemble was set to e = 30. Finally, the parameter vectors estimation is performed with the least square method.

To evaluate the detection ability of what proposed the following figures of merit have been considered:

-false positive (FP) rate: fraction of the experiments where the method detected a change before it actually appears; -false negative (FN) rate: fraction of the experiments where the method did not detected a change; -detection delay (DD): the number of samples necessary to detect a change;

The proposed method is compared with the HMM-CDT, where a single HMM was considered (the one with largest loglikelihood on a validation set among those considered for the ensemble).

APP D1: Synthetic data. The data for the synthetic application have been generated from the following non-linear model:

y(t) = sin(a T • (y(t -1), y(t -2)) + b • x(t -1)) + η(t)
where a ∈ [0, 1] 2 , b ∈ [0, 1], η(t) ∼ N (0, σ 2 ), σ ∈ {0.01a max , 0.05a max }. Each experiment lasts 6125 samples (i.e., 3268 for training, 817 for validation and 2040 for testing): faults are injected at time t = 5105. Results are averaged over 1000 runs.

Figure 1 shows the experimental results in the case of APP D1 and σ = 0.05a max . Curves are obtained by considering values of C ranging from 1 to 5.1, where 5.1 is the largest value of C for which F N ≤ 0.1 for all the faulty scenarios. Interestingly, in all the considered scenarios the ensemble approach is able to improve the detection ability (in terms of both FP and DD) of the single HMM-CDT. These curves show that the performance of EHMM-CDT cannot be achieved by the HMM-CDT by simply tuning the parameter C. In addition, in the faulty scenario M where FNs are present, the proposed EHMM-CDT behaves better than HMM-CDT even with respect to this figure of merit (see legend of Fig. 1.d). Experimental results presented in Table 5 refer to FN, FP and DD with fixed values of C. To ease the comparison we set C in the EHMM-CDT and HMM-CDT as the lowest values guaranteeing F N = 0 and F P ≤ 0.01 in APP D1 with σ = 0.01 (i.e., C = 4.814 for HMM-CDT, C = 4.629 for EHMM-CDT with A mean and C = 4.917 for EHMM-CDT with A min ). Remarkably, both EHMM-CDT aggregations provide lower DD than HMM-CDT. Interestingly, the mean aggregation mechanism generally outperforms the minimum one, since the mean is less influenced than minimum by outliers, which generally induce false alarms. Nonetheless, by comparing these results with those provided in Figure 1, we may also comment that the mean aggregation does not provide better results for each value of C: hence the minimum is a viable solution too. APP D2: Rialba Data. We consider data coming from a real-world distributed sensor network for rock-collapse forecasting [23,[START_REF] Alippi | A high-frequency sampling monitoring system for environmental and structural applications[END_REF]. This dataset is available at [25]. In particular, we analyzed two temperature datastreams composed by 5303 samples (3000 for training, 1000 for validation and 1303 for testing), coming from two network units. The sampling period is 5 minutes. We injected faults (A1-A3,M,S) at t = 4695. Experimental results in Table 5 are obtained by averaging the results of 50 runs. Interestingly, the results on the real-world datasets are in line with those of the synthetic one: the ensemble approach provides lower F N and DD for most of the considered scenarios.

Conclusions

We presented an novel approach for cognitive fault detection based on an ensemble of HMMs. The distinguishing feature of the proposed solution is the ability to improve the generalization ability (in terms of detection performance) of a single HMM-CDT by considering an ensemble of HMMs trained on the same training set, but with different initialization points. The effectiveness of the proposed solution has been tested on both synthetic and real datasets coming from a real-world distributed sensor network for rock-collapse forecasting.

Fig. 1 .

 1 Fig. 1. Experimental results showing the relationship between FP and DD in application D1 with σ = 0.05, where C ∈ [1, 5.1]

Table 1 .

 1 Detection results for the single and ensemble HMM-CDT approaches from applications D1 (with different σs) and D2

		HMM-CDT		EHMM-CDT
				Amean	Amin
		F N F P	DD	F N F P	DD F N F P	DD
	σ = 0.01amax	A1 0.000 0.007 21.614 0.000 0.007 19.419 0.000 0.006 19.717 A2 0.000 0.007 17.415 0.000 0.007 15.320 0.000 0.006 15.638 A3 0.000 0.007 15.396 0.000 0.007 13.724 0.000 0.006 13.998 M 0.000 0.007 37.057 0.000 0.007 35.355 0.000 0.006 35.794 S 0.000 0.007 16.186 0.000 0.007 15.335 0.000 0.006 15.648
	σ = 0.05amax	A1 0.000 0.007 67.939 0.000 0.009 63.745 0.000 0.009 64.708 A2 0.000 0.007 47.465 0.000 0.009 42.625 0.000 0.009 43.281 A3 0.000 0.007 39.676 0.000 0.009 34.734 0.000 0.009 35.006 M 0.077 0.007 185.989 0.057 0.009 161.401 0.055 0.009 166.641 S 0.000 0.007 45.139 0.000 0.009 42.413 0.000 0.009 42.781
		A1 0.340 0.000 314.879 0.000 0.000 172.100 0.280 0.000 234.500
	Rialba	A2 0.000 0.000 152.100 0.000 0.000 148.900 0.000 0.000 154.400 A3 0.000 0.000 119.700 0.000 0.000 30.700 0.000 0.000 93.800 M 0.040 0.000 163.250 0.000 0.000 153.200 0.000 0.000 162.100
		S 0.000 0.000 81.500 0.000 0.000 82.300 0.000 0.000 89.600


Sotirios P Chatzis

Dimitrios Kosmopoulos

A Partially-Observable Markov Decision Process for Dealing with Dynamically Changing Environments

Partially Observable Markov Decision Processes (POMDPs) have been met with great success in planning domains where agents must balance actions that provide knowledge and actions that provide reward. Recently, nonparametric Bayesian methods have been successfully applied to POMDPs to obviate the need of a priori knowledge of the size of the state space, allowing to assume that the number of visited states may grow as the agent explores its environment. These approaches rely on the assumption that the agent's environment remains stationary; however, in real-world scenarios the environment may change over time. In this work, we aim to address this inadequacy by introducing a dynamic nonparametric Bayesian POMDP model that both allows for automatic inference of the (distributional) representations of POMDP states, and for capturing non-stationarity in the modeled environments. Formulation of our method is based on imposition of a suitable dynamic hierarchical Dirichlet process (dHDP) prior over state transitions. We derive efficient algorithms for model inference and action planning and evaluate it on several benchmark tasks.

Introduction

Reinforcement learning in partially observable domains is a challenging and attractive research area in machine learning. One of the most common representations used for partially-observable reinforcement learning is the partially observable Markov decision process (POMDP). POMDPs are statistical models postulating that emission of the observation o t that an agent receives from the environment at time t follows a distribution Ω(o t |s t , a t ) that depends on the value of some latent (hidden) world-state s t , and the agent's most recent action a t . In addition, each action a t of the agent results in a reward R(s t , a t ) emitted from the environment, the value of which also depends on the current state s t , and induces a change in the latent state of the environment, which transitions to a new state s t+1 , drawn from a transition distribution T (s t+1 |s t , a t ). Due to the generic nature of their assumptions, POMDPs have been successfully applied to a large number of reinforcement learning scenarios with great success [START_REF] Shani | A survey of point-based POMDP solvers[END_REF].

A significant drawback of POMDPs is the large number of parameters entailed from the postulated emission distribution models Ω(o|s, a), state transition distribution models T (s |s, a), and reward models R(s, a). These parameters must be learned using data obtained through interaction of the agent with its environment, in an online fashion. However, the combination of the very limited availability of training data with the large number of parameters of the fitted models typically results in highly uncertain trained models, where planning becomes extremely computationally cumbersome. Bayesian reinforcement learning approaches [START_REF] Ross | Bayes-adaptive POMDPs[END_REF][START_REF] Poupart | An analytic solution to discrete Bayesian reinforcement learning[END_REF][START_REF] Ross | Bayesian reinforcement learning in continuous POMDPs with application to robot navigation[END_REF] resolve these issues by accounting for both uncertainty in the agent's model of the environment, and uncertainty within the environment itself. This is effected by maintaining distributions over both the parameters of the POMDP and the latent states of the world s.

A drawback of most Bayesian approaches is their requirement of a priori provision of the number of model states: even if the size of the state-space is actually known (which is seldom the case), performing learning for a large number of unknown model parameters from the beginning of the learning process (when no data is actually available) might result in poor model estimates and heavy overfitting proneness. Recently, [START_REF] Doshi-Velez | The infinite partially observable Markov decision process[END_REF] proposed leveraging the strengths of Bayesian nonparametrics, specifically hierarchical Dirichlet process (HDP) priors [START_REF] Teh | Hierarchical Dirichlet processes[END_REF], to resolve these issues. The so-obtained infinite POMDP (iPOMDP) postulates an infinite number of states, conceived as abstract entities whose sole function is to render the dynamics of the system Markovian, instead of actual physical aspects of the system. Despite the assumption of infinite model states though, at each iteration of the model learning algorithm, only a small number of (actually visited) effective states need to be instantiated with parameters. As such, the model can be initialized with only few parameters, which allows for effectively dealing with overfitting. However, as the agent accumulates experiences (i.e., training data) through interaction with its environment, the number of parameters may increase in an automatic, unsupervised manner, by exploiting the nonparametric nature of the model. Despite these advances, a significant drawback of existing nonparametric Bayesian formulations of POMDPs consists in their lack of appropriate mechanisms allowing for capturing non-stationarity in the modeled environments, expressed in the form of time-adaptive underlying state transition distributions. Indeed, the problem of capturing time-varying underlying distributions in conventional POMDP model formulations has been considered by various researchers in the recent literature (e.g., [START_REF] Theocharous | Approximate planning in POMDPs with macroactions[END_REF][START_REF] Jaulmes | Learning in non-stationary Partially Observable Markov Decision Processes[END_REF]). In this work, we address this inadequacy by introducing a non-stationary variant of the iPOMDP. Formulation of our model is based on imposition of the dynamic hierarchical Dirichlet process (dHDP) prior [START_REF] Ren | The dynamic hierarchical Dirichlet process[END_REF] over the postulated state transitions in the context of our model. We derive efficient model inference and action planning algorithms, based on a computationally scalable combination of Gibbs sampling interleaved with importance sampling techniques. We evaluate the efficacy of our approach considering a set of well-known benchmark tasks, dealing with partially observable environments.

The remainder of this paper is organized as follows: In Section 2, we introduce our proposed model, and derive its learning and action selection algorithms. In Section 3, we provide the experimental evaluation of our approach, and compare it to state-of-the-art alternatives. Finally, in the last section we summarize our results and conclude this paper.

Proposed Approach

Motivation

The iPOMDP model is based on utilization of an HDP prior to describe the state transition dynamics in the modeled environments. The HDP is a model that allows for linking a set of group-specific Dirichlet processes, learning the model components jointly across multiple groups. Specifically, let us assume C latent model states, and A possible actions; let us consider that each possible stateaction pair (s, a) defines a different scenario in the environment. The iPOMDP model, being an HDP-based model, postulates that the new state of the environment (after an action is taken) is drawn from a distribution with different parameters θ sa , which are in turn drawn from a scenario-specific Dirichlet process. In addition, the base distribution of the scenario-specific Dirichlet processes is taken as a common underlying Dirichlet process. Under this construction, the following generative model is obtained

s |s, a ∼ T (θ s,a ) (1)
θ s,a ∼ G s,a (2)
G s,a ∼ DP(α, G 0 ) (3)
G 0 ∼ DP(γ, H) (4)
As we observe, in the context of the HDP, different state transitions that refer to the same state-action pair (scenario) share the same parameters (atoms) that comprise G s,a . In addition, transitions might also share parameters (atoms) across different state-action pairs, probably with different mixing probabilities for each G s,a ; this is a consequence of the fact that the Dirichlet processes G s,a pertaining to all the modeled state-action pairs share a common base measure G 0 , which is also a discrete distribution.

Although the HDP introduces a dependency structure over the modeled scenarios, it does not account for the fact that, when it comes to modeling of sequential data, especially data the distribution of which changes over time, sharing of underlying atoms from the Dirichlet processes is more probable in proximal time points. Recently, [START_REF] Ren | The dynamic hierarchical Dirichlet process[END_REF] developed a dynamic variant of the HDP that allows for such a modeling capacity, namely the dynamic HDP (dHDP). Therefore, utilization of this prior emerges as a promising solution for us to effect our goals.

Model formulation

To introduce our model, we have to provide our prior assumptions regarding the state transition distributions, observation emission distributions, and reward emission distributions of our model. Let us begin with the state transition distributions of our model. As we have already discussed, to capture non-stationarity, we model state transitions using the dHDP prior [START_REF] Ren | The dynamic hierarchical Dirichlet process[END_REF].

Let us introduce the notation π s,a τ = (π s,a τ l ) ∞ l=1 . π s,a τ l denotes the (prior) probability of transitioning at some time point t to state l from state s by taking action a, given that the distributions of the various state transitions at that time point are the same as they were at time τ = φ t . In other words, the employed dHDP assumes that the dynamics of state transition may change over time, with different time points sharing common transition dynamics patterns. Specifically, following [START_REF] Ren | The dynamic hierarchical Dirichlet process[END_REF], we have

s t+1 = k|s t = s, a t = a ∼ Mult(π s,a φt ) (5) π s,a τ ∼ DP(α, G 0 ) (6)
and

G 0 ∼ DP(γ, H) (7)
whence

π s,a tl = πs,a tl l-1 h=1 (1 -πs,a th ) (8) πs,a tl ∼ Beta(α t β l , α t (1 - l m=1 β m )) (9)
β k = k k-1 q=1 (1 -q ) ( 10
)
and

k ∼ Beta(1, γ) (11)
In the above equations, the latent variables φ t are indicators of state-transition distribution sharing over time. Following [START_REF] Ren | The dynamic hierarchical Dirichlet process[END_REF], their prior distributions take the form

φ t | w ∼ Mult(w t ) (12)
with w t = (w tl ) t l=1 , and

w tl = wl-1 t-1 m=l (1 -wm ), l = 1, . . . , t (13)
while w0 = 1, and

wt |a t , b t ∼ Beta( wt |a t , b t ), t ≥ 1 ( 14
)
As observed from [START_REF] Shani | A survey of point-based POMDP solvers[END_REF], this construction induces a proximity-inclined transition dynamics sharing scheme; that is, w t1 < w t2 < • • • < w tt . In other words, it favors sharing the same dynamics between proximal time points, thus enforcing our assumptions of transition dynamics evolving over time in a coherent fashion. Finally, our observation emission distributions are taken in the form Ω(o|s, a) ∼ H, and our reward emission distributions yield R(r|s, a) ∼ H R . The distributions H and H R can have any form, with the choice depending on the application at hand. In this paper, we shall be considering discrete reward and action distributions; as such, a suitable conjugate selection for the priors over their parameters is the Dirichlet distribution.

This concludes the formulation of our model. We dub our model the infinite dynamic POMDP (iDPOMDP) model. Our model is a completely non-stationary POMDP model, formulated under the assumption of an infinite space of latent POMDP states, and treated under the Bayesian inference paradigm. Note also that limiting the generative non-stationarity assumptions to the transition functions of our model does not limit non-stationarity per se to state transitions. Indeed, the non-identifiability of the postulated model latent states results in the assumed generative non-stationarity of the transition functions being implicitly extended to the observation and reward functions of our model.

Inference algorithm

To efficiently perform inference for our model, we combine alternative application of a variant of the block Gibbs sampler of [START_REF] Ishwaran | Gibbs sampling methods for stick-breaking priors[END_REF], and importance sampling [START_REF] Siegmund | Importance sampling in the Monte Carlo study of sequential tests[END_REF], in a fashion similar to the iPOMDP model [START_REF] Doshi-Velez | The infinite partially observable Markov decision process[END_REF]. Our block Gibbs sampler allows for drawing samples from the true posterior. However, we limit ourselves to using our block Gibbs sampler only on a periodical basis, and not at each time point. In the meanwhile, we use instead an importance sampling algorithm, which merely reweighs the already drawn samples so as to reflect the current posterior as closely as possible. This way, we obtain a significant speedup of our inference algorithm, without compromising model accuracy, since the actual model posterior is not expected to undergo large changes over short time windows.

Block Gibbs sampler To make inference tractable, we use a truncated expression of the stick-breaking representation of the underlying shared Dirichlet process of our model, G 0 [START_REF] Sethuraman | A constructive definition of the Dirichlet prior[END_REF]. In other words, we set a truncation threshold C, and consider π s,a t = (π s,a tl ) C l=1 , ∀t, s, a [START_REF] Ishwaran | Gibbs sampling methods for stick-breaking priors[END_REF]. A large value of C allows for obtaining a good approximation of the infinite underlying process, since in practice the π s,a tl are expected to diminish quickly with increasing l, ∀t [START_REF] Ishwaran | Gibbs sampling methods for stick-breaking priors[END_REF]. Note also that, as discussed in [START_REF] Ren | The dynamic hierarchical Dirichlet process[END_REF], drawing one sample from the dHDP model by means of the block Gibbs sampler takes similar time as drawing one sample from HDP.

Let us consider a time horizon T steps long. We have

where ν s,a tk is the number of training episodes where we had a transition from state s to state k, by taking action a at time t.

The updates of the set of indicator variables φ t can be obtained by generating samples from multinomial distributions with entries of the form

p(φ t = τ |s t-1 = s, a t-1 = a; . . . ) ∝ wτ-1 t-1 m=τ (1 -wm )π s,a τ st st-1 q=1 (1 -πs,a τ q )
×p(o t+1 |s t , a t ) p(r t+1 |s t , a t ), τ = 1, . . . , t (17) Further, the posterior distribution over the latent model states yields

p(s t = k|s t-1 = s, a t-1 = a; . . . ) ∝ πs,a φtk k-1 q=1 (1 -πs,a φtq )p(o t+1 |s t , a t ) p(r t+1 |s t , a t )
(18) As we observe, this expression entails Markovian dynamics. Thus, to sample from it, we have to resort to some method suitable for distributions with temporal interdependencies. In our work, we employ the forward filtering-backward sampling (FFBS) algorithm [START_REF] Carter | On Gibbs sampling for state space models[END_REF]; this way, we can efficiently obtain samples of the underlying latent state sequences.

Finally, the observation and reward distribution parameters of our model are sampled in a manner similar to the original iPOMDP model [START_REF] Doshi-Velez | The infinite partially observable Markov decision process[END_REF].

Importance sampling At time points when we substitute block Gibbs sampling from the true posterior with importance sampling, we essentially reweigh the samples previously drawn from the true posterior. Initially, all samples have equal weight as they are drawn from the true posterior; this changes when we apply importance sampling, so as to capture small changes in the actual posterior in a computationally efficient manner (possible within short time-windows).

Let us denote as µ a sample of our model with weight w t (µ) at time t (all samples have initial weights equal to one). Similar to the iPOMDP model, the weight update at time t + 1 yields [START_REF] Doshi-Velez | The infinite partially observable Markov decision process[END_REF]

w t+1 (µ) ∝ w t (µ) ∀st Ω(o t+1 |s t, a t )b µ (s t ) ( 19
)
where b µ (s) is the belief (posterior probability) for state s, as determined in the sample µ of the model.

Action selection

Once we have obtained a set of samples from the posterior distribution of our model, we can use them to perform action selection. For this purpose, in this work we apply stochastic forward search in the model-space, as proposed in [START_REF] Doshi-Velez | The infinite partially observable Markov decision process[END_REF].

The main concept of forward search is to use a forward-looking tree to compute action-values [START_REF] Ross | Online planning algorithms for pomdps[END_REF]. Starting from the current posterior (belief) over the model parameters of the agent, the tree branches on each action the agent might take and each observation the agent might see. At each action node, the agent computes the (posterior) expectation of the immediate reward, given the drawn samples, in a standard Monte Carlo-type fashion.

Experimental Evaluation

We evaluate our method in several benchmark scenarios and compare its performance to related alternatives, namely Medusa [START_REF] Jaulmes | Learning in non-stationary Partially Observable Markov Decision Processes[END_REF] and iPOMDP. Medusa is provided with the true number of states, while iPOMDP determines it automatically, similar to our approach. In all experiments, the iPOMDP and iDPOMDP are initialized in such a way that the observations are given vague hyperparameters, while the rewards are given hyperparameters that encourage peaked distributions. Beliefs are approximated with sample sets of 10 models. In all cases, tests have 200 episodes of learning, which interleave acting and resampling models, and 100 episodes of testing with the models fixed. The first benchmark scenario considered here, namely Tiger-3, is adopted from [START_REF] Doshi-Velez | The infinite partially observable Markov decision process[END_REF]; it comprises an environment that changes over time, thus allowing for us to evaluate the capacity of our model to adapt to new situations. Specifically, Tiger-3 is an adaptation of the well-known Tiger benchmark [START_REF] Littman | Learning policies for partially observable environments: scaling up[END_REF]: The agent has to choose one of three doors to open. Two doors have tigers behind them (resulting in the maximum possible penalty, r = -100), and one door has a small actual reward (r = 10). At each time step, the agent may either open a door or listen for the "quiet" door. It hears the correct door correctly with probability 0.85. The reward is unlikely to be behind the third door (p = 0.2). However, during the first 100 episodes, we artificially ensure that the reward is always behind doors 1 or 2. Subsequently, we employ the full probabilistic environmental model, under which the reward may also be behind the third door with some (low) probability. Hence, the dynamics of the environment change after the 100th episode, thus requiring that the trained agent be capable of quickly adapting to environmental changes.

The rest of our considered benchmarks are well-known problems in the POMDP literature. Specifically, we consider:

1. Tiger : This benchmark was first proposed in [START_REF] Littman | Learning policies for partially observable environments: scaling up[END_REF]. It is similar to Tiger-3, with the exception of the environment being static. Dynamics do not change after the first 100 episodes of the learning algorithm, but we consider the probability of the reward being behind the third door equal to p = 0.2 from the beginning of the simulation.

2. Shuttle: This benchmark was introduced in [START_REF] Chrisman | Reinforcement learning with perceptual aliasing: The perceptual distinctions approach[END_REF]. It considers two space stations separated by a small amount of free space with loading docks located on each station. The task is to transport supplies between the two docks. Each time the agent successfully attaches to the least-recently visited station, it receives a reward equal to r = 10. In order to dock, the agent must position itself in front of the station, with its back to the dock, and backup. Whenever the agent collides with the station by propelling forward into the dock, it receives a penalty of r = -3. In all other cases, we consider r = 0. 3. Gridworld [START_REF] Littman | Learning policies for partially observable environments: scaling up[END_REF]: This comprises a simple environment consisting of a 4-by-4 grid, where all cells except for the goal in the lower right-hand corner are indistinguishable. Movement into adjacent cells is permitted in the four compass directions, but an attempt to move off the edge of the world has no effect, returning the agent to its original state with no indication that anything unusual has happened. All states have zero reward, except for the goal (right-hand corner), which has a r = +1 reward, and a distinctive appearance. The initial state for this problem is a uniform distribution over all but the bottom right state. Any action taken from the bottom right state results in a transition to any one of the remaining zero reward states with equal probability (i.e., return to the initial distribution).

Our results are provided in Table 1. As we observe, our approach is capable of inferring a smaller number of states than the true count, only retaining states for which adequate information can be derived from the accrued experiences (training episodes); this is attained without any compromises in the yielded accumulated rewards in all scenarios. Given the fact that, as discussed in Section 2.3, drawing one sample from the dHDP by means of the block Gibbs sampler takes similar time as drawing one sample from the HDP, we deduce that our approach allows for obtaining improved total reward compared to the iPOMDP for decreased model complexity and resulting computational costs. Note also that the obtained performance improvement is more prominent in the case of the Tiger-3 problem, where the environment changes over time, thus posing greater learning challenges to the postulated agents. This finding vouches for the capacity of our model to capture non-stationarities in the modeled environments, which is the ultimate goal of this work. Further, in the first three columns of Table 2, we compare the execution times of our approach and the baseline iPOMDP method1 . As we observe, our method imposes a modest computational overhead, which averages at less than a 10% increase in computational costs compared to iPOMDP. Based on this result, and taking into consideration the better performance of our algorithm (in terms of total accrued reward), we can claim that our approach yields a favorable trade-off between performance and computational complexity compared to the competition.

Finally, in the last column of Table 2, we show how the proposed inference algorithm, based on an appropriate combination of Gibbs sampling with importance sampling, compares to the more straightforward approach of solely relying on Gibbs sampling to perform inference. As we observe, solely relying on Gibbs sampling to perform inference for our model results in an overwhelming increase in computational costs, which averages at almost one order of magnitude more time. Therefore, we deduce that our strategy of performing inference utilizing a combination of Gibbs sampling interleaved with importance sampling succeeds in considerably accelerating our algorithm, and is crucial for the practical applicability of our method.

Conclusions and Future Work

In this paper, we proposed a nonparametric Bayesian formulation of POMDPs that addressed the problem of capturing non-stationarities in the modeled environments. Formulation of our model was based on the imposition of a suitable dynamic prior over the state transitions of our model, namely the dHDP prior. We devised efficient learning and planning algorithms for our model, based on a combination of block Gibbs sampling and importance sampling. We showed that our method outperforms related alternatives, namely Medusa and iPOMDP, in several benchmark tasks, combining increased reward performance with shorter model sizes, and, hence, better computational complexity.

Our future goals in this line of research concern applying our approach to autonomous path planning for aerial robots (drones) operating in unknown, un-structured environments. We are also interested in extending our non-stationary models to address problems dealing with continuous state and actions spaces (continuous POMDPs).

p

  ( wt | . . . ) = Beta( wt |a + n th is the number of time points such that φ t = h. Similar, p(π s,a tl | . . . ) = Beta πs,a tl |α t β l + jt = 0)I(ν s,a jk = 0)

Table 1 .

 1 Experimental Evaluation: Number of inferred states and total obtained reward.

			#States			Total Reward
	Problem Actual iPOMDP iDPOMDP Medusa iPOMDP iDPOMDP
	Tiger-3	4	4.1	3.8	-40.26 -42.07	-35.19
	Tiger	2	2.1	2.1	0.83	4.06	4.64
	Shuttle	8	2.1	2.1	10	10	10
	Gridworld	26	7.36	6.82	-49	-13	-12

Table 2 .

 2 Experimental Evaluation: Execution times (in seconds) of the iPOMDP and iDPOMDP models. For iDPOMDP we evaluate both the proposed inference algorithm as well as applying (exact) Gibbs sampling.

	Problem iPOMDP iDPOMDP iDPOMDP-Gibbs
	Tiger-3	842.91	913.88	5863.18
	Tiger	837.67	912.07	5738.55
	Shuttle	839.11	894.32	5707.41
	Gridworld 1108.31	1207.15	8094.17

Our experiments were executed on a Linux desktop computer, with an Intel Xeon E5

2.10GHz processor. All the considered algorithms were implemented as singlethreaded Python applications.

Acknowledgments

This work was implemented under the Operational Program "Education and Lifelong Learning" action Archimedes III, co-financed by the European Union (European Social Fund) and Greek national funds (National Strategic Reference Framework 2007 -2013).