Maya Carrillo

Aurelio López-López

Concept Based Representations as Complement of Bag of Words in Information Retrieval

Keywords: Information Retrieval, Concept Based Representation, Vector Model, Random Indexing, Holographic Reduced Representation

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

Introduction

Information Retrieval (IR) is a discipline involved with the representation, storage, organization, and access to information items [START_REF] Baeza | Modern Information Retrieval[END_REF]. IR systems are designed to provide, in response to a user query, references to documents which could contain the information desired by the user. To compare documents and queries, these have to be represented in an appropriate way to be processed. Sometimes, features are extracted from documents without performing any advanced processing; this produces what is known as Bag of Words representation (BoW), where the document attributes are words or word stems.

Merely considering the words of a document has shown not to be enough for representing content. For instance, consider two documents using the same set of words, but one discussing the topics in a positive sense, while the other refers to the same topic but in a negative sense. Then, a document would be more appropriately represented if syntactic and semantic information was included. There is research that has sought to include such semantic aspects as Latent Semantic Analysis [START_REF] Deerwester | Indexing by latent semantic analysis[END_REF], which has included implicit context information in the indexing process. The information is obtained by grouping terms that have similar meaning using Singular Value Decomposition (SVD). However, this method is quite computationally expensive.

On the other hand, there have been other efforts to represent more precise concepts than only words. For instance, Mitra et al., Evans and Zhai [START_REF] Evans | Noun-phrase Analysis in Unrestricted Text for Information Retrieval[END_REF], [START_REF] Mitra | An Analysis of Statistical and Syntactic Phrases[END_REF], among others have investigated the use of phrases as part of text representation since the early days of information retrieval. Their overall performance improvement has been only marginal, however. Recently Vilares, et al. in [START_REF] Vilares | Managing Syntactic Variation in Text Retrieval[END_REF] have extracted binary dependencies (i.e. noun-modifier, subject-verb and verbcomplement), their experiments have shown some improvement.

This paper, as an alternative to representing concepts, considers the use of Random Indexing (RI) to produce context vectors, which capture the implicit "semantics" of documents and queries without expensive reduction techniques as SVD. Thereafter, the context vectors are used to represent documents as Bag of Concepts (BoC) [START_REF] Sahlgren | Using Bag-of-Concepts to Improve the Performance of Support Vector Machines in Text Categorization[END_REF]. Besides this, we present the use of Holographic Reduced Representation (HRR) [START_REF] Plate | Holographic Reduced Representation: Distributed representation for cognitive structures[END_REF] to include syntactic relations between words. These techniques, to the best of our knowledge, have not been used in IR.

Nowadays, the traditional IR engines are able to retrieve the majority of relevant documents for most collections, but generally the ranking of the retrieved results leads to poor performance, in terms of precision. Therefore, we propose to use BoC and HRR to re-rank the results generated by the traditional vector space model (VSM) [START_REF] Salton | A vector space model for automatic indexing[END_REF]. Our assumption was that the BoW could be enriched with information from a concept-based representation to improve its precision. Our results achieved with the English CLEF2005 collection for Adhoc track, have confirmed our hypothesis showing an improvement of over 16% in mean average precision (MAP).

The remainder of this paper is organized as follows: Section 2 provides a brief description of related work, particularly on including phrases in information retrieval. Section 3 presents Random Indexing, how it is used to create BoC representations, and related work. Section 4 introduces the concept of Holographic Reduced Representations (HRRs) and presents how to use them to represent documents. Section 5 explains the experimental setup and the results obtained. Finally, section 6 concludes the paper and gives some directions for further work.

Previous Work

There are several previous works, suggesting the use of phrases to index and retrieve documents. For instance, Evans & Zhai [START_REF] Evans | Noun-phrase Analysis in Unrestricted Text for Information Retrieval[END_REF] present an approach to index noun phrases for IR. They describe a hybrid method to extract meaningful sub-compounds from complex noun phrases. Mitra et al. [START_REF] Mitra | An Analysis of Statistical and Syntactic Phrases[END_REF] present a study that compares the usefulness of phrase recognition by using linguistic and sta-tistical methods. Croft et al. describe an approach where phrases identified in natural language queries are used to build structured queries for a probabilistic retrieval model [START_REF] Croft | The use of phrases and structured queries in information retrieval[END_REF]. Despite their many implementations, retrieval experiments with phrases have shown inconsistent results. Recently, a number of retrieval approaches have investigated the effectiveness of language modeling approach in modeling statistical phrases such as n-grams or proximity-based phrases, showing promising results [START_REF] Metzler | A markov random field model for term dependencies[END_REF], [START_REF] Gao | Dependence language model for information retrieval[END_REF].

Our study differs from previous phrase-based approaches, in one aspect. We express phrases using a representation that reflects syntactic structure. This structure is then distributed across the document representation, rather than taking the phrases as new terms extending the space dimension.

Random Indexing

Random Indexing (RI) is a vector space methodology that accumulates context vectors for words based on co-occurrence data. The technique can be described via the following two steps:

1. A unique random representation known as index vector is assigned to each context (i.e. document). Index vectors are binary vectors with a small number of non-zero elements, which are either +1 or -1, with equal amounts of both. For example, if the index vectors have twenty non-zero elements in a 512-dimensional vector space, they will have ten +1s, ten -1s and 492 0s. Index vectors serve as indices or labels for contexts. 2. Index vectors are used to produce context vectors by scanning through the text and every time a given word occurs in a context; the index vector of the context is added to the context vector of the word [START_REF] Sahlgren | An introduction to random indexing[END_REF].

The above steps can be exemplified as follows: Let's suppose we have an eightdimensional space, two non-zero elements and two documents D1: Regular Right Part Grammars and their Parsers, whose index vector is [0,1,0,0,-1,0,0,0] and D2: Boolean Matrix Methods for the Detection of Simple Precedence Grammars with [0,1,0,0,0,-1,0,0] index vector. Then, the context vector for Grammars is the addition of both index vectors, since such word appears in them, producing the vector [0,2,0,0,-1,-1,0,0]. Word context vectors generated through this process are used to build document vectors as Bag of Concepts (BoC). Thus, a document vector is the sum of the context vectors of its words. Random Indexing, in the same manner as Latent Semantic Analysis (LSA), attempts to capture implicit "semantic" relations, but RI has additional advantages as: a) it does not have to use reduction techniques like Singular Value Decomposition (SVD) to reduce the space dimensionality; b) It is an incremental method, which means that we do not have to process all the data before we can start using the context vectors [START_REF] Sahlgren | An introduction to random indexing[END_REF].

There are several works that have validated the use of RI in text processing tasks: for example, Kanerva et al. in [START_REF] Kanerva | Random indexing of text samples for latent semantic analysis[END_REF] used Random Indexing to solve the part of the TOEFL, in which given a word, the subject is asked to choose its synonym from a list of four alternatives. Sahlgren & Karlgren [START_REF] Sahlgren | Automatic bilingual lexicon acquisition using Random Indexing of parallel corpora[END_REF] demonstrated that Random Indexing can be applied to parallel texts for automatic bilingual lexicon acquisition. Sahlgren & Cöster [START_REF] Sahlgren | Using Bag-of-Concepts to Improve the Performance of Support Vector Machines in Text Categorization[END_REF] used Random Indexing to carry out text categorization.

A Representation from Cognitive Science

Distributed representation allows to integrate connectionism and cognitivism, where mental representations (symbols) are specified by distributed patterns of neural activities, while is possible to introduce formal algebraic operations on these distributed patterns, to mathematically model cognitive operations [START_REF] Kvasnicka | Holographic Representation in Artificial Intelligence and Cognitive Science In[END_REF]. This approach, whose principles in cognitive science were formulated at the end of the 1960's [START_REF] Gabor | Holographic model for temporal recall[END_REF], [START_REF] Metcalfe Eich | Levels of processing, encoding specificity, elaboration, and charm[END_REF], [START_REF] Murdock | A theory for the storage and retrieval of item and associative information[END_REF], [START_REF] Slack | The role of distributed memory in natural language processing[END_REF], [START_REF] Willshaw | Non-holographic associative memory[END_REF], was culminated by the Holographic Reduced Representation (HRR) formulated by T. Plate [START_REF] Plate | Holographic Reduced Representation: Distributed representation for cognitive structures[END_REF]. The HRR, is a method for representing compositional structure in analogical reasoning. HRRs are vectors whose entries follow a normal distribution N (0, 1/n). They allow us to express structure using a circular convolution operator to bind terms. Circular convolution operator (⊗) binds two vectors x = (x 0 , x 1 , . . . , x n-1 ) and y = (y 0 , y 1 , . . . , y n-1 ) to give z = (z 0 , z 1 , . . . , z n-1 ) where z = x ⊗ y is defined as:

z i = n-1 k=0 x k y i-k i = 0 to n -1(subscripts are modulo-n) (1)
Illustrating the use of HRRs to represent simple predicates, we suppose an instantiated frame, which is the superposition of the frame name and the rolefiller bindings (roles convolved with their respective fillers). For example, in a very simplified frame for eating, the vector for the frame name is eating and the vectors for the roles are eat agent and eat object . This frame can be instantiated with the fillers Peter and the fish to produce "Peter eats the fish" as follows:

s 1 = eat + eat agent ⊗ peter + eat object ⊗ the f ish (2)
Accordingly, we adopt HRRs to build a text representation scheme in which two-word terms could be represented. Therefore, to define an HRR document representation, the following steps are done: a) Determine the index vectors for the vocabulary by adopting the random indexing method, as described earlier; b) Syntactically tag the documents using a natural language processing tool; c) Bind the tf.idf-weighted index vector of each word to its role. This "side" role is an HRR which serves to distinguish the right side from the left side of the two-word term. d) Add the resulting HRRs (with the two-word nouns encoded) to obtain a single HRR vector; e) Multiply the resulting HRR by an attenuating factor α; f) Normalize the HRR produced to obtain the vector which represents the document. In [START_REF] Carrillo | Combining Text Vector Representations for Information Retrieval[END_REF] and [START_REF] Carrillo | Representing Context Information for Document Retrieval[END_REF] there are some examples of this representation.

Fishbein, and Eliasmith have used the HRRs together with Random Indexing for text classification, having BoC as their baseline [START_REF] Fishbein | Integrating structure and meaning: A new method for encoding structure for text classification[END_REF]. We have reported other result using this representation in [START_REF] Carrillo | Combining Text Vector Representations for Information Retrieval[END_REF] with smaller collections and adding the HRRs to a special representation named Index Vector Representation. In [START_REF] Carrillo | Representing Context Information for Document Retrieval[END_REF] we reported results using GEOCLEF collection from 2005 to 2008 and using HRRs to code prepositional location phrases. It is important to mention that up to now, we are not aware of other research that uses RI together with HRRs.

Experimentation

The proposed document representation was generated for the English document collection used in CLEF 2005 for the Adhoc track. This is composed of 56,472 news articles taken from the Glasgow Herald (British) 1995 and 113,005 from LA Times (American) 1994 for a total of 169,477. The queries used were 50 from number 251 to number 300. They contain title, a brief description, and a narrative. The experiments, described below, were done taking only the title and description fields.

The experiments were divided into two stages. The aim of the first was to obtain as many relevant documents as possible; this was carried out by Lemur 1 , an open source system designed to facilitate research in information retrieval. The VSM using tf.idf weighting scheme and a cosine measure to determine vector similarity were configured in Lemur and the results generated were used as a baseline.

In the second stage, the list of documents generated by Lemur, with elements of three attributes query-document-similarity was re-ranked. In the re-ranking process the Lemur similarity list was combined (adding the similarity values) with two additional similarity lists. These lists were multiplied by 1/4 before the merging process to give more importance to the similarities obtained by Lemur. Of these additional lists, the former one was generated when documents and queries were represented as BoC and compared; the latter list was produced when the same documents and queries were represented as HRRs and compared. These lists were built taking only the first 1000 documents for each query to diminish the processing time. However, it should be mentioned that, on average, the time to build the BoC representation for a query and its associated documents was 2.9 min., and 4.6 min. to build the HRRs. In contrast, the time for comparing the query with the one thousand documents was only 0.124 seconds in both representations.

The HRR document representations were built as specified in section 4 where α was equal to 1/6, taking only two-word terms. MontyLingua [START_REF] Liu | MontyLingua: An end-to-end natural language processor with common sense[END_REF] was used for parsing the documents and queries and extracting the two-word terms. Examples of these composed terms are: civil war, serial killer, Russian force, military action. Both BoCs and HRRs representations were weighted and compared using the same schemes used for the VSM. We carried out several previous experiments intended to assess the effects of dimensionality, limited vocabulary, vector density and context definition. In our experiments the vector dimensionality was 4096 and the density 20 non-zero elements. We removed stop words and used stemming in the same way as the traditional VSM. These parameters, which were determined after our preliminary experiments, produced suitable data for our proposal. However, defining their right value is an open research topic.

Evaluation

The results after re-ranking the documents were evaluated with two metrics: Mean Average Precision (MAP), which is defined as the average of all the AvgP obtained for each query. AvgP is defined as:

AvgP = m k=1 P (r) x rel(r)/n (3)
Where P(r) is the precision at r considered documents, rel(r) is a binary function which indicates if document r is relevant or not for a given query q; n is the number of relevant documents for q; m is the number of relevant documents retrieved for q.

The second metric is R-Precision (R-Prec), which is defined as the precision reached after R documents have been retrieved, where R is the number of relevant documents for the current query.

Results

Table 1 compares Lemur results, with those produced after adding to it, BoC and HRR similarity lists. This process thereby produces Lemur + BoC and Lemur + BoC + HRR lists. Notice how BoC improves MAP and R-Prec by always being above 15%. Although BoC gave a high improvement in MAP, HRR additionally improved it by 1.3%. In contrast, the R-Prec decreased 2% when the HRRs were added. Consequently the HRRs, as was expected, help to emphasize the representation of specific concepts as observed for the MAP increment, but they cause a loss of generality reflected in the R-Prec decrement. The results obtained by both Lemur + BoC and Lemur + BoC + HRR, performing a paired t-student test, were found to be statistically significant in a 99% confidence interval in terms of MAP.

Table 2 shows the same comparison, but now in terms of precision at the indicated number of documents. The proposed representations increased the precision in all cases, but it should be noted that the difference is higher at low recall levels. It is difficult to compare our results with those mentioned in related work, because the authors worked with different collections, metrics and environments. However, as mentioned in [START_REF] Buckley | Evaluating Evaluation Measure Stability[END_REF] "Sparck Jones has suggested that a difference in the scores between two runs that is greater than 5% is noticeable, and a difference that is greater than 10% is material".

Conclusions and Future Works

In this article, we have presented a proposal for representing documents and queries that according to the experiments, has shown itself to be feasible and able to capture "semantic relations" and encode two-word terms. BoC improved the initial ranker. HRRs produced a slight gain in precision. However, they have the potential to encode other relations between concepts (e.g. syntactical relations such as subject-verb, or additional information as identifying named entities).We think if more types of relations are considered it could lead to a higher improvement. Based on our results, it seems reasonable to conjecture that these new representations when combined with the VSM to re-rank the documents, increase precision. Our results showed an improvement above 16% in MAP. Additional study and experimentation will be necessary to quantify the usefulness of the proposed representations. Then, we will continue working with other collections that provide us with more specific contexts to be represented. This allows us to thoroughly explore the usefulness of the proposed representations to improve IR effectiveness.

Table 1 .

 1 MAP and R-Prec results for ADHOC CLEF 2005 English document collection

	Metric Lemur Lemur+BoC %Diff Lemur+BoC+HRR %Diff
	MAP 0.2903	0.3392	16.84	0.3430	18.15
	R-Prec 0.3103	0.3579	15.34	0.3514	13.24

Table 2 .

 2 Precision at 5, 10, 15, 20, 30 and 100 documents

	RI System	P@5 P@10 P@15 P@20 P@30 P@100
	Lemur	0.4600 0.4160 0.3960 0.3610 0.3120 0.1854
	Lemur + BoC	0.5280 0.4640 0.4293 0.3980 0.3540 0.1996
	% Difference	14.78 11.54	8.41 10.25 13.46 7.66
	Lemur + BoC + HRR 0.5360 0.4740 0.4387 0.3990 0.3527 0.1998
	% Difference	16.52 13.94 10.78 10.53 13.04 7.77

The first author was supported by Conacyt scholarships 208265, while the second author was partially supported by SNI, Mexico. We would also like to thank the CNRG at the University of Waterloo, Canada for the resources provided.

http://www.lemurproject.org/


Omar Ali
email: omar.ali@bristol.ac.uk

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

Information Fusion For Entity Matching in Unstructured Data

Keywords: Information fusion, entity matching, information extraction, social network, data cleaning, web mining

Every day the global media system produces an abundance of news stories, all containing many references to people. An important task is to automatically generate reliable lists of people by analysing news content. We describe a system that leverages large amounts of data for this purpose. Lack of structure in this data gives rise to a large number of ways to refer to any particular person. Entity matching attempts to connect references that refer to the same person, usually employing some measure of similarity between references. We use information from multiple sources in order to produce a set of similarity measures with differing strengths and weaknesses. We show how their combination can improve precision without decreasing recall.

Introduction

The global media system produces a vast amount of news articles which discuss named entities, such as people, places and organisations. Extracting these references to named entities can enable us to study interactions between them and the news stories that they appear in.

In this paper we describe a complete system for the extraction and matching of named entities from unstructured news data, where large numbers and multiple sources of information are used to improve the precision of the extracted output. Our aim is to investigate how the fusion of information can improve the performance of the system.

To this end, the system has been collecting on-line news articles from multiple sources over a period of nearly two years. These come from RSS feeds, which are visited many times per day. Articles are passed through a named entity extraction tool, Gate [START_REF] Cunningham | GATE: A framework and graphical development environment for robust NLP tools and applications[END_REF], which provides us with references to named entities in each article. These references do not have one-to-one correspondences with named entities as there are many ways to refer to the same entity.

Currently the system contains 9.3 million English articles, which contain references to 3.8 million people. Amongst these references are many sources of noise, such as rare misspellings of names and errors in the entity extraction process.

Any study based on the people that appear in the media will be affected by the problem of multiple references, so these must first be resolved. Given the scale of the input this must be automated and we should be very careful not to merge similar-looking, yet different references, such as 'Tim Johnson' and 'Jim Johnson'.

We describe our approach to entity matching, fusing three sources of information to improve precision, without reducing recall and we test a method for the removal of ambiguous references based on their degree in a co-reference network.

Methods and Problem Formulation

In this section we formalise the problem of entity matching and discuss the similarity measures that will be used in our experiments.

Problem. We consider a set of references to named entities, {r 1 , r 2 , ...r n } ∈ R. References may occur in many articles and pairs that appear in the same article are said to co-occur. The number of articles that a reference A appears in is its frequency, f (A) and the number of times that any pair of references co-occur is their co-occurrence frequency, f (A, B).

This definition allows us to construct a graph of cooccurrences, G(V, E), which consists of references from set R as vertices and co-occurrences between references as edges. In this graph we wish to find pairs of references that represent the same person.

String Similarity. Most references to the same person share something in common. These range from multiple words, for example 'Hillary Clinton' and 'Hillary Rodham Clinton', to small differences in spelling like 'Hilary' or 'Hillary'. We use three measures of string similarity from the SimMetrics library [START_REF] Chapman | SimMetrics Library[END_REF]: Jaro-Winkler, Q-Gram and Levenshtein.

Titles, such as 'Mr', 'President', or 'Governor' should not be matched, therefore we maintain a list of titles and remove them prior to comparison. This leads us to rate 'President Barack Obama' and 'Barack Obama' very highly, whilst avoiding matches such as 'President Obama' and 'President Bush'.

Note that string similarity alone cannot resolve cases where similar names belong to different entities, as is the case for 'George W. Bush' and 'George H. W. Bush'. In order to resolve this ambiguity we require additional information.

Neighbourhood Similarity. Matching references are likely to be either directly linked, or to share a very similar set of neighbours. For this reason we employ measures of neighbourhood similarity in order to locate potential matches.

Finding references with similar neighbours could require us to compare all pairs, which is infeasible on large inputs. Fortunately we do not need to measure similarity between references that are more than two steps away from each other in the input graph, as we prove that their similarity must be zero. Definition 1. A graph G(V, E) is composed of a set of vertices (references), V and a set of edges (co-occurring references), E. Each edge connects exactly two vertices. The distance, d(u, v) between vertices u and v is the length of the shortest path between them. The neighbours of a vertex, N (v) are the set of all vertices that are adjacent to v. If u and v are adjacent, d(u, v) = 1.

A neighbourhood similarity measure, S nbr (u, v) describes the amount of overlap of the neighbourhoods of u and v. In general, if

N (u) ∩ N (v) = ∅ then S nbr (u, v) = 0 and if N (u) ∩ N (v) = N (u) ∪ N (v) = ∅ then S nbr (u, v) = 1.
Proposition 1. Any pair of vertices that have some neighbours in common, N (u) ∩ N (v) = ∅ must be within two steps of one another, i.e.:

S nbr (u, v) > 0, ∀ u, v ∈ V , s.t. d(u, v) ≤ 2
Proof. Assume we have a pair of vertices, (u, v), where S nbr (u, v) > 0 and

d(u, v) > 2. If S nbr (u, v) > 0, then N (u) ∩ N (v) = ∅, ∃ w ∈ V s.t. w ∈ N (u), w ∈ N (v). Therefore d(w, u) = 1, d(w, v) = 1 and d(u, v) ≤ d(w, u) + d(w, v) = 2,
which contradicts our assumption.

We use the Jaccard and Adar neighbourhood similarity measures [START_REF] Bhattacharya | Collective entity resolution in relational data[END_REF], which are defined in ( 1) and ( 2). Adar is similar to Jaccard with the addition of a uniqueness score for each reference.

S jaccard (r i , r j ) = |N (r i ) ∩ N (r j )| |N (r i ) ∪ N (r j )| (1)
S adar (r i , r j ) = c∈(N (ri)∩N (rj)) u(c) c∈(N (ri)∪N (rj)) u(c)
where

u(c) = 1 log(|N (c)|) (2)
Co-reference Similarity. Named entities are extracted using a named entity recognition tool that is part of the Gate distribution [START_REF] Cunningham | GATE: A framework and graphical development environment for robust NLP tools and applications[END_REF]. Gate also finds coreferences [START_REF] Dimitrov | A light-weight approach to coreference resolution for named entities in text[END_REF], which are references to the same entity that occur within the same article. This information is used as another clue in our entity matching process. We treat this as a binary measure as shown in (3).

S coref (r i , r j ) = 1, if f (r i , r j ) > 0 0, otherwise (3)
Note that since this can only link references that appear in the same article it will not resolve systematic spelling differences from different sources, such as 'Gaddafi' and 'Kaddafi'. For these we can only rely on string similarity.

The degree a node in this network reveals information about its ambiguity and is used to filter out ambiguous references, as we show in the next section.

Combination of Measures. All measures are normalised to be in the range [0, 1] and we test weighted combinations of them as shown, for example, in [START_REF] Newcombe | Automatic linkage of vital records[END_REF].

S(r 1 , r 2 ) = αS 1 (r 1 , r 2 ) + βS 2 (r 1 , r 2 ) + γS 3 (r 1 , r 2 ) where α, β, γ ∈ [0, 1], s.t. α + β + γ = 1 (4)
3 Experimental Set-Up

In this section we describe how our experiments were set up, then present and discuss our findings. We also discuss the difficulties of measuring performance in an unstructured setting. This is a setting where references are not retrieved from a database where a certain degree of standardisation has been enforced, but are extracted from free text using statistical methods.

Measuring Performance

Matching entities that are automatically extracted from unstructured data is difficult due to the variability of references and errors in extraction and spelling.

Freely available data sets for this task are difficult to find. In order to be able to measure performance on this type of data we produced our own data set, consisting of 1417 pairs of marked references. This breaks down into two sets containing 901 correct and 516 incorrect pairs 1 .

In web extraction applications it is more important to guarantee the quality of extracted information than it is to extract it all. As there is plenty of data available, we focus on high precision rather than high recall, in a similar vein to [15]. In addition we focus on relative changes in performance resulting from information fusion, rather than on absolute performance.

Precision and Recall. The input is a set of entity references, R from our entity database. All pairs of references could potentially be linked, P = R × R.

Our algorithms produce a set of linked pairs, P L ⊆ P . The ground-truth data consists of two sets of pairs, correct and incorrect, or P T ⊆ P and P F ⊆ P , respectively. Precision and recall are calculated according to [START_REF] Bekkerman | Disambiguating web appearances of people in a social network[END_REF].

Precision = |P T ∩ P L | |P T ∩ P L | + |P F ∩ P L | , Recall = |P T ∩ P L | |P T -P L | (5)

Basic Set Up

For experimental purposes we focus on one week of references from the 20th to the 27th December 2009. During this time we observed 114,388 references and 2,008,225 co-occurring pairs, in N = 96,880 articles. The size of this graph is reduced by discarding edges that co-occur less than 5 times. This reduces the size of the vertex and edge sets to, |V | = 8, 264 and |E| = 57, 361. χ-Square Test of Independence. To ensure that the remaining edges are statistically significant we use Pearson's χ-square test of independence [START_REF] Duda | Pattern classification[END_REF]. In this setting we examine the contents of an article and make a pair of observations on the presence of references A and B. Our null hypothesis is that references A and B are statistically independent so their expected frequency of co-occurrence should equal f (A)f (B)

N

, where N is the number of articles and f (A) is the number of articles reference A is seen in.

Our test makes multiple comparisons between reference pairs and the test statistic is calculated for all pairs of references which co-occur. In reality we implicitly compare g = n(n+1)

2

n pairs, for n total references. Therefore we apply the Bonferroni correction and adjust the significance level to 1/g.

For this network we have g ≈ 3.42 × 10 7 and an adjusted significance of 2.93 × 10 -10 . Applying the χ-square test of independence at this significance level leaves us with |V | = 8, 230 and |E| = 53, 462.

Results

We now present results for string, neighbourhood and co-reference similarities, along with weighted combinations of the three.

Note that all measures are implicitly aided by neighbourhood information, as comparisons are made between references that are up to two steps apart in the co-occurrence network. This step ensures that we do not calculate similarities for all pairs of references. When we discuss neighbourhood similarity we are referring to further specific measures on the immediate neighbours of each reference.

We quote values of precision and recall which demonstrate the peak precision of each method. This excludes any results where precision becomes unstable when the number of output pairs becomes too small.

String Similarity. Table 1 shows results for string similarity measures, along with weighted combinations of them. All measures exhibit reasonably high precision but have subtly different types of reference-pairs that they can and cannot match. JaroWinkler is biased toward matching the beginning of a string, which leads to incorrect matches such as, 'Robert Casey' and 'Robert Costa'.

Q-gram is able to handle more variation in the input as it operates on sets of 3-grams, so order and positioning of characters is less important. This works in the case of 'Thomas James Leggs Jr.' and 'Thomas J. Leggs Jr.', but fails on pairs such as 'James Anderson' and 'Pamela Anderson'.

Levenshtein is a lot more selective, as each insertion, modification or deletion incurs a cost. Very similar strings like 'Tim Johnson' and 'Jim Johnson' are still a problem, however this is true for all of the measures we have described.

Neighbourhood Similarity. The addition of neighbourhood to string similarity did not lead to any improvement. We ran a number of weighted combinations of these measures and in all cases precision fell to around 50%. This loss of precision was due to the inclusion of many false positives, which were typically strongly-connected pairs such as 'Warren Taylor' and his ex-wife 'Karen Taylor'. Neighbourhood measures have no way of discriminating references that are similar due to being related in some way from those which are the same. Similar to findings in [START_REF] Bhattacharya | Collective entity resolution in relational data[END_REF], references which are similar but not matching are scored highly and incorrectly matched.

Co-Reference Similarity. Table 1 also shows precision and recall for coreference similarity, followed by the addition of string and then neighbourhood similarity measures. Co-reference similarity alone shows strong performance, however we can improve this by adding in string measures.

Table 1. Precision and recall for measures, plus weighted combinations of them. Combining string measures seems to improve precision slightly, although Levenshtein performs best alone. Neighbourhood measures reduce performance (we show Levenshtein combined with both Jaccard and Adar -all other combinations perform comparably). Co-reference shows high precision and the addition of string similarity improves this, without a reduction in recall. The final line shows the effect of removing high-degree (ambiguous) references. Combining co-reference and string similarity gives some increase in performance. A co-reference error, which links 'Vicki Kennedy' to 'Ted Kennedy' is scored highly in terms of co-reference but relatively poorly by the Levenshtein measure, resulting in its removal. There is also the addition of pairs that cannot be found by co-reference alone, such as 'Mahmud Abbas' and 'Mahmoud Abbas'.

Method

This combination results in increased precision without decreasing recall over the baseline string and co-reference measures. The co-reference network map also allow us to identify and remove references that are ambiguous (high-degree nodes).

Related Work

Existing methods [START_REF] Han | Named entity disambiguation by leveraging Wikipedia semantic knowledge[END_REF][START_REF] Cucerzan | Large-scale named entity disambiguation based on Wikipedia data[END_REF] use on-line data, such as Wikipedia, to place references to entities into some context. An entity can then be disambiguated according to words or other entities that it appears alongside. Similarly, Bekkerman and McCallum [START_REF] Bekkerman | Disambiguating web appearances of people in a social network[END_REF] obtain context from a list of contacts in a user's mailbox. They suggest that web pages related to a person will exist in a community of web pages related to that person's contacts.

Most methods [START_REF] Köpcke | Frameworks for entity matching: A comparison[END_REF] operate on structured data so do not have to handle noise associated with automatically extracting named entities from unstructured text.

Whilst state-of-the-art entity matching tools produce high accuracies, they do not scale well to large data sets. Rastogi [START_REF] Rastogi | Large-scale collective entity matching[END_REF] addresses this by defining a general framework for large scale entity matching. Dalvi [START_REF] Dalvi | A web of concepts[END_REF] also discusses the more general problem of connecting related concepts.

Our system processes a high volume of unstructured data from the global media system, automatically extracting and storing named entities on a large scale. This introduces a lot of noise into our entity matching task and must be resolved with high precision in order that we may launch further studies with high confidence in our data.

Conclusions and Future Work

In this paper we have explored the use of information fusion for the task of information extraction from unstructured text. We have considered the problem of entity matching and have shown that combining multiple sources of information results in improved performance. Note that we have concentrated on relative changes in performance resulting from information fusion, rather than on absolute performance.

We looked at three similarity measures, all of which have different strengths and weaknesses. String similarity is a very effective method of comparison but is also very vulnerable to connecting similar-looking names. Co-reference information also gives high precision results and we have demonstrated that combining this with string similarity leads to increased precision, without reducing recall.

Neighbourhood similarity proved to be poor at this task as it assigns high scores to related references when we are looking for pairs which are the same. Whilst it does not prove useful as a similarity measure, the use of neighbourhood information is essential in order to reduce computation and produce a system which can scale.

In future work we will look to improve the recall of the system. The cooccurrence network is improved by considering greater volumes of news, for the simple reason that infrequent references can be disregarded, which greatly reduces noise in the input. We will also investigate further the performance improvements due to removing ambiguous (high-degree) nodes from the coreference network. Examples include common forenames, the removal of which produces a much cleaner network. These noise-reduction steps will allow us to select lower thresholds to increase recall, without reducing precision.

On a more general level, our task is to find nodes in a network which are strongly related to one another. In this case the relation is one of identity, i.e., do these references refer to the same person? Other strong relations like family or work are regularly found and we wish to ignore these. This also raises the issue of domain knowledge. One desirable property of an entity matching system is that it could be applied to other domains, as we also collect references to locations and organisations. It is very clear from our results that domain knowledge is very important and that a general system for matching entities of different types is a long way off. Increasing the amount of domain knowledge that we include should prove very effective at reducing the number of false positives that are produced.

Data available at: http://patterns.enm.bris.ac.uk/entity-matching-data.

Acknowledgements. We would like to give thanks to H. Cunningham, D. Maynard, K. Bontcheva and V. Tablan for creating and releasing Gate [1]. O. Ali is supported by a DTA grant, N. Cristianini is supported by a Royal Society Wolfson Merit Award and both are supported by the 'Pascal2' Network of Excellence.


Victor Silva

Jorge Fernandes
email: jorge.fernandes@inesc-id.pt

Horácio Neto

Reconfigurable Circuits using Magnetic Tunneling Junction Memories

Keywords: MRAM, Reconfigurable Hardware, Coarse-grained array, Programmable ALU, Multi-context

This paper presents the first results of our work to research and develop new reconfigurable circuits and topologies based on Magnetic RAM (MRAM) memory elements. This work proposes a coarse-grained reconfigurable array using MRAM. A coarse-grained array, where each reconfigurable element computes on 4-bit or larger input words, is more suitable to execute data-oriented algorithms and is more able to exploit large amounts of operation-level parallelism than common fine-grained architectures. The architecture is organized as a one-dimensional array of programmable ALU and the configuration bits are stored in MRAM. MRAM provide non-volatility with cell areas and with access speeds comparable to those of SRAM and with lower process complexity than FLASH memory. MRAM can also be efficiently organized as multi-context memories.

Introduction

The field of reconfigurable computing has been, so far, dominated by fine-grained Field Programmable Gate Arrays (FPGA). Nevertheless, FPGA have substantial drawbacks. Since most FPGA are SRAM based, their volatility makes FPGA unappealing for applications that require reduced parts count and small footprint or rapid availability of logic or high security [START_REF]Third Generation Non-Volatile FPGAs Enable System on Chip Functionality[END_REF]. FPGA also have a large routing overhead due to their bit-level nature, demand large configuration memories for both processing units and routing switches and require large configuration times that make runtime reconfiguration practically unfeasible.

Reconfigurable arrays (RA) try to overcome the disadvantages of Field Programmable Gate Array (FPGA) based computing solutions by providing multiple bit-wide data-paths and complex operators instead of bit-level configurability. The wider data-paths allow for the efficient implementation of complex operators in silicon. Thus, RA offer lower overhead, exploit better operation level parallelism and are better suited for data-oriented algorithms [START_REF] Nageldinger | Coarse-grained Reconfigurable Architectures Design Space Exploration[END_REF].

This work proposes a MTJ-based coarse-grained reconfigurable array. The reconfigurable architecture proposed is organized as a 1-dimensional coarse-grained array. The basic processing elements (PE) are arithmetic and logic function units 4 or more bits wide. The operation to be executed by each PE is controlled by the MRAM bits. The array is run-time reconfigurable. The MTJ structures can be rewritten while the circuit is in execution, and therefore a new reconfiguration can be loaded while the current application is running.

A number of architectural and circuit solutions are being studied, implemented and evaluated. The fundamental components of the RA have already been designed and electrically simulated. The results of the electrical simulations were on line with expectations.

A scaled down version of a coarse-grained reconfigurable array using TAS-MRAM was designed and a first prototype has been sent for fabrication and is expected to be delivered in a few weeks. This prototype will be further processed at INESC-MN facilities to lay out the layers that will form the MTJs.

Contribution to Technological Innovation

This work aims to answer a number of open research questions, such as:

• Is it possible to cost effectively deal with FPGA inherent volatility?

• Is there an alternative reconfigurable architectural model to the nasty FPGA bit-level architectural model?

• Is it possible to have it all, a non volatile reconfigurable device that it is more oriented for data intensive algorithms?

Magnetic RAM (MRAM) technology offers a solution to the intrinsic volatility of SRAM, with low reading and writing times, virtual limitless re-programmability and almost no area overhead compared with other technologies such as FLASH [START_REF] Bruchon | Magnetic remanent memory structures for dynamically reconfigurable FPGA[END_REF], [START_REF] Bruchon | Magnetic tunnelling junction based FPGA[END_REF].

At the architectural level, reconfigurable arrays (RA) try to overcome the disadvantages of FPGA based computing solutions by providing multiple bit-wide data-paths and complex operators instead of bit-level configurability. RA wider datapaths allow for the efficient implementation of complex operators in silicon. Thus, RA offer lower overhead, exploit better operation level parallelism and are better suited for data-oriented algorithms.

The objective of this research and development is, therefore, to design and develop a reconfigurable array architecture based on MRAM. This kind of device enjoys the advantage of non volatility due to be based on MRAM and at the same time offers the computational advantages that RA have over FPGA.

The use of magnetic tunneling junction (MTJ) memory cells in run-time reconfigurable hardware devices is a very promising technological solution and an emergent area of research. At the architectural level and in order to meet the increased computational requirements of data-intensive applications, reconfigurable devices are starting to evolve to coarse-grained compositions of functional units or program controlled processors, that are more able to improve performance and energy efficiency. The combination of these two aspects, as proposed in this research, can therefore provide a main contribution to technological innovation in the area of reconfigurable computing.

State of the Art

Since the 1990s, a number of architectures have been proposed and designed [START_REF] Nageldinger | Coarse-grained Reconfigurable Architectures Design Space Exploration[END_REF], [START_REF] Hartenstein | A Decade of Reconfigurable Computing: a Visionary Retrospective[END_REF], [START_REF] Zain-Ul-Abdin | Evolution in architectures and programming methodologies of coarse-grained reconfigurable computing[END_REF], [START_REF] Ebeling | The General Rapid Architecture Description[END_REF], [START_REF] Goldstein | PipeRench: A Coprocessor for Streaming Multimedia Acceleration[END_REF]. These architectures can be classified according to their basic interconnect structure, granularity and reconfiguration model. Practically all of the proposed architectures are SRAM-based and none of these is MRAM-based.

The predominant architectural arrangement has been a 2-D array or mesh, although some of the works, see for example [START_REF] Ebeling | The General Rapid Architecture Description[END_REF], [START_REF] Goldstein | PipeRench: A Coprocessor for Streaming Multimedia Acceleration[END_REF] have demonstrated that 1-dimensional coarse-grained linear array architectures can provide high-performance for specific application domains.

MRAM have so far been exclusively employed as elements on fine-grained FPGA look alike solutions, such as Look Up Tables (LUT) [START_REF] Bruchon | Magnetic remanent memory structures for dynamically reconfigurable FPGA[END_REF], [START_REF] Bruchon | Magnetic tunnelling junction based FPGA[END_REF], [START_REF] Bruchon | New non-volatile FPGA concept using Magnetic Tunneling Junction[END_REF], [START_REF] Zhao | TAS-MRAM based Nonvolatile FPGA logic circuit[END_REF], [START_REF] Guillemenet | A non-volatile runtime FPGA using thermally assisted switching MRAMS[END_REF], [START_REF] Zhao | Integration of Spin-RAM technology in FPGA circuits[END_REF] and no works have been published on MRAM-based coarse-grained reconfigurable arrays.

The most common MRAM cells consist of Magnetic Tunneling Junctions (MTJ) vertically integrated with silicon CMOS transistors as depicted on Fig. 1. A MTJ cell is conceptually made of two thin ferromagnetic layers separated by an ultra thin nonmagnetic oxide layer [START_REF] Bruchon | Magnetic remanent memory structures for dynamically reconfigurable FPGA[END_REF], [START_REF] Bruchon | Magnetic tunnelling junction based FPGA[END_REF], [START_REF] Bruchon | New non-volatile FPGA concept using Magnetic Tunneling Junction[END_REF]. Magnetic remanence of the ferromagnetic elements provides for non-volatility. The relative magnetic orientation of these layers defines two different values of equivalent resistance Rp (low resistance), when the free layer and the pinned layer are oriented to the same direction, and Rap (high resistance), when the free layer and the pinned layer are oriented in opposite direction. These different values of equivalent resistance can be employed as state variables to represent the logic states '0' and '1'.

This resistance can be evaluated by sending current through the junction and measuring the voltages at the nodes of the MTJ. A structure is required to determine whether the junction is on a low resistivity configuration or in a high resistivity configuration.

To write information in a MTJ, a magnetic field is applied through the junction in order to force the change on the magnetic orientation of the free layer. The strength and nature of the required magnetic field depends on the writing approach. Currently, there are 3 writing approaches known as Field Induced Magnetic Switching (FIMS) [START_REF] Bruchon | Magnetic remanent memory structures for dynamically reconfigurable FPGA[END_REF], [START_REF] Bruchon | Magnetic tunnelling junction based FPGA[END_REF], [START_REF] Bruchon | New non-volatile FPGA concept using Magnetic Tunneling Junction[END_REF], Thermally Assisted Switching (TAS) [START_REF] Zhao | TAS-MRAM based Nonvolatile FPGA logic circuit[END_REF], [START_REF] Guillemenet | A non-volatile runtime FPGA using thermally assisted switching MRAMS[END_REF] and Spin Transfer Torque (STT) [START_REF] Zhao | Integration of Spin-RAM technology in FPGA circuits[END_REF].

Most MRAM produced so far are FIMS-based, but their size has been limited to 16Mb [START_REF] Debrosse | A 16Mb MRAM featuring bootstrapped write drivers[END_REF] because this technique has major drawbacks such as its susceptibility to soft errors due to write selectivity, its lower scalability and its high current consumption. The TAS and STT approaches have been recently proposed to overcome the above mentioned issues. The TAS approach was preferred due to its weaker demands from the material point of view.

The TAS approach requires one bidirectional current to create the magnetic field. A local current (for each junction) is then used to enhance the effectiveness of the aforementioned magnetic field by momentarily heating the junction by Joule effect. This heating will unpin the free layer.

Research Contribution and Innovation

To the authors' knowledge, this is the first R&D work where a MRAM based coarse grained reconfigurable array is proposed and a proof of concept prototype is developed and manufactured. Also, the proposed design employs a TAS writing based MRAM instead of the more conventional FIMS writing based MRAM.

The reconfigurable architecture proposed in this work [START_REF] Silva | Run-Time Reconfigurable Array using Magnetic RAM[END_REF] is organized as a 1dimensional coarse-grained array. By providing a not too complex but very effective architecture organization 1-dimensional arrays are a good option to permit full characterization of the MRAM-based run-time reconfigurable technology. The basic processing elements (PE) are arithmetic and logic function units 4-bit wide (which can be easily scaled to larger bit-widths). The operation to be executed by each PE is controlled by the respective MRAM configuration memory bits. The array is run-time reconfigurable. The configuration memory on any PE can be rewritten while the circuit is in execution, and therefore a new reconfiguration can be loaded into any PE while the current application is running.

For computation, there are four global data buses, two input data buses and two output data buses, see Fig. 2. The A bus and the B bus feed the rALU with its operands. The S bus and the Carry out bus deliver the result of the logical-arithmetic operation executed and its eventual carry out. The exclusive access to the global data buses for each rALU is ensured by 16 selector signals, Sel(k), one for each rALU. For configuration, there is one input global bus, as shown in Fig. 3. The Conf bus carries the data that will be stored on the MTJ to be used later on for configuration, thus supporting shallow dynamic re-configurability.

Sixteen selector signals determine which rALU(k) configuration memory will be written. The configuration memory contains the information that defines the ALU functionality. This configuration memory is made of an array of identical TAS-MRAM cells as the one depicted on Fig. 3.

Datapath Unit

The data-path unit is implemented in a bit slice fashion. Since this module is implemented in full custom, a bit slice style makes it easier to change the available data-path width.

The 4 bit ALU is made by the concatenation of 4 identical data-path slices as the one depicted on Fig. 4. The less significant carry in bit can be set to '0' or '1' while the remaining carries in are connected to their direct predecessor lower order bit slice carry out. As shown in Fig. 4, the function computed by the ALU depends on the values of the five multiplexers selector values. These values depend on the data stored in the memory configuration bits and their values are easily generated from Fig. 4.

The adder is implemented as a classic Ripple Carry Adder. An adder-subtracter is implemented by adding a XOR gate to the adder input port A and by selectively setting the adder input port Carry In with a logic '1'. The XOR and MUX designs are implemented using transmission gates, because of simplicity of implementation. The implementation of the arithmetic-logic functions takes advantage of the adder defining equations ( 1)- [START_REF] Nageldinger | Coarse-grained Reconfigurable Architectures Design Space Exploration[END_REF].

S = A • B + A • Cin + B • Cin , (1)
Cout = A xor B xor Cin . ( 2
)
For example, the operation AND is implemented by selecting the adder-subtrater output S, given by equation ( 1) and setting the adder-subtracter Carry-in input signal to logic '0'. This is accomplished by setting the controls signals, Sel0-Sel5 to logic '0'.

TAS-MRAM Based Storage Cell

Two circuit designs have been evaluated for the TAS-MRAM based storage cell [START_REF] Zhao | TAS-MRAM based Nonvolatile FPGA logic circuit[END_REF], [START_REF] Guillemenet | A non-volatile runtime FPGA using thermally assisted switching MRAMS[END_REF]. These circuits, as shown in Fig. 5 consist of:

• An Unbalanced Flip Flop (UFF) used as a sense amplifier.

• Two MTJ cells (MTJ1 and MTJ2).

• Two unidirectional current sources CS1 and CS2. These two current sources are responsible for the Joule effect on each MTJ. • A write line that is employed to propagate the external magnetic field in either direction. This line is common to all storage cells. • Two PMOS isolation transistors (for architecture 2). During the read phase, the MN2 NMOS transistor acts as a short circuit, thus, the two cross-coupled inverters are pulled to a meta-stable operating state. The resistance value of each of the MTJ coupled to its respective inverter will move away the metastable operating point from one of the stable states and bring it closer to the other. So, when the Vsel/Read signal is released, the structure will move to the closest stable state. Afterwards, new information can be stored into the MTJ without altering the value stored in the UFF.

Due to the number of arithmetic-logic functions available on each ALU, a cluster of four memory bits is assigned to each individual ALU. Since the cluster size is small, the four control signals required are generated at the same writing cycle.

The inner working of the UFF coupled with MTJs provides the required support for run-time reconfiguration. So it is possible to write a new plane of configuration while the rALU is operating at full speed.

Bidirectional Current Generator

A bidirectional current generator capable of delivering a current higher than 20 mA has been designed to provide the current that is necessary to generate the bidirectional magnetic field responsible for switching the magnetic orientation of the MTJ's free layer and therefore write new information on the MTJ.

In order to better characterize the MTJ behavior, a digital controlled current source is used in association with a digital controlled current sink, see Fig. 6. The bidirectional current is shared among all TAS-MRAM storage cells, and therefore only one generator is required for the whole set of MTJ. The writing operation require 2 steps, in the first step the current flows in a direction that will allow writing a logical '1' on a given memory cell and in the second step, the current that flows in the write line will reverse its direction in order to allow writing a '0' in another memory cell.

Both Rbias1 and Rbias2 resistance are external and they are employed to change the intensity of the currents that passed across the current source and across the current sink respectively.

The switches S1 and S2 operate in complementary fashion. Their purpose is to turn on and turn off the current source as required by the logic responsible for the configuration. The switches S3 and S4 operates in complementary fashion and are responsible for turning off or on the current sink as required by the logic responsible for the configuration.

Unidirectional Current Generator

A unidirectional current generator able to deliver at least 1mA has been designed to provide the local current to momentarily heat each junction by Joule effect, as required by the TAS approach.

In order to facilitate the characterization of the MTJ behavior, a digital controlled current source has been designed, as depicted in Fig. 7. The unidirectional current generator is split into a front-end and a back-end. The Front-end is made of a resistance (Rbias3) and a PMOS transistor (MP0) while the back-end is made of switches (S1 and S2) and two identical PMOS transistor (MP1 and MP2). The frontend is shared among the whole set of unidirectional current generators while there is one back-end module associated with each memory cell pair of MTJ.

Rbias3 is an external resistance that is employed to bias the back-end's driver transistors (MP1 and MP2). The switches S1 and S2 operate in complementary fashion. Their purpose is to turn on and turn off the PMOS driver transistors (MP1 and MP2). The aforementioned switches are opened and closed depending on the value of an internal generated digital control signal.

Discussion of Results and Critical View

In order to fulfill our goal several architectural and circuits solutions are being studied, implemented and evaluated. The core blocks have already been designed for AMS 0.35µm 4-Metal CMOS process technology and have been electrical simulated with a set of stimuli pre and post-layout under PVT corners. The electrical responses of the core blocks were on line with expectations.

An initial proof of concept coarse-grained reconfigurable array using TAS-MRAM was designed and a first prototype has been sent for fabrication. This prototype will be further processed at INESC-MN facilities to lay out the layers that will form the MTJs. A final test and characterization of the design will validate the viability of TAS-MRAM based memory element in the context of coarse grained reconfigurable computing and provide a study of the inner core of the basic computing unit, the reconfigurable ALU (rALU). It will also be employed to figure out how the MRAM configuration memory and the reconfigurable ALU fit together.

The circuit implements 1 of the 16 rALU that are part of the initial architecture as depicted on Fig. 2. Each ALU is capable of supporting up to 16 different operations, thus a four MRAM bit configuration memory is associated to each ALU. It is the information stored on the configuration memory that selects which operation will be carried out.

Both storage-cell circuits were simulated pre and post-layout under the same conditions, including the same set of AMS recommended PVT corners. Both performed as expected, however, architecture 1 has been preferred over architecture 2 because it requires a lower TMR. The TMR (Tunneling Magneto Resistance) is defined by the ratio between the two MTJ equivalent resistances (TMR = ∆R/R) and is a critical factor for the viability of the MRAM. According to the post-layout simulation results, architecture 2 requires a TMR of at least 40% while architecture 1 requires a TMR of 30%. On both cases the value of Rp was set to 1kΩ.

The whole MRAM rALU was electrical simulated post-layout under an extensive set of stimuli. In order to mitigate the ground and power supply bounce without increasing the number of both power supply pads and ground pads, external semi rings with multiple metal pads to reduce the inductance due to the bonding wires for power and ground have been connected to their respective power and ground pads. The same procedure was performed to the auxiliary voltage reference source VDD/2.

Conclusions and Further Work

As mentioned in section 4 and as far as the authors are aware this is the first proposal of a TAS-MRAM based coarse grained reconfigurable array. This research aims to provide a new approach to overcome the problems due to volatility that make FPGA less appealing for many applications, while maintaining the advantages inherent to coarse grain level operators. Further, it offers an open door to a very cost effective partial and full run time reconfigurability.

A scaled down prototype was sent for manufacturing at Austria Microsystems in late June 2009 and samples have been received in October 2009. A PCB board will now be designed for further evaluation and analysis of this prototype.

There are still many open questions for further work, either at circuit level or at the architectural level. For multi-context reconfiguration, further research is necessary to evaluate which of the storage cell architecture developed is more adequate for multiple planes of configuration and if there is one optimum number of configuration planes. It is also important to find if those results are fully technology scalable.

From the architectural point of view, future research should consider issues such as a fixed interconnect structure versus a fully reconfigurable one, handshake mechanisms or level of homogeneity among functional units.

Fig. 1 .

 1 Fig. 1. Left: MTJ requires a few steps above standard CMOS. Right: Magnetic Tunnel Junction Structure.

Fig. 2 .

 2 Fig. 2. General Computational Architecture.

Fig. 3 .

 3 Fig. 3. Left: Configuration Architecture. Right: Configuration memory structure.

Fig. 4 .

 4 Fig. 4. Data path bit slice structure.

Fig. 5 .

 5 Fig. 5. TAS-MRAM based storage cell. Left Architecture 1. Right: Architecture 2.

Fig. 6 .

 6 Fig. 6. Left: Bidirectional current generator. Right: Bidirectional current generator electrical behavior.

Fig. 7 .

 7 Fig. 7. Unidirectional current generator.

Acknowledgments. We acknowledge the major contribution to this work from our partners of INESC-MN. This work is partially supported by the Portuguese Foundation for Science and Technology (FCT) through Project MRAM (PTDC/EEA-ELC/72933/2006).


Gonçalo Candido

José Barata

François Jammes
email: francois2.jammes@schneider-electric.com

Armando W Colombo
email: armando.colombo@schneider-electric.com

Applications of Dynamic Deployment of Services in Industrial Automation

Keywords: Service-oriented Architecture, Device Model, Services Dynamic Deployment, DPWS, WS-Management

Service-oriented Architecture (SOA) is becoming a de facto paradigm for business and enterprise integration. SOA is expanding into several domains of application envisioning a unified solution suitable across all different layers of an enterprise infrastructure. The application of SOA based on open web standards can significantly enhance the interoperability and openness of those devices. By embedding a dynamical deployment service even into small field de-vices, it would be either possible to allow machine builders to place built-in services and still allow the integrator to deploy on-the-run the services that best fit his current application. This approach allows the developer to keep his own preferred development language, but still deliver a SOA-compliant application. A dynamic deployment service is envisaged as a fundamental framework to support more complex applications, reducing deployment delays, while increasing overall system agility. As use-case scenario, a dynamic deployment service was implemented over DPWS and WS-Management specifications allowing designing and programming an automation application using IEC61131 languages, and deploying these components as web services into devices.

Introduction

Service-oriented Architecture (SOA) is a major focus of interest from device level to high level IT [START_REF] Bloomberg | Service orient or be doomed[END_REF] [2] [3] [START_REF] Bell | Service-oriented modeling: service analysis, design, and architecture[END_REF]. SOA promises to lead to near-perfect applications in which every function is implemented and exposed as a service possible to be discovered and used by other network element. SOA establishes an architectural model that aims to enhance the efficiency, agility, and productivity of an enterprise by positioning services as the primary means through which solution logic is represented in support of the realization of strategic goals associated with service-oriented computing. The continuous convergence between computing and networking areas, enabled by the advances in semiconductor and transmission technology, allows new approaches to communication between systems and devices, in particular, embedded devices. The expansion of SOA approaches into different domains of application promises to deliver a complete cross-level and cross-domain connectivity over the same technology paradigm.

At crescent rhythm, Internet technology is emerging as the basic carrier for interconnecting electronic devices in widely diverse domains of application [START_REF] Jammes | Service-oriented paradigms in industrial automation[END_REF] [6] [START_REF] Barata | Diagnosis using Service Oriented Architectures (SOA)[END_REF]. One of the most promising approaches concerns the application at device level where the usage of high level service-based communications infrastructure allows completely innovative advances. Some research opportunities were already mapped in [START_REF] Candido | SOA in reconfigurable supply chains: A research roadmap[END_REF].

The goal of this document is to summarize a SOA-based solution for the industrial automation domain evidencing the role of the services dynamic deployment feature as a fundamental tool to enhance systems agility at device level. The concept of agility in this context implies being more than flexible or lean. Flexibility refers to a company that can easily adapt itself to produce a mostly predetermined range of products, while lean essentially means producing without waste. On the other hand, agility corresponds to operating efficiently in a competitive environment dominated by change and uncertainty [START_REF] Goldman | Agile competitors and virtual organizations: strategies for enriching the customer[END_REF]. Agility is a fundamental requirement for modern production companies in order to face challenges provoked by the globalization, environmental and working conditions regulations, improved standards for quality and fast technological mutation [START_REF] Lin | Agility index in the supply chain[END_REF]. However, global company agility is always limited by its least agile building block -all levels of the CIM pyramid, from ERP to field device level, need to be agile and interact in a seamless and synchronized manner.

At organization level, managers already noticed that they need to cooperate with other organizations in order to remain competitive [START_REF] Vernadat | Interoperable enterprise systems: principles, concepts, and methods[END_REF]. Although several work has been done on the topics of virtual organizations agility of production and/or collaboration to deal with unexpected demands and volatile markets at level [START_REF] Camarinha-Matos | A modeling framework for collaborative networked organizations[END_REF] [13], this agility can only be achieved if all organization levels are also equally agile. The automation devices level plays a fundamental role, since a device is the last frontier where high level process workflows are transformed into a structured collection of physical actions to be performed in a particular sequence -device control and management aspects are here crucial to support above levels agility.

The next section clarifies the importance of this work as an innovative contribution to future exploitations in the domain SOA-ready devices in industrial automation; section 3 exposes a device model comprising the dynamic deployment feature; section 4 pictures the overall architecture comprising the previous device model features; section 5 summarizes a dynamic deployment prototype implementation for the industrial automation domain; and, at last, the final conclusions and future perspectives are presented.

Contribution to Technological Innovation

The approach exposed in this document represents a new trend input concerning SOA-ready devices. Specifically, in the industrial automation domain it is fundamental to understand the concrete requirements and progress expectations -how can SOA paradigm provide its own contribute here?

In the industrial automation domain, and more concretely in manufacturing systems, the major goal is to produce fast, cheap, and quality products in line with current and expected client demands while remaining agile enough to handle constant output fluctuations, in terms of form and quantity. The interoperability and easy access to a device plays a major role when trying to accomplish previous goal.

Since the majority of high level business IT is already based over SOA technologies, it is important to research the field device domain and make it effortlessly compliant with the above infrastructure, while providing the expected functionality and performance to domain experts. Although the device model present in this document is most focused over the industrial domain, it remains abstract enough to fit other domains of application, as well as the envisaged applications of this device model in an involving infrastructure. By deploying an SOA-based middleware that already provides, besides others, discovery, identification, services invocation and eventing functionalities over an open standard, any developments over it will only need to focus on application behaviour since compliance and openness are already implicitly embedded. So, by allowing to manage and to deploy services into a device in a generic way, the system agility is increased while remaining compliant with open standards which also increase device interoperability across different vendors.

In summary, this work is expected to increase overall system agility by providing a new device model enriched with a dynamic deployment of services feature laying over open web standards possible to be extended and mapped to new domains of application.

Device Model

Overview

In this context, a device is to be seen as the main logical entity that abstracts an application element, while its services represent the functionalities that a particular element allows others to exploit to accomplish its own goals. A service will encapsulate a function or behavior that can be discovered and employed by any other network element in order to execute a particular task. However, it's possible to define a logical device that can be defined whenever there is a need to abstract a particular system component not explicitly associated to a physical entity. The definition remains abstract enough to be mapped to a wider range of application domains. Also, the application can be composed of several devices that interact between them through the services hosted on those with no imposed control architecture envisaged a priori

Built-in vs. Deployed Services

The device model in Fig. 1 represents the device itself as a real-world physical entity. This physical device will already embed some built-in services that allow deploying applications but also other added-value services that allow the integrator to setup, monitor, and diagnose that particular device. These services are deployed by the device builder, being immediately available when taking a new device out from the box. They cannot be removed or modified by the end-user -if the end-user wants to add its own services, he can do it through dynamic deployment. This collection of services is considered generic to every particular range of devices. The dynamic deployment service is itself a built-in service, which allows the systems integrator to deploy its own resources i.e. logical devices and its services. The user application will be dynamically deployed in a form of logical devices. These logical devices will represent the logical entities that can be observed from the current application, exposing their hosted services as their capabilities that others can make use of. An application can even compose several of these logical devices into several layers of increasing abstraction, in an orchestration or choreography mannerapplication construction based on existing building blocks. Still, it would be possible to deploy services that will enhance the functionality already provided by the current built-in services -these services are also considered generic to that particular range of devices, although they are not considered mandatory to the majority of applications. This approach allows a higher level of device customization. Also, some application functionalities can be considered generic enough and be reused across several applications, being deployed whenever they are required. For example, it would be possible to deploy into a PLC device some services that can control some common system components. This approach will avoid the need to recode those components every time they are needed and still remain consistent with previous implementations or development guideline.

Infrastructure

The device model presented in previous section will then fit in a bigger infrastructure that will make use of its embedded capabilities. These features at device level will subsequently enhance overall system ability in terms of interoperability and agility by laying over open web standards and allowing a fast deployment of services whenever system requirements changes oblige to. Since implementation details are encapsulated by the service itself under its interface, it will be possible to retrieve and connect to a device without knowing its current IP address, but simply searching for the required functionality -transparent interoperability. The integrator has also the ability to manage the complete lifecycle of these resources, as described in [START_REF] Cândido | Generic Management Ser-vices for DPWS-enabled devices[END_REF].

Deployed services can either be developed by the integrator or retrieved under an online repository of services -offered by device manufacturer or any other partner (see Fig. 2). When built-in services are not enough to current system requirements, there is a need to deploy extra services that might allow a more complex control over the device, or implement a common function to a particular domain of application. This infrastructure opens the door to new business models, where a disparate range of developers sell their own services to fill common needs. Although users can develop and deploy their own devices and services resources, it would be also possible to build an application only by combining resources developed by partners and/or reused from previous projects. Besides, the clear separation between hardware and software layers will allow the same service to be deployed across dissimilar physical devices. Even if implementation changes due to variations on device firmware capabilities, the service interface remains the same for the same concrete function -a service can be substituted by an equivalent one without changing anything only by keeping the service interface.

Whenever there is a need to connect to a particular device for configuration, maintenance, monitoring or diagnosis purposes, it can be used a device with any web standards-compliant tools, such as a PDA or a tablet PC with wireless access. This allows the user motion along the platform to better check equipment status and behavior.

Fig. 2. Network topology example.

The device generic built-in services will provide basic discovery, management and connection operations even on a new device. In the same way, the actual application will be easily discoverable and directly interoperable in the network since it is deployed in the form of several logical devices deployed across different physical devices. From the end-user point of view, the application is totally independent from the actual hardware platform -logical view of the system.

Industrial Automation Scenario

In the industrial automation domain, systems integrators are used to their own processes and programming languages. IEC61131 programming languages are the most used within this domain, due to its simplicity and run-time performance. The challenge is then how to turn this reality compatible with a complete SOA environment, while increasing system capacity in terms of agility, interoperability and robustness.

Devices Profile for Web Services (DPWS) is a common web services middleware and profile for devices [START_REF]OASIS: Devices profile for web services version 1.1 specification[END_REF], being currently ongoing a standardization process by OASIS. WS-Management [START_REF]DMTF: Web services for management (ws-management) specification[END_REF] specification describes a general WS* based protocol for managing systems such as PCs, servers, devices, Web Services, applications, and other manageable entities. The implementation summarized in this chapter, firstly shown in SODA project industrial demonstrator [START_REF]SODA: Soda project industrial demonstrator[END_REF], will be further exploited in SOCRADES project industrial pilot application. It joints DPWS and WS-Management specifications in a single application that supports the dynamic deployment of services, besides other features already described in [START_REF] Cândido | Generic Management Ser-vices for DPWS-enabled devices[END_REF] The automation control application is developed by abstracting different system components and coding its behavior using IEC61131 programming languages. The original component IEC61131 code is translated to PLCOpen format, being embedded in a service template that will then be deployed into the device (see Fig. 3). It should be noted that this template is independent from particular implementation details, which will be comprised in a parameter value that can be run or interpreted by device firmware. Once the component is made available and active, it will be possible to retrieve it and its services invoked or events subscribed in the network as any other DPWS device -using DPWS, the discovery and identification features are already supported in a distributed manner.

As example, operating systems "Windows Vista" and "Windows 7" are already DPWS-compliant by default, being possible to use the available device explorer to discover and interact effortlessly with any DPWS device available in the network. It is then possible to retrieve its individual metadata values, comprising not only some catalog parameters but also available services contract and a link to the device web server where the user is able to define a collection of setup, monitoring and diagnostic parameters through any traditional web browser. This simple feature already represents a major input to enhance out-of-the-box device connectivity and setupone of the biggest customer demands.

Even though this implementation focused over industrial automation domain, it remains abstract enough to adapt to other domains of application since the implementation details are isolated from the process to deploy new services into devices.

Conclusions

SOA paradigm is envisaged to expand and become an essential aspect at device level, including in industrial automation domain. It is then important to create models and methodologies to extract the major inputs from this paradigm to face domain requirements.

The existence of a dynamic deployment service embedded on a device can al-low more complex applications plus the creation of new business opportunities. It increases device interoperability and overall system agility whenever there is a need to update, manage or connect to it due to behavior adjustments or occasional downtime. Implementation intricacies are hidden under services interfaces that remain compliant with the overall SOA infrastructure, allowing an end-to-end interoperability across the different levels of the global application. These devices and services can be retrieved and used in a distributed manner across a common IP network in a transparent way.

Still, there is an important need to create new tools and methodologies to provide an easier development under this new paradigm compliant with the major open web standards. Also, training and clarification activities are also of major importance when pushing a new paradigm into a domain known to be particularly restrict as the industrial automation domain. Security and semantic aspects, as possible adaptation to other domains of application can be envisaged as future research topics over this same subject.

Fig. 1 .

 1 Fig. 1. Device Model.

Fig. 3 .

 3 Fig. 3. Dynamic deployment process.

Acknowledgments. The work present here was developed within the scope of the European IST FP6 project "Service-Oriented Cross-layer infRAstructure for Distributed smart Embedded deviceS" (see http://www.socrades.eu).