published or not. The documents may come

Evidence for top-down matching in visual repetition

priming with abstract shapes

E Ev vi id de en nc ce e f fo or r a a t to op p--d do ow wn n m ma at tc ch hi in ng g m me ec ch ha an ni is sm m i in n

v vi is su ua al l p pr ri im mi in ng g w wi it th h a ab bs st tr ra ac ct t s sh ha ap pe es s

Birgitta Dresp

CNRS, Université de Strasbourg, FRANCE E E--m ma ai il l: : b bi ir rg gi it tt ta a. .d dr re es sp p@ @i ic cu ub be e. .u un ni is st tr ra a. .f fr r

Introduction

The present study investigates context effects of shape similarity and color on form recognition in abstract visual configurations.

Priming to probe attentional selection

Visually presented primes preceding a visually presented probe may influence attentional selection and perceptual judgements resulting from such a selection. The effect of a prime on the processing of a probe can be either facilitating or inhibiting [START_REF] Farah | Semantic and perceptual priming : how similar are the underlying mechanisms[END_REF][START_REF] Maxfield | Attention and semantic priming: a review of prime task effects[END_REF] depending on its beneficial or detrimental action on attentional processes activated by the task. It has been suggested (e.g. [START_REF] Ochsner | Varieties of priming[END_REF]) that priming effects depend on representations that are stored in modality-specific cortical memory systems. In the specific case of visual perception, this memory system may be based on parallel perceptual mechanisms, each devoted to the independent analysis of a single physical stimulus dimension [START_REF] Magnussen | The psychophysics of perceptual memory[END_REF], and coupled to a global storage system that may be identified in terms of the Tulving-Schacter [START_REF] Tulving | Priming and human memory systems[END_REF] perceptual representation system (PRS). How such a perceptual representation system is activated in priming strongly depends on the semantic and/or categorical properties of the stimuli under investigation. Moreover, priming effects are sensitive to constraints specific to the task, or instructions given to observers. Recent evidence from priming experiments with visual forms has established that observers can be induced to give attentional priority to a strictly local stimulus dimension and thereby be prevented from processing semantic information [START_REF] Murray | Attention to local form information can prevent access to semantic information[END_REF]. This finding suggests that task specific demands command the attentional selection process involved in priming.

The effect of task context and specific task demands

The possibility that priming effects may depend on task demands, or instructions communicated to observers has, until recently, received little attention.

However, [START_REF] Holbrook | The effects of study-task relevance on perceptual repetition priming[END_REF] found that repetition priming in a naming task was elicited by stimuli that were seemingly non-relevant to the task in cases where they had previously been pointed out as relevant in a search task. This observation shows that priming is highly sensitive to the task context, the specific study-task demands, and the overall contextual information communicated to observers. In agreement with [START_REF] Murray | Attention to local form information can prevent access to semantic information[END_REF], the authors concluded that attentional selection in priming effects appears to be more dynamic and flexible than had been previously considered. Similar conclusions had been drawn earlier from results of a repetition priming study with pictures [START_REF] Bruce | Perceptual priming is not a necessary consequence of semantic classification of pictures[END_REF]. Considering this, we wanted to clarify whether visual priming by abstract stimuli carrying no particular semantic « weight » would be elicited spontaneously in naive observers, or whether specific information indicating a possible relevance of the primes to the task under study needs to be provided.

Contextual dynamics of attentional selection

The shape or the colour of visual objects may determine attentional processing in any perceptual task. Evidence from visual search studies has produced a theoretical framework of so-called attentional binding to explain how object properties such as shape and colour are processed in a search task [START_REF] Treisman | Search, similarity, and integration of features between and within dimensions[END_REF]1998). According to the classic theory, visual search for an object defined by a conjunction of features, such as a particular colour and a particular shape, would require serial processing and attentional binding of shape and colour. Search for a single object attribute like shape, for example, would be preattentive and not require attentional binding of features.

Attentional binding describes what happens when a certain colour is bound to a certain shape. When the shape changes, the colour needs to be bound to the new shape at a certain cost, and when colour changes, the shape needs to be bound to the new colour at a certain cost. necessarily do so. This suggests the need for a rather flexible, dynamic theory of attentional selection (e.g. [START_REF] Holbrook | The effects of study-task relevance on perceptual repetition priming[END_REF].

The fact that priming can occur unexpectedly after some time in a context defined by a specific succession of trials or tasks, for example, indicates that dynamic mechanisms of perceptual learning are involved in attentional selection. [START_REF] Goolsby | Understanding priming of color-singleton search : roles of attention at encoding and « retrieval[END_REF] found that visual search for a single, odd-coloured item among homogeneously coloured distractors primed observers' responses in a subsequent search task. In fact, when a given colour combination happend to be a critical attribute for attentional selection in trials of a previous task, items defined by the same colour combination tended to be detected faster in trials of a subsequent experiment with different task requirements. This finding suggests that colour, and possibly any other attribute of a visual stimulus, can produce contextual dynamics in a more intricate and indirect way than previously considered.

Attentional selection by top-down matching

The role of contextual dynamics and basic mechanisms of visual learning, which may produce priming effects in a multitude of experimental paradigms, is emphasized in Grossberg's (e.g. 1999) theory of visual attention. According to this theory, attentional selection may elicit priming whenever an expectation (top-down) signal triggered by a previous visual event can be matched to an incoming (bottom-up) signal triggered by an ongoing visual event at a given moment in time. This topdown matching mechanism is sensitive to events from previous tasks or trials as well as specific task instructions which determine the general contextual relevance of a visual stimulus in a given situation, as indicated by some of the most recent experimental findings (e.g. [START_REF] Holbrook | The effects of study-task relevance on perceptual repetition priming[END_REF][START_REF] Goolsby | Understanding priming of color-singleton search : roles of attention at encoding and « retrieval[END_REF]. The principle of top-down matching is illustrated in Figure 1. In addition to contextual relevance, intrinsic object properties such as figure saliency, filling-in, and figure-ground organization (e.g. [START_REF] Grossberg | Cortical dynamics of three-dimensional figure-ground perception of two-dimensional figures[END_REF]1999) determine the strength of the expectation signal that an object will trigger in a given context.

Contextual relevance

The contextual relevance of a prime with regard to a probe depends on the instructions that are communicated to observers beforehand (see above). In the present experiments, two different task instructions were given to two different groups of subjects who all had to identify the shape of a probe preceded by a congruent prime, a non-congruent prime, or no prime at all. The potential importance of the primes with regard to the probes was explicitly pointed out to one group of subjects to make them aware of a possible contextual relevance. In the instructions given to the other group, no specific mention concerning the primes was communicated. The possible contextual relevance of the primes in regard to the probes was thus not made explicit to the subjects of that group. We predict that the explicit instructions should be particularly effcicient in triggering top-matching of primes and probes and may, therefore, engender stronger priming effects.

Temporal separation of primes and probes

The time interval separating the end of the presentation of a prime and the onset of a probe (prime-probe interval) has been identified as a critical variable in priming studies. Some studies have shown that there seems to be an optimal temporal window in which optimal priming effects occur. Our choice of a duration of about 770 ms as prime-probe interval is based on findings from two of such studies. One is concerned with attentional processes in a visual discrimination task [START_REF] Tanaka | Attention andshort-term memory in contrast detection[END_REF], the other with gender discrimination [START_REF] Versace | Negative priming in a gender decision task and a semantic categorization task[END_REF]. The results from both studies show that prime-probe intervals between 300 and 1000 ms produce optimal priming effects.

Experimental validation

To test these predictions relative to attentional selection by top-down matching of shape and colour signals triggered by primes and probes, we investigated facilitatory/inhibitory priming effects of shape and colour in the identification of abstract visual shapes.

Methods

Subjects 20 observers with normal or corrected-to-normal vision participated in the experiment. All observers were naive as to the purpose of the experiment. 10 of them received the explicit task instructions, 10 received the non-explicit instructions.

Stimuli

The stimuli were generated by a PC equipped with a graphic card (VGA Trident) and consisted of two complex abstract shapes (see Figure 1). One of the shapes was the target that subjects had to identify. The shapes were either empty (outlined) or filled-in, and their colour was either red or green. Red shapes had a luminance of 8.5 cd/m 2 , green shapes a luminance of 25,2 cd/m 2 . Pretesting established that red and green stimuli presented at these luminance levels appeared to have equivalent subjective intensity. The size of a given shape was 1.5 degrees of visual angle. Examples of the stimuli were shown to all observers before the experiment. An example of the shapes they had to discriminate (see Figure 1) was shown to them for as long as they wished.

Procedure

The task of an observer in any given trial was to decide which of the two possible shapes (see again Figure 1) was presented in the second stimulus interval (probe). A response was given by pressing one of two possible keys of the computer keyboard ("1" or "2"). The response time for a given trial and whether a reponse corresponded to a correct identification or an incorrect identification were recorded.

The experiment was run with two independent groups of observers. One group was made aware, by an explicit message in the instructions, that the shapes presented in the first stimulus interval (prime) could be relevant for identifying the probe. The instructions given to subjects in this condition, the so-called explicit instructions, were to "decide as quickly as possible without making mistakes which shape was presented in the second stimulus interval. Note that the stimulus presented just before could help you make that decision." The other group of subjects received the socalled non-explicit instructions with no message concerning the primes. The instruction given to subjects in this condition was to "decide as quickly as possible without making mistakes which shape was presented in the second stimulus interval."

In trials with prime-probe congruency, primes and probes had either the same colour but different shape (colour congruency), the same shape but different colour (shape congruency), or the same colour and shape (shape-and-colour congruency). In non-congruent trials, primes and probes differed in shape and colour. In some of the trials, henceforth referred to as neutral trials, no prime was presented, and a plain background preceded the probe instead. Congruent, non-congruent, and neutral trials were presented in a random order. In trials other than neutral trials, either of the two abstract shapes shown in Figure 1 was randomly presented as either the prime, or the probe. A trial block consisted of 96 trials for each of the five prime-probe congruency conditions. Filled and outlined shapes were presented in separate trial blocks. The order of presentation of the different trial blocks was counterbalanced for each observer and between observers. Each observer was given 480 trials in a block, and the rest period between blocks was approximately 15 minutes. Each observer completed four trial blocks on the same day, with two blocks of trials with filled shapes and two with outlined shapes.

Subjects were seated in a semi-dark room at a viewing distance of 3 metres from the computer screen. A prime was flashed on the computer screen for 67 milliseconds (ms), succeeded by a probe of exactly the same duration. Each prime/neutral event and each probe was announced by a brief sound of 100 ms, presented 170 ms before. The duration of the interval between the end of a prime or neutral event and the sound announcing a probe was 500 milliseconds. Subjects had to identify the shape of the probe as quickly as possible without making mistakes. The next sound, announcing the next prime or neutral event, appeared 1200 ms after a response had been given.

Results

Analysis of the number of correct responses and response times in the different experimental conditions revealed no systematic differences in number of correct reponses between conditions. The performance of subjects varied between 92% and 100% correct identifications in any of the experimental conditions. Noticeable systematic differences in response times between conditions were found, and ANOVA was performed on mean response times calculated per observer and per experimental condition. Response times for incorrect identifications were not taken into account for the computation of means.

ANOVA for a between-groups design that takes into account all five levels of the factor prime-probe congruency, was performed. This analysis consisted of a 2 x 2

x 5 ANOVA on response times with group (explicit instructions, implicit instructions) as between-subjects factor, and shape structure (filled, outlined) and prime-probe congruency (shape only, shape and colour, colour only, neutral, noncongruent) as within-subjects factors. A significant effect of the type of instructions communicated to observers (F(1,18) = 6.3, p < .05) was found. This effect is described by the observation that response times for the group who received nonexplicit instructions are fairly levelled, between 400 and 450 ms, with little variability across the five conditions of prime-probe congruency, whereas noticeable variations as a function of prime-probe congruency are found for the group who received explicit instructions (see Figure 2 a). The overall effect of the five levels of primeprobe congruency was statistically significant (F(4,72) = 3.43, p < .05). Figure 2 a shows, for example, that the group who received the explicit instructions identified probes with the same colour and the same shape as the prime considerably faster than probes that were not preceded by any prime (neutral trials), or probes that were preceded by a non-congruent prime. Conversely, probes with only the same colour as the prime were identified noticeably slower than probes that were not preceded by any prime, and somewhat slower than probes preceded by a non-congruent prime. The effect of shape structure, which describes the observation that response times for filled shapes were systematically shorter than response times for outlined shapes (see Figure 2 a), was statistically significant (F(1,18) = 37.2, p < .001). Significant interactions were found between the type of instructions communicated to observers and prime-probe congruency (F(4,72) = 11.87, p < .001), between the type of instructions and shape structure (F(1,18) = 4.293, p < .05), and between prime-probe congruency and shape structure (F(4,72) = 3.23, p < .01). The triple interaction between type of instructions, prime-probe congruency, and shape structure was, as expected, statistically significant (F(4,72) = 2.76, p < .05).

Discussion

The results of our study show that priming with abstract visual shapes requires subjects to be made aware, by an explicit message in the instructions, of the potential relevance of prime shapes for the identification of probe shapes. This observation lends further support to the idea that task specific demands "dictate" the attentional process that triggers the memory processes involved in priming (e.g. [START_REF] Murray | Attention to local form information can prevent access to semantic information[END_REF]. The effects of the explicit instructions on the processing of visual primes and probes reveal how task demands can determine the contextual relevance of a prime in a given situation. They also reveal that physical attributes of a visual prime, whether seemingly relevant or not to the task under study, carry potential contextual weight, which is consistent with the conclusions from [START_REF] Goolsby | Understanding priming of color-singleton search : roles of attention at encoding and « retrieval[END_REF] and Holbrook et al.'s (2003) studies. The impact a certain combination of stimulus attributes will have on a given performance or task depends on instructions given, and on the kind of visual signals that are triggered.

The ways in which primes and probes were processed by the observers of the group who received the explicit instructions reveal that attentional binding (e.g. Treisman, 1993[START_REF] Treisman | Feature binding, attention, and object perception[END_REF] of the attributes shape and colour occured during the task, despite the fact that subjects were required to identify shape only. Although it might be thought that shape was the only relevant stimulus attribute in the task presented here, we find significant interactions between shape and colour in the group of observers who received the explicit instructions. These interactions reveal that probes with the same shape and colour as the prime are processed considerably faster than probes with only the same shape and, more importantly, that colour and shape do not produce merely additive effects on response latencies. In addition, probes with the same colour as a prime but different shape produced noticeably longer response latencies than probes that were not preceded by any prime. They produced slightly longer latencies than probes that were preceded by a non-congruent prime. While these findings may reveal attentional binding of shape and colour (see introduction), the question as to how they can be interpreted in terms of a mechanism of attentional selection yet remains to be answered.

Grossberg's theory (e.g. [START_REF] Grossberg | The link between brain learning, attention, and consciousness[END_REF] On the one hand, we show that primes with both the same colour and the same shape as the probe produce considerably stronger facilitation than primes with only the same shape as the probe. This suggests that a single congruent attribute of a visual prime has less priming power compared with combinations of several congruent

attributes. An explanation in terms of a top-down matching mechanism would suggest that several congruent attributes of a prime generate a comparatively stronger expectation signal and therefore produce stronger response facilitation when a probe is presented, whereas a single congruent attribute of a prime would generate a comparatively weaker expectation signal and therefore produce less facilitation. This is consistent with the idea that visual mechansims devoted to the independent analysis of a single physical stimulus dimension feed into a global storage system, or perceptual representation system which, when activated by a stimulus that provides sufficient relevant structural information, produces a perceptual priming effect (e.g. [START_REF] Magnussen | The psychophysics of perceptual memory[END_REF][START_REF] Tulving | Priming and human memory systems[END_REF][START_REF] Srinivas | Perceptual specificity in non-verbal priming[END_REF].

On the other hand, we show that primes with the same colour as the probe but not the same shape are found to slow down shape identification compared to neutral trials where no primes are presented at all. This suppressive effect of "colourcongruent-only" primes is noticeably stronger than the suppressive effect of primes that are completely non-congruent with respect to the probe. In fact, in the case of "colour-congruency-only", the expectation signal triggered by the colour of the prime is matched when the probe is switched on, whereas the expectation signal triggered by the shape of the prime is not. "Colour-congruent-only" primes therefore generate a conflict between matching signals, one positive, the other negative. In the case of complete non-congruency of prime and probe, neither the expectation signal triggered by the colour of the prime, nor that triggered by the shape of the prime is matched when the probe is switched on. This readily explains why "colour-congruency-only" has a more detrimental effect on the speed of the discrimination process compared with complete non-congruency, which does not generate a conflict between matching signals, but only produces non-ambiguous, negative matching signals.

Finally, in the group with sufficiently explicit instructions, congruent primes with filled shapes had a tendency to produce slightly stronger effects (see Figure 2 a) than primes with outlined shapes. This effect can be explained by the relative figural saliency of the stimuli. Filled visual primes produce more salient figure-ground percepts, possibly because the colour of the filled primes covers a larger area of the visual field than the colour of outlined primes. As a consequence, filled primes are likely to activate a larger proportion of visual neurones. The facilitation they engender on the discrimination of subsequently presented probes could thus be due, at least partly, to spatio-temporal probability summation over neural « channels » activated by attentional selection (e.g. [START_REF] Tolhurst | Reaction times in the detection of gratings by human observers: a probabilistic mechanism[END_REF]. In luminance discrimination tasks, relatively brief stimuli with coloured surfaces have been found to attract visual attention more efficiently than brief stimuli with achromatic surfaces, for example (e.g. Dresp & Grossberg, 1999). As a consequence, it is plausible to assume that filled chromatic primes may benefit more efficiently from attentional selection and thereby trigger stronger top-down expectation signals compared with outlined chromatic primes. When such a stronger expectation signal is positively matched with a bottomup target signal, it would then generate a matching signal resulting in comparatively stronger response facilitation.

Conclusions

Whether the shape or colour of a prime produces a contextual effect on the identification of the shape of a probe in visual repetition priming depends on the instructions given to observers. These have to be explicit enough for observers to expect a possible relationship between prime and probe, but do not need to constrain observers to use a specific cue. Prime-probe relationships are likely to be processed by a top-down matching mechanism which generates facilitating or inhibiting matching signals when a probe is switched on, and thereby determines the speed of the discrimination process that triggers a response to the probe. This top-down matching mechanism is sensitive to variations in the context in which the stimuli are presented. Such a sensitivity is revealed by our findings, which can be explained by mechanisms of attentional selection such as those proposed in Grossberg's theory of attention and visual learning (e.g. [START_REF] Grossberg | The link between brain learning, attention, and consciousness[END_REF].

Figure Captions

Figure 1 The stimuli used in the experiment consisted of green and red abstract shapes.

Outlined shapes and filled shapes were presented in separate trial blocks. Within a given block, any shape could be either the prime, or the probe that was presented shortly after the prime. Subjects had to decide which shape was presented in the probe interval by pressing key "1" or "2" on the computerkeyboard.

Figure 2 a

Mean response times as a function of prime-probe congruency obtained with the two groups of observers. One group did not receive any information regarding a possible relevance of the prime for the identifcation of the probe (non-explicit instructions) the other group was told explicitly that the primes could be relevant to the identification of the probes.

Figure 2 b

Mean response times as a function of prime-probe congruency obtained with the group of observers who received the explicit instructions.

Figure 2 c

Mean response times as a function of prime-probe congruency obtained with the group of observers who received the explicit instructions.

  takes into account contextual dynamics of attention and suggests an explanation of how a selection process sensitive to the context of stimuli operates in visual priming and related phenomena. His concept of top-down matching describes a mechanism where top-down expectations activated by a specific context, or prime, are compared or matched to current bottom-up input. Top-down matching was conceived originally as a basic learning mechanism within a neural network model, and is now successfully applied to explain phenomena such as category matching in recognition processes, or the control of attentional processes by volition. This theoretical framework of visual attention and learning proposes that positive matches between top-down expectation signals and bottom-up stimulus signals produce facilitation, whereas negative matches between expectation signals and bottom-up events produce suppression. In the brain, facilitation would generate the progressive reinforcement of specific neural connections via repeated top-down matching; suppression would generate inhibition of connections. The logical behavioural consequence of neural facilitation or suppression would be a faster or a slower reaction to a target stimulus, or probe. Topdown matching provides a plausible model to explain how expectation signals triggered by a congruent or a non-congruent prime generate facilitating or inhibiting matching signals that speed up or slow down a response to a probe. The effects we report in this study can be explained in terms of such a top-down matching mechanism.

SHAPE "1" SHAPE "2"

Figure 1


Yumin Suh

Minsu Cho

Kyoung Mu Lee

Graph Matching via Sequential Monte Carlo

Keywords: graph matching, sequential Monte Carlo, feature correspondence, image matching, object recognition

Graph matching is a powerful tool for computer vision and machine learning. In this paper, a novel approach to graph matching is developed based on the sequential Monte Carlo framework. By constructing a sequence of intermediate target distributions, the proposed algorithm sequentially performs a sampling and importance resampling to maximize the graph matching objective. Through the sequential sampling procedure, the algorithm effectively collects potential matches under one-to-one matching constraints to avoid the adverse effect of outliers and deformation. Experimental evaluations on synthetic graphs and real images demonstrate its higher robustness to deformation and outliers.

Introduction

Graphs provide excellent means to represent features and the structural relationship between them, and the problem of feature correspondence is effectively solved by graph matching. Therefore, graph matching has gained high popularity in various applications in computer vision and machine learning (e.g., object recognition [START_REF] Duchenne | A graph-matching kernel for object categorization[END_REF], shape matching [START_REF] Cao | 2d nonrigid partial shape matching using mcmc and contour subdivision[END_REF], and feature tracking [START_REF] Birchfield | KLT: An implementation of the kanade-lucas-tomasi feature tracker[END_REF]). Due to the NP-hard nature of graph matching in general, its optimal solution is virtually unachievable so that a myriad of algorithms are proposed to approximate it. In recent computer vision literature, the graph matching problem is widely formulated as the Integer Quadratic Program (IQP) [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF][START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF][START_REF] Cho | Reweighted Random Walks for Graph Matching[END_REF][START_REF] Lee | A graph matching algorithm using data-driven markov chain monte carlo sampling[END_REF] that explicitly considers both local appearances and generic pairwise relations. This line of graph matching researches has further extended to hyper-graph matching [START_REF] Duchenne | A tensor-based algorithm for highorder graph matching[END_REF][START_REF] Lee | Hyper-graph matching via reweighted random walks[END_REF], learning techniques [START_REF] Caetano | Learning graph matching[END_REF][START_REF] Leordeanu | Unsupervised learning for graph matching[END_REF], and its progressive framework [START_REF] Cho | Progressive graph matching: Making a move of graphs via probabilistic voting[END_REF]. The existing methods, however, still suffer from severe distortion of the graphs (e.g., addition of outliers in nodes or deformation of attributes). Robustness to such distortion is of particular importance in practical vision problems because real-world image matching problems are widely exposed to background clutter and image variation.

In this paper, a robust graph matching algorithm based on the Sequential Monte Carlo (SMC) framework [START_REF] Cappé | An overview of existing methods and recent advances in sequential monte carlo[END_REF] is proposed. Unlike previous methods, the algorithm sequentially samples potential matches via proposal distributions to maximize the graph matching objective in a robust and effective manner. To treat the graph matching problem in the SMC framework, a sequence of artificial target distributions is designed, which provide smooth transitions from an initial distribution to the final target distribution as the graph matching objective. The proper design of an importance distribution and a resampling scheme allows the algorithm to explore the solution space efficiently under the matching constraints. Consequently, the proposed algorithm achieves higher robustness to outliers and deformation than other graph matching algorithms.

Among numerous graph matching methods, the algorithms closely related to ours are as follows. Maciel and Costeira [START_REF] Maciel | A global solution to sparse correspondence problems[END_REF] casted a graph matching problem as an integer constrained minimization, which is popularly adopted for its generality in recent studies including ours. Many of the subsequent approaches to the IQP formulation handle the original problem by solving a relaxed problem and then enforcing the matching constraint on its solution. For example, Gold and Rangarajan [START_REF] Gold | A graduated assignment algorithm for graph matching[END_REF] relaxed the IQP by dropping the integer constraint and iteratively estimated the convex approximations around the previous solution. Leordeanu et al. [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF] and Cour et al. [START_REF] Cour | Balanced graph matching[END_REF] proposed spectral types of relaxation followed by a discretization process. Torresani et al. [START_REF] Torresani | Feature Correspondence Via Graph Matching: Models and Global Optimization[END_REF] used dual decomposition technique for graph matching optimization. Cho et al. [START_REF] Cho | Reweighted Random Walks for Graph Matching[END_REF] introduced a random walk algorithm to explore the relaxed solution space in the consideration of the matching constraints. More recently, to overcome the limitation of pair-wise relations and embed higher-order information, hyper-graph matching techniques were proposed based on the generalization of the IQP [START_REF] Duchenne | A tensor-based algorithm for highorder graph matching[END_REF][START_REF] Lee | Hyper-graph matching via reweighted random walks[END_REF].

There have been many sampling-based algorithms for feature correspondence and shape matching in literature. Dellaert et al. [START_REF] Dellaert | Feature correspondence: A markov chain monte carlo approach[END_REF] used the Metropolis-Hastings (MH) scheme to solve a correspondence problem in a Bayesian framework. Cao et al. [START_REF] Cao | 2d nonrigid partial shape matching using mcmc and contour subdivision[END_REF] used the MH scheme for partial shape matching. Tamminen et al. [START_REF] Tamminen | Sequential monte carlo for bayesian matching of objects with occlusions[END_REF] used the SMC framework to solve Bayesian matching of objects with occlusion. Lu et al. [START_REF] Lu | Shape guided contour grouping with particle filters[END_REF] and Yang et al. [START_REF] Yang | Weakly Supervised Shape Based Object Detection with Particle Filter[END_REF] proposed a shape detection algorithm based on the particle filter with static observations. However, all these methods for shape matching problems cannot be applied to graph matching in general. Lee et al. [START_REF] Lee | A graph matching algorithm using data-driven markov chain monte carlo sampling[END_REF] introduced the data-driven Markov chain Monte Carlo (DDMCMC) algorithm for graph matching which adopts spectral relaxation for data-driven proposals. To our best knowledge, our work is the first attempt to use the SMC framework for the matching of general graphs.

Problem Definition

We consider two attributed graphs, G P = (V P , E P , A P ) and

G Q = (V Q , E Q , A Q ),
where V, E, and A denotes a set of nodes, edges, and attributes, respectively. In visual feature matching problems, attribute a P i ∈ A P of node v P i ∈ V P usually describes a local appearance at feature i in image P , and attribute a P ij ∈ A P of edge e P ij ∈ E P represents geometric relationship between features i and j in image P . In this paper, one-to-one matching constraints are adopted that every node in G P is mapped to at most one node in G Q and vice versa. Then, Graph matching is to find node correspondences between G P and G Q , which best preserve the attribute relations under the matching constraints. A graph matching solution M is represented by a set of assignments or matches

(v P i , v Q a ) between nodes v P i ∈ V P and v Q a ∈ V Q .
M can be alternatively expressed by an assignment matrix X ∈ {0, 1} n P ×n Q , where n P and n Q are the numbers of nodes in G P and G Q , respectively; X i,a = 1 if (v P i , v Q a ) ∈ M and zero otherwise. An assignment vector x denotes the column-wise concatenated vector of X, and the element of x corresponding to X i,a is represented by x(i, a). The affinity matrix W consists of the relational similarity values between edges and nodes; the compatibility of two edge attributes a P ij and a Q ab , or equivalently two matches

(v P i , v Q a ) and (v P j , v Q b )
, is encoded in non-diagonal component W i,a;j,b , and the compatibility of two node attributes a P i and a Q a is encoded in the diagonal component W i,a;i,a . The graph matching score of x is evaluated by x T Wx which corresponds to the sum of all similarity values covered by the matching. Therefore, graph matching is mathematically formulated as the following IQP problem [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF][START_REF] Lee | A graph matching algorithm using data-driven markov chain monte carlo sampling[END_REF][START_REF] Cho | Reweighted Random Walks for Graph Matching[END_REF]:

x * = argmax(x T Wx) s.t. x ∈ {0, 1} n P n Q , ∀i, a x(i, a) ≤ 1, ∀a, i x(i, a) ≤ 1.
(1)

Sequential Monte Carlo for Graph Matching

In this paper, graph matching is formulated as a sequential sampling of potential matches based on the SMC framework. The SMC methods (e.g., the particle filter [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF]) are widely used for dynamic problems in computer vision, such as object tracking and structure from motion. The basic concept of the SMC is to sequentially estimate the target probability distribution π t at time t with a set of particles, that is a cloud of weighted random samples {(x

(i) t , w (i) t )} N i=1 . A weight w (i)
t represents the importance of the associated sample x (i) t [START_REF] Moral | Sequential monte carlo for bayesian computation[END_REF]. The samples x (i) t at time t are generated from the importance distribution η t , which is constructed by a Markov transition kernel K and the previous distribution π t-1 [START_REF] Moral | Sequential monte carlo samplers[END_REF]; each sample x (i) t evolves from x (i) t-1 according to the kernel K, and the importance distribution η t is represented by

η t (x t ) = xt-1 π t-1 (x t-1 )K(x t-1 , x t ). (2)
The weight w

(i) t of each sample x (i) t
is proportional to the ratio of the target distribution π t to the importance distribution η t , and is defined as

W (i) t = π t (x (i) t ) η t (x (i) t ) , w (i) t = W (i) t N i=1 W (i) t . ( 3
)
Then, the particles as the weighted samples asymptotically converges to the target distribution:

πt (x t ) = N i=1 w (i) t δ x (i) t (x t ) a.s. --→ π t (x t ) as N → ∞, ( 4
)
where δ denotes the Dirac delta function. Unlike typical SMC methods for dynamic problems [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF], we do not assume any prior knowledge about the graph for generality, except for the affinity matrix. In this case, it is intractable to calculate the conditional distribution even up to a normalizing constant, thus the direct sequential sampling from conditional distributions is also intractable.

To formulate graph matching in the SMC framework, we introduced a sequence of intermediate distributions [START_REF] Moral | Sequential monte carlo samplers[END_REF], which starts from a simple initial distribution and gradually moves toward the final target distribution equivalent to the objective function of (1). This SMC procedure performs graph matching by sequentially re-distributing particles over the evolving sample space according to the intermediate target distribution at each step. The procedure is illustrated in Fig. 2, and the details are described in the following subsections.

Sequential Target Distribution

In the SMC graph matching, each particle incrementally collects a new match at each time step so that each particle x (i) t at time step t always has t matches. The maximum number of matches in the solution (or the maximum time step in the sampling) is L = min(n P , n Q ). We design the final target distribution as

π L (x L ) ∝ exp(x T L Wx L /τ ) ( 5
)
where τ is a scaling constant. Since the exponential function increases monotonically, the optimal solution of the graph matching score x T Wx in Eq. ( 1) maximizes the probability π L of Eq. ( 5). Since x L has high dimensionality of n P n Q , direct sampling from π L is not tractable in general cases. As illustrated in Fig. 2(a), a sequence of intermediate target distributions {π t } L-1 t=1 is introduced for the SMC sampling as follows:

π t (x t ) ∝ exp(x T t Wx t /τ ), t = 1, • • • , L -1. (6)
A feasible set of the graph matching problem, or a set of all possible x satisfying the constraints of Eq. ( 1), is denoted by X . Each intermediate target distribution π t in Eq. ( 6) then is defined on the measurable space (X t , t ) where X t = {x ∈ X | i,a x t (i, a) = t}. The more true matches a particle x (i) t includes, the higher value the probability π t (x

(i) t ) has. Thus, the sequence of distributions {π t } L-1 t=1
effectively drives the particles to the final target distribution π L .

Sequential Sampling

In order to sample from the intermediate target distribution π t , new particles are propagated from the previous particles {x

(i)
t-1 } N i=1 using the sampling and importance resampling (SIR) technique [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF]. In each time step, each particle additionally selects a new match m in a probabilistic manner according to the transition kernel,

K(x t-1 , x t-1 + e m ) = 1 Z exp(e T m Wx t-1 /τ ) if (x t-1 + e m ) ∈ X t 0 o t h e r w i s e (7)
where e m is a unit vector that corresponds to the match m and Z is a normalizing constant. In selecting the new match m, the kernel reflects both the matching constraints and the affinity relations with previously sampled matches in x t-1 .

As the time step increases, previously selected inlier matches boost the sampling probability of other inlier matches for each particle. The augmented particle in this step is denoted by x t = x t-1 + e m . Given that particles at time step t -1 follow the distribution π t-1 , the transition leads them to a new importance distribution

η t (x t ) = xt-1 π t-1 (x t-1 )K(x t-1 , x t ) ≈ N i=1 π t-1 (x (i) t-1 )K(x (i) t-1 , x t ). (8)
For further discussion, let us denote the particles after transition by {x

(i) t } N i=1
. The particles of equal matches are grouped together to form a set of n unique assignment vectors {g (j) t } n j=1 and the number of particles corresponding to the j-th group is denoted by n j . Then, the weight of the particle is approximated as follows:

W (i) t = π t (x (i) t ) η t (x (i) t ) ≈ π t (x (i) t ) 1 N n j=1 n j δ(x (i) t -g (j) t ) ∝ π t (x (i) t ) n I(i) ( 9
)
where I(i) is a group ID of the particle x (i)

t . Therefore, to calculate the weights, particles of same matches should be grouped together first as detailed in Sec. 3.4. Then, the weights are easily obtained by computing π t (x t ). Finally, the resampled particles based on the weights, {x

(i) t } N i=1 , follow the intermediate target distribution π t .

Particle Updating

To correct false matches sampled in early steps, we update particles after sampling at every time step. As shown in Fig. 2(c), the particle updating spreads the current particle to a neighborhood support sharing t -1 matches by changing the most unreliable match to a better match. Among the matches in the particle x(i) t , the match sharing the lowest affinity values with other matches is selected by

m w = argmin m s.t. e T m x(i) t =1 e T m Wx (i) t . ( 10
)
The selected match m w is replaced with a new match sampled by the transition kernel K(x

(i) t -e mw , x (i)
t ) of Eq. ( 7). After repeating the grouping and resampling process of Sec. 3.2, the updated particles {x (i) t } N i=1 are obtained. In this updating procedure, while following the intermediate target distribution, the particles are redistributed into the support with high probability under the target distribution.

Implementation Details

The proposed algorithm is summarized in Algorithm 1. Some implementation issues are addressed in the following.

Computational Complexity. One step procedure is composed of transition, grouping, resampling, and updating. The computational complexity for each subprocedure is as follows: Transition O(N n cm + G t n cm + G t t), grouping O(N t) (n cm : the number of candidate matches, N : the number of particles, G t : the number of unique groups at time step t, G t ≤ N , t ≤ L ≤ n cm ). Therefore the Algorithm 1: SMC graph matching input : affinity matrix W output: assignment vector x // Initialization Sample particles from the initial distribution π1; // SMC loop while sampling available do Propagate each particle by sampling a new match according to Eq. ( 7); Resample the particles according to the weights of Eq. ( 9); Update the particles according to Sec. 3.3; end Choose a particle x * with the highest matching score as the final solution;

total complexity for one step procedure is O(N n cm ), and the entire algorithm takes O(n cm LN ) where L denotes the number of samplings.

Initial Distribution. The initial distribution is calculated as the marginal of the intermediate target distribution, π 2 . Utilizing the symmetric property of the affinity matrix, the initial distribution π 1 is obtained as

π 1 (x 1 ) ∝ 1 T exp(W/τ )x 1 , (11)
where exp(W/τ ) denotes the elementwise exponent of (W/τ ) and 1 is a column vector with all ones. Transition Kernel. In order to reduce the computational cost and memory cost, a transition kernel K is computed as an approximated version which its lowest 100(1α)% was forced to be 0. Experimental results for different α are shown in synthetic random graph matching task in Sec. 4.3.

Grouping. Grouping of particles can be performed efficiently by using radix sort and a simple trick. First, a unique ID is assigned to every candidate match. Then each particle is represented by a combination of IDs. IDs in each combination are sorted so that the sequence of IDs form a N-ary t digit number with the i-th digit value corresponding to the i-th smallest ID. Now, after N-ary radix sort, particles can be efficiently grouped in O(N t) (N :the number of particles, t: match size) by comparing only the adjacent neighbors.

Final Solution. The SMC loop is terminated simply when no more sampling is possible while keeping the constraints. Then, a particle maximizing the score of Eq. ( 1) is selected as the final solution. Since the matches of each particle already satisfy the one-to-one matching constraints, no additional post-processing for discretization is needed in our approach.

Experiments

In this section, two sets of experiments were performed for quantitative evaluation: (1) synthetically generated random graph matching and (2) feature matching using real images. The proposed algorithm (SMCM) was compared with seven state-of-the-art methods including SM [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF], SMAC [START_REF] Cour | Balanced graph matching[END_REF], PM [START_REF] Zass | Probabilistic graph and hypergraph matching[END_REF], IPFP [START_REF] Leordeanu | An integer projected fixed point method for graph matching and map inference[END_REF], GAGM [START_REF] Gold | A graduated assignment algorithm for graph matching[END_REF], RRWM [START_REF] Cho | Reweighted Random Walks for Graph Matching[END_REF], and DDMCM [START_REF] Lee | A graph matching algorithm using data-driven markov chain monte carlo sampling[END_REF]. The authors' implementations were used for SM, SMAC1 , PM2 , IPFP3 , DDMCM, and RRWM4 . For GAGM, the implementation by Cour et al. [START_REF] Cour | Balanced graph matching[END_REF] is adopted. All methods were implemented using MATLAB and were tested on 2.40 GHz Core2 Quad desktop PC. In each experiment, the same affinity matrix was shared by all algorithms, and α is fixed to 0.1 in SMCM. In addition to the two experiments, the experimental analyses of SMCM will be provided in Sec. 4.3.

Synthetic Random Graph Matching

The random graph matching experiments were performed following the experimental protocol of [START_REF] Cour | Balanced graph matching[END_REF][START_REF] Gold | A graduated assignment algorithm for graph matching[END_REF][START_REF] Cho | Reweighted Random Walks for Graph Matching[END_REF]. In this experiment, the Hungarian algorithm [START_REF] Munkres | Algorithms for the assignment and transportation problems[END_REF] was used for the post-processing of discretization, and τ = 2 is used for SMCM.

Two graphs, G P and G Q , were constructed at each trial with n = n in + n out nodes, where n in and n out denote number of inlier and outlier nodes, respectively. The reference graph G P was generated with random edges, where each edge (i, j) ∈ E P was assigned a random attribute a P ij distributed uniformly in [0, 1]. A perturbed graph G Q was then created by adding noise on the edge attributes between inlier nodes: a Q p(i)p(j) = a P ij +ε, where p(.) is a random permutation function. The deformation noise ε was assigned by the Gaussian function N (0, σ 2 ). All the other edges connecting at least one of the outlier nodes were randomly generated with random edges in the same way of G P . Thus, G P and G Q share a common but perturbed subgraph with size n in . The affinity matrix W was computed by W i,a;j,b = exp(-|a P i,ja Q a,b | 2 /σ 2 s ), ∀e P ij ∈ E P , ∀e Q ab ∈ E Q and the diagonal terms are set to be zero. The scaling factor σ 2 s was chosen to be 0.1 to perform best in overall algorithms. The accuracy was computed as the ratio of the number of true positive matches to that of ground truths. The objective score was computed by the IQP objective x T Wx.

In the experimental setting, there are two independent variables, the number of outliers n out and the amount of deformation noise σ. Using these, three experiments with different conditions were conducted: (1) varying the amount of deformation noise with no outliers (2) varying the number of outliers with no deformation (3) varying the number of outliers with some deformation. Each experiment was repeated for 100 times with different matching problems generated from the above procedure, and the average accuracy and objective score were recorded. In all experiments, the number of inliers n in is fixed to 20. Figure 3(a) represents the results of varying deformation noise σ from 0 to 0.3 by increments of 0.05 while fixing the number of outliers n out = 0 and particles N = 10000. As observed in the score plots (middle) in Fig. 3, SMCM consistently outperforms all the other algorithms in the objective score, regardless of the degree of deformation and outliers; SMCM performs best as the optimizer of graph matching score. Especially, the accuracy of SMCM significantly exceeds those of the other algorithms under increasing outliers as shown in Figs. 3(b) and 3(c). It implies that in the SMC framework SMCM avoids the adverse effects of outliers effectively through sequential collection of inliers under the matching constraints. In deformation experiment of Fig. 3(a), the accuracy of SMCM is comparable or slightly inferior to the best of RRWM. However, SMCM outperforms all other methods in realistic conditions where both outliers and deformation exists as in Fig. 3(c). The bottom row of Fig. 3 shows the computational time.

Real Image Matching

In this experiment, we performed real image matching on the benchmark image dataset5 used in [START_REF] Cho | Reweighted Random Walks for Graph Matching[END_REF]. The dataset consists of 30 image pairs containing photos of various objects, most of which are collected from Caltech-101 and MSRC datasets, and provides the detected MSER features [START_REF] Matas | Robust wide baseline stereo from maximally stable extremal regions[END_REF], the initial matches, and the manually-labeled ground truth matches. For each image pair, two graphs were constructed by considering the features as nodes. To sparsify the affinity matrix, only the similarity values related to candidate correspondences are assigned in the affinity matrix. In our experiments, 70 nodes and 720 candidate matches per an image pair are used in average. The affinity matrix W i,a;j,b = exp(-d i,a;j,b /σ 2 s ) is computed using the symmetric transfer error d i,a;j,b , which is used in [START_REF] Cho | Reweighted Random Walks for Graph Matching[END_REF], as the measure of affine-invariant dissimilarity between two feature pairs, (v P i , v P j ) and (v Q a , v Q b ). The scaling parameter σ 2 s was set to 10 to enhance the overall accuracy over all algorithms. In this experiment, the greedy mapping was used for the post-processing of discretization, and τ = 10 and 500 particles are used for SMCM. The matching accuracy and the running time were measured for SM, RRWM, PM, IPFP, SMAC, GAGM, and SMCM. 6The results are summarized in the Table 1 and some examples are shown in Fig. 4. SMCM records the highest accuracy in acceptable running time. Its robustness to outliers and deformations is observed again in this real image matching experiment.

More Experimental Analyses

In this section, we performed three additional experiments to analyze the characteristics of SMCM. In the first experiment, we evaluated the performance of SMCM while varying number of particles. The larger the number of particles is, the more likely the set of matches with low probability are sampled, resulting in broader search. Therefore, more particles produce better performance at the cost of more computation. There is a trade-off between accuracy and time, and it can be controlled by the number of particles, depending on the application. Using the same synthetic random graph experiment of Sec. 4.1, we plotted the average accuracy over 30 experiments with respect to the number of particles. Figures 5(a) and 5(b) provide the results varying the number of outliers with no deformation, and varying deformation noise with no outliers, respectively. For the problem with outliers, 400-1000 samples are needed for saturation, and in the presence of deformation, more particles, about 5000, are needed to arrive at saturation point. Unlike outlier noise, the deformation noise lowers the affinity value between true matches, making true and false matches indistinguishable. Therefore, more particles are needed in the presence of deformation noise. Nevertheless, the required number of particles is only a tiny fraction of the number of all possible combinations (20!).

In the second experiment, we evaluated the efficiency of the algorithm. First, the average precision of particles at each time step is depicted in Fig. 6(a) for the synthetic random graph matching experiment in Sec. 4.1 while the number of outliers is varied. It increases abruptly after about three to eight samplings, which means that previously sampled matches in the particles boost sampling of other inlier matches. It decreases after time step 20 because the number of true matches is 20. Secondly, Fig. 6(b) shows the number of groups at each time step in the same experiments. Since the information of particles is shared within a group, the number of groups directly affects the computational cost. In Fig. 6, it decreases until time step 3-8 while average precision increases, which implies that the weights are highly concentrated on reliable groups at the early stages. When the precision saturates, the number of groups gradually decreases after a small increase, resulting in effective reduction of computational cost.

In the third experiment, we evaluated the accuracy for different settings of α for the same experimental settings in Sec. 4.1. The results are shown in Fig. 7. As the value of α increases, SMCM becomes more robust to the deformation noise. In the presence of outliers, however, the highest accuracy is achieved at α = 0.1 where the distracting outlier matches with relatively small affinity values are effectively ignored.

Conclusion

In this paper, we proposed a novel graph matching algorithm based on the Sequential Monte Carlo (SMC) framework. During the sequential sampling procedure, our algorithm effectively collects potential matches under matching constraints and avoids the adverse effect of outliers and deformation. The experimental results show that it outperforms the state-of-the-art algorithms and is highly robust to outliers. Since the SMC can preserves samples of multi-modes in particles, it is extendable to multi-modal graph matching algorithm by utilizing the properties. We leave this in future work.

Fig. 1 .

 1 Fig.1. The main idea of the proposed algorithm. The algorithm sequentially samples potential matches via proposal distributions to maximize the graph matching objective under the matching constraints. In every time step, new matches are sampled based on the affinity with the previously sampled matches.

Fig. 2 .

 2 Fig. 2. Overview of the proposed method. (a) A sequence of intermediate target distributions from a simple initial distribution to the target distribution is constructed. (b) Transition from time step t -1 to the t is performed based on the sampling and importance resampling (SIR) technique exploiting the particles from the previous distribution. (c) An example of the neighborhood relation between two candidate matchings. They share two common matches and differ in one match.

Figure 3 (

 3 b) shows the result of varying the number of outliers n out from 0 to 20 by increments of two while fixing N = 2000 and deformation noise σ = 0.

Fig. 3 .

 3 Fig. 3. Synthetic graph matching experiments. The accuracies (top), objective scores (middle) and computational times (bottom) are plotted for three different conditions: (a) varying deformation noise with no outliers, (b) varying the number of outliers with no deformation noise, and (c) varying the number of outliers with some deformation noise.

Figure 3 (

 3 Figure 3(c) represents the result of varying the number of outliers n out from 0 to 20 by increments of two while fixing N = 5000 and deformation noise σ = 0.1.As observed in the score plots (middle) in Fig.3, SMCM consistently outperforms all the other algorithms in the objective score, regardless of the degree of deformation and outliers; SMCM performs best as the optimizer of graph matching score. Especially, the accuracy of SMCM significantly exceeds those of the other algorithms under increasing outliers as shown in Figs.3(b) and 3(c). It implies that in the SMC framework SMCM avoids the adverse effects of outliers effectively through sequential collection of inliers under the matching constraints. In deformation experiment of Fig.3(a), the accuracy of SMCM is comparable or slightly inferior to the best of RRWM. However, SMCM outperforms all other methods in realistic conditions where both outliers and deformation exists as in Fig.3(c). The bottom row of Fig.3shows the computational time.

Fig. 4 .

 4 Fig. 4. Some representative results of the real image matching experiments. True positive matches are represented by blue lines and false positive matches are represented by black lines.

Fig. 5 .

 5 Fig. 5. To determine the proper number of particles experimentally, we plotted the average accuracy over 30 experiments with varying the number of particles and problem difficulty in the synthetic random graph matching experiment (Sec. 4.1). The plots are obtained by varying (a) the number of outliers and (b) deformation rate. In both cases, the accuracy saturates as the number of particles become large enough, except for the extreme conditions.

Fig. 6 .

 6 Fig. 6. The average precision of particles and the number of particle groups at each time step are measured on the synthetic random graph matching in Sec. 4.1. (a) The average precision of particles increases as the number of matches in particles increases. The plot is depicted while the number of outliers is varied. An abrupt increase occurs when enough true matches (3-8) are sampled. (b) The number of particle groups is depicted versus the time step while the number of outliers is varied. The number of groups decreases as the match size increases.

Fig. 7 .

 7 Fig. 7. The accuracies for different settings of α are shown. The experimental settings are same as the synthetic random graph matching in Sec. 4.1.

Table 1 .

 1 Avergage performance on the real images

	Algorithm	SM RRWM PM IPFP SMAC GAGM SMCM
	Accuracy (%) 65.3	69.0	60.5 65.7	50.8	67.6	69.6
	Time (Sec.) 0.02	1.00	0.05 0.13	0.03	1.67	0.89

http://www.seas.upenn.edu/ ~timothee/

http://www.cs.huji.ac.il/ ~zass/

http://86.34.14.245/code.php

http://cv.snu.ac.kr/research/ ~RRWM/

The dataset is available from http://cv.snu.ac.kr/research/ ~RRWM/

For SMCM, we measured the average accuracy over 30 trials because SMCM is a stochastic algorithm unlike others.


Juan Antonio Lossio-Ventura

Clement Jonquet

Mathieu Roche

Maguelonne Teisseire

Journées internationales d'Analyse statistique des Données Textuelles Biomedical Terminology Extraction: A new combination of Statistical and Web Mining Approaches

Keywords: Biomedical Natural Language Processing (BioNLP), Biomedical Thesaurus, Statistic Measure, Text Mining, Web Mining, C-value

The objective of this work is to combine statistical and web mining methods for the automatic extraction, and ranking of biomedical terms from free text. We present new extraction methods that use linguistic patterns specialized for the biomedical field, and use term extraction measures, such as C-value, and keyword extraction measures, such as Okapi BM25, and TFIDF. We propose several combinations of these measures to improve the extraction and ranking process and we investigate which combinations are more relevant for different cases. Each measure gives us a ranked list of candidate terms that we finally re-rank with a new web-based measure. Our experiments show, first that an appropriate harmonic mean of C-value used with keyword extraction measures offers better precision results than used alone, either for the extraction of single-word and multi-words terms; second, that best precision results are often obtained when we re-rank using the web-based measure. We illustrate our results on the extraction of English and French biomedical terms from a corpus of laboratory tests available online in both languages. The results are validated by using UMLS (in English) and only MeSH (in French) as reference dictionary.

Résumé

L'objectif de ce travail est de combiner les méthodes d'extraction statistiques et la fouille du web pour l'extraction automatique et le classement des termes biomédicaux à partir de documents textuels. Nous présentons de nouvelles méthodes d'extraction qui utilisent des patrons linguistiques spécialisés du domaine biomédical associés à des mesures d'extraction de termes, tels que C-value, et des mesures d'extraction de motsclés comme Okapi BM25 et TFIDF. Nous proposons plusieurs combinaisons de ces mesures afin d'améliorer le processus d'extraction et de classement. Chaque mesure nous donne une liste ordonnée des termes candidats que nous avons finalement réordonné avec une nouvelle mesure web. Nos expérimentations montrent, d'abord, que la moyenne harmonique de C-value avec une mesure d'extraction de mots-clés offre de meilleurs résultats de précision que leur utilisation seule pour l'extraction des termes composés d'un seul mot et des syntagmes. Les meilleurs résultats de précision sont souvent obtenus quand nous appliquons la mesure fondée sur le web. Nous illustrons nos résultats à partir de l'extraction des termes biomédicaux en anglais et en français sur un corpus de tests de laboratoire disponibles en ligne dans les deux langues. Les résultats sont validés à l'aide de UMLS (en anglais) et MeSH (en français) comme dictionnaire de référence.

Introduction

The huge amount of data available online today is often composed of plain text field, for instances clinical trial description, adverse event report or electronic health records. These texts often contain the real language (expressions and terms) used by the community.

JADT 2014 : 12 es Journées internationales d'Analyse statistique des Données Textuelles Although in the biomedical domain there exist hundred of terminologies and ontologies to describe such languages [START_REF] Noy | BioPortal: ontologies and integrated data resources at the click of a mouse[END_REF], those terminologies often miss concepts or possible alternative terms for those concepts. Our motivation is to improve the precision of automatic terms extraction process, the main reason for this, is that language evolves faster than our ability to formalize and catalog it. This is even more true for French in which the number of terms formalized in terminologies is significantly less important than in English.

NLP (natural language processing) tools and methods enable to enrich biomedical dictionaries from texts. Automatic Term Recognition (ATR) is a field in language technology that involves the extraction of technical terms from domain-specific language corpora [START_REF] Zhang | A Comparative Evaluation of Term Recognition Algorithms[END_REF]. Similarly, Automatic Keyword Extraction (AKE) is the process of extracting the most relevant words or phrases in a document with the propose of automatic indexing. Keywords, which we define as a sequence of one or more words, provide a compact representation of a document's content; two popular AKE measures are Okapi BM25 [START_REF] Robertson | Okapi at TREC-7: automatic ad hoc, filtering, VLC and interactive track[END_REF] and TFIDF (also called weighting measures). These two fields are summarized in Table 1.

ATR AKE

Automatic Term Recognition

Automatic In our work, we adopt as baselines an ATR method, C-value [START_REF] Frantzi | Automatic Recognition of Multi-Word Terms: the Cvalue/NC-value Method[END_REF], and the best two AKE methods [START_REF] Hussey | Automatic keyphrase extraction: a comparison of methods[END_REF], previously mentioned and considered state-ofthe-art. Indeed, the C-value, compared to other ATR methods, often gets best precision results and specially in biomedical studies [START_REF] Knoth | Towards a Framework for Comparing Automatic Term Recognition Methods[END_REF], [START_REF] Zhang | A Comparative Evaluation of Term Recognition Algorithms[END_REF], [START_REF] Zhang | A Comparison of Keyword-and Keyterm-Based Methods for Automatic Web Site Summarization[END_REF]. Moreover, C-value is defined for multi-word term extraction but can be easily adapted for single-word term and it has never been applied to French text, which is appealing in our case. The rest of the paper is organized as follows: Section 2 describes the related work in the field of ATR, and specially the uses of the C-value; Section 3 presents our combination of measures and the web-based measure for re-ranking candidate terms; Section 4 shows and discusses our experiment results; and Section 5 concludes the paper.

Related Work

ATR studies can be divided into four main categories: (i) rule-based approaches, (ii) dictionarybased approaches, (iii) statistical approaches, and (iv) hybrid approaches. Rulebased approaches for instance [START_REF] Gaizauskas | Term Recognition and Classification in Biological Science Journal Articles[END_REF], attempt to recover terms thanks to the formation patterns, the main idea is to build rules in order to describe naming structures for different classes using orthographic, lexical, or morphosyntactic characteristics. Dictionarybased approaches use existing terminology resources in order to locate term occurrences in texts [START_REF] Krauthammer | Term identification in the biomedical literature[END_REF]. Statistical approaches are often built for extracting general terms [START_REF] Eck | Automatic term identification for bibliometric mapping[END_REF]; the most basic measure is frequency. XTRACT (Smadja, 1993) is a statistical method, first it extracts the binary terms located in a window of ten words. The binary terms selected are those that exceed a statistically significantly frequency due to the chance. The next step is to extract the terms containing the binary terms found in the previous step. Another method is ACABIT [START_REF] Daille | Towards Automatic Extraction of Monolingual and Bilingual Terminology[END_REF] that performs a linguistic analysis to convert the nominal terms in binary terms. Then these terms are sorted according to statistical measures. C/NC-value [START_REF] Frantzi | Automatic Recognition of Multi-Word Terms: the Cvalue/NC-value Method[END_REF], is another statistical method well known in the literature that combines statistical and linguistic information for the extraction of multi-word and nested terms. While most studies address specific types of entities, C/NC-value is a domain-independent method. It was also used for recognizing terms from biomedical literature (Hliaoutakis et al., 2009). The C/NC-value method was also applied to many different languages besides English [START_REF] Frantzi | Automatic Recognition of Multi-Word Terms: the Cvalue/NC-value Method[END_REF] such as Japanese [START_REF] Mima | An application and evaluation of the C/NC-value approach for the automatic term recognition of multi-word units in Japanese. Japanese Term Extraction[END_REF], Serbian, Slovenian, Polish, Chinese [START_REF] Sum | Chinese Terminology Extraction Using Window-Based Contextual Information[END_REF], Spanish [START_REF] Barrón-Cedeño | An Improved Automatic Term Recognition Method for Spanish[END_REF], and Arabic, however to the best of our knowledge not for French. An objective of this work is to combine this method with AKE methods and to apply them to English and French. We believe that the combination of biomedical term extraction and the extraction of keywords describing a document, could be beneficial since keywords techniques give greater importance to the actual terms of this domain. This combination has never been proposed and experimented in the literature.

Proposed Methodology for Automatic Biomedical Term Extraction

This section describes the baselines measures and their customizations as well as the new combinations of these measures and the new web-based measure that we propose for automatic biomedical terms extraction and ranking. Our method for automatic term extraction has five main steps; described in Figure 1:

(1) Part-of-Speech tagging, (2) Candidate terms extraction, (3) Ranking of candidate terms, (4) Computing the new combined measures, (5) Re-ranking using web-based measure.

We execute those five steps taking either C-value (right branch), and Okapi/TFIDF (left branch) as the baseline method. Notice, that because C-value is a method that deals with an unique corpus as input whereas weighting measure deal with several documents (cf. Table 1) then we need to do the union of documents of the corpus in the right branch case, in order to consider the whole corpus as an unique document. A preliminary step not represented in Figure 1 is the creation of patterns for French and English, as described hereafter.

Part-of-Speech tagging

Part-of-speech (POS) tagging is the process of assigning each word in a text to its grammatical category (e.g., noun, adjective). This process is performed based on the definition of the word or on the context which it appears in.

We apply part-of-speech to the whole corpus. We evaluated three tools (TreeTagger, Stanford Tagger and Brill's rules), and finally choose TreeTagger which gave the best results and is usable both for French and English.

Candidate Terms Extraction

Building biomedical patterns

As previously cited work, we supposed that biomedical terms have similar syntactic structure.

Therefore, we build a list of the most common lexical patterns according the syntactic structure of biomedical terms present in the UMLS1 (for English) and the French version of MeSH2 (for French).

We also do a part-of-speech tagging of the biomedical terms using TreeTagger3 , then compute the frequency of syntactic structures. We finally choose the 200 highest frequencies to build the list of patterns for each language. The number of terms used to build these lists of patterns was 2 300 000 for English and 65 000 for French. Examples of patterns are given in

Candidate terms extraction following patterns

Before applying any measures we filter out the content of our input corpus using patterns previously computed. We select only the terms which syntactic structure is in the patterns list.

Ranking of Candidate Terms

Using C-value

The C-value method combines linguistic and statistical information [START_REF] Frantzi | Automatic Recognition of Multi-Word Terms: the Cvalue/NC-value Method[END_REF]; the linguistic information is the use of a general regular expression as linguistic patterns, and the statistical information is the value assigned with the C-value measure based on frequency of terms to compute the termhood (i.e., the association strength of a term to domain concepts).

JADT 2014 : 12 es Journées internationales d'Analyse statistique des Données Textuelles

The aim of the C-value method is to improve the extraction of nested terms, it was specially built for extracting multi-word terms.

C_ = × (), if ∉ × - 1 ! × ! ∈ ! ! , ℎ (1)
Original

C-value Modified C-value w(a) = log2(|a|) w(a) = log2(|a| + 1) antiphospholipid antibodies log 2 (2) = 1 log 2 (2 + 1) = 1.6 white blood log 2 (2) = 1 log 2 (2 + 1) = 1.6 platelet log2(1) = 0 log 2 (1 + 1) = 1
Table 3: Calculation of w(a).

Using Okapi -TFIDF

Those measures are used to associate each term of a document with a weight that represents its relevance to the meaning of the document it appears relatively to the corpus it is included in (and relatively to the size of the document int the case of Okapi). The output is a ranked list of terms for each document, which is often used in information retrieval, to order documents by their importance given a query [START_REF] Robertson | Okapi at TREC-7: automatic ad hoc, filtering, VLC and interactive track[END_REF]. Okapi can be seen as an improvement of TFIDF measure, taking into account the document length.

The outputs of Okapi and TFIDF are calculated with a variable number of data so their values are heterogeneous. In order to manipulate these lists, the weights obtained from each document must be normalized. Once values normalized we have to merge the terms into a single list unique for the whole corpus to compare the results. Clearly the precision will depend on the method used to perform such merging. We merged following three functions, which calculate respectively the sum(S), max(M) and average(A) of the measures values of the term in whole the corpus. At the end of this task we have three lists from Okapi and three from TFIDF. The notation for these lists are ! () and ! (), where a is the term, X the factor ∈ {M, S, A}. For example, ! () is the value obtained by taking the maximum Okapi value for a term a in the whole corpus.

Computing the New Combined Measures

With aim of improving the precision of terms extraction we have conceived two new combined measures schemes, taking into account the values obtained in the above steps.

F-OCapi and F-TFIDF-C

Considered as the harmonic mean of the two used values, this method has the advantage of using all the values of the distribution.

JADT 2014 : 12 es Journées internationales d'Analyse statistique des Données Textuelles

-! = 2 × ! × - ! + - (2) --! = 2 × ! × - ! + - (3)

C-Okapi and C-TFIDF

For this measure, our assumption is that C-value can be more representative if the frequency, in the Equation (1), of the terms is replaced with a more significant value, in this case the Okapi's or TFIDF's values of the terms (over the whole corpus).

C -() = × (), if ∉ × - 1 ! × ! ∈ ! ! , ℎ (4)
Where () = ! , ! , and X ∈ , , .

Table 4 shows different ranking of terms with our system based on different measures. This example highlights specific and very relevant terms such as "antiphospholipid antibodies" and "platelet" which are explicitly better ranked with F-TFIDF-CM (15,45); in comparison for "white blood" we get the opposite effect (796), because this candidate term is not a biomedical term by itself.

Ranking of the terms C-value TFIDF M Okapi M F-TFIDF-C M F-OCapi

Re-ranking using Web-based Measure

After the extraction of terms we use a web-based measure to re-rank the candidate terms in order to augment the top k terms precision.

Different web mining studies focus on semantic similarity, semantic relatedness [START_REF] Gracia | The AMTEx approach in the medical document indexing and retrieval application[END_REF]. It means to quantify the degree in which some words or concepts are related, considering not only similarity but any possible semantic relationship among them. They are also used for multi-ontology disambiguation [START_REF] Gracia | Querying the web: a multiontology disambiguation method[END_REF]. Web-based measures use web search engines to compute this similarity. One of the most well known web-based measure is the Normalized Google Distance [START_REF] Cilibrasi | The Google Similarity Distance[END_REF].

Our web-based measure has for objective to tell us if a candidate term is a real biomedical term or not. It is specially appropriated for multi terms, as it computes the dependence between the words of a term. In our case, we compute a "strict" dependence, which means the proximity of words of terms (i.e., neighboring words) is calculated with a strict restriction. In comparison with other web-based measures [START_REF] Cilibrasi | The Google Similarity Distance[END_REF], WebR reduces the number of pages to consider by taking only into account web pages containing all the words of the terms. In addition, our measure can be easily adopted for all types of multi terms.

= _ "" _ ( 5
)
Where a is the candidate term, num_doc("a") the number of documents returned by the search engine with exact match only with multi term a (query with quotation marks "a"), num_doc(a) the number of documents returned by the search engine including not exact match (query a without quotation marks), i.e., the whole documents containing the words of the multi term a. For example, the multi term treponema pallidum, will generate 2 queries, the first num_doc("treponema pallidum") which returns with Yahoo 1'100'000 documents, and the second query num_doc(treponema pallidum) which returns 1'300'000 documents, then:

= 1 100 000 1 300 000 = 0.85 our workflow we have tested Yahoo, Bing and Google, but WebR uses Yahoo because the results were the best. WebR re-rank the list of candidate terms returned by the combined measures. This is the final output of our workflow, on which we can evaluate precision taking the top k terms (P@k, in the following k = 60,300,900), and compare them to results obtained either directly by baseline measures or by new combined measures without WebR.

In the following section, we evaluate a large list of extracted and ranked terms with our new measures and their different combinations.

Experiments and Results

Data and Experimental Protocol

We used biological laboratory tests, extracted from Lab Tests Online4 as corpus. This site provides information in several languages to patient or family caregiver on clinical lab tests. Each test which forms a document in our corpus, includes the formal lab test name, some synonyms and possible alternate names as well as a description of the test (at a glance, the test sample, the test and common questions), they are document that contain free text. Our extracted corpus contains 235 clinical tests (about 400 000 words) for English and 137 (about 210 000 words) for French.

In order to automatically validate our candidate terms we use as dictionaries UMLS for English and MeSH for French.

Experiments and Results

The evaluation was done automatically. Results are evaluated in terms of precision obtained over the top k terms (P@k, where k=60, 300, 900) at different steps of our workflow presented in previous section. Okapi and TFIDF provided three lists of ranked candidate terms (M, S, A). For each combined measure using Okapi or TFIDF, the experiments are done with the three lists. Therefore, the number of ranked list to compare is C-value(1)

+ Okapi(3) + TFIDF(3) + F-OCapi(3) + F-TFIDF-C(3) + C-Okapi(3) + C-TFIDF(3) + WebR(1) = 20.
In addition we experimented the workflow either for all (single and multi) or multi terms which finally gave 40 ranked lists.

The following paragraphs show part of the experiment results done for all (single-and multiword terms) or multi terms. In the following we narrow down the presented results by keeping for the next workflow step only the best results.

Results obtained with baselines and new combined measures Table 5: Extract of precision comparison for term extraction for English and French

Table 5 compares the precision between the best baselines measures and the best combined measures. Best results were obtained in general with F-TFIDF-C M for English and F-OCapi M for French. This table proves that the combined measures based on the harmonic mean are better than the baselines measures, and especially for multi word terms, for which the gain in precision reaches 16%. This result is particularly positive because in the biomedical domain it is often more interesting to extract multiword terms than single-word terms. However, one can notice that results obtained to extract all terms with C-Okapi X and C-TFIDF X are not better than Okapi X or TFIDF X use directly. The main reason for this is because the performance of those new combined measures are absorbed by the effect of extracting also single word terms. Definitively, all the new combined measures are really performing better for multi word terms.

Results of AKE methods for English show that TFIDF obtains better results than Okapi. The main reason for this, is because the size of the English corpus is larger than the French one, and Okapi is known to perform better when the corpus size is smaller (Lv et al., 2011).

In addition, Table 5 shows that C-value can be used to extract French biomedical terms with a better precision than what has been obtained in previous cited works with different languages. The precision of C-value for the previous work was between 26% and 31%.

WebR results

Our web mining approach is applied at the end of the process. With a number of terms small because the number of queries from an application to the search engines is limited, we took the lists with best results. The objective is re-rank the 300 terms of each list putting the "true"

English French All Terms

Multi Terms All Terms Multi Terms P@60 P@300 P@900 P@60 P@300 P@900 P@60 P@300 P@900 P@60 P@300 P@900 terms at the top of the list, in this way the precision by intervals is improved. For this we had to choose the list, which got the best precision in the automatic validation.

! 0.
Due to the restriction on the number of queries to search engines, it is more interesting for us first to evaluate the web measure with the French data. Table 15 shows the results between F-OCapi M and the WebR with automatic validation. We can see that WebR gets better results by intervals, this means true biomedical terms have a better ranking.

Multi Terms with Automatic Validation P@30 P@60 P@90 P@120 P@180 P@300

-! 63

Discussion

Several terms proposed by our system are considered as irrelevant (i.e., false positive examples) with our automatic validation protocol because they are not present in known biomedical dictionaries, which does not mean that they are actually irrelevant. Indeed, elements that are not automatically validated can be considered relevant after the manual validation. For instance, they can represent new terms to add in biomedical ontologies or terminologies. Therefore, we proceed to a manual validation of the rest of the terms (i.e., the ones not found in the validation dictionary). For this, we gave a list of extracted terms to an user to validate manually. Table 7 shows the precision evaluated through human review for the best new combined measures for each language and for the web measure only for French. Note that the manual validation confirms that our ranking measure has a good behavior because the precision value is better for first terms. Table 7 also shows clearly that WebR gets better results by intervals than F-Ocapi M .

Multi Terms with Manual Validation P@30 P@60 P@90 P@120 P@180 P@300 English --100.00% 100.00% 99.17% 98.89% 96.67% 93.00% We also have done experiments with two more corpus: (i) the Drugs data from MedlinePlus in English and, (ii) PubMed citations' titles in English and French, we have verified that the new combined measures are performing better, particularly these based on the harmonic mean, F-TFIDF-C M and F-OCapi M .

Conclusions and Perspectives

This work present a methodology for term extraction and ranking for two languages, French and English. We have adapted C-value to extract French biomedical terms, which was not proposed in the literature before.

We presented and evaluated two new measures obtained by combining three existing methods and another new web-based measure. The best results were obtained by combining C-value with the best results from AKE methods, i.e., F-TFIDF-C M and F-OCapi M .

JADT 2014 : 12 es Journées internationales d'Analyse statistique des Données Textuelles

Finally, WebR was applied to re-rank the best list of candidate terms to move "true" biomedical terms towards the top of list and thus to improve the P@k. The evaluation shows that WebR applied after F-OCapi M got the best precision for the extraction of French term.

The fact that we found false positive means that the term is not found in the validation data set. Then, we proposed a manual validation, for which the new precision results are very good and encouraging to use in terminology enrichment scenarios.

For our future evaluations, we will enrich our dictionaries with BioPortal's5 terms for English and CISMeF's6 terms for French. Our next task will be the extraction of relations between these new terms and already known terms, to help in ontology population. In addition, we are currently implementing a web application that implements these measures for the community.

Our work shows a comparison with some measures used in the literature, one of our objectives is to compare our work with a large number of measures on ATR for all domains and ATR applied to biomedicine in order to position our methodology regarding the others.

Figure 1 :

 1 Figure 1: Workflow Methodology for Biomedical Term Extraction.

Table 1 :

 1 Differences between ATR and AKE.

	Keyword
	Extraction

Table 2 :

 2

		English	French
	1	ProperNoun	Noun
	2	Noun	Noun Adj
	3	ProperNoun ProperNoun	Noun Prep Noun
	4	Noun Noun	Noun Adj Adj
	5	Adj Noun	Noun Prep:det Noun
	6	Noun Noun ProperNoun	Noun Prep ProperNoun
	7	Adj ProperNoun ProperNoun	Noun ProperNoun
	8	Noun ProperNoun ProperNoun	Noun Noun
	9	Noun Noun Prep Noun	Noun Prep Noun Adj
	Table 2: 9 most frequent syntactic structures of biomedical terms.

Table 4 :

 4 Ranking of terms based on different measures.

	M	C-TFIDF S	C-Okapi S

Table 6 :

 6 Precision comparison between F-OCapi M and WebR with automatic validation.

.67% WebR (Yahoo) 100.00% 98.33% 97.78% 97.50% 95.56% 91.67%

	French	-!	100.00% 98.33% 95.56%	95.83%	95.00% 91

Table 7 :

 7 Precision of F-TFIDF-C M for English and F-OCapi

M , WebR for French with manual validation.

JADT 2014 : 12 es Journées internationales d'Analyse statistique des Données Textuelles

http://www.nlm.nih.gov/research/umls

http://mesh.inserm.fr/mesh/

http://www.cis.uni-muenchen.de/~schmid/tools/TreeTagger/

http://labtestsonline.org/

http://bioportal.bioontology.org/

http://www.chu-rouen.fr/cismef/

Acknowledgments

This work was supported in part by the French National Research Agency under JCJC program, grant ANR-12-JS02-01001, as well as by University Montpellier 2, CNRS and the FINCyT program, Peru.