S V Georgakopoulos

S K Tasoulis
email: tasoulis@cs.helsinki.fi

I Maglogiannis

V P Plagianakos

On-line Fall Detection via Mobile Accelerometer Data

Keywords: Principal Component Analysis, Incremental Principal Component Analysis, Cumulative Sum, Smartphones, Accelerometer Sensor

Mobile devices have entered our daily life in several forms, such as tablets, smartphones, smartwatches and wearable devices, in general. The majority of those devices have built-in several motion sensors, such as accelerometers, gyroscopes, orientation and rotation sensors. The activity recognition or emergency event detection in cases of falls or abnormal activity conduce a challenging task, especially for elder people living independently in their homes. In this work, we present a methodology capable of performing real time fall detect, using data from a mobile accelerometer sensor. To this end, data taken from the 3-axis accelerometer is transformed using the Incremental Principal Components Analysis methodology. Next, we utilize the cumulative sum algorithm, which is capable of detecting changes using devices having limited CPU power and memory resources. Our experimental results are promising and indicate that using the proposed methodology, real time fall detection is feasible.

Introduction

The life quality improvement of social communities and individuals constitutes fundamental priority on a wide range of research fields. The opportunity that every human living independent of the continuous concern of the fellowmen, is integral right. At the same time, the population of elderly is increased, causing new requirement for social inclusion and access to healthcare.

In recent literature [START_REF] West | Do rates of hospital admission for falls and hip fracture in elderly people vary by socio-economic status?[END_REF][START_REF] Ong | The relationship between socioeconomic status and fracture in a fracture clinic setting: Data from the nottingham fracture liaison service[END_REF][START_REF] Melzer | Postural stability in the elderly: a comparison between fallers and non-fallers[END_REF] is reported that approximately 33% of elders over the age of 65 and 50% over the age of 85 experience a fall each year. Such incidents may cause light or serious injuries. The studies indicate that hip fractures of 50% of older people make them unable to live independently, while 25% and 33% of them will die within six months and a year, respectively. Falling injuries are frequently identified both in home and in hospital environments and make many elderly persons live under continue observation, causing discomfort. Discreet monitoring of the individuals in order to identify such major injuries, is a challenging task.

Several techniques have been produced to detect emergency events, having the common aspect of collecting sensor data in an attempt to interpret activity. More specifically, in the field of activity recognition with focus to fall detection, many recent studies can be found in the literature [START_REF] Doukas | Advanced sound and distress speech expression classification for human status awareness in assistive environments[END_REF][START_REF] Doukas | Advanced classification and rules-based evaluation of motion, visual and biosignal data for patient fall incident detection[END_REF][START_REF] Miaou | A customized human fall detection system using omni-camera images and personal information[END_REF][START_REF] Khawandi | Real time recognition of elderly daily activity using fuzzy logic through fusion of motion and location data[END_REF]. Some studies use microphones to detect falls, while others use information obtained by cameras that track the movement and the trajectory of humans in assisted environments, where long and/or unusual inactivity can be interpreted as a fall. Another approach is to use signals acquired by accelerometers and gyroscopes [START_REF] Noury | Monitoring behavior in home using a smart fall sensor and position sensors[END_REF]. To analyse these data, machine learning [START_REF] Ozdemir | Detecting falls with wearable sensors using machine learning techniques[END_REF] and statistical methods [START_REF] Lee | Detection of falls using accelerometers and mobile phone technology[END_REF] have been proposed.

In this work, we attend to discreetly monitor an individual using data from a smartphone (or a wearable sensor) that is equipped with a 3-axis accelerometer, to on-line detect falls. To interpret the accelerometer data, we project the three dimensional data to the principal component direction. Instead of computing the space of eigenvectors by the traditional Principal Component Analysis (PCA), which requires a batch computation step, we employ the Incremental Principal Component Analysis (IPCA). Finally, we incorporate a parametric model, which is able to detect the change at unknown time instants. The technique we used here is the Cumulative Sum (CuSum) algorithm [START_REF] Page | Continuous Inspection Schemes[END_REF].

The rest of the paper is structured as follows: In Section 2, background material for dimensionality reduction and classification methods are provided. In Section 3, we present the proposed methodology and the experimental results. Finally, Section 4 contains concluding remarks and pointers for future work.

Background Methods

In this section, we review the basic tools used in the proposed methodology. In particular, we present the Incremental Principal Component Analysis (IPCA) for the feature extraction task and the Cumulative Sum (CuSum) algorithm for the classification of the transformed data.

Incremental Principal Components Analysis

The typical computational approach to PCA requires all the data input to be available in order to compute the eigenvalues and eigenvectors of the sample covariance matrix, and thus it belongs to the category of batch methods. This approach is not feasible when the data are incrementally derived from an online stream. Thus, an incremental method is required to estimate the principal components for observations arriving sequentially. This can be achieved by updating the principal components for by each arriving observation vector, while avoiding to estimate the covariance matrix as an intermediate result. Here, for that purpose we employ the Candid Covariancefree IPCA (CCIPCA) method [START_REF] Weng | Candid covariance-free incremental principal component analysis[END_REF], which is based on the works of Oja and Karhunen [START_REF] Oja | On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix[END_REF] and Sanger [START_REF] Sanger | Optimal unsupervised learning in a single-layer linear feedforward neural network[END_REF]. A short description of the method follows.

Let d 1 , d 2 , . . . be the sample vectors that are acquired sequentially at each time point and let u 1 be the first principal component. Each d n , n = 1, 2, . . ., is a a-dimensional vector, where each dimension corresponds to an accelerometer signal for the case at hand. Without loss of generality, we can assume that d n has a zero mean, since the mean may be incrementally estimated and subtracted out. Then, the n-th step estimate u n 1 of u 1 is given by

u n 1 = n -1 -l n u n-1 1 + 1 + l n d n d T n u n-1 1 u n-1 1 ,
where (n -1)/n is the weight for the last estimate and 1/n is the weight of the new data, while the one dimensional projection y n onto u n 1 is given by

y n = u n 1 d n .
The positive parameter l is called the amnesic parameter. With the presence of l, larger weight is given to new samples and the effect of old samples will gradually fade out. Finally, to begin the iteration, we set u 0 1 = d 1 , the first direction of data spread. A mathematical proof of the convergence of CCIPCA can be found in [START_REF] Zhang | Convergence analysis of complementary candid incremental principal component analysis[END_REF].

Cumulative Sum

The Cumulative Sum (CuSum) is a change detection algorithm that can be used for off-line or on-line change detection. The CuSum has been firstly proposed in [START_REF] Page | Continuous Inspection Schemes[END_REF]. In this work, we utilize the on-line version of the algorithm.

To describe the functionality of the algorithm, we consider a sequence of independent random variables y n , which correspond to a signal for various discrete time instances n, with a probability density p θ (y), which depends only to the parameter θ. To capture the change of the signal at an unknown time instance t 0 , the parameter θ have to change from the initial value θ 0 (θ is equal to θ 0 ) to θ 1 where θ 0 = θ 1 . The approximation of these parameters that can be addressed using a training set of sample data.

More specifically, we assume the following hypotheses concerning the parameter θ:

H 0 : θ = θ 0 H 1 : θ = θ 1 (1)
In the fall detection problem considered here, the signal samples are captured by the accelerometer in real time and the proper hypotheses must be computed.

When the decision is continuously in favor of hypothesis H 0 , there is absence of signal change, while a decision in favor of H 1 corresponds to signal samples that indicate a change, i.e. a fall.

In this paper, the following notation will be used. Let

S n = n i=1 s i , where s i = ln p θ1 (y i ) p θ0 (y i ) (2)
is the log-likelihood ratio for the observations from y i to y n , where n is the current time instant and refer to s i as sufficient statistic. Considering the particular case where the distribution is Gaussian, with µ the mean value and σ the constance variance, when the changing parameter θ corresponds to µ. The probability density is denoted as

p θ (y) = 1 σ (2π) exp -(y-θ) 2 /2σ 2 (3)
and the sufficient statistic s i as

s i = θ 1 -θ 0 σ 2 (y i - θ 0 + θ 1 2 ). (4)
To detect the fall, at each instant time, the following decision rule is utilized:

g n = S n -µ n ≥ h, where µ n = min 1≥j≥n S j . (5)
The stopping time, denoted as t a , is

t a = min {n : g n ≥ h} (6)
and can be rewritten as

t a = min {n : S n ≥ µ n + h}. (7)
The above decision rule compares the cumulative sum S n and the adaptive thresholding µ n + h, since the µ n keeps memory of the past observations whereas, the parameter h must be specified. The parameter h is critical, affects the decision rule threshold and therefore the signal change correctness.

Proposed Method and Experimental Results

In this section, we describe the technical details of the proposed methodology and we examine its efficiency on processing mobile accelerometer data for on-line fall detection. To construct the training set, accelerometer data were recorded using a smartphone that was in the pocket or purse of walking and falling volunteers. The sampling time during the motion is divided to timesteps, each timestep corresponds to the acquired accelerometer sensor data (approximately 12ms). Consequently, using the same mobile device and settings, the test set was constructed.

To detect the change in the data, the CuSum algorithm needs the mean values of the walking and falling states. Using the training set experiments, we can easily compute these mean values. Additionally, we have supplied the CuSum algorithm with a value for the parameter h. Since different values may lead to different results, a wide range of possible values of h parameter was tested. Below, we report the most promising region for h values and the corresponding results (Table 1). Figure 1 illustrates an example of raw data recorded by the 3-axis accelerometer. In this experiment, an actual fall occurred approximately at timestep t = 1800. Note that the three axes are not equally sensitive regarding the fall; in this experiment y-axis seems to be less informative. Additionally, because of the possible rotation of the device during the fall, there also exists the problem of accelerometer values to shift from one axis to another.

As a first experiment, since the CuSum algorithm can be applied only on one dimensional input data, we apply it to each of the three axis independently. Figure 4 exhibits the data recorded along the x-axis (left) and the output of the CuSum algorithm (right). Note that the actual as well as the detected fall is indicated by a red dot. Figures 5 and6 show similar plots regarding the y-axis and z-axis, respectively. In this experiment, as it was expected, if the CuSum algorithm is executed using as input the x-axis (or z-axis) data, the fall is reliably detected. On the other hand, y-axis data do not provide enough information and the CuSum fails to detect the fall incidence. To alleviate the problem of having to choose (for each experiment) the correct axis that captures adequate information regarding the fall, we have employed the Principal Component Analysis (PCA) method. Using the PCA method, the 3-dimensional signal of various walking and falling cases is utilized to compute the corresponding space of eigenvectors. Next, the new input data are projected on the direction of the eigenvector that corresponds to the largest eigenvalue. To this end, the transformed signal becomes one dimensional, capturing the most significant information of the original signal. Finally, the CuSum algorithm is applied to detect the change. Figure 2 exhibits a successfully detected fall.

Although this approach gives relatively good results, it requires the PCA method, which demands a batch computation step for the calculation of the eigenspace. Since in this study our aim is the on-line fall detection, we employ the Incremental Principal Component Analysis (IPCA), in an attempt to achieve higher classification results using sensor data streams. As a first step, the classic PCA method is applied on the training set (comprised of many walking and falling samples) to compute the initial eigenspace. Subsequently, each incoming input signal updates the eigenspace and is projected on the direction of the eigenvector corresponding to the largest eigenvalue. The transformed onedimensional data series is then fed to the CuSum algorithm to detect changes, i.e. falls. Figure 3 illustrates the transformed signal and the output of the CuSum algorithm. In this instance, the fall was successfully detected.

Finally, to further evaluate the efficiency of the proposed methodology we use two metrics; the number of "false alarms", which is the number of times that the algorithm mistakenly reports a fall and the "delay", i.e. the time elapsed between the actual and the detected fall. In Table 1 the results of CuSum algorithm for the different scenarios discussed above are presented. When the x-axis or the z-axis were used, correct fall detection was possible for specific values of parameter h. On the other hand, y-axis provided no information regarding the fall, so the CuSum algorithm failed [START_REF] Tasoulis | Statistical data mining of streaming motion data for activity and fall recognition in assistive environments[END_REF]. The PCA method, utilizing information from the three accelerometer axis, gave better results (less false alarms, lower delay). However, the h parameter still needs fine tunning. Finally, the proposed methodology seems more robust to different parameter h values. The range of acceptable h values can lead to real time fall detection without false alarms.

As a general remark it must be noted that larger values for the parameter h may lead the CuSum algorithm to be more accurate (less false alarms), but increase the delay, as well. On the other hand, lower h values reduce the delay, but introduce more false alarms. Thus, the proposed algorithm having a wider region of acceptable h values can be successfully utilized to on-line real time fall detection.

Conclusion

In this work, we present an on-line real time fall detection methodology that detects falls utilizing the 3-axis accelerometer data obtained by the sensor of a smartphone. Human falls were detected using signal change detection by the Cumulative Sum (CuSum) statistical data mining algorithm.

Original 3-axis data were projected on to a suitable direction computed by the Incremental Principal Component Analysis. The experimental results indicate that the proposed methodology is capable to detect falls in real-time. In a future work we intend to incorporate additional sensors (e.g. microphone) to improve the accuracy of our system and enhance the smartphone application. In addition, we will apply our methodology to public fall datasets and make a comparative analysis with other methods.

Fig. 1 .

 1 Fig. 1. The time sequence of the three accelerometer axes.

Fig. 2 .

 2 Fig. 2. Data series of the accelerometer data projected on the first PCA eigenvector (left) and the corresponding CuSum decision function (right). The red dot denotes the actual and the detected fall. In this instance, the CuSum algorithm successfully detected the fall.

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

 345 Fig. 3. Data series of the accelerometer data projected on the first IPCA eigenvector (left) and the corresponding CuSum decision function (right). The red dot denotes the actual and the detected fall. In this instance, the CuSum algorithm successfully detected the fall.

Fig. 6 .

 6 Fig. 6. Data series of the accelerometer z-axis (left) and the corresponding CuSum decision function (right). The red dot denotes the actual and the detected fall. In this instance, the CuSum algorithm successfully detected the fall.

Table 1 .

 1 Experimental Results

	h	0.010 0.050 0.100 0.150 0.200 0.500 1.000 1.500 2.000
	Accelerometer Axis X
	False Alarm	112 27	9	5	1	1	0	0	0
	Delay (timesteps)	6	7	28	39	39	54	78	91 101
	Accelerometer Axis Y
	False Alarm	-	-	-	-	-	-	-	-	-
	Delay (timesteps)	-	-	-	-	-	-	-	-	-
	Accelerometer Axis Z
	False Alarm	21	13	9	6	5	2	1	0	0
	Delay (timesteps)	7	8	8	9	9	15	17	22	26
	PCA Projection
	False Alarm	130 47	18	10	3	0	0	0	0
	Delay (timesteps)	7	40	44	88	92 103 122 141 162
	IPCA Projection
	False Alarm	88	29	11	2	0	0	0	0	0
	Delay (timesteps)	1	1	3	4	5	7	18	31	45

Acknowledgments. The authors would like to thank the European Union (European Social Fund ESF) and Greek national funds 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", for financially supporting this work.


Stamatios Giannoulakis
email: s.giannoulakis@cut.ac.cy

Nicolas Tsapatsoulis
email: nicolas.tsapatsoulis@cut.ac.cy

Instagram hashtags as image annotation metadata

Keywords: Instagram, hashtags, image tagging, image retrieval, machine learning

Image tagging is an essential step for developing automatic image annotation methods that are based on the learning by example paradigm. However, manual image annotation, even for creating training sets for machine learning algorithms, requires hard effort and contains human judgment errors and subjectivity. Thus, alternative ways for automatically creating training examples, i.e., pairs of images and tags, are pursued. In this work we investigate whether tags accompanying photos in social media and especially the Instagram hashtags, provide a form of image annotation. If such a claim is proved then Instagram could be a very rich source of training data, easily collectable automatically, for the development of automatic image annotation techniques. Our hypothesis is that Instagram hashtags, and especially those provided by the photo owner / creator, express more accurately the content of a photo compared to the tags assigned to a photo during explicit image annotation processes like crowdsourcing. In this context, we explore the descriptive power of hashtags by examining whether other users would use the same, with the owner, hashtags to annotate an image. For this purpose a set of 30 randomly chosen, from Instagram, images were used as a dataset for our research. Then, one to four hashtags, considered as the most descriptive ones for the image in question, were selected among the hashtags used by the image owner. Three online questionnaires with ten images each were distributed to experiment participants in order to choose the best suitable hashtag for every image according to their interpretation. Results show that an average of 55% of the participants hashtag choices coincide with those suggested by the photo owners; thus, an initial evidence towards our hypothesis confirmation can be claimed.

Introduction

On average 350 million photos are uploaded to Facebook per day [START_REF]A Focus on Efficiency. A white paper from Facebook, Ericsson and Qualcomm[END_REF] while an average of 70 million photos are shared every day in Instagram [START_REF]Intsagram: Introducing Layout from Instagram[END_REF]. Thus, the total amount of images in the Web nowadays is huge and continuously increasing. Locating and retrieving these images is very challenging not only in terms of effectiveness (retrieve the right image according to the user needs / queries) and efficiency (execution time) but also in terms of visibility (being locatable). Contemporary search engines retrieve images in a text-based manner since the majority of end users are familiar with text-based queries for retrieving web pages and digital documents. In text-based image retrieval images must be somehow related with specific keywords or textual description. This kind of textual description is, usually, obtained from the web page, or the document, containing the corresponding images and includes HTML alternative text, the file names of the images, captions, metadata tags and surrounding text [START_REF] Ntalianis | Automatic annotation of image databases based on implicit crowdsourcing, visual concept modeling and evolution[END_REF]. However, images in social media, which constitute the great majority of images in the Web, cannot effectively indexed (extract relevant text description) with pure webbased techniques mainly because the user pages in social media do not follow the classic web-page structure. As a result a new research field dealing with this problem emerged: Automatic Image Annotation (AIA) [START_REF] Hanbury | A survey of methods for image annotation[END_REF], that is the process of extracting low-level features from an image and assigning one or more semantic concepts to it [START_REF] Jin | Automatic image annotation using feature selection based on improving quantum particle swarm optimization[END_REF].

A large category of AIA involves machine learning techniques and is based on the learning by example paradigm [START_REF] Theodosiou | Image retrieval using keywords: The machine learning perspective[END_REF]. Training examples that are used for automatic image annotation are pairs of images and related tags. Different models and machine learning techniques were developed to build the so called 'visual models', that is, models that capture the correlation between image features and textual words from the training examples. Visual models are then fed with image features extracted from unseen images to predict their tagging [START_REF] Snoek | Concept-based video retrieval[END_REF]. Assuming that good visual models can be achieved, image retrieval using the training by example paradigm provides a promising alternative to text-based methods (since it does not require explicit annotation of all images in the collection, but only a small set of properly annotated images) [START_REF] Theodosiou | Crowdsourcing annotation: Modelling keywords using low level features[END_REF]. Nevertheless, the first important step to create effective visual models is to use good training examples (pairs of images and annotations). In this context automatic creation of training examples via crawling is highly desirable because it addresses the scalability (models for new concepts) and adaptability (modification of training models) issues.

According to a survey of Pew Research Internet Project, Instagram is the fastest growing social network among the adult Americans who use the Internet [START_REF]A Focus on Efficiency. A white paper from Facebook, Ericsson and Qualcomm[END_REF]. Instagram is a free application for mobile devices, which offer user the possibility to upload, edit and share with other pictures and very short video. The term Instagram is a combination of two words, from the word instant used to market old cameras and the gram comes from telegram from the snapshots people were taking1 . Instagram launched on 6 October 2010 and rapidly gained popularity, managed to have 300 million active users per month and 70 million pictures per day [START_REF]Intsagram: Introducing Layout from Instagram[END_REF] being shared. In January 2011 Instagram added hashtags [START_REF] Baranovic | What #hashtags mean to mobile photography[END_REF] and from 27 April 2015 users are able to use emoji as hashtags 2 . Hashtags are tags or words prepended with '#' used to indicate the content of the picture, allowing users to search for pictures and increase visibility. Emoji are pictograms, which are connected with emotions a user wants to give to the picture. The story of hashtags began with IRC (Internet Relay Chat) where the users used it in order to categorize items into groups. The first who used hashtags in Twitter was designer Chris Messina who asked from his followers how they felt about using the pound sign to group conversations [START_REF] Bennett | The history of hashtags in social media marketing[END_REF]. Thus, we can conclude that the role of hashtags was traditionally to organize knowledge and facilitate access and enable retrieval of information. On the other hand, we know that users extend the function of hashtagging beyond findability and give hashtags a metacommunicative use. The metacommunicative function can be grouped into the following codes: Emphasizing, Iterating, Critiquing, Identifying, and Rallying. Emphasizing is used to give emphasis or call attention, Critiquing in order to express judgment or verdict, Identifying to refer to the author of the post, Iterating to express humor and Rallying to bring awareness or support to a cause [START_REF] Daer | Rhetorical Functions of Hashtag Forms Across Social Media Applications[END_REF]. In a research on the tags of a set of 2700 pictures it was measured that approximately 10% of these photos were related with emotion words not directly related with their visual [START_REF] Carmean | Selfie examinations?: applying computer vision, hashtag scraping and sentiment analysis to finding and interpreting selfies[END_REF].

It should be evident from the above discussion that Instagram provides a rich forum for automatically creating training sets for AIA. It contains a huge amount of images which are commented through hashtags by their creators / owners. Thus, if we assume that it is the owner who can better expresses the real visual content or meaning of an image then choosing among the hashtags for assigning tags to images is much more safe than traditional text-based indexing approaches. This is extremely important in training sets where pairs of images and tags have to be carefully selected because they affect the effectiveness of tag predicting models. However, Intsagram hashtags are used not only to describe the visual content of an image but also serve other functions falling under the metacommunicative use. In this work we are trying to check the extent to which hashtags are indeed related with the actual content of an image and the percentage of hashtags that are relevant to Instagram photo compared to those referring to metacommunicative use.

Related work

To the best of our knowledge this is the first work that examines the appropriateness of Instagram photo-hashtag pairs for creating training sets for AIA. However, this problem falls under a more broad category dealing with the quality of manual image annotation. Nowak & Ruger [START_REF] Nowak | How reliable are annotations via crowdsourcing? A study about inter-annotator agreement for multi-label image annotation[END_REF] investigated the reliability of image annotation via crowdsourcing. They tried first to explore to which extent several sets of expert annotations differ from each other and then to investigate whether non-expert annotations are reliable. The researchers selected a subset of 99 images from the MIR Flickr Image Dataset. The aforementioned set of images was annotated by 11 expert annotators from the Fraunhofer IDMT research staff using 53 concepts. The same set of images was distributed over the online marketplace Amazon Mechanical Turk in order get non-expert annotations. The consistency among expert annotators proved to be very high. The same also proved between the expert and non-expert groups. Thus, the conclusion was that crowdsourced annotation is as accurate as experts' annotation. Since the cost of crowdsourcing annotation is far more cheeper and efficient than experts' annotation this conclusion opened up new ways towards AIA. The importance of crowdsourcing annotation lead to several research efforts which further examine the quality of crowdsourced data. In crowdsourcing annotation the participants expose different behavior during the annotation task. There are many reasons for the aforementioned behavior including the level of expertise, low-attention / low-concentration when they perform the task and there is always the bad intent of the annotators. Examples of annotators with bad intention can be spammers, dishonest or try to manipulate the system by answering in an unrelated or nonsense way [START_REF] Kara | Modeling annotator behaviors for crowd labeling[END_REF]. In a research about crowdsourcing annotators' consistency Theodosiou et. al. [START_REF] Theodosiou | Crowdsourcing annotation: Modelling keywords using low level features[END_REF] used both vocabulary keywords and free keywords to check whether guided annotation (as assumed by the use of structured vocabulary) would increase annotation consistency. The researchers concluded that, indeed, by combing free keywords and vocabulary keywords annotation consistency increases compared to the use of free keywords alone.

Even the crowdsourced data are far more difficult to collect than data crawled from the Web. This was recognized by Tsikrika et. al [START_REF] Tsikrika | Reliability and effectiveness of clickthrough data for automatic image annotation[END_REF] who examined the quality of clickthrough data for training concept detectors in images. They showed that clickthrough data, if properly filtered, would be used for AIA. The problem with clickthrough data is that they express the interpretation of end users rather than this of the image creators / owners, and, thus, they are highly subjective. Despite that, the use of clickthrough data for developing AIA models is an attractive approach and Microsoft Research announced, for a second year in a row, a challenge based on data provided by Bing search engine 3 .

In order to examine the image retrieval from social media and especially the diversification of image retrieval results, Ionescu et. al [START_REF] Ionescu | Result diversification in social image retrieval: a benchmarking framework[END_REF] compared experts and crowdsourcing annotation. The results showed that in the crowdsourcing annotation the inter-rater agreement were a slightly lower than expert annotators. Our assumption is that the owners' annotation data (in our case Instagram hashtags) are more close to experts' annotation compared to that of crowdsourcing since the latter expresses the end-users' perspective. Furthermore, web-crawled data are far more easier to collect than crowdsourcing ones. Among the web-crawled data the ones collected from Instagram are much more accurate (in terms of descriptive value) compared to those used in traditional web-document indexing (keyword extraction from web-pages) while they are richer than those collected via clickthroughs.

Methodology

In order to derive concrete results, in our study we followed a hybrid methodology combing a set up from social science research with a strict mathematical 3 http://research.microsoft.com/en-us/projects/irc/ framework which is common in natural sciences. We decided to define clear research questions and properly select the participants of the experiment rather than randomly choosing among ordinary users of social media. We consider that in order to assess the descriptive value of Instagram hashtags of the photo owners / creators we need users that are familiar both with the social media and the use of metadata in digital content. Librarians would be ideal for this purpose. They use social networks daily and one of their main tasks is to organize knowledge and annotate electronic resources, so we can say they are, in some respect, experts in image annotation. Moreover, undergraduate and postgraduate university students are also good candidates for the population group because social media are highly popular among students as we can conclude from the survey of Pew Research Internet Project [START_REF] Duggan | Social Media Update[END_REF].

Aim of the research

The present study has two goals. The first is to investigate whether Instagram hashtags accompanying images can be used as image tags so as to create imagetag pairs for training machine learning approaches for AIA. The second is to provide a rough estimation on the percentage of Instagram hashtags that describe the visual content of accompanying images. Towards this end we have designed a questionnaire which includes a total number of 30 randomly selected pictures from 18 Instagram users. Owners' hashtags surrounding these images were automatically crawled using the Beautiful Soup4 library of Python. Then we chose, manually, 1 to 4 hashtags for each picture, which, according to our interpretation, better describe its visual content. As already stated not all hashtags are intended to describe image on increasing its findability. The selected hashtags along with irrelevant hashtags are presented below each picture, in the questionnaire, and the participants are asked to choose among them the ones that better describe the shown photo. Fig. 1 presents an example. Among the eight choices given only three are hashtags the owner of the photo used in the Instagram. If participants' choices coincide with the hashtags the owner gave we have a good indication that these hashtags are, indeed, related with the visual content of the picture (since what the participants see is the context-free picture without any sort of metadata).

Data collection

The data for this survey were gathered using an online questionnaire designed with the aid of Surveymonkey 5 . The 30 pictures were divided in three separate questionnaires containing 10 pictures each. The aim was to reduce the time required to fill in the questionnaire and avoid fatigue effects. The choices given below each picture are either 4 or 8 depending on the number of hashtags the owner used. If only one hashtag of the owner was present then the choices given Fig. 1. An example of an image interpretation multiple choice question to the participants were four (including the hashtag of the owner); otherwise the participants were given eight options to select from. This rule was applied in order to keep a minimum chance level higher than or equal to 25%. In any case, participants were not aware that any of the given choices were related in any respect with the picture; thus, they were free to select as many of them as they wished according to their interpretation of the shown photo.

Initially, the three online questionnaires were distributed by electronic mail to three experts in order to evaluate them. The results of the evaluation assisted the creation of a more appropriate version which was, then, distributed by electronic mail to librarians of the library of Cyprus University of Technology and to undergraduate and postgraduate students of the department of Communication & Internet Studies. It is important to mention, here, that each participant group, librarians, undergraduate and postgraduates students was randomly divided so as to distribute the three questionnaires equally in each group. The survey was conducted between March, 19th and March 31st, 2015. A total of 39 questionnaires were collected and used for analysis.

Mathematical Formulation

Let us denote by P i the i-th participant (i=1,...,N P ) of a total of N P participants (N P = 39 in this study as already mentioned above). We also denote with I j the j-th image (j=1,...,N I ) in the image dataset where N I is the total number of images (in our case N I = 30). By set H = {h 1 , h 2 , ..., h N H } we define the set of hashtags the owners / creators used to tag the images in set I while N H is the total number of tags used for this purpose.

In order be able to conclude on the research questions defined earlier we must use some effectiveness measures. For this purpose we modified the well known Recall, Precision and F-measures [START_REF] Hersh | Information Retrieval: A Health and Biomedical Perspective[END_REF] to fit in with the current experiment. In particular we define the participant's P i recall value, R ij , for image I j as the proportion of owner's hashtags, for this image, that were selected by P i in the questionnaire. In a mathematically formal way this is given by:

R ij = ||T jc ∩ T ji || ||T jc || (1)
where T jc is the set of distinct hashtags assigned to image I j by the image owner, T ji is the set of distinct hashtags the participant P i assigned to image I j (based on the choices presented to him/her in the questionnaire), ∩ is the set intersection operation and ||Ω|| denotes the cardinality of set Ω.

Aggregating the R ij across all participants and all images we define per image and per participant recall values, R j and R i , respectively:

R j = 1 N P N P i=1 R ij (2)
R i = 1 N I N I j=1 R ij (3)
In a similar manner we define per image (see eq. 5) and per participant precision (see eq. 6), i.e., the proportion of a participant's choices that coincide with owner's hashtags, and F-measure (harmonic mean of recall and precision) as follows:

P ij = ||T jc ∩ T ji || ||T ji || (4)
(precision of participant's P i choices for j-th image)

P j = 1 N P N P i=1 P ij (5)
P i = 1 N I N I j=1 P ij (6)
F j = 2 • R j • P j R j + P j ( 7
)
F i = 2 • R i • P i R i + P i (8)
Let us now assume an index of hashtags V in which all the hashtag choices presented to the participants though the questionnaire images are concatenated. That is, if in the questionnaire the participants are asked to choose between 8 hashtags in the first image then these hashtags are the first 8 entries of vector V . The available hashtag choices for the second image of the questionnaire will follow, then that of the third image and so on. Note that in index V the same hashtag may appear more than once and in different position indicating a particular choice for a specific image. If we denote with '1' the hashtags chosen by a specific participant and with '0' the hashtags not chosen then a participant P i can be represented by a binary vector P i , with length equal to that of index V , denoting his / her 'profile'. In a similar way we can define the creators / owners vector, say C in which the hashtags used by the photo owners are represented with ones and hashtags not used by zeros. Obviously, the vector C does not correspond to a specific user profile but to the aggregated profile of all photo owners. The similarity of images' interpretation between photo owners / creators and each one of the participants can be, then, estimated by any vector comparison metric. Because both vectors C and P i are binary ones the choose of Hamming distance [START_REF] Kulshrestha | On the Hamming Distance Between Base-N Representations of Whole Numbers[END_REF] is evident. The aforementioned distance was introduced by Richard Hamming, is implied only at two equal strings and gives the number of positions at which corresponding symbols differ [START_REF] Kulshrestha | On the Hamming Distance Between Base-N Representations of Whole Numbers[END_REF].

Thus, the similarity S(C, P i ) between the choices a participant P i made in order to characterize the images in the questionnaire with the actual hashtags the owners used, is given by:

S(C, P i ) = 1 - h(C, P i ) L (9)
where h(C, P i ) is the Hamming distance of vectors C and P i and L is the corresponding vector space dimension (i.e., the length of vectors C and P i and index V ).

Experimental Results and Discussion

The data of the 39 filled in questionnaires were analyzed with aid of SPSS6 , MS Excel7 and the MATLAB8 platform using the metrics defined in the previous section. Fig. 2 shows the per participants' Recall (eq. 3), Precision (eq. 6) and F-measure (eq. 8) of the 10 pictures each participant had to interpret in the experiment. As already explained not all participants evaluated all images; thus, the computations were done using the subsets of images shown to the participants according to the questionnaire they war given. In practice, this means that N I in equations 3, 6, 8 was equal to ten (the number of images in each questionnaire). Some basic statistics of the per participant Recall, Precision and F-measure are shown in Table 1. We see there that the recall performance per participant is 0.55 ± 0.15 with the extreme values being 0.23 (minimum) and 0.78 (maximum). Thus, the conclusion is that at least one out two hashtags used by the owner in Instagram images is relevant to image content since other users consider it descriptive as well. The variation in performance, among users, is rather low indicating that in the experiment there were no spammers or users with dishonest behavior. The per participant precision is significantly higher (0.67 ± 0.12) than recall, showing the tendency of people to use as few as possible keywords to describe an image. This is in agreement with the generic behavior of Web users who use, on average, one to three keywords when searching for information through search engines. Of course we do not know whether this is an intrinsic human tendency or a behavior cultivated by the way search engines work (the fewer the keywords given the more the results presented to the user). Furthermore, the high precision values indicate also that the participants did not answer (chose hashtags for the shown images) randomly.

Overall, with the aid of Fig. 2 and Table 1 we can conclude on both research questions set in this study. Given that the participants in our experiments can be seen as experts (librarians and students of internet and communication studies) we can claim that around 55% of the Instagram hashtags that accompany images relevant to the actual content of the images and can be used for training purposes. By pointing out that on average only 40% of the (owner's) Instagram image hashtags are relevant to the images close to which they appear we can state that on average 22% (0.55 • 0.4) of Instagram hashtags are related with the visual content of images.

Figure 3 shows the dissimilarity of image interpretation between each one of the participants and the photo owners with the aid of (normalized) Hamming distance and the mathematical formulation presented in the previous section. By normalized we mean that the Hamming distance is divided by the length of the strings compared (in our case total number of choices presented to the users in the 10 questions of the questionnaire they took). As we see in Table 2 the average normalized Hamming distance between the photo owners and the participants is 0.245 ± 0.048. This means that there is less than 25% disagreement (only one out of four hashtag choices between image owners and participants differ); thus, we can confirm, once again, that the participants do not answer at random or in any dishonest manner. By looking at the extreme values in Fig. 3 we see that only two users (those with ids 22 and 25) show somehow low performance (high dissimilarity with the interpretation of picture owners) but even in these cases no random or dishonest behavior can be justified since the average Hamming distance is well below 40%. On the other hand, the users with ids 3 and 31 present an excellent performance which indicates that even perfect matching between owners and participants is not impossible; this means that the hashtags given by the owners to the photos are indeed related with the visual content of images (i.e., what the images actually show and not, for instance, context or emotional information). In Fig. 4 we present the per image Recall (eq.2), Precision (eq.5), and Fmeasure (eq.7) values while in Table 3 are shown summary statistics for those values. The basic aim of this analysis is to check whether the difficulty of interpreting images depends on their visual content. ComparingTables 1 and 3 we observe that the variation of Recall, Precision, and F-measure across images is higher than that across participants. The same also holds for the extreme values. Thus, we can conclude that image content affects interpretability. On the other hand, in Fig. 5 we show the images with the lowest recall and precision scores (from left to right images with ids 2, 20 and 28). In a first glance it does not seem that these images present abstract concepts, which are, generally, difficult to interpret. Thus, probably the owners hashtags for these image might be irrelevant with their visual content causing a different interpretation by the experiment participants. In the last part of our analysis we deal with the recall values of the hashtags.

Our assumption is that abstract concepts should have lower recall values than concepts referring to tangible objects. Figure 6 presents the recall values for all owners' hashtags (the set H mentioned in Section 3.3). It is clear that abstract concepts tend to have low recall values, as expected, however, the three out of four concepts that have zero recall refer to places (Florida, Chile, Indochina). This lead us to the conclusion that out of context interpretation of images is, in some cases, problematic. Nevertheless, the difficulty of interpretation in this case does not necessarily mean that the hashtag used by the owner is inappropriate for characterizing the particular image. By saying so we mean that the pair image-hashtag is still a good training example.

Conclusion

In this paper we have presented our study about the descriptive value of Instagram hashtags as metadata for the images they accompany. By measuring if the participants would choose the same hashtags with the image creator / owner we found that in the 55% of the chosen hashtags participants and owners agree that the suggested hashtags can describe the visual content of an image. Moreover, we have an indication that almost 30% of the Instagram hashtag datasets are appropriate for use in training examples (image -tag pairs) for machine learning algorithms. The results show also that an important portion of image hashtags in Instagram are not directly related with the concept depicted by the image. We have found also that both the image content and the context in which an image resides affect interpretability. However, as we explained, this does not necessarily implies that the pairs images -difficult to interpret tags are invalid for training purposes.

Further research, including larger participants' and images' population, has to be done before the indications extracted in the current study become solid conclusions. For this purpose we have already started an automated process for dynamically creating online image interpretation questions with the aid of a MySQL database schema and PHP programming. This will allow larger participation in the experiment and automatic analysis of the results.

Another action that can be taken in the future is to check the validity of image-hashtag pairs for training visual concept models (see [START_REF] Theodosiou | Image retrieval using keywords: The machine learning perspective[END_REF]) in practice. This will lead us to a second, practical, stage of investigation and will allow comparison of the theoretical findings of this study with practical issues faced during training. However, we must be aware that, in machine learning, good training examples must be properly processed to extract appropriate, for learning, low level features; this is by no means an easy task.

Fig. 3 .Fig. 4 .

 34 Fig. 3. The hamming distance between participants and image owners / creators

Fig. 5 .

 5 Fig. 5. Difficult to interpret images

Fig. 6 .

 6 Fig. 6. Percentage of the participants that chose each of the owner / creator hashtags

Table 1 .

 1 Per participant Recall, Precision and F-measure value statistics

		Mean St. Dev. Minimum Maximum
	Recall	0.55	0.15	0.23	0.78
	Precision 0.67	0.12	0.47	1.00
	F-measure 0.56	0.12	0.33	0.77

Fig. 2. Average hashtags' recall, precision and F-measure per participant

Table 2 .

 2 Statistics of normalized Hamming distance between participants and photo owners in image interpretation

	Mean St. Dev. Minimum Maximum
	0.245 0.048	0.138	0.375

Table 3 .

 3 Per image Recall, Precision and F-measure value statistics

		Mean St. Dev. Minimum Maximum
	Recall	0.55	0.18	0.15	0.91
	Precision 0.67	0.22	0.22	1.00
	F-measure 0.56	0.17	0.17	0.90

Instagram: FAQ, https://instagram.com/about/faq/#

Instagram: Our Story, https://instagram.com/press/

http://www.crummy.com/software/BeautifulSoup/bs4/doc/

http://www.surveymonkey.com/

http://www-01.ibm.com/software/analytics/spss/

https://products.office.com/en-us/excel

http://www.mathworks.com/products/matlab/


Sondre Glimsdal

Ole-Christoffer Granmo

Thompson Sampling Guided Stochastic Searching on the Line for Adversarial Learning

Keywords: N-Door Puzzle, Multi-armed Bandit Problem, Adversarial Learning, Bayesian Learning, Thompson Sampling

The multi-armed bandit problem has been studied for decades. In brief, a gambler repeatedly pulls one out of N slot machine arms, randomly receiving a reward or a penalty from each pull. The aim of the gambler is to maximize the expected number of rewards received, when the probabilities of receiving rewards are unknown. Thus, the gambler must, as quickly as possible, identify the arm with the largest probability of producing rewards, compactly capturing the exploration-exploitation dilemma in reinforcement learning. In this paper we introduce a particular challenging variant of the multi-armed bandit problem, inspired by the so-called N-Door Puzzle. In this variant, the gambler is only told whether the optimal arm lies to the "left" or to the "right" of the one pulled, with the feedback being erroneous with probability 1 -p. Our novel scheme for this problem is based on a Bayesian representation of the solution space, and combines this representation with Thompson sampling to balance exploration against exploitation. Furthermore, we introduce the possibility of traitorous environments that lie about the direction of the optimal arm (adversarial learning problem). Empirical results show that our scheme deals with both traitorous and non-traitorous environments, significantly outperforming competing algorithms.

Introduction

A reinforcement learning (RL) problem, at the most basic level, consists of a learner that interacts with a teacher, often also called the environment. The learner performs some action and the teacher either rewards or penalizes the learner to reinforce a particular behavior. In most cases the teacher is modeled with a stochastic component that represents noise or imperfection in the environment. Traditionally, the teacher is restricted to be on-average informative. That is, given that the learner performs the intended behavior, the teacher will more often than not reward the learner. This allows the learner to, over time, identify the correct behavior. However, in this paper we also consider the highly interesting scenario where the teacher may also be of a deceptive nature, giving a penalty on correct behavior instead of a reward. This leads to a novel variant of the well known exploration versus exploitation dilemma. Should the learner trust the teacher and follow the teachers advice (exploit) or should the learner try to explore the truthfulness of the teacher.

A puzzle found in the book "To Mock a Mockingbird" [? ] illustrates this point: "Someone was sentenced to death, but since the king loves riddles, he threw this guy into a room with two doors. One leading to death, one leading to freedom. There are two guards, each one guarding one door. One of the guards is a perfect liar, the other one will always tell the truth. The man is allowed to ask one guard a single yes-no question and then has to decide, which door to take. What single question can he ask to guarantee his freedom?"

To avoid spoiling the puzzle for any interested reader, we omit the solution here and note that asking a double negative question will often be the correct course of action in these types of puzzles. Extending this puzzle into a general setting, lead us to the N-door puzzle: Here instead of simply 2 doors, the prisoner is faced with N doors, with a guard posted between each door. Now, a sole door leads to freedom and the remaining doors leads to death. At sunrise each day the prisoner is allowed to ask a single guard if the door is to the guards left or to the guards right. However, only a fixed proportion of the guards answers truthfully, the rest are compulsive liars, and since the guards are randomly assigned a position each sunrise, knowing who lies and who tells the truth is impossible. As an additional complication, depending on the mood of the king, the prisoner may be ordered to walk through one door of his choosing at an arbitrary day. Therefore, to save his life, it is imperative that the prisoner as quickly as possible zero in on the door leading to his freedom.

The N-door puzzle is a reinforcement learning puzzle where the agent (the prisoner) at each iteration chooses freely between N -1 guards, each stationed between two doors. However, what separate N-door from traditional RL problems is the possible existence of a deceptive teacher. Let π = #truthful guards #guards be the ratio of truthful guards. As the guards are randomly assigned each day the probability of a truthful answer is governed by π. If π < 0.5 then the majority of the guards are compulsive liars and the guards, as an entity are said to be deceptive. Conversely, if π > 0 then the majority of the guards are truthful and the the guards can be seen as informative. For completeness we mention that the puzzle is unsolvable for the case where π is exactly equal to 1

2 as each answer is then turned into a coin flip with a fair coin and consequentially voiding any possible information gain.

Since the guards or teacher may be deceptive the traditional RL approaches is rendered ineffective, as they inherently trust the teacher to on average be informative. To handle the case of a possibly deceptive teacher any solution scheme must not only use the feedback provided by the guards to locate the door that leads to freedom but also learn the nature of the guards. Are they informative or deceptive?

This paper introduces Thompson Sampling guided Stochastic Point Search (TS-SPL) -a novel scheme for solving the N-door puzzle. A probabilistic model of all possible N-door instances is simultaneously explored and exploited as determined by Thompson Sampling (TS), gradually filtering away unlikely instances until we have identified the correct one, thus revealing the optimal decision. This means that instead of directly solving the N-door puzzle, we -in a Bayesian line of thought -start with all possible N-door puzzles and progressively try to determine which puzzle has the highest probability of giving us the current feedback.

As we shall see, not only does this scheme handle an arbitrary level of noise, but it also exhibits better performance characteristics than the current state of art. TS-SPL also fulfill the anytime component of the N-door puzzle, namely that the prisoner should be able, at any time, to provide a best guess on what door leads to his freedom.

Stochastic Point Location

To see the applications of the N-door puzzle it is profitable to review the Stochastic Point Location (SPL) problem [? ]. Consider an agent (algorithm or learning mechanism) that moves on a line attempting to locate a particular location λ * . The agent can communicate with a teacher (or oracle) that informs the agent its current location λ is greater or lower than λ * . However, the teacher is of a stochastic nature and with probability 1 -π feeds the agent erroneous feedback.

The SPL problem, due to its simplicity has been shown to have fascinating applications in meta-optimizing such as improving the performance of Multidimensional Scaling (MDS) [? ] and estimation of non-stationary binomial distributions [? ] as well as within routing optimization [? ].

Related Work

Stochastic Searching on a Line. Baeza-Yates et al. [? ] introduced the precursor to the SPL problem as Searching for a Point on a Line (PL). The PL problem is near identical to SPL with the obvious difference that as opposed to SPL, PL operate solely with deterministic feedback.

In his pioneering work Oommen et al.

[? ] introduced SPL as a meta-optimization algorithm. Following this paper, the general theme for investigation has been to apply various Learning Automata (LA) schemes [? ? ? ]. And to the best of our knowledge the general state-of-art solver is Adaptive Step Searching (ASS) [? ], although it is outperformed by the Hierarchical Stochastic Searching on the Line (HSSL)[? ] for highly volatile non-stationary environments [? ]. However, all the above schemes are restricted to the case where the teacher is informative (π > 0.5).

The SPL problem with a possible deceptive teacher is a magnitude harder problem than the original SPL problem and the only known solution, CPL-AdS, can be found in [? ]. The CPL-AdS scheme is a two phase algorithm, first phase consist of using a sequence of intelligently selected questions to, with arbitrary high probability, classify the teacher as either informative or deceptive. In the second phase a regular SPL solving scheme is used where all the feedback from the teacher is negated if the first phase decided that the teacher was deceptive.

This type of scheme can be seen as a semi off-line estimator scheme where the parameters is first collected from a long sequence of observations, then given a sufficient high number of observations, estimate the best parameters. The main drawback with this approach is the fact that the observations in phase one is not given any consideration until the parameters are ready to be estimated. And as we shall see, leads to significantly worse performance compared with schemes that operate on the data in an on-line fashion. Another major drawback is the fact that once the scheme has decided on the nature of the teacher, it is stuck with that decision. Thus the first phase must sufficiently guarantee a correct decision. Consequentially CPL-AdS scheme is not anytime due to the simple fact that it cannot guarantee us any results until it has converged.

Thompson Sampling. The Thompson Sampling (TS) principle was introduced by Thompson in 1933 [? ], and is currently primarily employed to solve the Multi-Armed Bandit (MAB) problem.

The iconic MAB is concerned by maximizing the profit of a gambler playing slots on one armed bandits machines. The gambler knows that one of the arms pays out more than the others and wants to identify this optimal arm. However, he also does not want to waste his tokens by playing sub-optimal arms. Solving a MAB problem thus involves determining a strategy that identify the optimal arm while minimizing the loss inflicted by not playing the optimal arm. For this paper we will not be concerned with the traditional MAB problem where each arm is independent of each other, instead we will establish a global-informative MAB (GI-MAB) [? ] where each selected arm rewards all other arms.

TS has proven to be one of the top contenders for traditional MAB problems [? ? ], contextual MAB problems [? ], and has also been utilized for Gaussian Process optimization [? ] as well as a foundation for solving the Maximum a Posteriori Estimation (MAP) problem [? ].

Contribution of the Paper

The contributions of this paper can be summarized as follows:

1. We demonstrate the efficiency of a Bayesian line of thought to progressively explore and exploit (using Thompson Sampling) a probabilistic model over all possible N-door instances instead of focusing directly on solving a single specific problem. 2. We present a novel scheme, TS-SPL for solving the N-door puzzle (and SPL) that outperforms the current state-of-art in the case of an informative teacher. If the teacher is deceptive TS-SPL outperform the state-of-art by an order of magnitude. 3. The performance of TS-SPL is also highly stable compared to the current state of art, i.e. it exhibits a low variance. 4. A secondary benefit of TS-SPL is that it not only outperform state-of-art, but in addition also estimates the degree of truthfulness of the teacher.

Paper outline

In Section 3, we present our scheme for Thompson Sampling guided Stochastic Point Search (TS-SPL). Here we start with a brief outline of the TS-SPL scheme and a intuitive explanation on how TS-SPL works. Thereafter, we derive the probabilistic model that tracks the probabilities for which door is the correct choice, as well as the truthfulness of the guards. Using this probabilistic model as a foundation, we formulate a MAB problem that we solve using TS in such a manner that by solving the MAB problem we also solve the N-door puzzle.

Then, in Section 4, we define an ensemble of empirical experiments that we employ to evaluate the performance of TS-SPL compared to state-of-the-art. We conclude in Section 5 and present interesting venues for further work.

3 Thompson Sampling Guided Stochastic Search on the Line (TS-SPL)

The Thompson Sampling guided Stochastic Searching on the Line (TS-SPL) scheme introduced in this paper utilizes a Bayesian approach to capture the Ndoor puzzle. A N-door puzzle can be succinctly represented as a 2-tuple (λ * , π) where λ * ∈ D is the door leading to freedom and π ∈ T is the truthfulness of the guards. Let Ω be a set containing all possible N-door puzzles. Then, assuming no a-priori information, we formulate a uniform prior over all N-door puzzles in Ω.

The essence of TS-SPL is then to gradually refine the posterior over Ω by letting TS guide our questioning and then update our posterior with the resulting new information. As this process is repeated the likelihood of any other puzzle than (λ * , π) is lowered and thus the probability of (λ * , π) is increased. Consequently, given enough iterations TS-SPL will correctly identify λ * as the door leading to freedom as the posterior probability of (λ * , π) approaches unity.

The probabilistic model. The main purpose for the probabilistic model is to determine a posterior distribution over the possible N-door puzzle instances, Ω.

Let the probability of the doors and the truthfulness of the guards be defined by two random variables (r.v.) denoted D and T , respectively. We here assume that D and T are independent of each other. The information we obtain from questioning the guards are represented as a set of conditionally independent r.v.

Q = {Q 1 , . . . , Q n },
Where Q = n-1 k=1 P (Q k |d, t) and Q + = P (Q n |d, t).
(2) follows directly from Bayes Theorem. (3) From marginalizing out Q(Q|t). (4) From the independence of D and T , and ( 5) from the independence between the questions in Q. Applying memoization on Q allow us then to swiftly compute the next probability term as the number of answers in Q grow.

Multi-armed-bandit The above section describes how once we have obtained information from the guards we can turn it into probabilities for the different doors. However, as mentioned in the introduction we have trade-off between exploring different doors and zeroing in on the correct door. To handle this trade-off we model the door selection as a MAB.

To apply MAB to the N-door puzzle we enable a bijective mapping between the MAB arms and the doors found in the N-door puzzle. To decide on what arm to select for each turn we solve the MAB by utilizing the principle of TS. Here, the selection process is simply to select a random door proportional to the probability that that door is the best. Once the door has been selected we need to find what guard to ask that is standing adjacent to that door. We do this by, again, select a guard randomly proportionally to the sum of the probability of the door next to the guard on each side. So for example, if we have three doors d k , 0 < k < 4, and thus three arms with probability P (d 1 ) = 0.1, P (d 2 ) = 0.2, P (d 3 ) = 0.7, then, in lieu with the TS principle these are also the probabilities of selecting that particular arm. Since selecting a door affect D, the probability of each door, we have a GI-MAB as opposed to a traditional MAB. The advantage of using TS in the selection process is evident as it provides a effective yet intuitive handling of arm selection in GI-MAB. The resulting scheme allows for more exploration in the start and gradually become increasingly greedy as the probability distribution over the arms converge.

In section we will thoroughly demonstrate the superiority of TS-SPL as compared with existing state-of-the-art. Firstly, how it outperforms the state-ofart a setting where the teacher is either informative or deceptive. Secondly, we will demonstrate how it compares with the classical informative SPL schemes. Thirdly, we will consider how the performance of TS-SPL can be enhanced by applying prior information. And finally, we will investigate to what degree TS-SPL is able in a on-line fashion to track the truthfulnesses of the teacher, before concluding with some final remarks on the behavior of TS-SPL.

The configuration of TS-SPL remains the same throughout all the different scenarios. We used a lambda set: λ 0 , λ 1 , . . . , λ 200 evenly distributed over 0.0 -1.0.

Regret is measured as the distance d between the point x selected and the optimal point λ * . If the distance |d| is less than Ω = 2 -8 we clamp d to zero. This is done to allow the algorithms that operate with continues values to pseudo converge and facilitates easy comparison between the discrete and continues schemes.

Deceptive or informative teacher

With the underlying π taking on values in the interval [0, 1] -{ 1 2 } we test TS-SPL vs CPL-AdS[? ] for speed of convergence and how much regret on average one accumulate before converging. However, due to the vast difference in regret between the two method a direct comparison is almost meaningless. The large regret accumulated by CPL-AdS is mainly occurring as it requires a separate phase for detecting if a environment is, informative or deceptive.

From their paper this decision phase needs approximately 200 time steps, and by this time TS-SPL is already close to converging. The other parameters in CPL-AdS the same as in their paper, LRI-θ = 0.8 and LRI-= 0.05.

To illustrate this point see Table 1 where it is clear that TS-SPL is superior to CPL-AdS by several orders of magnitude. π = 0.85 π = 0.15 TS-SPL (λ * = 0.85) 6.2 6.2 CPL-AdS (λ * = 0.85) 501.6 / 354.9 842.8/502.3

Table 1: The accumulative regret for TS-SPL and CPL-AdS. All entries was estimated taking the average of an ensemble of 1000 independent trials and each entry corresponds to the estimated cumulative regret using N = 1000 time steps, leading to a negligible variance of the estimates relative to the large difference in performance among the competing schemes. The number after the slash corresponds to the regret applied after CPL-AdS determines if the teacher is informative or deceptive.

Informative teacher

For the case where we restrict the teacher to be informative π > 0.5 we can compare TS-SPL against both the Adaptive Step Searching (ASS) [? ] and the Hierarchical Stochastic Searching on the Line (HSSL) [? ]. Another highly fascinating scheme is found by modifying TS-SPL to use an informative prior, as such, TS-SPL knows that 0.5 < π ≤ 1. We denote this modified scheme as TS-SPL-INF.

For HSSL we used a tree branching factor of D = 8, and for ASS we set N max = 200. This give the closest resolution between the tree schemes. Table 2: The cumulative regret for the competitive schemes for solving a informative SPL problem. All entries were estimated taking the average of an ensemble of 1000 independent trials and each entry corresponds to the estimated cumulative regret using N = 1000 time steps.

An important point to make is that in this scenario TS-SPL is configured with a uniform prior over π, so that the TS-SPL does not take advantage of the fact that π is restricted to certain values. Changing this by applying a uniform distribution over the feasible interval of π = [0.5, 1.0] and zero elsewhere we obtain an significant increase in performance, as evident by TS-SPL-INF. This is one of the main advantages that TS-SPL present, the ability to, in a straight forward way, encode any prior information, both concerning λ * and π. This is useful if one believe that for instance π should be close to 1 2 or that one prefer a more cautious approach and thus instead of applying a uniform distribution one could for instance select a Gaussian distribution with a mean of 1 2 and a suitable variance.

Tracking the truthfulness of the teacher

A interesting property of TS-SPL is its inherit ability to not only give a probability distribution over doors, but it can also give a distribution over truthfulness π. This is a great advantage as it present the end-user with a better view into the underlying environment, which can in particular be leveraged upon in the case of repeated trials, where previous trials can be us as a prior on subsequent trials, hence greatly increasing the speed of convergence. Figure 1 shows the probability for each level of noise as the TS-SPL progresses with a deceptive π = 0.2 Fig. 1: TS-SPL tracks the probability π of correct feedback (y-axis). Here the true value of π is 0.2, and it is clear from the figure that TS-SPL is close to the optimal choice after only 100 iterations. The figure is based on an average of 1000 independent trials.

Stability of solution

To investigate the stability of TS-SPL, we study the variance of the regret for 1000 independent trial runs, leaving sta. Low variance means more stable performance in each trial. This property is important as it gives a higher belief that the algorithm will perform well on every occasion. For ease of comparison, the standard deviation is shown instead of the variance. Table 3 shows the results of this stability evaluation. Table 3: The standard deviation of the result of 1000 independent trials measured in regret, each trial was done using N = 1000 time steps.

Conclusions and Further Work

In this paper we investigated a novel reinforcement learning problem, inspired by the N-door puzzle. This puzzle has the fascinating property that it allows the reinforcement of the incorrect behavior, also known as a deceptive teacher. This renders traditional RL approaches ineffective due to their dependency on "on average" correct feedback, that is, an informative teacher.

Thus, to formulate a solution we first mapped the N-door puzzle into a Multi-Armed-Bandit (MAB) Problem, that we applied TS to solve. However, due to the non-trivial properties of the N-door puzzle, a probabilistic model was used to calculate the arm probabilities in the MAB, thus abstracting the possibility of a deceptive environment away from TS.

The resulting scheme, TS-SPL, was applied to the Stochastic Point Location (SPL) problem and demonstrated superior performance when compared to existing state-of-art solutions for a significant set of problem configurations. In the case of an informative teacher, TS-SPL slightly outperforms state-of-the-art, and for a deceptive teacher TS-SPL is an order of magnitude better. For both cases, TS-SPL demonstrates excellent stability, having remarkable low variance compared to state-of-the-art solutions.

However, the TS-SPL scheme is limited in the sense that it does not handle a non-stationary solution that some of the the informative schemes support. Further work therefore includes to investigate how we can incorporate support for non-stationary environments, such as switching environments where the teacher switches from informative to deceptive or vice versa.

π

  = 0.55 π = 0.65 π = 0.75 π = 0.85 TS-SPL (λ * = 0.85)

π

  = 0.55 π = 0.65 π = 0.75 π = 0.85 TS-SPL (λ * = 0

  How to compute the probability of a guards answer.Applying the algorithm given above to find P (Q|d, t) we derive a simple expression that find the posterior distribution given the answers. Shown here is the derivation of P (d ∈ D|Q), however the derivation of P (t ∈ T |Q) is analogous.

	t P (right | guard, door, t) = 1 -t else P (left | guard, door, t) = 1 -t P (right | guard, door, t) = t end t∈T P (d|Q, t)P (t) = t∈T P (Q|d, t)P (d|t)P (t) P (Q|t) ∝ t∈T P (Q|d, t)P (d|t)P (t) ∝ t∈T P (Q|d, t)P (d)P (t) t∈T Algorithm 1: P (d ∈ D|Q) = ∝ QQ + P (d)P (t)	(1) (2) (3) (4) (5)

each conditioned on D and T . For each question Q k we can compute the probability of the answer (left or right) that we received from the guard as follows:

Data: guard, truthfulness t ∈ T and door d ∈ D Result: P (Q k |d, t) -P (left) and P (right) given the input if guard is left of door then P (left | guard, door, t) =