Dr Shian-Hua Lin
email: shlin@ncnu.edu.tw

Cheng-Yu Lu

Jen-Chang Liu

; Samuel

Jen-Shin Hong

Samuel Cruz-Lara

Automatic Event-Level Textual Emotion Sensing Using Mutual Action Histogram between

Keywords: emotion sensing, web text mining, semantic role labeling, affect recognition emotion sensing, web text mining, semantic role labeling, affect recognition

Automatic emotion sensing in textual data is crucial for the development of intelligent interfaces in many interactive computer applications. This paper describes a high-precision, knowledgebase-independent approach for automatic emotion sensing for the subjects of events embedded within sentences. The proposed approach is based on the probability distribution of common mutual actions between the subject and the object of an event. We have incorporated web-based text mining and semantic role labeling techniques, together with a number of reference entity pairs and hand-crafted emotion generation rules to realize an event emotion detection system. The evaluation outcome reveals a satisfactory result with about 85% accuracy for detecting the positive, negative and neutral emotions.

Emotion sensing from textual data

Research on interface agents shows that a system's capacity for emotional interactions can makes the agents valuable [Bates 1994]. Aiming at enabling computers to express and to recognize emotions, emerging technological advances are inspiring the field of research on "affective computing" [Picard 1997]. Since many computer user interfaces today are textually-based, the automatic emotion recognition from textual data plays an important role in the design of intelligent user interfaces that are more natural and user-friendly.

In the past, many studies have been conducted to automatically detect a user's affective states from textual data. Some using "keyword-spotting" techniques [Elliott 1992], but the results are not satisfactory. Keyword-spotting approach apparently can't apply to sentences without clearly-defined affective keywords. A number of studies applied emotion theories to determine emotions of interactive agents in intelligent systems [Dyer 1987;Bartneck 2002]. In those approaches a variety of hand-crafted emotion models based on psychological theories (particularly those of [START_REF] Ortony | The cognitive structure of emotions[END_REF]) were employed to specify how interactive events, agents and objects are appraised according to individual's goals, standards and attitudes. At this stage, emotion sensing based on an emotion theory, is Manuscript Click here to view linked References only applicable in interactive systems where the interactive events can be precisely defined, enumerated and automatically detected. Because of the thorough nature of this approach, its application in free-texts requires a detailed understanding and analysis of the text which is rather beyond the reach of current natural language processing techniques. [Liu et al. 2003] reported an approach to detect sentence-level emotion based on a large-scale common sense knowledgebase, ConceptNet. The approach uses real world knowledge about the inherent affective nature of everyday situations (such as "getting into a car accident") to classify sentences into basic emotion categories. In the initial stage, concepts in the ConceptNet with clearly defined affective keywords were automatically annotated with desired basic emotion categories. Then the emotion for other concepts with semantic relationships to the affectively annotated concepts are assigned automatically based on certain emotion propagation models. The accuracy of such emotion propagation process has not yet been investigated. In our opinion, the restricted coverage of the concepts and relationships in ConceptNet seriously limits the use of such approach in real life applications. [START_REF] Shaikh | [END_REF]] recently developed a linguistic tool "SenseNet" to detect polarity values of word, phrase, and sentence-level textual data. The approach uses WordNet [Fellbaum 1998] as a linguistic corpus. Polarity values for adjectives and adverbs in WordNet were manually annotated. The polarity of a verb is calculated via some hand-crafted equations that count positive and negative senses from the definitions in WordNet. The polarity of a noun is assigned based on the related verbs obtained from relationships recorded in ConceptNet. For instance, "ticket" is connected to the following verbs "allow", "access", "get", "provide", and "represent" in ConceptNet. Thus the polarity of "ticket" is assigned as the average value of these verbs. One major problem is that since the data in ConceptNet contains many misspelled words, false concepts, and overly-specific data [Smith and Thomas 2004], the correctness of polarity value of many concepts in SenseNet is questionable.

Moreover, SenseNet can only handle concepts existing in WordNet, so the concepts not included in WordNet cannot be processed.

[ Wu et al. 2006] recently proposed a novel approach for sentence-level emotion detection based on the semantic labels (SLs) and attributes (ATTs) of entities of a sentence. To distinguish the emotions "happy" and "unhappy", the SLs are manually classified into three categories, Active SLs (e.g. obtain, reach, lost, hinder), Negative SLs (e.g. no, never), and Transitive SLs (e.g. finally, but, fortunately). ATTs of an entity are automatically obtained by using WordNet as the lexical resource. For example, in the sentence "I lost my money", the emotion would be unhappy due to the verb "lost" (an Active SL) and the attributes of "money" (such as wealth and property). Wu carried out his work in two phases, training phase and testing phase. In the training phase, a collection of sentences tagged with corresponding emotion states are used as the training set. The SLs and ATTs of these sentences are automatically extracted and then processed to obtain a variety of emotion associate rules (EARs) that associate a particular emotion states with patterns of the SLs and ATTs. In the testing phase, a target sentence is processed in the same manner to obtain its SLs and ATTs before feeding into an emotion classifier. The emotion of the target sentence is assigned based on the similarity comparison of the SLs and ATTs to the sets in the EARs. An evaluation was conducted by using a small-scale corpus of a collection of college students' daily conversations.

Consequently, the major issues of emotion sensing that might limit the performance and applicability of this approach in wider contexts include: (1) the need of affective-annotated sentences as training samples, and (2) the use of attributes (ATTs) as the sentence-level emotion-invoking ingredients. First, the proposed approach requires a sufficient large number of emotion-annotated sentences that are not frequently available promptly within other domains. Furthermore, in many real life situations, the "emotion-invoking" factors of an event may not always be possible to be explicitly represented by the attributes (ATTs) of the event participants.

Emotions determined only with the attributes recorded in WordNet may often cause erroneous results. For example, although a "rat" and a "squirrel" have quite a number of similar or even identical attributes, rodent and mammal, as annotated in WordNet, emotions evoked by both entities (the rat and the squirrel) are totally different. Even worse, in real-life applications, event participants in a sentence often cover a wide-spectrum of modern or domain-specific terms which may not be included in formal lexical resources such as WordNet. For the example "Wii", the newest home video game console released by Nintendo, which could often be mentioned in daily conversations or news articles these days, is unfortunately not yet included in the current version of WordNet. It is essential for a really universal and robust emotion detection system to handle these situations.

As a first step for our endeavor towards a robust emotion sensing engine from free-texts using web mining approaches, this study proposes a novel approach for detecting emotion of an individual "event" embedded in English sentences such as "a student failed in the examination", "a girl saw a diamond", "a cat was chased by a dog", "a mouse encountered a cat", etc. We adopt the "common mutual actions" between the event participants as the major cue to determine the event-level emotions.

In a real-life application when the emotions for free-text sentences are to be detected automatically, the subject, verb, and object of an event embedded in a free-text sentence can be obtained using Semantic Role Labeling (SRL) techniques. A general overview of the state-of-the-art SRL techniques has been discussed fully in [Gildea and Jurafsky 2002;[START_REF] Pradhan | [END_REF]Carreras and Marquez 2005]. Simply speaking, in any sentence, a verb (predicate) dominates an event. The syntactic arguments of a verb are usually associated with the participants of the event. A "semantic role" is the relationship of a syntactic argument with the verb. One commonly used scheme for specifying semantic roles is PropBank annotation [Dang and Palmer 2005;Punyakanok et al. 2004;[START_REF] Punyakanok | [END_REF]]. In PropBank annotations, the arguments of a verb are labeled sequentially from ARG0 to ARG5, where ARG0 is usually the subject of a transitive verb; ARG1 is a direct object, etc. A variety of adjunctive arguments, such as ARGM-LOC for locatives, and ARGM-TMP for temporal information, are also tagged. As an illustrative example, the set of semantic roles for the sentence, "I saw a girl in the park this morning" based on the PropBank style markup, can be presented as:

[ARG0 I] [Target saw] [ARG1 a girl] [ARGM-LOC in the park] [ARGM-TMP this morning]
SRL techniques can be applied to automatically identify the semantic roles of a sentence. However, automatically tagging the semantic roles with high precision is difficult since an event can often be referred to, by a variety of lexical items with different syntactic realizations. In the literature survey, a number of studies have proposed different methodologies for this purpose, such as [Gildea and Jurafsky 2002;[START_REF] Pradhan | [END_REF][START_REF] Koomen | [END_REF]]. These methodologies have yielded quite accurate results with about 80% precision on ARG0, ARG1, and 70% on ARGM-LOC, ARGM-TMP [Carreras and Marquez 2005;[START_REF] Pradhan | [END_REF]]. Given the reasonable accuracy of current state-of-the-art SRL techniques, the automatically parsing of subject, object, and verb in a free-text sentence for the emotion-sensing applications is satisfactory.

In the following sections, the underlying principles of our approach will be elaborated.

Emotion sensing based on Mutual Action Histograms (MAHs)

This section describes the underlying principles and detail processes of our methodology for automatically sensing emotions of events embedded in textual sentences. We first present here a typical scenario to illustrate the steps to achieve our goal. In any English sentence, the verb of a sentence typically indicates a particular "action" performed by one event participant to the other participant. For example, in the sentence "The girl saw a viper snake", the action is a "sighting action" with two entities: "the girl" as the subject and "a viper snake" as the object. While we often intuitively assume that the girl would often be terrified while meeting a viper snake, but how can a computer understand this?

Let us investigate why a girl would usually be terrified when she sees a viper snake.

One way to reason is that the snake "usually" performs certain undesirable actions (e.g. bite, paralyze, attack, or kill) but "seldom" performs desirable actions (e.g. love, feed, or supply) on a girl. Contrarily, a baby would usually be happy to see his/her mother since his/her mother "usually" perform desirable actions on the baby. The real-life probability distribution of such "mutual actions" between a subject and an object is termed as the "Mutual Action Histogram (MAH)" in this paper. In practice, knowing the MAH between the subject and the object in a specific event would allow a computer to reasonably guess the emotion invoked. For example, if the MAH between a vampire and a girl is close to that between a snake and a girl, the emotion of a girl when she saw a vampire should most likely similar to that of a girl when she saw a snake. As compared to the relevant work by [Wu et al. 2006], our approach adopts the mutual actions between the event participants instead of using their attributes as the features to determine the emotions. Based on the above analysis, it appears that the success of our approach for emotion detection would hinge on the ability of a computer to automatically retrieve the MAHs between two entities that participate in an event. While people may intuitively believe that MAHs between entities are difficult or impossible to obtain without extensive human annotations, we resort to web-based text mining that fortunately provide a convenient solution to achieve our goal. We introduce the overall flow diagram for our proposed emotion detection engine, as shown in Figure 1 the MAHs to that of the TE-Pair. In the following, the underlying principles and detail operations of the proposed framework will be elaborated.

Web-based text mining for MAHs between entities

We apply web-based text mining techniques to retrieve mutual actions between two given entities. In the past, studies based on variations of text mining approaches have been investigated to retrieve different types of knowledge (e.g. [Gildea et al. 2006;[START_REF] Etzioni | [END_REF][START_REF] Girju | [END_REF]). Given the vast amount of textual data available on the Web, we believe that the actions of two given entities described in web pages shall give a roughly normalized distribution of their common interactions.

In the text mining approach, given a target event with two entities (the subject and target objects), the system analyzes the mutual actions between both entities by collecting large amount of emotion-invoking sentences from the Web. Therefore, hand-crafted "lexico-syntactic patterns" are generated and submitted to search engines for accumulating sentences from web pages within the search results. We borrow the glossary "lexico-syntactic patterns (LSPs)" from [START_REF] Hearst | Automatic Acquisition of Hyponyms from Large Text Corpora[END_REF]], in which a LSP indicates a particular semantic relationship between two entities.

In this paper, a set of effective lexico-syntactic patterns are formulated to describe emotion-invoking sentences. These sentences can be written either in "passive" or "active" style and the subject/target entities can be put in active/passive roles.

Consequently, given an Event (E1, A, E2), with an action A and two entities E1 and E2, four different styles of LSP sentences are automatically generated as followings: Ÿ S1 (E1-Active-E2): (e.g., "She saw a snake.") Ÿ S2 (E2-Passive-E1): (e.g., "The snake was killed by her.") Ÿ S3 (E2-Active-E1): (e.g., "A snake bites her.") Ÿ S4 (E1-Passive-E2): (e.g., "She was bitten by a snake.")

The following examples illustrate the process for obtaining the mutual actions between two given entities. Considering an attempt to retrieve sentences that describe the mutual actions between "female" and "snake", typically intuitive syntactic patterns can be applied to formulate following web queries: Ÿ S1: "she * a snake", Ÿ S2: "snake was * by her", Ÿ S3: "snakes * her", and Ÿ S4: "she was * by the snake".

In case there are insufficient collected sentences by using these primitive patterns, it is possible to extend the patterns by considering variations of the verb tenses (e.g.

"she was * by the snake" in S4), plural forms (e.g. "snakes were * by her" in S2), and articles (e.g. "she * the snake"). With these query strings, we typically accumulate a large number of raw sentences from the snippets of web search results. To effectively and efficiently compare the MAHs among entities pairs, the collected action verbs will be categorized and normalized for estimating the MAHs of each writing styles respectively.

Verb categorization

In practice, the matching for the MAHs between the TE-Pair and RE-Pair are based on a coarse-grained verb categorization. We collected about 800 popular verbs from Yahoo! Online Dictionary 1 . Given an entity pair of an event, semantically similar verbs typically invoke a similar emotion to the subject. Thus, these collected verbs are first categorized into 87 groups of synonyms (refer to Appendix 1). Within these verb groups, we manually determine whether a given verb group is "emotion-invoking" or not. If a verb of a given event often causes a certain emotion to the subject or object, it is considered as emotion-invoking. For example, if E1 frequently "attacks" E2, it is naturally that E1 is an unpleasant object to E2 and thus "attack" is considered as an emotion-invoking verb. These emotion-invoking verbs are used as the main features to predict the emotion of the subject or object of an event. Based on this principle, 30 emotion-invoking verb groups are manually selected by experts, including abandon, abduct, accept, astonish, attach, attack, avenge, award, blame, bite, bother, challenge, compete, eat, encourage, entertain, espouse, finish, force, gain, hate, kill, lie, move, pollute, purchase, save, want and warn. Verbs other than those identified as emotion-invoking verbs are grouped as "neutral" verbs. Consequently, experts manually assign 800 verbs into 31 verb groups. (she, perfume). Notably, a female frequently "loves" perfume (S3) but is frequently "attacked" by a tiger (S4). Overall, both cases have significantly different histograms.

Following research issue is finding the best matching between the MAHs of a TE-Pair with the RE-pairs so that the query emotion can be predicted by applying the best matching on MAHs.

Reference Entity Pairs (RE-Pairs) with Emotion Generation Rules (EGRs)

We select a number of RE-Pairs appearing in daily emotional events and manually assign emotions to those events to form a set of EGRs. The MAHs between RE-Pairs are obtained by using the web-based text mining approach described above.

Obviously, the interaction between two entities of a RE-Pair is widely described in web pages so that the MAH would reliably represent the un-biased distribution of mutual actions between them. To widely cover different emotion-invoking scenarios, the RE-Pair set needs to take care of all the emotion categories for the training performance. Also, all actions defined in the verb groups should be considered.

However, given a RE-Pair, only few actions are used to describe the events of the RE-Pair. That is many actions are zero-frequency in the RE-Pair's MAHs as we can see in Figure 2. Consequently for each RE-Pair, a set of EGRs are manually constructed for all verb groups, in which zero-frequency verbs are labeled as "N/A".

Appendix 2 gives a list of EGRs for an example RE-Pair, "she" and "diamond ring".

Rule 1 says that the emotion of a female when she "abandons" a diamond ring is typically unhappy. Rule 4 says a female is typically happy when she "accepts" a diamond ring.

Matching MAHs among RE-Pairs

In the emotion recognition stage, the emotion of the subject in a target event is assigned based on the similarity comparison between the MAHs of the TE-Pair (i.e.

the event participants) with those of the RE-Pairs. The emotion of the subject in a target event is based on the RE-Pairs with the most similar MAH to that of the TE-Pair. For instance, given the target event, "a girl meets a wolf", the MAH that a wolf frequently acts on a girl is similar to that of the RE-Pair, "female" and "snake".

The emotion of the girl is inferred as "unhappy" according to the "meet" EGRs of the RE-Pair, "female" and "snake."

Conventionally, comparisons of histograms can be achieved by using "Mean Square Error (MSE)" or "KL divergence" algorithms [START_REF] Kullback | [END_REF].

We applied the MSE approach in this study since it is more computational efficient.

Let the 4-style 31-verb histograms of a TE-Pair be {:1...124},

Ti

Hti == and the 4-tyle histograms of a RE-Pair be {:1...124}

Ri

Hri == . The L 1 distance is adopted to compute the dissimilarity between the 4-style histograms of the TE-Pair and the 4-style histograms of the RE-Pairs. L 1 distance has been used to compare histograms in many applications, such as image retrieval [Rubner et al. 2000]. The L 1 distance between two histograms is defined as:

1 ( , )

L T R i i i d H H t r = - ∑ .
The RE-Pair with the minimum L 1 distance to the TE-Pair is considered to have the most similar relationship between entities as the target event. For example, the entity pair (she, purse) is matched to (she, diamond) with minimum L 1 distance. It is apparent that two entity pairs have a similar emotion relationship, while (she, purse)

and (she, snake) have a larger distance in the entity-relationship space. After matching the target pair to one RE-pair, the emotion of the subject in a target event is inferred from the EGRs of the matched RE-Pair.

Evaluations

To evaluate the performance of the proposed methodology we have conducted the following evaluation experiments. First, a number of entity pairs, covering "pleasant", "unpleasant", and "neutral" objects, are selected as RE-Pairs. MAHs of RE-Pairs are automatically measured based on the web text mining approach that analyzes sentences from large amount of web pages. Then, three researchers label each sentence with one of three emotional categories: "positive (happy)", "negative (unhappy)", and "neutral". These data form the training set of the system.

The testing data are also collected from sentences that describe daily events. These testing data are labeled by the manpower different from the training data to reserve the objectivity of evaluation. Details of training, testing, evaluation and observation processes are illustrated in the following sections.

The Training Phase

In the training phase, the subject "she" and following objects touched in the daily life are selected to form 11 RE-Pairs.

Ÿ Pleasant objects: diamond ring, purse, new dress, prince;

Ÿ Unpleasant objects: tiger, thief, spider, bug;

Ÿ Neutral objects: table, tissue, book.

For each RE-Pair, the web text mining processes of generating the MAHs (124-dimensions: four styles of 31 verb groups) and emotion generation rules (EGRs) of the RE-Pair are summarize as followings:

Ÿ The general web crawler collects emotion-invoking web pages by submitting queries (e.g. "she * diamond ring") to search engines and following links within search results to crawl more pages, as described in section 2.1.

Ÿ According to these collected web pages, each sentence is extracted and parsed by the SRL tool to identify the objects and verbs of the event. We use the publicly available SRL tool, ASSERT [START_REF] Pradhan | [END_REF], to perform the task. Although only the query "she * diamond ring" was issued to the search engine, more RE-Pairs are also collected after the SRL parsing process. For example, other emotion-invoking sentences with subject "she" and verb group "buy" contain objects, such as "chicken nuggets", "i-pod", "ps2", etc. These novel objects will be considered as testing objects in the testing phase.

Ÿ Based on the RE-Pair (e.g. she and diamond ring) and 31 verb groups, the statistical information is used to generate the MAH of the RE-Pair as shown in the aforementioned Figure 2.

Ÿ Then, the emotions of events corresponding to the RE-Pair and 31 verb groups are manually labeled as: happy, unhappy, neutral, or N/A, as shown in Appendix 2.

The RE-Pair and one verb group determine the emotion of the event forms the emotion generation rule (EGR). For example, the RE-Pair (she, diamond ring)

with EGRs corresponding to "actions" was manually labeled as shown in Appendix 2. The rule 1 presents the knowledge: ( she, diamond ring) AND "abandon" imply the "unhappy" emotion. The rule 4 indicates: (she, diamond ring)

AND "accept" imply "happy". The rule 2 is labeled as "N/A" since people seldom describe (she, diamond ring) AND "abduct" in the same event. Each EGR is determined based on an agreement reached by three researchers.

Consequently, the EGR set consists of 341 rules associated to the emotions of all events generated from 11 RE-Pairs and 31 verb groups.

The Testing Phase

In the testing phase (or predicting phase), using "she" as the subject, various objects and verbs (actions) that a female widely encounters in her daily life are selected to be TE-Pairs (roughly 120 or so). By randomly combining verbs with the TE-Pairs, we efficiently generated thousands sentences as candidate events of the testing set. For example, sentences about daily life, such as "she saw a car accident", "she plays a

Wii", "she buys a hamburger", etc. are automatically generated as events in this way.

Obviously, the authors have manually precluded various unreasonable events (e.g.

"she drinks a computer") for the experiment. Consequently, 600 sentences with equal-distribution on three emotion categories (roughly labeled by the authors) are employed in the evaluation experiment, as shown in Table 1. To objectively evaluate the testing result, the testing events are labeled by the manpower different from that of the training set. We recruit 10 graduate students (mostly graduate students majoring in computer science) to assess these 600 events.

Every assessor is requested to judge the emotion for each of the six hundred events as one of the "Positive", "Negative", and "Neutral" emotions. The ground-truth emotion of an event is determined by the majority voting from the answers of assessors.

Among the 600 events, 529 events receive more than 5 consistent votes (the half of votes) among the 10 assessors, in which the 529 events include 184/175/170 positive/negative/neutral sentences. Human assessors do not reach consistent emotion judgments on many events, such as "she changes her dress" and "she rides a bicycle".

Only 161 events receive more than 9 consistent votes among the 10 assessors. This implies that there is a certain degree of inconsistency (uncertainty) in the emotional evaluations.

The testing set is shown in Appendix 3. The web mining system automatically generates lexico-syntactic patterns based on the subject "she" with those objects and verbs listed in Appendix 3. Then, the same crawling and analyzing processes are applied to these events for measuring MAHs of TE-Pairs. Given the MAH of a TE-Pair, the matching process illustrated in section 2.3 is applied to find the best matched MAH from the RE-Pair set. The EGRs (rule set) of the matched RE-Pair is triggered by the action (verb) of the event, the emotion of the event is therefore predicted based on the emotion category labeled in the fired EGR.

Experiment Results

The performance of the proposed emotion detection system is measured by the precision of correct predictions. Based on the events and emotions labeled in section 3.2, the ground-truth testing sets are dynamically determined based on the threshold of majority votes reached by assessors. Accordingly, the precision rate is defined as:

# of correctly answered events by system . # of events with the majority vote precision n = >

The evaluation results are shown in Table 2. For the case with the threshold of majority vote (n > 5), the precision rate is about 77.5%. As the threshold n increases, the precision rate also increases accordingly. The highest precision rate 90.0% is achieved at n = 9. This indicates that the system is able to correctly predict emotions of events that human assessors tend to have consistent opinions on those emotions. In general, the system achieves a high precision rate 85% by averaging all cases of majority votes (n = 5 -9).

Observations

Based on the web text mining approach, many events with novel object nouns are correctly predicted. For example, tested sentences with the lexical-syntactic pattern "she bought a * yesterday" are correctly predicted for novel objects, such as "Wii", "i-Phone", "i-Pod", "PS2", "Mercedes S600", "Rolex", etc. Those novel nouns are usually found in daily conversations but absent in the dictionary or the common sense knowledgebase so that emotions of sentences contain novel nouns are hard to be identified by knowledge-based approaches. Consequently, the web text mining method is adaptive to the rapidly changed web environment.

In previous emotion-detection systems, some wrong predictions are raised from modifiers (e.g. adjective "luxury" or adverb adjective "pretty good") that are often used to modify noun phrases of TE-Pair objects within general sentences. Apparently, the modifier may change the meaning of a noun phrase so that the emotion of the sentence is also influenced. For instance, two opposite sentences "she bought a nice car" and "she bought a broken car" are decorated with opposite modifiers "nice" and "broken", respectively. Therefore, for the same object "car" and verb "buy", both sentences are labeled with positive and negative emotions, respectively. The advantage of the proposed methodology is that a modifier to the noun phrase can be completely identified as an object so that "nice car" or "broken car" are individually processed by the web mining approach and are correctly matched with MAHs of RE-Pairs. For example, the S1 template of the TE-Pair (she, nice car) shows female usually loves/purchases a nice car and dominates the matching process toward to the RE-Pair (she, purse). Similarly, the TE-Pair (she, broken car) is matched with the RE-Pair (she, thief) since the S1 template of (she, broken car) presents female usually abandons/dislikes a broken car as that of (she, thief).

According to the experiment results, the highest precision rate is 90.0% with the threshold of majority vote 9, i.e. 90% assessors have the same emotion judgment. In this test, there are 11, 4 and 1 sentences mismatched with manually labeled emotion categories of "positive", "negative" and "neutral", respectively. Some of the incorrectly predicted sentences are depicted below and observations of these error predictions are also discussed for seeking further improvements.

The problems of wrong predictions result largely from the polysemy entities that have multiple senses corresponding to different emotion interpretations. For instance, the TE-Pairs (she, jaguar) and (she, giant) do not match with the correct (or relevant) RE-Pairs, because "jaguar" and "giant" are usually regarded as the famous brands that produce vehicles and bikes, respectively. So assessors labeled both entities as "Happy". However, "jaguar" is a panther and often performs several unpleasant actions (e.g. attack, kill, etc.). After analyzing from web pages, MAHs of both TE-Pairs tend to clarify general meanings so that the system inferred the "negative" emotion of "she meets a jaguar" from that of "she meets a tiger".

As for the semantic problem about the subject "she", females generally have positive feeling to objects "chocolate", "rabbit" and "puppy"; assessors therefore tend to label sentences with TE-Pairs (she, chocolate), (she, rabbit), and (she, puppy) as positive emotions. However, S4 templates of the MAHs show that females are usually bitten and attacked by those objects. S1 and S2 templates represent that females do not often perform "love", "purchase" and other "pleasant" actions on those objects.

Therefore, these TE-Pairs tend to match with "negative" RE-Pairs and result in wrong predictions.

Context-sensitive problems vs. Emotion sensing

Based on the aforementioned observations, incorrectly predicted sentences are resulted from "polysemy entities" and "semantic problems". Both situations can be concluded as "context-sensitive problems". For example, in many retrieved web pages, extracted sentences contain the polysemy entities "jaguar" and "giant" also frequently contain nearby sentences describing about "animals" and "adventures", respectively.

As for the semantic problem, web page sentences mention "chocolate" are frequently relevant to party or politic events, such as "people are attacked by chocolates" in parties or politic activities. Many web pages also mention that puppies (or rabbit)

probably attack (or bite) people during the playing activities. Therefore, the system collected these kinds of sentences for TE-Pairs (she, chocolate), (she, rabbit), and

(she, puppy) and mined MAHs that are dominated by S4 templates. Consequently, these TE-Pairs are matched with RE-Pairs like (she, tiger) or (she, snake) and are predicted as "negative" emotions.

According to these observations, we conclude that emotions of sentences are context-sensitive. However, the context-sensitive problem is not considered in the tested sentences since each sentence is individually applied without nearby sentences.

Generally speaking, emotion sensing applications should be domain-dependent so that the domain background knowledge facilitates the prediction of emotion. For example, applying the system to chatbot (chat robot) applications will obtain better performance of emotion sensing since previous typed sentences can be use to detect the background domain of the current chitchat, such as "animals", "adventures", or "parties". Therefore, domain-knowledge and the proposed emotion sensing system will be integrated to improve the system performance for various applications in the future.

Conclusions and future works

This paper proposes an event-level textual emotion detecting approach based on the common action distribution between event participants. Based on 11 RE-Pairs associated with 31 verb groups, sentences (parsed by the SRL tool) are collected from web search engines and manually labeled with emotions, Positive, Negative or

Neutral. The web-based text mining approach is applied to collect and analyze large amount of event sentences as training and testing data. No need of any large-scale lexical sources or knowledgebase, the proposed system works well on predicting the emotion of a sentence, even the sentence contains entities or verbs that are absent in the knowledgebase or database. Experiment results indicate that the proposed system achieves a relative high precision about 85% in par with past studies. Also, the system is adaptive to the dynamic Web environment that novel name entities are frequently created in web pages.

As we concluded that the emotion sensing problem is context-sensitive, the future work is toward to applying the system to domain-dependent applications like chatbot.

Based on the current result, improving the system for sensing more complicated sentences or emotions is the future research issue. In [START_REF] Soong | [END_REF], machine learning techniques are applied to handle complicated sentences or paragraphs where many events are often intermingled together. For example, the sentence "I saw a snake chasing a frog" is simple but contains more than one event. Based on the emotion theory [START_REF] Ortony | [END_REF], the emotion of a sentence is influenced by all participants contained in the sentence. As for sensing more complicated emotions, to enhance the usability of the system, the proposed method should be able to precisely sensing more emotional categories, such as big-six emotions [Ekman 1993], including Happy, Sadness, Fear, Anger, Disgust and Surprise. Those emotions are widely used in human-computer interactive applications.

Figure 1 .

 1 Figure 1. Illustrative diagram for the proposed approach.

  below. First, in the training phase, we select a number of entity pairs ( subject-object, e.g. girl-spider, girl-diamond, etc.) as the Reference Entity Pairs (RE-Pairs). For each RE-Pair, the MAH is obtained using web-based text mining techniques. Then for each RE-Pair, possible emotion-invoking events that often occur between the two entities are enumerated and manually assigned with emotions to form a set of "Emotion Generation Rules" (EGRs). In the predicting (or testing) phase (emotion sensing stage), the subject and object of a target event, termed as the Target Entity Pair (TE-Pair), in a sentence is automatically recognized using semantic role labeling techniques. The MAH of the TE-Pair is obtained using web-based text mining techniques to search and extract TE-Pair sentences from search engines. The emotion of the target event is assigned based on the EGRs of the RE-Pairs with best match on

Figure 2 :

 2 Figure 2: Mutual Action Histograms for two entity pairs.

Table 1

 1

	: number of sentences for evaluation
	Emotion Categories	Positive	Negative	Neutral
	# of composed sentences (events)	200	200	200

Table 2 :

 2 Evaluation results of the proposed emotion detection system

	Majority votes (n)	# of Sentences	Positive Negative Neutral	Precision	# of sentences (correct)	Positive (correct)	Negative (correct)	Neutral (correct)
	5	529	184	175	170	77.5%	410	130	146	134
	6	380	141	115	124	81.0%	308	98	102	108
	7	303	103	102	98	87.1%	264	79	92	93
	8	183	54	66	63	88.5%	162	40	61	61
	9	161	46	57	58	90.0%	145	35	53	57

http://tw.dictionary.yahoo.com/

Appendix 1: Synonym groups for the verbs 636 637

Group

Verbs Abandon (cease, discard, terminate, discontinue, stop, halt, escape, restrain, quit, forsake, leave) Abduct (kidnap, hijack) Abound (teem, swarm, flourish, overflow) Accept (allow, permit, admit, recognize, adopt, agree, approve, accede, obey) Access (entry, approach) Addict (affect) Aim (try, intend, attempt, attend, direct, point) Ask (question, inquire, query, interrogate, request, beg, solicit, demand, plead, consult) Astonish (surprise, amaze, astound, shock) Attach (affix, tack, append, adhere) Attack (hurt, beset, hit, cuff, assail, bombard, kick, strike, swat, punch, assault, maul) Avenge (revenge, retaliate, requite, punish, repay, retort) Award (reward, prize, medal, trophy, grant, gift, bestow) Banish (exile, deport, outlaw) Bark (yelp, yip, yap, bay, woof, ululate, bowwow, snap, hoot) Bear (tolerate, yield, endure) Begin (start ,commence) Bite (pierce, nip) Blame (berate , accuse, impeach, reprehend, decry, condemn, denounce, charge, indict) Bother (disturb, annoy, irritate) Challenge (confront, question, dispute, counteract, defy, doubt, dare, suspect, protest, gage, controvert, mistrust, withdraw, struggle) Change (alter, vary, deviate, substitute, replace, modify, convert, shift, switch, transfer, turn, exchange, transform) Clarify (explain, refine, simplify, illuminate, illustrate, expound, specify, purify, define, interpret, unfold) Classify (organize, categorize, sort, catalog, assort, grade, file, rank, collocate) Collect (gather, assemble, accumulate) Compete (contest, rival, contend, fight, strive) Conduct (manage, direct, guide, control, govern, captain, command, instruct, steer) Congratulate (bless, compliment, flatter, commend, praise) Conquer (prevail, overtake, vanquish, defeat, overcome, rout, overpower) Contain (include, hold, comprise, involve, enclose) Cooperate (coact, coordinate, conspire) Compare (correlate, parallel) Create (build, make, manufacture, fabricate, develop, form, compose, shape, devise, invent, originate) Dance (dance, rock, reel, twirl, caper, step, swing, prance, disco, hop, gambol, romp, leap, wiggle, wriggle) Decrease (decline, decelerate, detract, devalue, dilute, weaken, thin, diminish, deduct, deteriorate, demote, degrade, reduce, lower, debase, abase, cheapen, devaluate) Deliver (consign, convey, transport, transmit, send, dispatch, forward, pass) Determine (decide, judge) Devote(devote, consecrate, hallow) Die (decease, perish, expire) Disguise (conceal, hide, camouflage, misrepresent) Ease (facilitate, relieve, help, comfort, relax, loosen, aid, lighten, assuage, allay, release) Eat (dine, chew, swallow, feed, graze, devour, nibble, gobble, gulp) Emphasize (stress, punctuate, accent, mark, intensify, highlight, underscore, accentuate,) Encourage (support, urge, sponsor, promote, cheer, inspire, boost, excite, arouse, awaken, wake, kindle, pique, provoke, actuate, rouse, arise, aspire) Entertain (play, amuse, delight, titillate, tickle, please, show) Espouse (espouse, betroth) Evaluate (valuate, assess, compute, count, account, calculate, gauge, rate, measure, criticize, weigh, reckon, appraise, approximate) Evolve (breed, develop, diffuse, grow,) Examine (inspect, observe, study, review, investigate, scrutinize, diagnose) Expect (anticipate, await, hope) Express (tell, present, describe, allege , announce, declare, acquaint, articulate, aver, inform, mean, signify, connote, perform, talk, assert, pronounce, confide, denote, detail, elaborate, display, show, speak, appear, say, show) Fall (immerse, drop, plunge, swoop, sink) Find (discover, detect, excavate, dredge, dig, unearth, dissect, learn, ascertain, locate) Finish (accomplish, fulfill, complete, consummate, end, terminate, conclude, cease, stop) Force (compel, pressure, compress, confine, bend, constrict, tighten, lessen, press, push, brake, quell, choke, coerce, oblige, motivate, propel) Forget (disregard, overlook, ignore, pretermit, neglect) Frustrate (dampen, dishearten, depress, despair, discourage, dissuade, dismay, thwart) Gain (earn, secure, obtain, acquire, receive, get) Go (run, walk) Greet (welcome, invite) Group (flock, sort, classify, organize, arrange, assemble, cluster, gather) Grow (breed, develop, diffuse, disseminate, grow, evolve, mature, raise) Guarantee (affirm, guarantee, assure, convince, pledge, insure, satisfy, vow, vouch, ensure, promise, attest, certify, depose, testify, confirm, verify, validate,


Didier Hoareau

Yves Mahéo

Propagative Deployment of Hierarchical Components in a Dynamic Network

This paper addresses the distribution and the deployment of hierarchical components on heterogeneous dynamic networks. Such networks may include fixed and mobile resource-constrained devices and are characterized by the volatility of their hosts and connections, which may lead to their fragmentation. We propose a propagative, hierarchically-controlled deployment process for such networks and an ADL extension allowing the specification of this context-aware deployment.

Introduction

The component-based approach becomes widely reckoned to be relevant for developing complex distributed applications and many component models and their associated technologies are now available. Some of the proposed models (e.g. Koala [START_REF] Van Ommering | Koala, a Component Model for Consumer Electronics Product Software[END_REF], Darwin [START_REF] Magee | Specifying Distributed Software Architectures[END_REF] or Sofa [START_REF] Plasil | SOFA/DCUP: Architecture for Component Trading and Dynamic Updating[END_REF]), known as hierarchical models, wake up the interest of software architects. In such models, a component -that is then called a composite componentcan be itself an assembly of components, recursive inclusion ending with primitive components that encapsulate computing code.

Besides, the distributed platforms that are susceptible of being the target of complex distributed applications, have evolved in a few years from homogeneous networks of workstations to networks of heterogeneous hosts that may comprise mobile and resource-constrained devices. Among these platforms, dynamic networks represent common but challenging environments. What we call a dynamic network is a network that is characterised by its heterogeneity (e.g. hosts do not all provide similar hardware and software resources), and its dynamism (e.g. hosts may become unaccessible because of their mobility or their volatility). A major consequence of this dynamism is that the target platform cannot be considered as a fully connected network. It is rather described as a partitioned network, viewed as a collection of independent islands. An island is equivalent to a connected graph of hosts that can communicate together, while no communication is possible between two islands. In addition, the configuration of the islands may change dynamically.

This paper describes a distribution scheme of hierarchical components and its associated deployment process that targets the abovementioned dynamic networks. Because of the very constrained environment in which the application is to be deployed, we can hardly envisage a permanent access to the services offered by the application or an optimal use of the resources. The emphasis is put on finding a distribution scheme and some deployment mechanisms (focusing on the instantiation and the activation phases) that achieve a minimal availability while taking account of the environment.

Distributed Hierarchical Component Model for Dynamic Networks

In order to support network disconnections we propose a distributed hierarchical component model which allows an application to run in a degraded mode, avoiding that the entire application becomes unusable. We introduce the notion of active interface to the component model. Our runtime support detects network disconnections and deactivates some components' interfaces accordingly. The underlying distribution scheme of the model is based on the replication of composite components. This replication allows the interfaces of a composite to be easily accessible on a set of hosts. Only the membrane, that contains architectural information, is replicated, thus reducing consistency maintenance problems. Each primitive component is localized on a single host, which reflects the semantics of the architecture descriptor in which each reference to a component corresponds one (possibly statefull) component. Further details about the distribution and the support of this distributed hierarchical component model can be found in [START_REF] Hoareau | Distribution of a Hierarchical Component in a Non-Connected Environment[END_REF].

Context-Aware Deployment Specification

When considering the deployment of distributed components, the key issue is to build a mapping between the component instances and the hosts of the target platform. This task implies to have some knowledge not only about the identity of the hosts involved in the deployment phase, but about the characteristics of each of them as well. However, at design-time, the designer is unlikely to know where to deploy each component regarding resource availability. This motivates the need to differ this task at runtime. We propose to add a deployment aspect to an existing architecture description language (such as [START_REF]xAcme: Acme Extensions to xArch[END_REF][START_REF] Dashofy | An Infrastructure for the Rapid Development of XML-based Architecture Description Languages[END_REF]).This will allow the description of the resource properties that must be satisfied by a machine for hosting a specific component. We follow the approach of [START_REF] Dearle | A framework for constraint-based deployment and autonomic management of distributed applications[END_REF] to specify the deployment of the hierarchy of components in a constraint-based declarative way (see figure 1). The architecture descriptors of the components are augmented with deployment descriptors in which constraints on the resources required by components and on their possible locations can be specified. It is not mandatory to give explicit names or addresses to target machines: the placement of components are mainly driven by constraints on the resources the target host(s) should satisfy. The choice of the machine that will host a component will be made automatically at runtime (during the deployment).

When the deployment is triggered, all the constraints listed in the deployment descriptor may not be satisfied immediately. The dynamism of the network makes the situation even more difficult as it may occur that the set of hosts that would satisfy globally the deployment constraints are never connected together at the same time, precluding any deployment.

<component name=" DocumentSearch " > <component name=" DocumentFinder " > <deploymentcontext > < l o c a t i o n c o n s t r a i n t > < t a r g e t varname =" x " / > </ l o c a t i o n c o n s t r a i n t > </ deploymentcontext > </ component> <component name=" DocumentBuffer " > <deploymentcontext > <resourceconstraint > <memory f r e e ="200" u n i t ="MB" operator =" min " / > </ resourceconstraint > < l o c a t i o n c o n s t r a i n t > < t a r g e t varname =" y " / > </ l o c a t i o n c o n s t r a i n t > </ deploymentcontext > </ component> <deploymentcontext >

< l o c a t i o n c o n s t r a i n t >

<operator name=" a l l d i f f " > <arg varname =" t h i s . DocumentSearch . x " / > <arg varname =" t h i s . DocumentBuffer . y " / > </ operator </ l o c a t i o n c o n s t r a i n t > <deploymentcontext > </ component>

Propagative Deployment

The deployment process we propose is a propagative one: it allows an application to be activated progressively, that is, part of its provided services can be put at disposal even if some machines that are required for the "not yet" installed components are not available. As soon as these machines become connected (or accessible) or some required resources appear (or become available), the deployment will go along. Thanks to our distributed hierarchical component model and the dynamic activation of interfaces, the application can run in a degraded manner even if some of its parts are not yet started.

The main issue of such a deployment is to ensure the unicity of the component instantiations imposed by the architecture descriptor. Indeed on one hand, since we cannot predict which machines will be connected at any time, we cannot select one to be responsible for the instantiation decisions of the entire application. On the other hand, if we let each machine make an instantiation decision, we cannot guarantee that in two different islands contradictory instantiations may not be performed.

Ensuring consistent instantiations comes down to establishing a distributed consensus across several islands. We use the results of [START_REF] Mostéfaoui | Condition-based consensus solvability: a hierarchy of conditions and efficient protocols[END_REF] where the authors identify conditions for which there exists an asynchronous protocol that solves the consensus problem despite the occurrence of crashes. It is thus possible to elect a machine responsible for the instantiation of a component within an island composed of a majority of machines. When an applicant machine is elected and when an instantiation is made, the deployment descriptor is updated with this information. As in the work described in [START_REF] Quéma | Asynchronous, hierarchical and scalable deployment of component-based applications[END_REF], the scalability of our proposition is ensured by the distributed and hierarchical organisation of the control: each composite component of the hierarchy is represented by a machine.

We propose to alleviate the risk that the consensus algorithm may not terminate (e.g. the number of hosts within an island may not be sufficient) by taking advantage of network changes to make the consensus evolve. We detect network changes (e.g. a machine is newly connected) and possibly react to these changes (e.g. make a newly connected machine participate to the consensus). Moreover, in order to avoid that a machine responsible for a composite component makes instantiation decisions in a non-majority island, a reelection mechanism is triggered after comparing the different versions of the deployment descriptors.

Conclusion

This paper has presented a support for deploying and executing an application built with hierarchical components on an heterogeneous and dynamic network. The main contri-bution of this work is that it attempts to take into account a challenging distributed target platform characterized by the heterogeneity and the volatility of the hosts, volatility that may result in the fragmentation of the network.

The propagative deployment presented in this paper is based on a constraint-based language for the description of the placement of the components according to resource requirements. Our distributed component model has been implemented using Julia, a Java implementation of the Fractal component model [START_REF] Bruneton | An Open Component Model and its Support in Java[END_REF]. The standard Fractal ADL has been extended thanks to the addition of new modules. We use D-Raje [START_REF] Mahéo | A Java Middleware Platform for Resource-Aware Distributed Applications[END_REF], a framework developed in our team, dedicated to the observation of distributed system resources in Java. We can thus detect network changes and exploit them in the deployment process.

The main direction of our future work consists in the extension of our propagative deployment in order to define an autonomic deployment in which decisions about the placement of components could be reconsidered.

Fig. 1 .

 1 Fig. 1. Deployment descriptor


Didier Hoareau
email: didier.hoareau@univ-ubs.fr

Yves Mahéo
email: yves.maheo@univ-ubs.fr

Distribution of a Hierarchical Component in a Non-Connected Environment

Keywords: hierarchical components, distributed components, context-awareness, disconnections, Fractal

This article addresses the utilisation of the componentbased approach for building and executing a distributed application that can offer services over a set of heterogeneous and possibly volatile devices. We propose to rely on a hierarchical component model and present a method for distributing a component that makes the set of its interfaces available everywhere. The runtime system associated with this model allows disconnections of devices to be reflected on the architecture of the component by disabling some of its interfaces while allowing it to perform in a degraded mode.

Introduction

Mobile devices such as PDAs, laptops or mobiles phones are becoming more and more popular. When used together with traditional workstations, they can form new distributed platforms for which new distributed applicative needs emerge. One of the challenges we are faced is to be able to implement distributed applications that take into account the heterogeneous and dynamic characteristics of this kind of equipment. Indeed, designing and deploying applications in this context requires to consider software and hardware specificities of the various devices as well as to support the (more or less important) dynamic characteristics of the runtime environment, which are namely induced by the volatility of the hosts and the connections.

Existing component models [START_REF]Microsoft Windows NT Server white paper[END_REF][START_REF] Monson-Haefel | Enterprise JavaBeans[END_REF][START_REF]Corba components. Adopted Specification formal/02-06-65[END_REF] and more generally the component approach have proved their interest in designing, implementing and maintaining distributed applications. They allow an application to be designed as a set of interconnected components accessible through well defined interfaces, the whole forming a potentially complex architecture. But most of the existing models and their associ-ated middleware support have been designed for business client/server applications targeting traditional networks of workstations. They often rely on rather strong assumptions on the stability of the execution platform (e.g. permanent availability of a server component) and suppose that each of the hosts offers sufficient resources. In general, an application designed this way cannot be installed or execute on networks of potentially volatile hosts with sometimes limited resources. This article addresses the utilisation of the componentbased approach for building and executing an application that should offer services over a set of mobile devices with possibly limited hardware and software resources. The different parts of the application do not necessarily reside on all the hosts but on each of them, the application should be usable. A degraded functioning mode may take place if all the parts of the application are not accessible.

In this perspective, we propose to use a hierarchical component model in which a component can be itself an assembly of components (it is then called a composite component). A common way to distribute a component-based application consists in installing each component instance on a host; the distribution then refers to the fact that a component can make distant invocations to the services implemented by another component. As for us, we propose to take advantage of the hierarchical structure of the component architecture and to allow a composite component to be accessible on several hosts although each of its subcomponents is instantiated on a single machine. In this context, the volatility of the devices and the connections eventually results in temporary failures of some bindings between subcomponents. To avoid that the entire application becomes unusable, the runtime support implements mechanisms that detect these failures and make inactive some of the component's interfaces. The other interfaces remain active so that the component can continue to perform part of its functions. The runtime support we have built provides for introspection on the fact that an interface is active or not, thus allowing the development of applications that can adapt to disconnections.

This article is structured as follows: we first present the hierarchical component model we have adopted and detail how a hierarchical component can be distributed. Secondly, the notion of active interface is taken up and we precise how it is implemented in the support of our hierarchical distributed component model. The next section gives some details on the prototype we have built based on the Fractal model. Finally we conclude by mentioning some related works and the future research directions we envisage.

Towards a distributed hierarchical component

Hierarchical component

In a hierarchical component model, composite components provide a uniform view of an application across different abstraction levels. Hence, a composite component represents a more or less complex structure of interconnected components -described by a configuration stored in an architecture descriptor-and thus can be used as a simple component with well-defined required and provided interfaces. Recursion stops with primitive components that correspond to computing units. Components are interconnected through bindings that represent each a link (local or distant) between a required interface and a provided interface.

The notion of composite component is often used at design time and is found in so-called architecture description languages (ADL) [START_REF] Medvidovic | A Classification and Comparison Framework for Software Architecture Description Languages[END_REF]. In the applicative framework we have chosen, it is however interesting to also be able to manipulate a composite at execution time. Indeed, it eases the provision for dynamic adaptation mechanisms whose aims are to allow subcomponents to be added, withdrawn or replaced, and bindings between components to be redefined. The hierarchical structure is then a means to take into account several abstraction levels at execution time.

When compared with other models of hierarchical components like Darwin [START_REF] Magee | Specifying Distributed Software Architectures[END_REF] or Koala [START_REF] Van Ommering | Koala, a Component Model for Consumer Electronics Product Software[END_REF], Fractal [START_REF] Bruneton | An Open Component Model and its Support in Java[END_REF] offers most of the characteristics we need. We will rely on a subset of this hierarchical component model if the following.

The Fractal model defines a component as being composed of two parts: a membrane (or controller) and a content. The membrane exposes the interfaces (required and provided) of the component and intercepts all the invocations at the interface level. A composite component is defined as a component exposing its content, i.e. a set of subcomponents. To each required and provided interface of a composite corresponds the interface of a subcomponent.

Composition in Fractal is done through bindings between required an provided interfaces and through the presence of components inside a composite. The model is recursive: a composite component can itself appears in the content of a composite component.

The initial configuration of the components is described in an architecture descriptor written in Fractal ADL. Standard features of Fractal ADL allow the user to specify namely the details (name, type, implementation,...) concerning the primitive and composite components and the bindings between components. New modules may be added to this ADL to express other aspects related for example to the architecture (e.g. inheritance, attributes) or to the deployment (such as the placement directives mentioned below).

A number of control interfaces (as opposed to functional interfaces) are provided in order to introspect an reconfigure the internal features of the component, for example to perform the dynamic addition and withdrawal of bindings between components. The user may add new such interfaces to handle specific reflection mechanisms.

Figure 1 shows the architecture of an application composed of a composite component that contains two primitive subcomponents. Two control interfaces are depicted that are responsible of controlling actions respectively on the subcomponents and on the bindings bewteen subcomponents.

Distribution of a hierarchical component

As mentioned in the introduction, we wish to deploy a hierarchy of components on a distributed platform that is characterized namely by its heterogeneity and its volatility. The application components will be distributed on a set of hosts. The placing of the components is performed while taking account of the hardware and software resources available on each host. The way this placement is initially chosen and how it evolves is one of the aspects of our project but is not detailed in this paper. We will focus on describing the mechanisms allowing a distributed execution of hierarchical components.

¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¢ ¡¢
§ ¡ § § ¡ § ¡¡ ¨© ¡© © ¡© ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡
In our approach, the architecture of a component is coupled to its placement and this relationship is dealt with differently for composite components than for primitive components. As far as distribution is concerned, a primitive component executes on one host whereas a composite is possibly physically distributed on a set of different hosts. This mainly allow the services implemented by a composite to be invoked on more than one host.

A single instance corresponds to primitive composite. On the contrary, an instance of composite may be replicated. In a context of dynamicity and therefore as new hosts may appear, the target set of this replication should not be considered as fixed. However, for simplification reasons, we will consider here that it is explicitly defined in the architecture descriptor. In this descriptor, a single host is associated with a primitive component whereas a set of hosts is associated with a composite component. The set of hosts associated with a given composite component must be a subset of the set of hosts associated with the including component. If no set is specified, the placement set is inherited from the including component.

A composite component c is distributed over a set of hosts if it exists on every host of an instance of c.

All the instances of c are created according to the directives found in the architecture descriptor. At execution time, each instance of c maintains locally the configuration of its subcomponents. Hence, a distributed composite component c distributed over respects the following properties:

• The provided and required interfaces of c are accessible on all the hosts m i of . These interfaces are those defined in the architecture descriptor.

• let c be a composite component that contains a single primitive subcomponent p. It exists a single host m i on which p executes. For every host m j ∈ (j = i), it exits c j , an instance of c on m j . Each c j holds a distant reference to p.

Each instance that represents the same composite is locally responsible for the architectural configuration of the composite. Figure 2 carries on with the example of the composite component described in Figure 1. It depicts its distribution on three hosts. If, during execution, host m 1 becomes unaccessible from m 2 and m 3 , component p cannot be referenced any longer. However, for m 2 and m 3 , binding to q is still possible. On m 2 and m 3 , one can still access to the services offered by q through interface b. Indeed, the interfaces of the component are available on each host. Invoking methods on these interfaces still poses problems when the subcomponents are not accessible. Indeed, instantiating the composite on all the hosts makes possible the use of its provided interfaces on each host. However, due to network disconnections, on a given site, an access to a distant primitive component can be interrupted. Consequently, an invocation method in this case is likely to raise some kind of network exception. This problem is not specific to our approach but appears as soon as distant references are used, that may point to unaccessible components at any time. In order to prevent invocations that may not complete because of disconnections, we introduce the notion of active and non active interfaces. We propose to add a control interface to components to allow introspection on the state (active or not) of its provided and required interfaces.

Active Interfaces

The life-cycle of a component is significantly tied to the one of the components it requires: for a component to be activated (i.e. it is safe to invoke any method defined in its interfaces) it must have all its required interfaces bound. As in a dynamical environment disconnections have to be taken into account, this approach can be severely disadvantageous. We may not want a component to be deactivated even if all of its (required) interfaces are not bound. In this case the component still offers a service but in a degraded mode.

Figure 3 shows an assembly of components that points out the two parts of its architecture that are independent. Dependencies between required interfaces and provided interfaces for composite component A are represented by a graph. So, if a primitive component of graph grA becomes unavailable, we can still make safe method invocations on interface a 2 . Interface a 2 is being kept active whereas a 0 and a 1 have to be deactivated to prevent failures of method invocations on these provided interfaces.

Our previous example introduces the notion of active interface. Indeed the activity of an interface represents its state regarding method invocations. An active interface delegates a method invocation to the component owning this interface.

A provided interface is active if it is bound to a provided interface which is also active. A provided interface is active if:

• for a primitive component: all its required interfaces are active;

• for a composite component: the provided interface of the corresponding subcomponent is active.

Inactive interfaces are defined by taking the negative form of the previous clauses. We can notice that the deactivation of only one required interface of a primitive component makes all of its provided interface inactive. This is due to the lack of a priori explicit information to describe dependencies between provided interfaces and required interfaces within a primitive component. To some extent, this problem could be alleviated by declarative features or by code analysis.

Consequently to our characterization of the state of components, the state of a composite component is independent of the one of its required interfaces. It is by the analysis of the hierarchical structure of the architecture that the dependencies are revealed. Indeed, the activation or the deactivation of an interface is propagated through the architecture. In a dynamical environment, disconnections will affect the component structure by inducing breaks of binding. Conversely, the appearance of a component of the architecture (after a disconnection) will result in the creation of some binding(s) and thus the activation of some interface(s).

We can use the hierarchical structure of our model to update the state of the architecture regarding interfaces. When a primitive component activates or deactivates its provided or required interfaces, this information is propagated to the corresponding enclosing composite component. The latter, which has a global view of its sub-architecture (in terms of bindings between subcomponents) is in charge of activating or deactivating the corresponding interfaces of the involved components.

We can also use active interfaces in the reconfiguration of an application by replacing the implementation of a component by an other one. We have to isolate the part of the architecture affected by this modification in order to perform the substitution at runtime. The technique that consists in stopping the composite component which contains the subcomponent to be substituted may be disadvantageous because dependencies between provided and required interfaces are not taken into account. For example, the substitution of component H of Figure 3 requires that the provided interfaces of H (h 0 ) be deactivated. This will gradually cause the deactivation of d 0 (component D) and c 0 (component C). We can thus call methods on interface c 0 which is still active.

Implementation

Extension of the Fractal component model

We have implemented a middleware support for hierarchical distributed components by extending Julia [START_REF] Bruneton | An Open Component Model and its Support in Java[END_REF], a Java implementation of the Fractal component model. Active interfaces have been realized thanks to the addition of a new controller to the primitive and composite components. As mentioned in section 2.1, controllers in the Fractal component model represent non functional operations (functional interfaces are directly bound to the business code of the components). The specification [START_REF] Bruneton | An Open Component Model and its Support in Java[END_REF] defines some control interfaces to manage the bindings between components, subcomponents etc. Our new controller is in charge of maintaining up-to-date the state of the required and provided interfaces. It also allows the activation and the deactivation of any interface of the component. Propagation within the architecture is based on the dependencies between interfaces, which are explicitely declared with the binding clause in the Fractal architecture descriptor.

The controller prevents method invocations on the inactive interfaces of the component. To do so, method reification has been performed by using the interceptor mechanisms of Julia (MetaCodeGenerator). If an interface is inactive, the current strategy consists in stopping the method calls during a parameterizable amount of time and in throw- ing an exception if the interface has not been activated after this time. This default behaviour can be modified, as illustrated in the next section.

The support for managing active and inactive interfaces relies on the mixin mechanisms offered by Julia that allow code insertion in the membrane of the component, according to the aspect oriented programming approach. Thus it is possible to take into account this kind of interface in any application implemented with Julia, independently of our execution platform. The components are then endowed with an API for discovering the state of the interfaces (active or not) and the dependencies between interfaces.

The appearance of components results in an automatic reconfiguration of the bindings between components like in [START_REF] Cervantes | Autonomous Adaptation to Dynamic Availability Using a Service-Oriented Component Model[END_REF]. Due to interception mechanisms, the propagation time for the deactivation of an interface in the hierarchy is linear with the depth of the hierarchy. We have improved the default behaviour of our prototype by adding to each membrane the dependencies between provided and required interfaces. So, when a required interface becomes inactive for a composite component, we can directly exploit the list of the provided interfaces which have to be deactivated. For example, if component I of figure 3 becomes unavailable, interface c 0 is deactivated but instead of propagating this information to component C, we can directly deactivate interface c 1 . Although this optimization is beneficial in complex architectures, we have now to manage methods calls that have not been captured between the moment we deactivate a required interface and its corresponding provided interface.

Context-awareness

Disconnections have been taken into account thanks to D-RAJE (Distributed Resource-Aware Java Environment) [START_REF] Mahéo | A Java Middleware Platform for Resource-Aware Distributed Applications[END_REF], an extensible Java-based middleware developed in our team. D-RAJE makes it possible to model and to monitor resources in a distributed environment. With this middleware, hardware resources (e.g. processor, memory, network interface...) or software resources (process, socket, thread, directory...) can be modeled in an homogeneous way. Like in a previous work on parallel components [START_REF] Mahéo | Middleware Support for the Deployment of Resource-Aware Parallel Java Components on Heterogeneous Distributed Platforms[END_REF], D-RAJE has been extended in order to model components and bindings as resources. It is thus possible to discover the existence of a component, to look for a specific component and to collect information on the state of a component and its interfaces. Information can be obtained by direct observation or by being notified after subscription to interesting events concerning specific components.

When a physical disconnection or a reconnection occurs (i.e. at the network level), the bindings between components as well as the state of the interfaces are modified accordingly. For this purpose, we use the D-RAJE NetworkLink resource that models the physical link between two hosts and maintains information about the state of the network connection. We have added the RemoteBinding resource that models the binding beetween components. Each NetworkLink resource is related to one or more RemoteBinding resources. D-RAJE monitors are created on NetworkLink resources so that the state of the RemoteBinding re- sources are modified when the corresponding network link fails. The event on the change of a RemoteBinding resource is captured with the result that the Fractal binding is withdrawn and the corresponding interfaces are deactivated. Conversely, when a monitor on a NetworkLink resource detects that the network becomes up again, it notifies the RemoteBindings resources. As previously, this results in reestablishing the broken Fractal bindings an activating the corresponding interfaces. In D-RAJE, a naming system gives any resource a unique identity. This allows us to identify each instance of a distributed composite component. So, when a network connection becomes available, our system can discover all the instances of the same composite component and reestablish a binding if needed.

Figure 5 illustrates how we can use our API to manage strategies according to the state of the interfaces. In this example, the programmer decides to wait for the reconnection before invoking a method on an inactive interface.

Related works

Our project is focused on providing facilities to support distributed component-based applications that can adapt themselves. Among other works sharing this goal, few consider the use of a hierarchical distributed component model and the management of disconnections at the same time.

Our approach has some similarities to [START_REF] David | Towards a Framework for Self-Adaptive Component-Based Applications[END_REF][START_REF] Andersen | A Reflective Middleware Platform including Quality of Service Management[END_REF]. These works aims at providing general adaptation mechanisms applied to hierarchical component-based applications. More specifically, in [START_REF] Kouici | Caching Components for Disconnection Management in Mobile Environments[END_REF] adaptation to disconnections is discussed but for the Corba Component Model [START_REF]Corba components. Adopted Specification formal/02-06-65[END_REF] which is a flat component model. In order to guarantee continuity of services, the authors have introduced « disconnected components » whose role are to perform the logging of methods calls and reconciliation when disconnections occur. It is not / / Get t h e s t a t e o f t h e c l i e n t i n t e r f a c e / / named " c l t I t f " i f ( k c o n t r o l l e r . g e t F c I t f S t a t e ( " c l t I t f " ) = = f a l s e ) {

/ / Manual management o f t h e d i s c o n n e c t i o n

RemoteBinding r b = k c o n t r o l l e r . getRemoteB i nd i ng ( " c l i e n t I t f " ) ; w h i l e ( ! r b . g e t S t a t e ( ) ) { / / W a i t i n g f o r t h e i n t e r f a c e a c t i v a t i o n } / / Now we c a n do t h e i n v o c a t i o n c l i e n t I t f . s o m e t h i n g ( ) ; } envisaged that services are maintained (even in a degraded mode) when disconnections occur.

The notion of hierarchical components physically distributed over several hosts is also discussed in [START_REF] Baude | From Distributed Objects to Hierarchical Grid Components[END_REF] where an implementation of the Fractal component model, using the Proactive library, is presented in order to provide Grid components. Although they are not explicitly dealt with, disconnections are taken into account to some extent thanks to the use of Proactive asynchronous communications between components.

The Gravity project [START_REF] Cervantes | Autonomous Adaptation to Dynamic Availability Using a Service-Oriented Component Model[END_REF] is based on a service-oriented component model. In this approach, the bindings between components are considered as dependencies between services (like in the service oriented approach). So, automatic adaptation can be done within a component composition according to the services' availability. The availability of one or more services required by a component results in valid or invalid instances. The current development of the Gravity project does not consider distributed components.

Conclusion

In this paper we have presented the utilization of a hierarchical component model for building and executing an application distributed over a set of heterogeneous and possibly volatile devices. We take advantage of the hierarchical model in the distribution of the components as well as in the management of disconnections.

Our model rely on the Fractal hierarchical component model. We have defined an operating scheme to execute a Fractal composite component that is physically distributed over several machines. In this scheme, the interface of a composite component are available on a set of machines, even if its primitive subcomponents are not replicated, thus allowing for the heterogeneity of the target platform.

The architecture of a composite component is handled in a decentralized way in order to ease the management of network disconnections. These disconnections are reflected on the architecture as widthdrawal of bindings. The Fractal hierarchical component model has been extended with the notion of active interface in order to isolate dependencies between required and provided interfaces. A network disconnection triggers the break of the component bindings on which they rely and consequently the deactivation of the related interfaces. Lastly, interface deactivations are propagated within the component hierarchy. The interfaces that remain active allow a component to perform in a degraded mode. Reconnections are dealt with along the same line, ending up with the activation of some component interfaces.

We have realized a prototype and integrated it into Julia, a Java implementation of the Fractal component model. Our mechanisms in charge of supporting disconnections have been added as a non-functional service into Julia, endowing it with an introspection interface through which one may discover the state of each interface in order to build strategies of adaptation to disconnections.

The work presented in this paper is the first stage of the development of a middleware supporting adaptive components, that is components capable of reconfigure themselves according to changes occurring in their runtime environment.

We plan to integrate adaptation strategies from information on the state of the application architecture at runtime. In particular, our current work focuses on the adaptive aspects of the deployment of a hierarchical component. Indeed such a deployment could be done in a continuous way during the execution of the application according to resources availability.

Figure 1 .

 1 Figure 1. Internal view of a Fractal component.

Figure 2 .

 2 Figure 2. Distribution of a composite component on three hosts.

Figure 3 .

 3 Figure 3. Dependencies between provided and required interfaces within a composite component. Graphs grA and grB emphasize the sub-architecture that can be isolated.

Figure 4 .

 4 Figure 4. Management of remote bindings with resources in D-RAJE.

/

  / O b t a i n a r e f e r e n c e on o u r c o n t r o l l e r C u b i k C o n t r o l l e r k c o n t r o l l e r = ( C u b i k C o n t r o l l e r ) comp . g e t F c I n t e r f a c e ( " c u b i k -c o n t r o l l e r " ) ;

Figure 5 .

 5 Figure 5. Introspection on the state of an interface.

  ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦