Elena Hensinger
email: elena.hensinger@bristol.ac.uk

Ilias Flaounas
email: ilias.flaounas@bristol.ac.uk

Nello Cristianini
email: nello.cristianini@bristol.ac.uk

Learning the Preferences of News Readers with SVM and Lasso Ranking

Keywords: Learning to Rank, News Content Analysis, User Preferences, Support Vector Machines, Lasso

We attack the task of predicting which news-stories are more appealing to a given audience by comparing 'most popular stories', gathered from various online news outlets, over a period of seven months, with stories that did not become popular despite appearing on the same page at the same time. We cast this as a learning-to-rank task, and train two different learning algorithms to reproduce the preferences of the readers, within each of the outlets. The first method is based on Support Vector Machines, the second on the Lasso. By just using words as features, SVM ranking can reach significant accuracy in correctly predicting the preference of readers for a given pair of articles. Furthermore, by exploiting the sparsity of the solutions found by the Lasso, we can also generate lists of keywords that are expected to trigger the attention of the outlets' readers.

Introduction

We are interested in understanding and predicting which news articles are most intriguing for readers of a given news outlet. This problem is of importance to both media analysts and news editors, as well as to engineers designing recommendation systems.

"What makes stories newsworthy?" has been the classical question in media studies [START_REF] Gans | Deciding What's News: A Study of CBS Evening News, NBC Nightly News[END_REF]. A related question is "What makes stories popular?", and it can be addressed today due to the online availability of news media and the capability to capture preferences of readers by their clicks on news items. There are many possible answers to this 'Popularity question': it does not only depend on the textual content of the article, but it is also influenced by its position on the web page [START_REF] Wu | Popularity, novelty and attention[END_REF], on the images or videos associated with it and on its timing and according novelty [START_REF] Szabó | Predicting the popularity of online content[END_REF].

The study of ranking user preferences has been recently approached by researchers in data mining, text processing and web analysis. Examples and applications in the area include the study of popularity of micro-blogging [START_REF] Szabó | Predicting the popularity of online content[END_REF], advertisement selection [START_REF] Ghose | An empirical analysis of search engine advertising: Sponsored search in electronic markets[END_REF] and search engine log analysis [START_REF] Joachims | Optimizing search engines using clickthrough data[END_REF].

In our study, we focus on news media data with the goal to learn and predict preferences of news readers. We work on the content of news articles that readers will use in order to make their reading choices: the title and short description -the text snippet that is presented to readers before they click on a given link -from RSS (Real Simple Syndication) feeds of 10 news outlets with online presence, including broadcast media such as 'CBS' and newspapers such as 'LA Times'. We used two feeds per outlet: a) the 'Main' feed which contains the main stories of the day, as selected by the outlets' editors and b) the 'Most popular' feed formed by the readers' click choices. Can this information be sufficient to predict the interests and preferences of readers? To our knowledge, this question has not been addressed in literature.

We model the task as a problem of ordinal learning, or 'Learning to Rank': given a set of ordered data pairs, we learn a utility function that can be used to score every article, in a way that the scores can be used to rank them appropriately. The methods we use to infer linear utility functions are based on quadratic programming: Ranking SVMs (Support Vector Machines), as introduced by Joachims [START_REF] Joachims | Optimizing search engines using clickthrough data[END_REF], and Lasso [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF] that we applied for the ranking task. The motivation for the latter choice is to obtain sparse solutions, and hence extract the keywords that are most likely to predict article popularity and to trigger readers' attention.

In Sect. 2 we describe the two algorithms and present their relative merits in terms of generalisation performance and feature extraction ability. While Ranking SVM and Lasso originally solve different tasks, we show how Lasso can be applied to learn pairwise ranking.

In Sect. 3 we discuss the application of the two methods to news media datasets and report our results. For most outlets, the SVM-based ranking method can make predictions that are significantly stronger than random guessing. Under the posed experimental framework the Lasso-based ranking method performs less efficiently but still making significantly valid predictions and it has its actual strength in getting sparse solutions. Therefore we use the utility function inferred by the SVM to rank articles and the Lasso utility function to detect the strongest keywords that make articles become popular.

Task and Techniques

In this section we first present how the task of learning pairwise preference relationships can be transformed into a classification problem, secondly the ranking SVM and Lasso methods we used to solve it, and last their empirical comparison on synthetic data.

Pairwise Ranking as Classification

We aim to learn the ranking of items x ∈ R n , based on partial information about the preference relationship between pairs (x i , x j ). We denote that item x i is preferred to x j by x i ≻ x j . By defining a linear utility function u : R n → R of the form w, x , we can express this relationship as:

x i ≻ x j ⇐⇒ u(x i ) > u(x j ) ⇐⇒ w, (x i -x j ) > 0 (1)
where u(x i ) is the utility value of x i . The task of learning the relationship between items x i and x j can now be expressed as a binary classification problem on the vector of their difference. which we will denote as s k ∈ S, with S being the set of pair differences. We assign class label y k = +1, if w, s k ≥ 0, and y k = -1 otherwise.

Ranking SVM

SVMs is a well studied method for binary classification [START_REF] Boser | A training algorithm for optimal margin classifiers[END_REF][START_REF] Cristianini | An introduction to support vector machines and other kernel-based learning methods[END_REF]. The SVM formulation has been extended to learn pairwise preference relationships based on difference vectors of form s k through the Ranking SVM [START_REF] Joachims | Optimizing search engines using clickthrough data[END_REF]. Slack variables ξ k allow to deal with non-linearly separable data, and the entire task for l training items of S is expressed as a quadratic optimisation problem:

minimise ξ,w w, w + C l k=1 ξ k (2) subject to y k ( w, s k ) ≥ 1 -ξ k , ξ k ≥ 0 ∀k = 1, . . . , l
The solution is a weight vector w that can not only compute the preference relationship between two items x i and x j , but can also give the rank, i.e. the utility value, of item x i since u(x i ) = w, x i .

Lasso for Ranking

The second method we used is a special form of linear regression, the Lasso (Least Absolute Shrinkage and Selection Operator) [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF]. In our setting rather than searching for a fit to real values we try to classify the pairwise differences s k to their labels y k . In order to produce a sparse solution, the regression problem is constrained on the L 1 -norm, denoted as || • || 1 , of the computed weight vector w through a parameter t ∈ IR. The according quadratic optimisation problem is:

minimise w l k=1 ( w, s k -y k ) 2 (3) subject to ||w|| 1 ≤ t
The solution is a weight vector w which, as in the case of SVMs, is used for calculating the utility value of item x i as u(x i ) = w, x i .

Empirical comparison of Ranking SVM and Lasso

We compared Ranking SVM and Lasso in an experiment on small scale synthetic data to explore their potential on: a) correctly predicting class labels for the pairwise ranking task and b) handling sparse data and especially their ability to correctly identify relevant features, that is excluding features with zero value. We synthetically created data items of 50 features with uniformly distributed values in (0, 1). A weight value from the real interval [0, 10] was randomly assigned to each feature, and 50% of features were randomly set to zero to simulate sparse data. We created difference vector pairs s k and assigned class label +1 or -1, depending on the utility values of x i and x j . In all our computations we trained on 100 different data sets, ranging from 10 to 500 pairs of items, and we tested on 100 item pairs, averaging over 10 different data initialisations. We set parameters C in Ranking SVM and t in Lasso to their optimal values, as found for the described experimental setup.

To evaluate the two methods on preference prediction performance we used accuracy, defined as the percentage of correctly classified pairs. The resulting learning curves are illustrated in Fig. 1A. Both approaches improve their performance with increasing amount of training data, reaching an asymptotic bound on their performance. While Ranking SVM scores better in most cases, 'Lasso Ranking' can keep up successfully in this setting of predicting pairwise preferences. To evaluate performance on identifying zero valued features (ZF ) we used precision and recall measures, defined as: precision = # of correctly identif ied ZF / # total retrieved ZF (4) recall = # of correctly identif ied ZF / # total true ZF in f eatures [START_REF] Joachims | Optimizing search engines using clickthrough data[END_REF] Figure 1B presents precision and recall on detecting zero features using Lasso as a function of different levels of sparseness of the solution w for the 500 training pairs case. In our experimental setup, Ranking SVM produced dense solutions, even with the relaxation of counting features with absolute values less than 0.0005 as zero-valued.

Based on these results, we have an indication that Lasso can perform comparably with Ranking SVM in terms of prediction accuracy on pairwise difference data. Furthermore, it can identify relevant features in data, allowing to retrieve a sparse and meaningful solution.

Experimental Results on News-Outlets Data

We tested Ranking SVM and Lasso on real world data from 10 news-media outlets monitored from June 1st to December 31st, 2009. Since there are no publicly available datasets that provide annotated articles to use for learning readers' preferences we created our own system to gather this information from outlets that offer their content online [START_REF] Flaounas | Inference and validation of networks[END_REF].

Our system processes the content of media outlets that offer their content as RSS feeds, an easily machine readable format. Feeds contain for each article only limited information: a title, a summary and publication date. Most outlets serve multiple different RSS feeds of which we are interested in two specific ones, namely the 'Main' feed, and the 'Most Popular Stories' feed. The first one contains articles that comprise the leading stories of the outlet as chosen by their editors and roughly correspond to the front page of a newspaper. The second contains articles that readers found most interesting -these articles are not necessarily present in the 'Main' feed. We define feeds as 'Most Popular' if they carry the 'Most clicked' articles. For the outlets which miss such feeds, we adopted the 'Most emailed stories' or the 'Most discussed stories'. The article titles and summaries were gathered on a daily basis and processed with typical text mining methods such as stemming [START_REF] Porter | An algorithm for suffix stripping[END_REF], stop words removal, indexing and TF-IDF (bag-of-words) representation of articles [START_REF] Liu | Web Data Mining, Exploring Hyperlinks, Contents, and Usage Data[END_REF].

For each day of the period of study and for each outlet separately, we created pairs of articles from all combinations of articles that a) appeared in both 'Main' and 'Most Popular' feeds, and b) articles that appeared only in 'Main' feed and not in the 'Most Popular' one. The pairwise preference relationship is given by the fact that some articles of the 'Main' feed were preferred by the outlet's readers, while others were not. In total we formed 405,487 pairs -on average 5942 pairs per outlet per month. For 'Florida Times-Union' we managed to collect data for five months and for 'LA Times' for three months only.

We train both Ranking SVM and Lasso on one month per outlet and test on the following month's data. We have seven months of data resulting in six training/testing setups per outlet. For this set of experiments we used the SV M Rank implementation of Ranking SVM [START_REF] Joachims | Optimizing search engines using clickthrough data[END_REF]. We measured classification accuracy for three different values of C parameter, namely 1, 10 and 100, and we report the best results per outlet in Fig. 2.

In the case of Lasso, we are interested to discover the most interesting keywords that characterise popular articles, thus we adjusted the t parameter to achieve a sparse solution of roughly 100 words per outlet per month. Average month-to-month prediction results of readers' preferences are reported in Fig. 3. In both cases, we consider classifiers to have significant performance if they achieve an average accuracy over 50% for the 95% confidence intervals. Using SVMs, we get significant performance for seven outlets, reaching up to 73.14% Fig. 2. Average month-to-month prediction accuracies per outlet using Ranking SVMs. Error bars are set to 95% confidence interval. Notice that for 'Guardian' we have limited amount of articles per day, and for 'LA Times' only three months of data resulting in a small confidence interval. for 'LA Times'. For 'Guardian' we had the least available data -only 482 pairs on average per month rather than thousands as in the rest of the outlets -and this explains the low performance. For 'CNN' and 'Time' we managed to get only marginally significant results, and we assume the diversity of their audience and topic coverage to be the reason. As expected, we achieved on average 5.78% less accuracy using Lasso for the seven outlets for which we had significant results. However, it is the same outlets that failed to give significant results for SVMs which also fail for Lasso.

We used the SVM classifiers that predict article popularity with significant performance to detect the most popular stories per month for each outlet. To identify the most promising keywords that can trigger the audience's attention, we applied Lasso. As an example, we present the titles of the top-3 most popular articles per outlet and the top-10 keywords for December 2009 in Table 1. The stories we found reflect stories that were in the focus of media for that period of time. The stemmed keywords are similarly sensible and understandable. The

Conclusions

In this paper, we presented the feasibility of applying machine learning algorithms for the task of modelling readers' preferences on stories gathered from real world news-media outlets. We formulated the problem as a Learning to Rank task on preference-ordered pairs of items and applied two different methods, each with its own strengths. Ranking SVM allowed us to calculate a ranking of all articles and to retrieve the most popular articles per outlet. Lasso was applied to identify the keywords that relate to popularity of articles.

To rank articles we used only limited textual information, their titles and summaries, and we managed to achieve more than 70% accuracy in several cases. This is quite impressive given the limited data available and all the other factors that affect readers' choices, such as the placement of the article in the layout of the web-page, the presence of accompanying photos or videos, the potential sentiment content in the article, or the exact timestamp. Also the segmentation of the audience is very coarse: the readers of a given outlet are bundled into the same set, as we do not have more refined information about them (e.g. their location). That is we managed to quantify the contribution of content to the choices of readers, isolating this from other factors. Even more, in this research we focused only on the main page of each outlet -stories that the editors expect to be interesting and popular. We expect to be able to achieve a higher performance if we don't restrict the data to the first page only, but use the entire content of an outlet as a negative set of non-popular stories.

Future plans include research on higher level features to describe articles, such as topic or sentiment to improve performance in learning, predicting, and understanding what affects readers' preferences.

Fig. 1 .

 1 Fig. 1. A. Learning curves for Ranking SVM and Lasso. B. Lasso's ability to identify zero-valued features.

Fig. 3 .

 3 Fig. 3. Average month-to-month prediction accuracies per outlet using Lasso. Error bars are set to 95% confidence interval.

Table 1 .

 1 Titles of most popular articles per outlet as ranked using Ranking SVMs and keywords per outlet as identified using Lasso, for December 2009.

	Outlet	Titles of Top-3 Articles	Top-10 Keywords
	CBS	Sources: Elin Done with Tiger -Tiger Woods Slapped	defend, murphi, tiger, lake,
		with Ticket for Crash -Tiger Woods: I let my Family	mom, flight, bengal, man,
		Down	goldman, unredact
	Florida	Pizza delivery woman killed on Westside -A family's	wade, middleburg, chest,
	Times-	search for justice, 15 years later -Rants & Raves: Napoli-	send, charlton, petti, kill,
	Union	tano unqualified	augustin, shoot, levar
	LA	Pacquiao to fight Mayweather in March -Bone marrow	insul, immigr, disnei, futur,
	Times	transplant 'gets rid of' sickle cell anemia -Disney toys	california, cash, studi, ra-
		get Pixar animation guru's touch	diat, lo, selznick
	NY	Poor Children Likelier to Get Antipsychotics -Surf's	studi, visual, art, monei, gift,
	Times	Up, Way Up, and Competitors Let Out a Big Mahalo	drug, journal, counterterror,
		-Grandma's Gifts Need Extra Reindeer	water, korean
	Reuters Dubai says not responsible for Dubai World debt -Boe-	secur, health, shot, land-
		ing Dreamliner touches down after first flight -Iran's	mark, ahmadinejad, exxon,
		Ahmadinejad mocks Obama, "TV series" nuke talks	oilfield, wood, jihad, test
	Seattle	Hospital: Actress Brittany Murphy dies at age 32 -Ac-	patrolman, gainesvil, break-
	Post	tor Charlie Sheen arrested in Colorado -Charlie Sheen	fast, girl, insur, salvat, hoax,
		accused of using weapon in Aspen	ohio, sheen, utah
	Yahoo!	Yemen is growing front in al-Qaida battle -Report: US	care, storm, famili, white,
	News	helped Yemen's strike against al-Qaida -AP source: Al-	sheen, slai, brittani, qaida,
		Qaida operative killed by US missile	medicar, volcano
	different findings between outlets reflect a) differences of editors' choices on which
	stories to cover, and b) differences of what readers of different media outlets
	preferred to read.

Acknowledgements. The authors would like to thank Mark Schmidt for his implementation of Lasso LARS algorithm. We used 'QPC -Quadratic Programming in C' Matlab Interface in the empirical comparing of SVM and Lasso section. I. Flaounas is supported by the A. S. Onassis Public Benefit Foundation; N. Cristianini is supported by a Royal Society Wolfson Merit Award. This research was partly supported by the "University of Bristol Bridging the Gaps Cross-Disciplinary Feasibility Account" (EP/H024786/1). Group activities are supported by PASCAL2 Network of Excellence.


Mirosław Stawniak
email: stawniak@kti.ue.poznan.pl

Wojciech Cellary
email: cellary@kti.ue.poznan.pl

The TSTS Method in Cultural Heritage Search

Keywords: semantic web, semantic search, cultural objects, cultural heritage

In cultural heritage content management systems in which cultural objects are described with the use of their semantic, temporal and spatial properties, the search capabilities taking all those properties into consideration are very limited. The difficulty comes from the fact that concepts evolve over time and depend on location. In this paper the TSTS search method is presented based on the TST similarity measure that allows assessing the similarity factor between different resources in a knowledgebase. A ranked search result is generated basing on the semantic distance between the fuzzy set created for the user query and fuzzy sets describing potential results in the time-space continuum.

Introduction

In recent years increasing interest in creating virtual museums is observed. Virtual museum objects are stored in heritage content management systems. Detailed descriptions of the objects include e.g. the dates and places of their creation, storage and renovation. In many content management systems objects are also mutually linked according to their semantic conceptual relationships. Current heritage content management systems usually allow users to search for cultural objects, however, the search capabilities provided are quite limited. The problem is that concepts related to cultural objects are dependent on time and geographical location, can evolve over time, and may have different meaning in different locations. As a result, search methods developed so far, both keyword-based and semantically oriented, fail because of the imprecision of data -on the one hand contained in museum knowledgebases, and on the other hand used in the queries by users.

In this paper a TSTS (Theme-Space-Time Search) method of semantic search is proposed that takes into account three factors to answer a user query: relations between concepts in context of their temporal and spatial properties. Contribution of the TSTS method to technological innovation in the domain of semantic search in the cultural heritage field is presented in Section 2. In Section 3, current solutions for cultural objects search engines are discussed. In Section 4, the TSTS method is presented, including the TST concept similarity measure and its application in search. The characteristics of the TSTS method are discussed in Section 5. Finally, Section 6 concludes the paper.

Contribution of the TSTS Search Method to Technological Innovation

To present contribution of the TSTS search method to technological innovation consider the following example of a fragment of a cultural heritage domain presented in Figure 1. This domain deals with cultural objects, geographical places, and historical periods. Rectangles represent concept instances, while ovals -their properties. For the sake of clarity, only properties describing time spans (denoted by t) and geographical coordinates (denoted by g) in literal values are presented. In this example some of the concept instances are directly described by the time and space information (e.g. Vase 1 was created in time t 1 and place g 1 ), while for others time/space information is expressed by references to other concept instances (e.g. Vase 2 was created in time t 2 in Greece). Moreover, some concept instances can be linked with more than one pair (time, place) since they evolved over time or appeared in different places at different times. Greece is an example of an evolving concept instance, because the borders of Greece have changed many times. As a result, location and area of 'Greece' depend on the date considered. As a consequence, when the term 'Greece' is used in a query, time has to be specified to obtain a precise response. Similarly, term 'Archaic Period' is not bound to only one period in time, but depending on place may refer to different time spans. For example the archaic period occurred in Egypt between 3100-2600 BC, but in Greece between 750-480 BC. A typical query issued by an archaeologist is: find all the vases originating from Greece created in the archaic period.

There are two types of search methods that could be used to answer such a query: keyword search and semantic search. Keyword search is the simplest and the most common search method. In the cultural heritage context, where terms are ambiguous, results obtained using this method are usually inaccurate. This method is able to return only those objects for which a given keyword occurs inside their textual description.

Semantic search methods are usually more accurate than keyword based methods, because they are able to analyze relations between concepts and their instances. However, if a purely semantic search method was used in the example above, it would also return inaccurate results, because some concepts are not explicitly connected to each other, but they relate only through their temporal and geographical coincidence (e.g. 'Archaic period' and 'Vase 1' are related because they both occurred in the same place at the same time).

The TSTS method of semantic search presented in this paper takes into account three factors to answer a user query: relations between concepts together with their temporal and spatial properties. As the majority of users are accustomed to expressing their information needs in terms of keywords, the TSTS method allows users to ask questions using a traditional 'Google like' interface. However, the TSTS uses semantic information concerning the application domain to obtain results that are not possible to be found when traditional search methods are applied. The TSTS method is based on the TST similarity measure that allows assessing the distance between different concepts in a semantic, spatiotemporal database. During the evaluation of this measure, for each concept a fuzzy set of points in the time-space continuum is constructed. In such a fuzzy set, the more closely a point is related to the analyzed node, the higher degree of membership it receives. In the next step fuzzy set operations such as intersection and union are applied to the fuzzy sets that correspond to the concepts from the user query. As a result, another fuzzy set is obtained that represents the region in space and time that the user is interested in.

In the example above, in a user query three concepts 'Vase', 'Greece' and 'Archaic Period' are mentioned. The concept 'Vase' yields the set containing points in the time-space continuum that correspond to all acts of the creation of a vase. For the concept 'Greece', a set is generated including all the points in space in which Greece has ever existed. Finally, the concept 'Archaic Period' yields the set of points in which that period occurred. Intersection of these three fuzzy sets is a region in time and space matching the user's query. Finally, cultural objects that are 'closest' to that region are found and presented as the query result.

Searching Cultural Objects

A number of different approaches to cultural object searching have been developed and presented in the literature.

Fitzwilliam Museum [1] website makes its collection accessible through the standard OPAC (Online Public Access Catalog) search interface. The search is based on keywords. Although, it is possible to issue a query limiting search results to a certain place and time period, search is performed on textual basis. Mainly due to data inconsistency, search results are prone to be inaccurate, which is a common disadvantage of search methods based on keywords.

Heritage 4 [START_REF] Snizek | Heritage 4 -A 4D Cultural Heritage Management System[END_REF] is a system for storing and presenting cultural objects used to build the virtual Museum of Copenhagen [3]. In this system users can conduct searches choosing textual, geographical and/or, temporal criteria or through relations between objects. Although in the Heritage 4 system search is made via an appealing interface, it does not support complex queries such as the one presented in Section 1. The spatiotemporal search can only operate on objects that are directly described by space and time properties and those properties cannot be inferred through relations with other objects. Therefore, this system does not indirectly support the evolving concepts.

Semantic search is a process used to improve searching capabilities by using semantic networks to disambiguate queries in order to generate more relevant results. The semantic search methods are divided into two categories: exact methods and approximate methods.

The SPARQL language is devoted to the exact semantic search methods. SPARQL is a language for querying the RDF semantic networks developed by RDF Data Access Working Group (DAWG) [START_REF]SPARQL Query Language for RDF[END_REF]. SPARQL is designed for finding patterns in semantic graphs. Although the SPARQL language is very powerful, initially it was not designed to answer the queries that deal with time and space . Some extensions to SPARQL exist [START_REF] Dodds | SPARQL Geo Extensions[END_REF] that allow querying for time and space, but they make the use of this language even more sophisticated.

Another interesting approach to the exact semantic search is proposed in [START_REF] Perry | Analyzing theme, space, and time: an ontologybased approach[END_REF], in which spatial and temporal query operators have been formalized and evaluated. Although the proposed framework was designed to deal with queries containing references to time and space, there is no direct support for the changing or evolving entities.

In general, the exact search methods have two disadvantages. First disadvantage concerns the relationship with a knowledgebase. The exact search methods either require a user to know the structure of a knowledgebase and then the search system may cooperate with different knowledgebases, or the search system is strictly bound to knowledgebases of a single structure fixed a priori. The second disadvantage of the exact search methods is their inability to return the results that do not meet a given search criterion, but which are close to meet it. Although this property is not considered to be a disadvantage in certain applications, in the cultural heritage domain it is a disadvantage. In the cultural heritage domain spatiotemporal data in the knowledgebase and in the user query can be imprecise, so the possibility to find objects that are close to meeting a given criterion and ranking the results is very important.

Approximate semantic search methods are based on similarity measures. These methods usually do not require a user to know the structure of the semantic network and they permit to rank the results. Although there has been a number of such measures proposed [START_REF] Rocha | A hybrid approach for searching in the semantic web[END_REF][START_REF] Ziegler | Automatic computation of semantic proximity using taxonomic knowledge[END_REF], none of them takes both time and space information into consideration.

The TSTS method presented in this paper can be categorised as an approximate semantic search method, because it is based on a similarity measure, namely the TST (Theme-Space-Time). The main feature of the TSTS method, as opposed to the existing methods, is its ability to seamlessly deal with the concepts evolving or changing in time and space. Also, the TSTS method does not require a user to know the structure of the searched knowledgebase. Finally, the TSTS method is able to operate on imprecise data and rank the search results.

The TSTS Method

In this section, the word node is used to denote a concept or a concept instance in a semantic network; the word edge -to denote a relation instance, and the word graph -to denote the semantic network.

Concept Similarity Measure

The TST (Theme-Space-Time) measure presented in this paper indicates similarity between two concept instances in a semantic network. The computation of this measure in done in three steps: weight mapping, fuzzy set creation, and distance measuring.

Weight Mapping

In a classical semantic network each edge has only a label associated to it. Therefore, it is only possible to indicate the presence or absence of a relation between two concept instances. The computation of the TST measure requires additional numerical value associated with the relation instances expressing their strength. Different ideas can be found in literature for devising a calculation that can generate a formula for the strength of each existing relation instance in the knowledgebase. However, despite the research, a formula that outperforms all the others in a large set of experiments, or proves to be the best for all application domains has not been found. In this paper the technique of calculating a numerical weight value based on analysis of link structure, called weight mapping, presented in [START_REF] Ziegler | Automatic computation of semantic proximity using taxonomic knowledge[END_REF] has been applied. The following specificity measure was used:

j ij n W 1 = . ( 1
)
The value n j is equal to the number of instances of a given relation type that have concept C j as its destination node. Therefore, the weight of the relation is inversely proportional to the number of relations with the concept C j . The more concepts with the same type as C i and related to C there are j , the higher W ij is.

Fuzzy Set Creation

In the fuzzy sets theory each element is given a degree of membership. Mathematically it is described with the aid of a membership function valued in the real unit interval [0,1]. Operations on fuzzy sets are generalizations of crisp set operations such as union or intersection. There is more than one possible generalization. Fuzzy intersection and fuzzy union are the functions that map the degree of membership from given sets into a new degree of membership.

The TSTS method requires that for each concept being measured the fuzzy set of points representing the concept in space-time continuum is created. The main idea is that if a given concept is related to other concepts that are positioned somewhere in time and space, there is a great possibility that the concept itself is also related to the same point.

For concept C i the membership function expressing the fuzzy set is expressed by the following recursive formula:

U j j Wij i i x x k x ) ( ) ( ) 1 ( ) ( µ α µ ⊕ - = . ( 2
)
) ( ) 1 ( ) ( ) ( x t W x s W x j i ij j i ij j i ∩ ∪ ⊕ - + = µ ) ( ) ( ) ( ), ( ) ( ) ( ) ( ) ( x x x t x x x x x s j i j i j i j i j i µ µ µ µ µ µ = - + = ∩ ∪ (3)
The s and t are the functions that were chosen for computing fuzzy union and fuzzy intersection, respectively.

During the process of computing the fuzzy set, for each propagation through an edge the degree of membership is reduced. The process repeats until newly visited nodes do not add any significant information or there are no further nodes to be processed. The k value corresponds to the percentage of the degree of the membership value that the membership function is decreased by every time an edge is processed, effectively functioning as an attenuation factor.

Measuring Distance

The TST measure is the distance between two nodes and it is the compound of the semantic distance in the semantic network, and the distance in time and space. It is defined by the following formula:

) , ( * ) , ( * ) , ( ) , ( j i t t j i g g j i s s j i d d C C d C C TST µ µ λ µ µ λ λ = . (4) Function ) , ( j i s C C d
is the semantic similarity between concepts C i and C j .

Computing the semantic similarity is widely discussed in the literature, where many different formulas were proposed. For the TSTS method, a function that simply counts the intermediate nodes on the shortest path between C i and C j was chosen.

The functions ) , (

Discussion

The TSTS method responses to the problem of searching objects in the cultural heritage domain, where concepts are dependent on time and geographical location. As a result, those concepts are imprecise both in the knowledgebases describing cultural heritage subdomains and in the query expression. Imprecision concerns rivers, seashores, islands, countries, periods, as well as artistic, literary and intellectual movements, etc. The use of fuzzy sets to represent concepts in the time-space continuum permits to deal with this imprecision. The TSTS method is independent of the knowledgebase schema. The search results may be ranked, as they have numerical values of the TST similarity measure attached.

Conclusions

The TSTS search method is particularly important in case of multinational and multicultural audience visiting a virtual museum. In such case, queries are imprecise more than ever, as searchers do not have background knowledge of the heritage domain. The TSTS method provides information that contributes to acquiring that knowledge, because it locates the concepts searched in time and space. Thanks to that location, the objects found may be presented in a clear and attractive way on maps and time scales.

Future research on the TSTS search method will be focused on the comparison of different measures. Generalization and specialization of concepts has to be taken into account to improve accuracy of the TSTS method, when applied in closed cultural heritage subdomains.

Fig. 1 .

 1 Fig. 1. A fragment of a simplified semantic model instance for a cultural heritage domain.

  between points in the fuzzy sets computed for concepts C i and C j in the geographic coordinates and time dimension respectively, expressed by the formulas:

  Function i µ denotes the fuzzy set for the concept C i . Function i α represents the region in the space-time continuum defined by the properties immediately defined for node C i . Function j µ denotes the fuzzy set for the concept C j being the neighbouring node of the node C i . Operator Wij ⊕ is able to interpolate between the fuzzy union and fuzzy intersection depending on the weight W ij of the relation between nodes C i and C j . This operator is defined by the following function:

where α µ > i is a set of points from the fuzzy set described by function i µ for which the degree of membership is greater then α .Value g i is the geographical part of an element in the fuzzy set. Value t i denotes the time part of an element in the fuzzy set. Parameters s λ , g λ , t λ are the scaling factors that allow the end user to weight which part of the measure is the most important.

Answering User Queries

Searching for cultural objects that satisfy a query specified by a user is performed in three phases: the resolving phase, the fuzzy set building phase, and the measuring phase. In the resolving phase each keyword or a phrase from the user query is mapped to an existing node in the underlying semantic network. In many cases a keyword alone cannot be used to unambiguously identify the node. In such case the user is presented with a list of matching nodes and is asked to indicate the concept or its instance of his/her interest.

In the next phase, a fuzzy set of points in the time-space continuum is created from the nodes contained in the user query. The nodes from the user query are joined through the three most common relations: and, or and not. The resulting fuzzy set is constructed using appropriate fuzzy set operations on the fuzzy sets corresponding to the nodes in the query -fuzzy intersection for and, fuzzy union for or, and fuzzy complement for not.

Finally, for each cultural object in the underlying knowledgebase the TST distance between the node representing the cultural object and the user query is computed. If the user query contains only one node, the TST distance has the form described in Section 4.1.3. If the user query consists of more than one concept, the semantic distance d s in the presented formula needs to be computed differently. The value d s is obtained by combining semantic distances between nodes referenced in user query and the currently analysed cultural object node using the same functions that were used to join the fuzzy sets. On the base of the TST measure the results are ranked. Those cultural objects for which the TST distance is the lowest are the best match.

In the presented TSTS method, the results can be shown as a flat list, because the TST measure is a numerical value. However, the final value of TST measure is compounded of three distances -in semantic, temporal and geographical dimension. All those distances can be separately visualized for each object found, giving a user a better understanding of why a particular cultural object was considered. Moreover, the fuzzy set constructed from the user query can also be visualized, indicating the actual area in time and space that was covered by the user query.


Carlos Simplício
email: simplicio@estg.ipleiria.pt

José Prado

Jorge Dias

A Face Attention Technique for a Robot Able to Interpret Facial Expressions

Keywords: Facial Symmetry, Focus of Attention, Dynamic Bayesian Network

Automatic facial expressions recognition using vision is an important subject towards human-robot interaction. Here is proposed a human face focus of attention technique and a facial expressions classifier (a Dynamic Bayesian Network) to incorporate in an autonomous mobile agent whose hardware is composed by a robotic platform and a robotic head. The focus of attention technique is based on the symmetry presented by human faces. By using the output of this module the autonomous agent keeps always targeting the human face frontally. In order to accomplish this, the robot platform performs an arc centered at the human; thus the robotic head, when necessary, moves synchronized. In the proposed probabilistic classifier the information is propagated, from the previous instant, in a lower level of the network, to the current instant. Moreover, to recognize facial expressions are used not only positive evidences but also negative.

Introduction

Usually, human beings express their emotional states through paralinguistic cues, e.g., facial expressions, gaze, gestures, body positions or movements. Among all, our main work focuses specifically on human facial expressions.

Automatic facial expression recognition systems have many potential applications. They can be used in medicine / psychology, surveillance or in intelligent humanmachine interaction. In this paper is proposed a human face focus of attention technique and a Dynamic Bayesian Network to classify human beings facial expressions. They will be incorporated in a companion robot, an autonomous mobile agent, whose hardware is composed by a robotic platform and a robotic head. The autonomous agent must observe and react according to the facial expressions of a person. This agent will be used in the context of assisted ambiance. The global project addresses the emergent tendencies of developing new devices to the elderly community.

Related Work and Contribution to Technological Innovation

A great part of the research done in facial expressions uses the tool FACS (Facial Action Coding System) proposed by Ekman [START_REF] Ekman | Facial Action Coding System -The Manual. A Human Face[END_REF]. FACS was developed to describe the visible "distortions" on the face produced by muscular activity.

Some studies about techniques to find automatically the vertical symmetry axis of human faces were published. Hiremath and Danti [START_REF] Hiremath | Detection of multiple faces in an image using skin color information and lines-of-separability face model[END_REF] proposed a bottom-up approach to model human faces. In this method a face is explained by various lines-ofseparability, being one of them the axis of symmetry. Chen [START_REF] Chen | Fully automated facial symmetry axis detection in frontal color images[END_REF] proposed a method to automatically extract the face vertical middle line. In their method the histogram of gray level differences (between both sides of the face) is build. The symmetry axis corresponds to the line with maximal Y value (obtained as the relation between the number of events equals to the mean and the variance of the histogram). Nakao [START_REF] Nakao | Automatic detection of facial midline and its contributions to facial feature extraction[END_REF] applied the generalized Hough transform to find the vertical symmetry axis in frontal faces.

Various attempts have been done to develop a system classifying human facial expressions, but only a few through Bayesian networks. One of these classifiers was presented by Datcu and Rothkrantz [START_REF] Datcu | Automatic recognition of facial expressions using bayesian belief networks[END_REF]: it is a Bayesian belief network that handles behaviors along the time. A Bayesian network with a dynamic fusion strategy was developed by Zhang and Ji to classify six facial expressions [START_REF] Zhang | Active and dynamic information fusion for facial expression understanding from image sequences[END_REF].

Facial expressions recognition becomes easier if done in frontal face images. Normally, the image acquisition device is fixed and does not follow the head movements. To solve this problem, 3D models of the human face, projections of textures in the model and geometric transformations are used to obtain a image of a frontal face. In this paper a different method to get always a frontal face image is proposed: a robotic system is used to follow the human being movements. In the proposed technique of human face focus of attention, the robotic platform navigate, running an arc centered in the human, to keep always targeting the face frontally. If necessary, the robotic head rotates in synchronization with the platform. The approximated symmetry presented by human faces is the attribute to support the extraction of information to control the tasks of movement.

Facial expressions recognition is performed by a Dynamic Bayesian Network (DBN). With this classifier, one of six emotional states (anger, fear, happiness, sadness, neutral or other) will be assigned to the human being. The evidences provided to the DBN are derived from some Action Units as defined by Ekman [START_REF] Ekman | Facial Action Coding System -The Manual. A Human Face[END_REF]. However, unlike other authors, positive and negative evidences are used explicitly to obtain the probability associated with each facial expression (for the neutral facial expression are used just negative evidences, therefore it is an exceptional case). There is another difference from previous works: the information is propagated along time in a low level, near the nodes which collect the evidences from the sensors.

Autonomous Mobile Agent (AMA)

The Autonomous Mobile Agent (AMA) architecture is presented in Fig. 1. At hardware level, the AMA consists in a Robotic Head and a Robotic Platform. The commands (head movement and platform movement), to put the AMA frontally to the human being face, are sent to the hardware by the Robotic Systems Controller (RSC). This module (it is briefly described in sub-section 3.1) receives an input, face pose, coming from the module Face Pose Identification System (FPIS). As is explained in sub-section 3.2, FPIS processes an image to provide the respective output, face pose. With the Robotic Head positioned "face-to-face" with the human being, the module Automatic Facial Expression Recognition System (AFERS) takes an image and provides the respective Emotional State in probabilistic terms. This output is associated with a discrete random variable with six events (anger, fear, happy, sad, neutral and other). Specifically, the system output is composed by six probabilities: p(anger), p(fear), p(happy), p(sad), p(neutral) and p(other). In sub-section 3.3 is presented the Dynamic Bayesian Network which provides this module output.

Robotic Systems Controller (RSC)

The Robotic Platform does three types of movements (longitudinal or transversal translations and rotations) following the commands provided by the RSC.

Longitudinal translations are performed to approach or move away the AMA from the human being. The objective is keeping the image of the human being face with the same number of pixels. Transversal translations are performed to keep always the face in the centre of the image.

Rotations correspond to an arc of circle centered in the human being. These movements are performed to follow the rotation movements done by the human being, getting always an image of a frontal face.

The Robotic Head can move in synchronization with the platform when it is necessary.

Face Pose Identification System (FPIS)

In a perfect bilateral symmetric image, the difference between a pixel value and the respective symmetric counterpart is zero. By nature, human faces do not present a perfect bilateral symmetry and it is reflected in the acquired images. Moreover, the "imperfections" in the images are worsened by the noise associated to the acquisition process or due to lights distribution. Despite this, gray-level differences can be used to detect the bilateral symmetry axis of a human face.

The theoretical method used to identify the axis of symmetry is based on rather simple principles but is very effective. A vertical axis is defined to divide the face image region in two parts with equal number of pixels and a Normalized Gray-level Difference Histogram (NGDH) is built. When the face is frontal, this vertical axis bisects it and the information collected in the NGDH is strongly concentrated near the mean. If the camera is fixed, when the face rotates the defined axis is not a symmetry axis and the information is scattered along the NGDH. In practice, instead the mean, is used a narrow region (+/-10 units) around it: the pseudomean.

Our method requires a frontal face just in the initialization, but it assumes in all phases an upright face. The algorithm begins performing the face detection using Haar-like features [START_REF] Viola | Robust real-time face detection[END_REF]. In this way, a region of interest is found and a vertical axis is established in the middle of this region. To find the real face orientation, the region of interest is successively rotated about that axis using a 3D transformation. Five rotation angles, taken from interval [-30; +30] with 15º steps, are used to generate five synthetic images. For every synthesized image, the NGDH is built and the probability of pseudomean is computed. The five probabilities are compared. The real face orientation, corresponding to the great probability, is sent inside the command face pose to the module RSC.

Automatic Facial Expressions Recognition System (AFERS)

Psychologists identified seven transcultural emotions. In this paper we will only consider five of them (anger, fear, happiness, sadness and the neutral state). Normally, every emotional state has a characteristic facial expressions associated to it. In Fig. 2 are presented examples of facial expressions. The AFERS try to recognize local facial actions as defined in FACS [START_REF] Ekman | Facial Action Coding System -The Manual. A Human Face[END_REF]. FACS defines a total of 52 Action Units (Aus). Eight of them are related with the head pose.

The remainder 44 concern to facial expressions. Each of these AUs is anatomically related to the activity of a specific set of muscles which produces changes in the facial appearance (in our work, only a sub-set of these AUs is used). A facial expression can be interpreted as a set of specific AUs, which cause "distortions" in facial features (i.e., mouth, eyes, eyebrows or noise). Identified these "distortions", facial expressions can be recognized.

Inside the AFERS, there is a specific module to classify the facial expressions: a Dynamic Bayesian Network (DBN). Fig. 3 presents part of the structure of this classifier of 6 levels. At the DBN's first level there is only one node. The overall classification result is provided by the random variable associated with this node: Emotional State ∈ {anger, fear, happy, sad, neutral, other}. First five events correspond to emotional states that actually are intended to classify. The sixth (other) is used for completeness when the facial expression does not fit the five preceding categories.

In the second level there are five nodes, one for every facial expression associated to an emotional state to recognize. To each node is associated one of the following variables: E-Anger ∈ {no, yes}, E-Fear ∈ {no, yes}, E-Happy ∈ {no, yes}, E-Sad ∈ {no, yes} or E-Neutral ∈ {no, yes}; where two events are associated with each variable.

After the second level, the structure presented in Fig. 3 is not complete. The figure only shows, from top to bottom, all the nodes and arcs used to classify the facial expression corresponding to happiness (since a similar structure is used to the other emotional states, we avoid to overcharge the figure). In the following, description will only be made to the happiness emotional state.

To the happiness, in the third level of the DBN, there are eleven nodes which are associated with the following variables: EH-AU1-N ∈ {no, yes}, EH-AU4-N ∈ {no, yes}, EH-AU6-P ∈ {no, yes}, EH-AU7-N ∈ {no, yes}, EH-AU12-P ∈ {no, yes}, EH-AU15-N ∈ {no, yes}, EH-AU17-N ∈ {no, yes}, EH-AU20-N ∈ {no, yes}, EH-AU23-N scene in our laboratory with the human face segmented. From (c) to (g) are the synthesized face images after the application of the 3D transformation and, from (j) to (n), the correspondent NGDHs. The pseudomean probability increases as the synthesized image becomes more similar to a frontal face, as it is observable at the histograms. In (h) is illustrated graphically the output as a line segment drawn superimposed to the segmented face. The angle of this segment, referenced to the image vertical axis, corresponds to the real human head orientation. In this case a vertical segment means a frontal face.

Even when the human is not facing the AMA, always one of the synthesized images presents a near frontal face and the real orientation can be found.

Fig. 4.

Working principles of the technique to find the real head orientation. In (a), image of a scene with a frontal face segmented. In (b) is defined the positive direction of the rotations used to synthesize images. Synthesized images after applying a 3D rotation with an angle of (c) -30º, (d) -15º, (e) 0º, (f) +15º and (g) +30º. NGDHs of the synthetic images generated for an angle of (j) -30º, (k) -15º, (l) 0º, (m) +15º and (n) +30º. In (h) is presented the output: a vertical line segment means a 0º head orientation. In (i) is defined the vertical axis reference of the output image.

The implementation of the presented DBN architecture is actually under test. Reaching conclusions based on negative evidences is something that should be done with special care because it can lead to mistakes. However, unlike other types of classifiers, Bayesian networks can treat negative evidences naturally and correctly through priors values near zero. Anyway, in the proposed method, the classification is done using mainly the positive evidences. The two main exceptions are neutral and other emotional states.

Conclusions and Further Work

In this paper is proposed a human face focus of attention technique and a Dynamic Bayesian Network structure to classify facial expressions. Both are to incorporate in an autonomous mobile agent whose high level architecture is also proposed here.

The focus of attention technique has a good performance, is fast and easy to implement. In the future we intend to use it as a valuable help to automatically extract facial feature points without the use of a complex 3D model. Before that, the technique will be validated more rigorously attaching a inertial sensor to the human head and comparing its outputs with that of the proposed method.

The proposed DBN uses explicitly two types of evidences (negative and positive) and the temporal information is propagated at a low level. The preliminary tests done with the DBN showed that it has great potentialities. We intend to build a simpler version of the proposed DBN (using only positive evidences) and, comparing the two versions, prove the real advantages incoming by the use of negative evidences.

Fig. 1 .

 1 Fig. 1. Autonomous Mobile Agent (AMA) -principal modules.

Fig. 2 .

 2 Fig. 2. Facial expressions associated to some transcultural emotional states: (a) anger, (b) fear, (c) happiness, (d) neutral and (e) sadness.

Fig. 3 .

 3 Fig. 3. Dynamic Bayesian Network (DBN) -partial structure. Light nodes are of the present time slice, while dark nodes belong to the previous one (t-1). The dashed arrows connect nodes of different time slices: from past to present and from here to future (these nodes are not represented).

Acknowledgments. The authors gratefully acknowledge support from EC-contract number BACS FP6-IST-027140, the contribution of the Institute of Systems and Robotics at Coimbra University and reviewers' comments.

∈ {no, yes}, EH-AU24-N ∈ {no, yes} and EH-AU25-P ∈ {no, yes}. The events associated with these variables are related to the absence or presence of "distortions" (respectively on eyebrows, eyes and mouth) that are relevant to the facial expression. The probabilities assigned to events of these third level variables depend on evidences (positives and negatives) strength.

In table 1 are discriminated, for every facial expression, the AUs that lead to positive or negative evidences. For example, to happiness, the AU6 is positive evidence, but AU7 is negative evidence. From this table it is possible to reconstitute completely the structure of the DBN. It is through the nodes of the fifth level that information is propagated between time slices. In Fig. 3 this propagation, from past or to future, is represented by dashed arrows, and dark nodes are those of a previous time slice (t-1). As an example, EH-AU1 State(t)∈ {minimum, low, medium, high, maximum} is a variable associated to one node of this fifth level in present. The functionality of the fifth level nodes is to combine / fuse probabilistically, through inertia, information coming from the low level in present time slice with that from the previous instant. After the fusion, the information is used in the present by the high level nodes and is made available to the next time slice to be fused therein.

In the sixth level of the DBN are the nodes associated with variables collecting the evidences provided by the sensors. For example, EH-AU1 Sensor ∈ {minimum, low, medium, high, maximum}, is one of those variables.

Discussion of Results and Critical View

Fig. 4 presents some results obtained by the proposed technique to identify the head orientation when the human is facing the AMA directly. In image (a) is showed a


Mihai Duguleana
email: mihai.duguleana@unitbv.ro

Gheorghe Leonte Mogan
email: mogan@unitbv.ro

Using Eye Blinking for EOG-Based Robot Control

Keywords: electrooculography, robot, control, human-robot interaction, eye blink

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

Robot control is one of the key fields in Robotics. Efficient alternative controlling capabilities are important for motor-disabled persons, elderly people and patients suffering from several types of Sclerosis or other diseases that affect hand and facial muscles. Using information from multiple sensor devices will also increase the quality of HRI when applying sensor-fusion.

Human eye movements have been recently used with success in human-computer interaction by several researchers [START_REF] Barea | Guidance of a Wheelchair Using Electrooculography[END_REF], [START_REF] De Peralta Menendez | Modern Electrophysiological Methods for Brain-Computer Interfaces[END_REF], [START_REF] Usakli | On The Use of Electrooculogram For Efficient Human Computer Interfaces[END_REF] and [START_REF] Youngmin | Robust Discrimination Method of the Electrooculogram Signals for Human-Computer Interaction Controlling Mobile Robot[END_REF]. Most of the applications based on this kind of feedback are conducted in fields like Virtual Reality, Robotics and Biomedicine.

Eye movements can be recorded in 3 ways: with magnetic coils, using video processing or using EOG [START_REF] Usakli | On The Use of Electrooculogram For Efficient Human Computer Interfaces[END_REF]. Video processing and EOG are most used techniques, however, although video processing requirements are very easy to fulfill (just a quality camera), EOG tends to produce more quality outputs in terms of speed and error. While in the video-based approach, the camera scans for the eyes of the subject and measures the movement using powerful yet time consuming image processing libraries, in the EOG approach, a simple low cost device can use one or two pairs of electrodes to measure the resting potential of the retina. This potential is the result of eyeball movement within the conducting environment of the skull and it varies proportional to the amplitude of eye movements [START_REF] Barea | Guidance of a Wheelchair Using Electrooculography[END_REF].

Several other researchers have been conducting related studies to the subject of our paper. In order to use EOG, some researchers have been able to reduce noise in EOG recordings by filtering the heart beating pollution from the output signal and by eliminating the drift that appears randomly when the subject is moving his eyes [START_REF] Usakli | On The Use of Electrooculogram For Efficient Human Computer Interfaces[END_REF], to minimize the signal differences between different testing subjects or to eliminate certain signals [START_REF] Manoilov | An Algorithm for Eye-Blinking Artefacts Duration Determination[END_REF] and to control wheelchairs and other mobile robots [START_REF] Barea | Guidance of a Wheelchair Using Electrooculography[END_REF].

Different types of signals have been identified for each of the following actions: blinking, horizontal and vertical saccadic motions or winking [START_REF] Youngmin | Robust Discrimination Method of the Electrooculogram Signals for Human-Computer Interaction Controlling Mobile Robot[END_REF].

There are also available comparisons between different EOG devices and their efficiency or between measuring methods such as EOG, EEG and EMG [START_REF] De Peralta Menendez | Modern Electrophysiological Methods for Brain-Computer Interfaces[END_REF]. The research question which we approach is whether robust robot control in real time using EOG can be achieved.

In this paper, we focus on developing a simple motor controlling application for commanding the grasping modules of a humanoid robot using EOG. We propose a new algorithm for blinking detection in real-time EOG applications. Furthermore, we describe in the "Experimental Setup" section the equipment we have used for conducting our research and conclude in the last section with implementation issues and further research problems.

Contribution to Technological Innovation

Although there have been several attempts to clearly delimitate a good interaction model between humans and robots using EOG information, most of the literature focuses on offline control and saccadic eye movements processing [START_REF] Choudhury | Design and Development of a Novel EOG Biopotential Amplifier[END_REF]. Most of the experiments are based on EOG devices that require skin preparation (skin scrubbing) and the appliance of conducting gel between the electrode surface and the skin of the subject. We present a system the uses dry electrodes and wireless technology for communicating with the processing unit, thus speeding up the testing process and increasing the flexibility of this solution.

We foresee the implementation of a fully functional EOG-based device that could be used in industrial environment for integrating people with disabilities into the work field or for achieving more precise robot control as one of the practical technological applications that can be developed based on the results presented this paper.

EOG-based Robot Commanding Paradigm

Having eye blinking the only form of input increases the robustness of the system. We propose a new commanding paradigm for real-time control with eye blinking in an EOG-based HRI (see Fig. 1).

The EOG device mounted on the subject's head sends amplified data to the computer unit. Considering the continuous attribute of the experiment, we split the application into 2 threads. In the signal processing module, the data is processed and the result is sent to the state handler. Several filters (like noise, drift and other biometric algorithms) are contributing to robust eye blinking identification.

Depending on the state of the robot and on the previous data received by the state handler, this module accesses predefined commands of the robot. The handler consists of 2 states: the waiting state and the active state. One may choose to let the robot finishing its previous tasks before engaging into other new activities, or to override these with the new received command. As data is continuously received from the signal processing module, some commands that are quickly assessed may have a certain initial value that may change its meaning when receiving new information. In the first part of this section we describe the experimental equipment used for completing our study. We then present the algorithm used for detecting eye blinking. We end this section with a critical analysis of experiment results.

Experimental Setup

We are using for this experiment an EOG solution from Starlab Company. The wireless electro-physiology sensor system (presented in the left side of Fig. 2) is mounted on the subject's head; 2 of the electrodes are placed on the sides, the other 2 above each eye and the Driven Right Leg (DRL) circuit (the reference) on the right ear of the subject (center Fig. 2). DRL circuit is particularly important because it influences the quality of measurements. We are using for DRL conductive gel to increase the common-mode rejection ratio (CMRR) and to improve the noise immunity [START_REF] Enobio | [END_REF].

When blinking, humans use their facial muscles. Because of this, the EOG blinking signal is very strong, thus allowing us to mount the electrodes in approximate positions without having to worry about data loss.

The EOG wireless device sends data to a USB modem connected to our computer. The Enobio application auto-filters the signal and uses Channels 2 and 3 for providing EOG information.

The computer that handles the entire experiment is also connected in the same network with a humanoid robot called NAO and produced by Aldebaran Company (right side of Fig. 2). We will command the hand grippers of the robot, differentiating between left and right motors by blinking once or blinking two times.

Processing Blink Signal

Considering a normal EOG wave signal, the event of a blink triggers a peak occurrence in the amplitude values recorded by Enobio software, far higher than any other possible noise that the EOG measurement might have if the blink wouldn't exist. As seen in Fig. 3, an average blink lasts between 100ms and 200ms (these values vary depending on the subject's bio-attributes, fatigue level, eye health and other factors) and reaches up to a 400µV (a 250-300µV in average) maximum before returning to the mean voltage level that was recorded before blinking.

Using the above observations, we may detect blinks by adding a preset minimum threshold which should filter most of the noise and false peaks. Unfortunately, there are some cases in which the signal wave experiences a drift -sometimes the voltage increases with similar values like the ones recorded from blinks. We can further filter these cases by setting a maximum threshold and calculating difference between the minimum values recorded before and after peak occurrence. When implementing these restrictions in real time, we apply the following algorithm written in pseudocode:

In order to differentiate between one and multiple blinks, we will use the time retained from the last acknowledged blink. Two or more blinks occur continuously, one wave after another. We expect i.e. to record two blinks within a maximum 500ms timeframe. We will set this interval to be the waiting period after which we decide if the subject has blinked once or twice.

Discussion of Results

We compare the data received from Enobio device and processed by our application with the data saved by Enobio in EDF format, available the end of each session. The differences are presented in Fig. 4.

The main problem faced by real-time computing is the processing time. Intel processors (as any other processor) execute instructions once every few milliseconds, depending on their clock frequency and their interruption rate. We can try to increase the interrupt rate granularity using Microsoft Windows Multimedia SDK (for Win 32 systems), thus improving the preciseness of our system, but this comes with a severe power cost. The algorithm used for data decoding and processing also requires a few milliseconds, as well as receiving data from the wireless modem. Summing up all these times, our system (Intel Core 2 Duo T9300, 2.50 GHz, 2GB DDR2 SDRAM, Window Vista) works with data received every 15 to 20ms. This limitation has serious impact on the recorded wave. There are cases when blinks are missed, or data is seriously affected. After 20 measuring sessions on a single subject (313 recorded blinks), we can calculate the average blink recognition rate to be 56.23%. The double blink recognition rate (28 recorded double blinks) is 42.85%. The results are displayed in Fig. 5.

Conclusions and Further Work

Integrating the proposed EOG-based HRI paradigm for real-time robot controlling in real life can be both useful and time-saving. The main result is that people with severe movement-disabilities will be able to have an efficient interaction with environment. Although the implementation of the described paradigm requires bypassing issues like the need of complete redesign of the living environment, control with eye blinking can be achieved. After extending the symbolic functions presented in our experiment, persons with paralyzed facial muscles will be able to use robots to fulfill a wide variety of tasks. Fig. 5. Analyzing the recognition rates for single and double blinks, over a dataset of 20 test sessions. On the OX axis is displayed the session number and on the OY axis, the number of occurrences.

The experiment results depend with the system on which we run the application. Further work will be conducted into performing the experiment on different hardware and software platforms.

The computation times need to be lowered as much as possible. Further work will be conducted into improving the communication between the EOG equipment and the processing unit, optimizing the source code of the application and reconsidering the thresholds values to more precise ones, obtained after statistically analyzing data from multiple sessions.

Fig. 1 .

 1 Fig. 1. Real-time eye blinking EOG-based HRI paradigm.

Fig. 2 .

 2 Fig. 2. Experiment setup. Left side -EOG device with 4 electrodes and wireless transmitter (Enobio equipment), center -Enobio electrodes setup (head scheme), right side -humanoid robot (Nao).

Fig. 4 .

 4 Fig. 4. Comparing recorded results (first graph) with EDF stored results (bottom graph). In this experiment session, the first three blinks are properly recorded and processed. The following two blinks are missed due processor delay. The next 3 blinks are also properly assessed. The continuous blinking at the end of the session is missed by the application.

Acknowledgments. This paper is supported by the Sectoral Operational Programme Human Resources Development (SOP HRD), financed from the European Social Fund and by the Romanian Government under the contract number POSDRU/6/1.5/S/6 and by the national research grant ID_775/2009. The experiments were conducted at Italian Institute of Technology (IIT), Italy.

The algorithm searches for amplitude points recorded at the end of a peak, after a certain period from the last acknowledged blink, to ensure that we do not count twice the same recording. If local minimum is found, we sequentially check for the maximum value recorded within a proper time interval, compare it with minimum (240µV) and maximum thresholds (450µV), search for the minimum value recorded before the occurrence of maximum and compare it with current data to eliminate drift errors. In the event of a valid result (i.e. a maximum 100 µV difference between the 2 minimums), we compute the command and retain the occurrence time.


Pedro Pereira

M Helena Fino
email: hfino@ieee.org

Fernando Coito

Mário Ventim-Neves

GADISI -Genetic Algorithms Applied to the Automatic Design of Integrated Spiral Inductors

Keywords: Discrete-Variable Optimization, Genetic Algorithm, Spiral Inductor Design

This work introduces a tool for the optimization of CMOS integrated spiral inductors. The main objective of this tool is to offer designers a first approach for the determination of the inductor layout parameters. The core of the tool is a Genetic Algorithm (GA) optimization procedure where technology constraints on the inductor layout parameters are considered. Further constraints regarding inductor design heuristics are also accounted for. Since the layout parameters are inherently discrete due to technology and topology constraints, discrete variable optimization techniques are used. The Matlab GA toolbox is used and the modifications on the GA functions, yielding technology feasible solutions is presented. For the sake of efficiency and simplicity the pi-model is used for characterizing the inductor. The validity of the design results obtained with the tool, is checked against circuit simulation with ASITIC.

Introduction

The rapid growth and reduced cost of communication systems operating at high frequencies, has motivated the development of devices with a large number of elements implemented in integrated circuit. In the particular case of RF transceivers, voltage controlled oscillators (VCOs) are responsible for the purity of the signal generated. For these applications LC-VCOs are often chosen due to their phase-noise behaviour. The performance of the LC-VCOs is well determined by the quality factor of the spiral inductor.

For the design of spiral inductors, designers usually adopt methodologies based on either pre-characterized inductor designs or ad hoc techniques [START_REF] Hamm | Design of Integrated LC VVCOs[END_REF]. In either case designing a spiral inductor involves the determination of multiple correlated variables. Due to the complexity of the design, optimization-based techniques have been proposed [START_REF] Nieuwoudt | Multi-level Approach for Integrated Spiral Inductor Optimization[END_REF], [START_REF] Allstot | Parasitic-Aware Optimization of CMOS RF Circuits[END_REF] and [START_REF] Chan | LTCC Spiral Inductor Modeling,Synthesis and Optimization[END_REF]. In these approaches, however, continuous variable optimization techniques are employed and constraints are considered only on the bounding values for the inductor layout parameters. Technology-constrains regarding the discrete nature of the variables is dealt in a subsequent procedure where the layout parameters obtained from optimization are rounded to the nearest technology feasible value. This methodology usually yields sub-optimum solutions where the correlation of the parameters obtained is not granted.

During the last years GAs have been widely used in circuit design [START_REF] Stelmack | Genetic Algorithms for Mixed Discrete/Continuous Optimization in Multidisciplinary Design[END_REF] and [START_REF] Wankhede | Optimization of Cell-based VLSI Circuit Design using a Genetic Algorithm: Design Approach[END_REF]. This paper introduces a GA tool for the optimization-based design of spiral inductors. In this tool the solution is obtained considering user-defined constraints in the design, reflecting a discretization of the variable values according to the technology used. Further constraints imposing bounds on the ratio between design variables are also accounted for as a way of supporting design heuristics. The tool offers the possibility to choose the performance parameter to be optimized, such as maximizing the quality factor, Q, at a given operation frequency, or the minimization of the area occupied by the device. The tool was developed in Matlab and the GA optimization toolbox was used. The validity of the solution obtained is checked against results from simulation with ASITIC simulator.

Contribution to Technological Innovation

The main objective of the optimization based tool presented is to generate the geometrical layout parameters of integrated spiral inductors. For this purpose two main concerns were considered. On one hand a technology-aware methodology is adopted where the discrete nature of the variables is accounted for as a way of restricting the search space to those points allowed by the technology. Further constraints arising from heuristic design rules are also considered. On the other hand the necessity for obtaining solutions in an efficient way led to the use of the inductor physical model, instead of using a simulation based approach.

Planar Spiral Inductor Pi-Model

The efficiency of the optimization tool is obtained through the use of an inductor model. For the sake of simplicity the pi-model, illustrated in Fig. 1.a., is adopted. For the evaluation of the inductance, Ls, several approaches have been proposed, based on a fitting process to values obtained experimentally [START_REF] Mohan | Simple Accurate Expressions for Planar Spiral Inductances[END_REF], or through physicsbased equations [START_REF] Jenei | Physics-Based Closed-Form Inductance Expression for Compact Modelling of Integrated Spiral Inductors[END_REF]. In this tool the Modified Wheeler formula is used [START_REF] Mohan | Simple Accurate Expressions for Planar Spiral Inductances[END_REF], where ( )

2 s 1 0 avg 2 L =k µ n d 1+k ρ , (1)
given that

( ) ( ) ( ) ( ) out in out in avg out in out in ρ= d -d d -d , d =0.5 d +d , d =d +2 n w+2 n-1 s . (2.a) (2.b) (2.c)
where, n is the number of turns, s is the track to track distance, and w is the track width, as represented in Fig. 1.b. Finally, k 1 and k 2 , are coefficients allowing the model to be adapted to several inductor shapes [START_REF] Mohan | Simple Accurate Expressions for Planar Spiral Inductances[END_REF]. The evaluation of R s, R si C s , C ox , and C si , is obtained with equations in [START_REF] Choi | Experimental Analysis of the Effect of Metal Thickness on the Quality Factor in Integrated Spiral Inductors for RF ICs[END_REF] and [START_REF] Murphy | Advanced Physical Modelling of Multilayer Inductors for CMOS RF Front-End Applications[END_REF].

Genetic Algorithms Applied to Integrated Inductor Design

Genetic Algorithms (GAs) are a stochastic search method that mimics the natural biological evolution, operating on a population of potential solutions, applying the principle of survival of the fittest to produce better and better approximations to a solution. GAs can be applied to any problem that can be formulated as function optimization problems. As a result, they are applied to non-linear problems, defined on discrete, continuous or mixed search spaces, constrained or unconstrained. Besides that, GAs are conceptually simple and have proved to be robust to dynamic changes.

The main advantages of using GAs in optimization problems instead of the more traditional search and optimization methods reside in the fact that they search a population of points in parallel instead of a single point, thus making results less sensitive to the point chosen. Furthermore, GAs do not require derivative information or previous knowledge, they handle noisy functions well, and are resistant to becoming trapped in local optima [START_REF] Sivanandam | Introduction to Genetic Algorithms[END_REF].

The optimization tool developed was implemented with the Matlab GA toolbox. Since this toolbox shows several limitations for discrete optimization problems, where each variable has an imposed step-size, three functions were developed. The flowchart showing the process of GA is represented in Fig. 2, where the additional functions, are shown with a dark background.

Optimization Methodology for Inductor Design

The methodology adopted aims to achieve a technology/topology-aware solution, where constraints are mandatory. Regarding the number of turns, n, it was considered to have a minimum value of 1.5 and subsequent values are obtained with an unitary increment, i.e., [ [ n 1.5,2.5,3.5,..... , ∈

Due to the inductor model considered the shape of the inductor must account for square, hexagonal and octagonal topologies.On what concerns the technological constraints, minimum values for the track width, w, for the track-to-track spacing, s, and for in input diameter, d in , must be defined. Technology-depend minimum increment values for these layout parameters must also be considered. Finally the correlation between the layout parameters defined by ( 4) is considered, as a way of including heuristic design rules for reducing the parasitic phenomena due to the proximity effect [START_REF] Aguilera | Design and Test of Integrated Inductors for RF Applications[END_REF]. Concerning the cost function three different scenarios are available yielding either the minimization of the tolerance, δ, the minimization of the device area, d out , or the maximization of the quality factor, for a predefined frequency of operation and a maximum output diameter, d out [START_REF] Pereira | ADISI -An efficient tool for the automatic design of integrated spiral inductor[END_REF]. For the pi-model, the expression of the quality factor becomes [START_REF] Yue | Design Strategy of On-Chip Inductors for Highly Integrated RF Systems[END_REF] ( )

( ) ( ) 2 2 2 s s s p p s p s s s p s ω L Q= ωL R R R + +1 R 1-C R L -ω L C . R               ⋅ ⋅                 (6)
Where ( )

( ) ( ) 2 2 2 2 p ox si si ox si ox R = 1 ω C R + R C +C C (7) ( ) ( ) ( ) si si 2 2 2 2 2 p ox ox si si ox si C = C 1+ω C +C C R 1+ω C +C R (8)
For the inductor design, the GA procedure starts with the creation of the initial population, where each individual is composed by four variables (w,d,n,N), representing the layout geometry parameters. The initial population is randomly created, but the individual's genes must obey to variable boundaries. Represented in Fig. 2 an alternative functions for creating an integer-valued population is used. The population is converted to real values and then evaluated through the objective function. In this function each individual is evaluated according to the constraints imposed and if it is not compliant, a penalty is applied so that it shows a very low probability of being elected for the next population. The algorithm stops here, if termination conditions are verified.

The next step accounts for the generation of a new population. Here selection and reproduction functions are used. For the selection the roulette wheel method is chosen. Afterwards, reproduction (or mutation) is made. Due to the difficulty of Matlab in dealing with real-valued population with predefined step-size, a mutation function was defined, allowing the creation of a new population of integer-valued individuals.

Results

The results presented in this section spotlight the ability of the developed GA-based tool to achieve optimal design of spiral inductors. The design of 7 nH inductor for an operation frequency of 0.8 GHz is addressed, where the technological parameters shown in Table 1 are used to evaluate R si , C s , C ox and C si . The determination of the layout parameters is done according to the constraints represented in Table 2. Also a minimum space between tracks of 1.5 µm and a maximum tolerance δ of 2.5%, are assumed. In this section, three examples are addressed. In example A, the inductor layout parameters minimizing the tolerance, δ, are computed; example B deals with designing an inductor with the smallest device area. Finally in example C an inductor with maximum quality factor, given a maximum output diameter of 500 µm is obtained. In examples B and C the tolerance, δ, is an additional constraint, with maximum value of 2.5%. The results obtained are presented in Table 3. Regarding the results in Table 3, for the working example A, we should mention that several different results can be obtained for the same goal. This means that there is a grid of solutions that match the objective. On the other hand for examples B and C the use of a maximum tolerance, δ, as an additional restriction, leads to the optimum result shown. It is also possible to conclude that there is a commitment between Q and d out ,i.e., when maximizing Q, the largest area is chosen. The validity of these results was checked against simulation with ASITIC yielding results shown in Table 4.

Conclusions

This paper introduces a tool for the determination of the layout parameters of CMOS spiral inductors. In this tool a GA optimization methodology is adopted, where constraints on the values of the variables representing the layout parameters are used. These constraints regard not only a limitation on the maximum/minimum values of the variables but also a discretization on their values. This enables the generation of the best solution for the technology used. Further constraints imposing predefined correlation between layout parameters are considered as a way of implementing heuristic design rules. Three working examples showing the design of an inductor for different optimization goals were shown. The solutions obtained are in good accuracy when compared to simulation results, with errors below 7%.

The evolution of the tool to a multi-objective optimization will be addressed, allowing designers to have a better understanding of the solution space, and to choose the best solution. The main limitation of the work proposed resides in the applicability of the tool to higher frequencies. This limitation is inherent to the pi-model used for the integrated inductor. The inclusion of more appropriate high frequency model will be considered as a continuation of the work proposed.

Fig. 1 .

 1 Fig. 1. a) Planar inductor pi-model; b) Layout of a square inductor.

Fig. 2 .

 2 Fig. 2. Simple Genetic Algorithm flowchart.

  Cost(n,d in ,w,N) and L(n,d in ,w,N) as the cost function and the inductance of the spiral, and L exp and δ the targeting inductance value and the Integer Mutation Create initial population of integer valued Create initial population Matlab GA Toolbox fnc Evaluate fitness for each population Mapping Integer to real values Optimal or good solution found? Selection for Reproduction Create new population Matlab GA Tbx Stop Yes Start tolerance allowed for the inductance to deviate from the targeting value, the optimization problem is formulated as the minimization of Cost(n,d in ,w,N) subject to

  function Population = integer_pop(GenomeLength,FitnessFcn,options) totalpopulation = sum(options.PopulationSize); range = options.PopInitRange; lowerBound= range(1,:); span = range(2,:) -lowerBound; % ROUND fun guarantee that individuals are integers Population = repmat(lowerBound,totalpopulation,1) + ... round(repmat(span,totalpopulation,1) .* rand(totalpopulation,GenomeLength)); % End of creation function

  function mutationChildren = integer_mutation(parents,options,GenomeLength, ... FitnessFcn,state,thisScore,thisPopulation) shrink = 0.1; scale = 1.0; scale = scale -shrink * scale * ... state.Generation/options.Generations; range = options.PopInitRange; lowerBound = range(1,:); upperBound = range(2,:); scale = scale * (upperBound -lowerBound); mutationPop = length(parents); mutationChildren = repmat(lowerBound,mutationPop,1) ... + round(repmat(scale,mutationPop,1) .* ... rand(mutationPop,GenomeLength)); % End of mutation function

Table 1 .

 1 Technological parameters.

	Parameter	Value	Parameter	Value
	ε o ε r σ (Ωm)	8.85e-12 1.0 1 / 2.65e-8	t ox (µm) C sub (F/m 2 ) G sub (S/m 2 )	600 4.0e-6 2.43e+5

Table 2 .

 2 Design Constraints.

	Parameter	Min	Step	Max
	w (µm)	5.0	0.25	50.0
	d in (µm)	20.0	0.25	250.0
	n	1.5	1.0	15.5

Table 3 .

 3 Optimization results.

		w(µm) d in (µm)	n	N side	d out (µm)	L tool (nH)	δ(%)	Q tool
	A 11.00	149.50	4.5	4	259.00	7.00	0.0	3.90
	B	5.50	48.50	7.5	4	150.50	6.83	2.42	2.35
	C 34.75	176.25	4.5	8	499.50	7.17	2.42	9.19

Table 4 .

 4 Comparison of results between evaluated and simulated.

		L tool (nH) L Asitic (nH) Error (%) Q tool (nH) Q Asitic (nH) Error (%)
	A	7.00	6.97	0.43	3.90	3.83	1.82
	B	6.83	6.73	1.49	2.35	2.30	2.17
	C	7.17	7.01	2.23	9.19	8.65	6.24