A Novel optIcAl GrANulometry AlGorIthm for ore pArtIcles

This paper proposes a novel algorithm to detect the particle size distribution of ores with irregular shapes and dim edges. This optical granulometry algorithm is particularly suitable for blast furnace process control, so its result can be used directly as a reliable basis for control system dynamics optimization. The paper explains the algorithm and its concept, as well as its method, which consists of five steps to detect ore granularity and distribution. A series of comparative experiments under industrial environments proved that this novel algorithm, compared with conventional ones, improves the accuracy of granulometry.

Introduction
During the feeding process of a blast furnace, raw materials should be uniformly distributed in accordance with their granularity, so as to ensure the quality of the process [1,2]. In order to make a blast furnace more effective, granulometry measurements are taken first to obtain a reliable basis for the associated control system dynamics optimization.
Compared with traditional granulometry methods such as an artificial screen, optical methods have more advantages. They are non-contact in operation, which will not disturb the industrial process to make results closer to an actual situation. They can also measure the distribution across the whole surface and are not limited to the part under the screen. Today, more and more optical granulometry algorithms to obtain the granularity of ore particles are being introduced into blast furnace process control.
While taking optical granulometry measurements, a special camera device acquires surface pictures of the ore. Particle size distribution (PSD) [3] should be calculated inside certain zones of the surface, so as to guide the control system to make better decisions, and then adjust the feeding devices to achieve the optimized aim automatically.
It is clear that the optical granulometry algorithm is the key technology for the entire system. Faced with poor illumination and the dusty environment inside a blast furnace, many conventional algorithms may fail to get accurate results. This paper proposes a better algorithm to resolve such problems.

Basic concepts
Optical granulometry is traditionally an image segmentation problem. Commonlyused image segmentation techniques are mainly divided into four categories: thresholding, edge division, clustering and texture analysis [4]. Conventional algorithms using these techniques in other areas are usually applied to simple situations, such as biological or chemistry particles with large contrasts between the background and the regular geometry shapes. Since the ore surface is not a typical scenario with a background and foreground, thresholding is not suitable. All ore particles are of a similar pattern and texture, and clustering and texture analysis cannot be used to separate them. Edge division is the only starting point for doing optical granulometry on ore particles. Figure 1 shows part of a picture taken from an ore surface in the blast furnace during the ore feeding process. From the picture, we can see that, in general, raw materials of the industrial process are irregular shapes. They have thousands of different sizes and shapes, one overlaps another, and the edges of particles are dim and obscure due to a rather thick layer of dust over them and lack of illumination.
Most conventional methods focus on how to retrieve the exact and accurate contour of each particle. These contours are sufficient for calculating the ore particle size. However, due to the above mentioned environmental conditions, satisfactory results are usually not practically available. An alternative approach being considered is to find the actual centroid position of each particle instead of its contour. Since particles usually cluster together, the distances between them can statistically decide the ore PSD. The algorithm in this paper first calculates the centroid position for each particle based on the detected edges, and uses several methods to overcome the wrongly classified fake edges. Delaunay planar division is used to expand the regions occupied by particles, in order to reflect the distances between particles. The "double circle" of each particle region, meaning the smallest circumscribed circle and the largest inscribed circle, is then retrieved. Finally, the radiuses of the two circles based on the shape analysis are used to automatically identify the particle's granularity. The formula for calculating the granularity is as follows: ... (1) where R and r are the radiuses of the smallest circumscribed circle and the largest inscribed circle, respectively. T [.] can be any type of T-norm fuzzy logic operator [5], to make sure that the supremum of granularity does not exceed the diameter of region's smallest circumscribed circle, or d ≤ 2R.

Algorithm steps
The algorithm consists of the following five steps: image pre-processing, morphological smoothing, positioning of particle points, region expansion of particles, double circle granularity detection.

Image pre-processing
The image shown in Figure 1 is first converted from RGB space into HSV space [6], whose three components indicate hue, brightness and saturation. Each component is pre-processed through a Gaussian smoothing filter and histogram equalization, to enhance the image's quality as well as reduce noise. Figure 2 shows the preprocessed result of Figure 1.

morphological smoothing
In order to restore the scattered edges caused by shadows and reflections, further smoothing is used to separate the particles.
Smoothing here does not mean space or frequency domain filters, since they will ruin the edges. Instead, we use the color morphology method as the smooth operator. This method inherits the mathematical basis of the binary and grayscale morphology [7], and can be used to merge image pixels with close hue, brightness or stature. In order to understand the issues, we use the hue component H as an example, described as follows: First, select a morphology structure element B=B(x,y), such as circle of radius 5 pixels, where x and y are the coordinates of the image.
Secondly, use the hue component H=H(x,y), of image at pixel (x,y), and do the grayscale dilate operation defined as: ... (2) Then, use the same B to do the erode operation as: ... (3) D H and D B in formula (2) and (3) are domains of H and B.
Thirdly, combine the dilate and erode operations, and do the open and close operations as follows: Open: ... (4) Close: ... (5) Repeat the open and close operations on the saturation component S and the brightness component V. Merge the above three smoothed components into an HSV image. Then do the inverse conversion from HSV space to RGB space to generate a new image. Figure 3 shows the morphology smoothing result of Figure 2. From the figure, we can see that the color granulation of particles is evident. All particles are segmented into different color blocks, which is helpful for the following edge detection.

positioning of particle points
To identify the exact granularity of particles, we use the improved color space Canny algorithm [8,9] to extract the edges of the smoothed image in Figure 3. The extracted edges are shown in Figure 4 as white lines. It can be seen from Figure 4 that there are still some pixels that are wrongly classified as edge points due to the noise, dust or dim illumination. These fake edge points must be filtered out after edge extraction. To accomplish this, the window projection method can be used.
The window projection method means setting a window with adjustable size to scan the entire image. The window size determines the detectable granularity of particles. It must be larger than the gap size between particles and smaller than the minimum detectable granularity. We can predetermine the window size according to granularity of ore from experience. We scan the entire image and count the number of edge points inside the window using formula (6): ... (6) where, f(x,y) is the extracted binary edge image with edge pixels of value 1 and nonedge pixels of value 0; x and y are the  Fig.2 image's abscissa and ordinate; s is the adjustable window size; m and n are the center of the scanning window; r(m,n) is the count of edge points inside window.
Compare r(m,n) with an adjustable threshold, from experience usually with a strong relationship with the particle surface areas. If the total number of edge points inside a window is less than this threshold, the point at the window center will be considered as a non-edge point. The white regions shown in Figure 4 are made of nonedge points from Figure 3.
On the other hand, we can further determine the actual positions of particles in order to keep track of particle numbers and locations. A particle region may contain more than one non-edge point, such as the simply connected regions shown in Figure 4. We use a binary contour extraction algorithm to divide this binary image into separate simply connected regions. The particle position can be treated as the centroid of each region, as shown in formula (7): ... (7) in which, g(x,y) is the separate binary region image, with the inside pixels of value 1, and the outside pixels of value 0; c x and c y are the calculated coordinates of this region's centroid. In Figure 5, white spots indicate the calculated positions of particles in Figure 1.

region expansion of particles
Using particle positions from the previous step, we expand the regions of particles with the help of planar subdivision. As an example, we use the improved Delaunay-Voronoi algorithm to divide the ore surface plane into regions. The result is shown in Figure 6. The black spots in the figure are the position points of particles from Figure 5.  The gray block around each spot forms the largest expansion region. Points inside each spot's block are nearer to this spot than all the other spots. It is clear that the points on black borders are equidistant with two or more particles.
It should be emphasized that the expansion regions are not identical with the particles' occupied regions, but they still have statistical significance. The region will be used by the double circle algorithm to decide the particle size distribution statistically.
It must be pointed out that the classic Delaunay triangular algorithm [10] is based on discrete grids with theoretical uniqueness and rigor, and can meet the empty-circle criterion. However, it is not easy to introduce new typical lines and is slow when building a large mesh grid. If the point set makes nonconvex regions or contains inner loops, it will generate illegal triangles.
In order to overcome these shortcomings, this paper adopts an improved algorithm to enhance the division efficiency, although this algorithm relaxes the constraint of the empty-circle criterion.

Double circle granularity detection
This final step of shape analysis is divided into three substeps: First, find the smallest circumscribed circle of a particle's expansion region using three contact vertexes. This circle is the smallest circle which contains all the pixels inside the region. In Figure 7, circle O abc is the smallest circumscribed circle of the central region, in which a, b and c are chosen as the appropriate contact vertexes; Secondly, find the largest inscribed circle of this particle's expansion region using three tangent edges. This circle is the largest circle which only contains the pixels inside the region. In Figure 7 inscribed circle and put them into formula (1) to get granularity d.
After the above five steps from 3.1 to 3.5, we may further filter out the fake regions. Exclude some unreasonable regions such as small fake regions due to dust, small gap and noise, or large fake regions due to the barriers, calibrations and reflection.

study cases
To validate the algorithm proposed in this paper, we take pictures of the ore surfaces during feeding process of a blast furnace in a large-scale steel plant. Since we use the optical granulometry as a basis for feeding control system optimization, we divide the surface into eight radial zones from the interior wall to the center of the blast furnace. In order to be consistent with artificial screen mesh size, we set the following classification criteria: d ≤ 15 mm, 15 mm < d ≤ 25 mm, 25 mm < d ≤ 40 mm, 40 mm < d ≤ 55 mm and d > 55 mm, in which d is the diameter size of ores.
We apply the conventional algorithm using the image threshold and edge segment, provided by reference [3]. We also calculate the ore granularity using the novel algorithm proposed in this paper. We calculate the particle size distribution as follows: ... (8) where  ij is the distribution percentage,  ij is the number of class j (j=1,2,...., 5) particles inside zone i (i=1,2,…., 8), and  i is the total number of the five classes of particles inside zone i.

results
We filter the ores through screens and do the artificial statistics. We compare the experimental results of the two algorithms along with the statistics from the artificial screens. The results are shown in Table 1~ 3.

conclusion
This paper proposes an optical granulometry algorithm for irregular ores with dim and obscure edges. According to the above experiments, the concept of double circle ratio has given the algorithm evident superiority and practicality over the conventional ones. Experiments in the largescale steel plant validated and affirmed the fact that it is particularly suitable for feeding process control optimizations of blast furnaces as well as other particle size distribution measurement systems. The idea of region expansion and double circle ratio is also instructive to other optical measurement systems.


extfieldsofstudy: Physics Geography

text:
A media information analysis for implementing effective countermeasure against harmful rumor

When large scale earthquake occurred, the word of "harmful rumor" came to be frequently heard. The harmful rumor means an economic damage which is caused by the action that people regard actually safe foods or areas as dangerous and then abort consumption or sightseeing. In the case of harmful rumor caused by earthquake, especially, tourism industry receives massive economic damage. Currently, harmful rumor which gives substantial economic damage have become serious social issue which must be solved. In this paper, we propose a countermeasure method for harmful rumor on the basis of media trend in order to implement speedy recovery from harmful rumor. Here, we investigate the amount and content of information which is transmitted to the general public by the media when an earthquake occurred. In addition, the media information in three earthquakes is treated as instance. Finally, we discuss an effective countermeasure method for dispeling harmful rumor through these analysis results.

Introduction
Several large earthquakes have occurred in Japan for the past few years, and they have given serious damage to various regions. For example, the 2007 Chuetsu O shore Earthquake is included as the earthquake which is fresh in one's memory.
When large scale earthquake occurred, the word of \harmful rumor" came to befrequently heard. The harmful rumor means an economic damage which is caused by the action that people regard actually safe foods or areas as dangerous and then abort consumption or sightseeing 1]. In the case of earthquake, especially, the harmful rumor often arises in tourism industry. Currently, harmful rumor which gives substantial economic damage to neighboring tourism area which d o e s not have p h ysical damage around disaster-stricken area have become serious social issue which must be solved because harmful rumor gives bad in uence to the revival of disaster-stricken area.
Despite this, the problem of harmful rumor is not supported by the laws or statutes of Japan government 2]. Moreover, academic studies on harmful rumor and its countermeasure are few. Therefore, the people who receives harmful rumor have to carry out the countermeasure through trial and error 3]. For this reason, the establishment of e ective countermeasure for realizing early recovery from harmful rumor is required immediately.
It is obvious that the information transmitted to the general public by the media is included as one of major causes for the occurrence and expansion of harmful rumor. Immediately after the occurence of earthquake, the biased information such as the earthquake magnitude and serious damage condition in disaster-stricken areas is transmitted to the general public. The biased information is reported by v arious media such as newspaper and web all the time. The general public misunderstand that neighboring sightseeing areas which do not actually receive damage have p h ysical damages as serious as the disaster-stricken areas by looking at or hearing the biased coverage.
It is likely that the e ect of countermeasure of harmful rumor depends on the media condition because the occurrence and expansion of harmful rumor relates to the media information. Therefore, the countermeasure for harmful rumor must be performed in consideration of the condition of media information 4]. Namely, su cient e ect of countermeasure may not be obtained even if the countermeasure is conducted in the biased condition that the media transmits only devastating damage aspects. It seems reasonable to suppose that the countermeasure should be performed when the media condition became appropriate condition that the coverage which give bad in uence against sightseeing blows over. However, the studies on the countermeasure for harmful rumor based on the media trend have been not performed.
In this paper, we propose a countermeasure method for harmful rumor on the basis of media trend in order to implement speedy recovery from harmful rumor. In our research, rst, we investigate the amount and contents of information which is transmitted to the general public by the media when an earthquake occurred. Here, we employ newspaper and web news as investigation target. Newspaper has a feature which can transmit the information to the wide range of age, while web news has a feature that the circulation of information is speedy. We also analyze the di erence among two medium which have di erent character. Additionally, we performclassi cation of the information reported by each media. In this classi cation, the information is classi ed on the basis of whether the article gives bad in uence to sightseeing or not. The temporal alterations in these analyses is examined.
These analyses are applied to three earthquake disasters which have recently occurred in Japan. Their earthquakes are \2007 Noto Earthquake", \2007 Niigata Chuetsu O shore Earthquake" and \2008 Iwate-Miyagi Nairiku Earthquake". They were the earthquakes which gave serious physical damage to cities near seismic center. On the other hand, in these earthquakes, the sightseeing areas which are located comparatively near their disaster-stricken areas and do not almost have physical damage received harmful rumor. We reveal the relationship among media information, physical damage and harmful rumor through the analysis of media information in these earthquakes.
Finally, w e discuss an e ective countermeasure method for dispeling harmful rumor through these analysis results.

Outline of Harmful Rumor
When a air, trouble and disaster occurred, the fact is extensively reported by various media. The general public hears and sees the report, and then stop consumption or tourism because they regard the fundamentally safe product or area as dangerous. The word of "Harmful rumor" currently used indicates an economic damage which is caused by such behavior of the general public. Especially, inaccurate reports and exaggerated reports expands harmful rumor, and then the magnitude of damage of harmful rumor becomes huge. However, the report by media does not have all source of harmful rumor. Harmful rumor is also generated by the problem on the side of the receiver of information even if media transmitted accurate information. The trouble of Chinese-made poisoned frozen dumpling which occurred in Japan is included as such example.
A health hazard of foodpoisoning occurred on January 2008 in Chiba prefecture of Japan. After investigation, the poison used for bug killer was detected from Chinese-made frozen meat dumpling which was eaten as a meal. Many patients complaining of food poisoning appeared on various region in Japan after the coverage of this food poisoning. However, there was no patients having a foodpoisoning caused by the poison which is used for the bug killer. Due to this coverage, not only Chinese-made other frozen food did receive harmful rumor, but also Japanese food maker treating frozen food, and the restaurant of Chinese food received economic damage.
In this a air, the report that a Chinese-made frozen meat dumpling is dangerous was transmitted to the general public. Ordinarily, the general public ought to understand that a meat dumpling made by a speci c Chinese food maker is dangerous. However, the general public thought that all Chinese-made food and all meat dumpling which d o e s n o t almost have the relationship is dangerous. Harmful rumor is generated by an extended interpretation by t h e receiver of information even if the media reports detailed information. It is actually impossible to prevent the occurrence of harmful rumor because it is di cult to completely remove the ambiguity from the information and coverage. Therefore, a risk management for harmful rumor is required.

Harmful Rumor by Earthquake
The same may besaid of harmful rumor caused by earthquake. When earthquake happened, each media intensively perform the coverage about the area which received heavy damage. Therefore, it is likely that the general public misunderstands the scale of damage in the area. Namely, the scale of damage is recognized greater than actual situation. Moreover, the general public can guess the rough location of area which received damage. However, it is di cult to accurately guess the range of damage area from contents of coverage. Thus, the general public misunderstands that the damage area is wider than actual damage region. As these results, the general public misunderstand that earthquake g a ve immense damage to wide range.
Harmful rumor by earthquake gives immense economic damage to local economy. Enormous cost is required for the revival of the area which received physical damage. However, in the area which was saved from physical damage, tourism industry receives considerable economic damage. The income from tourism industry is cut o . As these results, the local economy is confused. The vicious circle is generated that the recovery of disaster-stricken area becomes sluggish and harmful rumor extend over a long period of time. However, the study on harmful rumor which is generated by earthquake has been few. Consequently, the countermeasure of harmful rumor has been performed through trial and error. Currently, the establishment of e ective c o u n termeasure for harmful rumor is demanded.

Countermeasure for Harmful Rumor on the basis of Media Trend
It is important to perform the countermeasure which can realize early recovery from harmful rumor because it is di cult to prevent harmful rumor from beinggenerated. Therefore, it is required to perform public relations activities for attracting tourists by providing information to consumers.
The trend of the information transmitted by media should be checked when such countermeasure is performed. Tourists are easily in uenced by the information transmitted by media. Namely, i t i s o b vious that tourists restrain visiting to neighboring area around disasterstricken area while the media transmits biased coverage of disaster related information such a s damage condition. Even if the countermeasure for harmful rumor was performed in the period when the biased coverage is transmitted, enough e ect can not be obtained. Moreover, it is likely that the general public has doubt about the countermeasure activity and the countermeasure has the opposite e ect. As time advances, the number of disaster related information decreases, and the contents of coverage change from the situation of damage to the situation of restoration. It is possible to get enough e ect without the obstruction by disaster related information, if the countermeasure for harmful rumor is put into practice during such period. When the condition of media changed for the better, the enforcement o f c o u n termeasure for harmful rumor which utilize the media is e ective. The appropriate countermeasure using the media in the period which biased condition in media blows over can promote tourism activity of consumer because consumer is easily in uenced by the media.
So far, various countermeasures such as public relations activity on the street have been performed in order to wipe out harmful rumor. However, there were many countermeasures which had no e ect because they were executed while the media extensively transmitted the biased information about the situation of disaster.
Therefore, rstly, it is necessary to grasp the trend of disaster related information transmitted by the media, and then clarify the period which can su ciently obtain the e ect of countermeasure. In addition, the discussion about the contents of e ective countermeasure activity in such period is needed.
In this research, we investigate and analyze the coverage of the media in three earthquakes which r e c e n tly occurred in Japan. In addition, we i n vestigate the relationship between damage situation and media coverage, and grasp the trend of media. The contents and start period of countermeasure is discussed on the basis of the analysis results. From our achievement, the countermeasure based on the media trend can beimplemented, and harmful rumor in the tourism area around disaster-stricken area can be e ectively wiped out in comparison with the case that the countermeasure through trial and error is performed.

2007 Noto Earthquake
The 2007 Noto Earthquake is a massive earthquake which occurred in 25th March, 2007. The Noto is a peninsula which is located on the side of Sea of Japan (See Figure 1). Almost whole area of peninsula belongs to the Ishikawa prefecture. The seismic center is the Sea of Japan near Noto peninsula. On the Richter scale, the magnitude of the earthquake was estimated at 6.9. The earthquake shook the city of Nanao and the town of Anamizu on the Ishikawa prefecture with a seismic intensity of 6 upper in Japan's shindo scale. The earthquake brought d o wn great damage to many cities and towns in the Ishikawa prefecture and the Toyama prefecture which i s neighboring prefecture of Ishikawa prefecture. At least, 1 dead and 279 injured in the Ishikawa and the Toyama prefectures have been reported as human su erings. As physical damage, 649 completely destroyed houses and 26,614 partly destroyed houses have been reported. The lifeline utilities, e.g., electricity, w ater, gas supplies and so on, were destroyed. In addition, all railways in this area stopped. In this earthquake, harmful rumor happened in many tourist resorts in Ishikawa prefecture. For instance, in the Wakura Hot-spring resort in Ishikawa prefecture, there were 66,413 lodging cancelations in hotels during a month from the earthquake occurrence. The Waj i m aCity of Ishikawa prefecture had 15,526 lodging cancelations in hotels. Moreover, the sales related to tourism decreased 20% in Kaga Hot-spring resorts in Ishikawa prefecture which received almost no physical damage and is far from the seismic center. In addition, 23 buildings were completely destroyed and 1,155 buildings were partly destroyed. In this earthquake, massive landslide occurred around the seismic center. Some rivers were dammed by mudslide, and then some landslide dams were generated. There was a fear that secondary disaster happens by the collapse of landslide dams. On the other hand, urban area did not almost receive p h ysical damage because the seismic center was mountain region. Many reservations for tourism were canceled in many cities and tourist resorts in the prefectures around the seismic center although there was almost no damage in urban area. As one misfortune followed another, a big earthquake which was 6 upper on Japan's shindo scale happened after one month. By this earthquake, tourism industry in the region around seismic center received extensive damage by harmful rumor.

Analysis Method
We collected the information related to each earthquake i n t wo kinds of media. One is newspaper and another is online news website (described as web news) which is managed by newspaper publishing company. In each earthquake, we collected the articles related to earthquake from ve newspapers. They are four national newspapers which are Asahi Shinbun, Yomiuri Shinbun, Nihon Keizai Shinbun and Mainichi Shinbun, and a local newspaper which is Hokkaido Shinbun. In the analysis of web news, we used two websites for 2007 Noto Earthquake, three websites for 2007 Niigata Earthquake, and ve w ebsites for the 2008 Iwate Earthquake, respectively. We collected the articles from CHUNICHI Web (http://www.chunichi.co.jp/) and YOMIURI Online (http://www.yomiuri.co.jp/) in the 2007 Noto Earthquake. In the 2007 Niigata Earthquake, we collected the articles related to earthquake from MSN Sankei News (http://sankei.jp.msn.com/), Niigata-Nippo Online (http://www.niigata-nippo.co.jp/) and YOMIURI Online. Finally, i n t h e 2008 Iwate Earthquake, the articles were collected from MSN Sankei, Mainichi JP, KAHOKU ONLINE NETWORK (http://www.kahoku.co.jp/), CHUNICHI Online and YOMIURI Online. YOMIURI Online, MSN Sankei News, Mainichi JP are online news website managed by national newspaper publishing company in Japan, and CHUNICHI Web, Niigata-Nippo Online and KAHOKU ONLINE NETWORK are online news website for local newspaper publishing company. In this collection, we treated the articles including the name of the earthquake a s t h e disaster related information. The period to collect the articles was 50 days from the occurrence of each earthquake.
We i n vestigated the information amount in newspaper and web news. Here, we used the area of articles as the information amount in newspaper. And, we used the numberof articles as the information amount in web news. Moreover, we analyzed the contents of articles collected from both media. In this contents analysis, we classi ed the articles into three categories on the basis of whether it gives avoidance emotion to the general public against sightseeing or not. The articles giving avoidance emotion to the public are classi ed into \-" category. For example, the articles which the situation of damage and the numberof deaths are reported are included in this category. The articles which alleviate avoidance emotion are classi ed into \+" category. This category include the articles about the public relations activity and the advance of revival. Finally, the articles which do not relate to avoidance emotion are classi ed into \0" category. The articles which report the movement of economy and politics related to the occurrence of earthquake are included in this category. Figure 2 indicates the transition of information amount in newspaper for three earthquakes. In this gure, the x-axis means the numberof days after the occurrence of earthquake, and the y-axis means the total size of articles published with ve news papers. As shown in this gure, the information amount in the 2007 Noto Earthquake remarkably decreased during 3 days from the occurrence of earthquake, and the amount did not increase after this. In the case of 2007 Noto Earthquake, property damage happened over wide range, but human su ering was few. It is likely that the amount of coverage decreased becauseof the lack of fresh information. In the case of 2007 Niigata Earthquake, the amount of information increased after one week and after one month of the earthquake occurrence, and the amount did not increase after this. The increase after 48 days is exception because the reason of this increase was caused by tourism public relations advertisement published by government. In this earthquake, the prolonged coverage was performed. We can befairly certain that the prolonged coverage was performed because this earthquake had the characteristic damage, e.g., the accident i n n uclear power plant and the stoppage of car manufacture which give also bad in uence to other area. Finally, in the 2008 Iwate Earthquake, the information amount remarkably increased after one week of the  occurrence. The damage in this earthquake concentrated to narrow area of mountain-ringed region, and the neighboring urban area did not almost receive physical damage. However, human su ering was higher than the 2007 Noto Earthquake, and the rescue operation of the su erers had hard going. The summary of situation of damage was reported after one week of the occurrence. As compared with three results, in the case where the coverage extends over a long periodoftime, it was found that the summary of earthquake disaster was reported. In addition, it was revealed that the continuity of coverage depends on the scale and feature of damage in earthquake. We analyzed the appropriate periodfor performing the countermeasure for harmful rumor from the result of information amount. We regarded as calm state of media the situation that the information amount is adequately low v alue and does not rapidly increase again. From the results, we judged that the appropriate period was one week after the occurrence in the 2007 Noto Earthquake, the period in the 2007 Niigata Earthquake was after one month, and the period in 2008 Iwate Earthquake w as after 10 days, respectively.

Analysis Result
Results of contents analysis in newspaper for three earthquakes are represented in Figure 3, 4 and 5. These gures show the ratio of the information amount i n e a c h category. In Figure 3, the situation of contents of newspapers in the 2007 Noto Earthquake can be divided into three periodson the basis of the ratio on each category. First period is a time between the day of occurence and one week after. Second period is a time between one week and about three weeks after from the occurrence. Final periodis after three weeks from the occurrence. In the rst period, the ratio of \-" category was continuously high, and then the ratios except \+" category had large oscillation in second period. In nal period, the ratios of all categories had large oscillation. As shown in Figure 4, the result of the contents analysis could be also divided into three periods in the 2007 Niigata Earthquake. In the rst period, i.e., until after four weeks of the earthquake occurence, the ratio of \-" category was high, and then the ratio of \0" category came high in second period, i.e., during two weeks after the end of rst period. After this, the ratio of each category had large oscillation. In the 2008 Iwate Earthquake, the result can be divided into the ve periods on the basis of the ratio on each category. The situation that the ratio of \-" was large continued during one week from the occurrence of earthquake. After this, the ratios except \+" had oscillation until after three weeks of the occurrence. The three ratios had oscillation until after four weeks, and then the ratio of \-" increased again. Finally, three ratios had oscillation again from after four weeks half of the occurrence. From these results, we judge calm period of the media information from the contents point o f v i e w . Here, we regarded as the calm period of contents in the disaster related information the situations that the ratio of \-" category is low and the ratio of \+" category emerges. In addition, this calm period is judged with the consideration of continuity of the ratio in each category. As this result, it was revealed that it was three weeks half after in the 2007 Noto Earthquake, six weeks later in the 2007  Figure 10. Summarized result of appropriate period for countermeasure Niigata Earthquake, and four weeks half after in the 2008 Iwate Earthquake, respectively. As the appropriate period for countermeasure of harmful rumor, it is likely that the calm situation of media information needs to be con rmed in both aspects of amount and contents. Therefore, in the analysis results of newspaper, the appropriate period for countermeasure of harmful rumor corresponded with the calm period of contents. Figure 6 shows the transition of information amount i n w eb news. In this gure, the average number of articles per one website is represented. Although three earthquakes happened in the morning, the maximum value of information amount emerged on the day of occurrence in the 2008 Iwate Earthquake, and emerged on the next day of occurrence in other earthquakes. This di erence depends on the time required to con rm whole of damage in earthquake. The 2007 Noto Earthquake and 2007 Niigata Earthquake caused damage over large areas. Therefore, the maximum value emerged on the next day of the occurrence because it took long time to investigate a whole of damage situation. On the other hand, in the 2008 Iwate Earthquake, the con rmation of damage situation was smoothly performed because damage area concentrated to narrow area of the mountain range. Thus, the maximum value was con rmed on the day o f the occurence. Although the trend of information amount in three earthquakes was di erent until two w eeks after the occurence of earthquake, the slow decrease trend could be found in all after this. This means that disaster related information on web news was calm by two weeks. Judging from information amount, the calm period for media information was after two weeks of the occurrence. Figure 7, 8 and 9 indicates the result of contents analysis in web news for three earthquakes. When the calm period of contents in media information is regarded as the situations that the ratio of \-" category is low and the ratio of \+" category emerges, it was found that the period was after three weeks of the occurrence in the 2007 Noto Earthquake. For remaining two earthquakes, it was four weeks later. The appropriate timing for the countermeasure of harmful rumor corresponded with the calm period of content as in the result of newspaper, because the biased condition in both of amount and contents mu s t b e b l o wn over. Figure 10 shows the summarized result of appropriate period for countermeasure of harmful rumor in three earthquake.

Discussion
We discuss the countermeasure method using each media for harmful rumor on the basis of the analysis results.
The newspaper has the characteristics that the article having large area attracts someone's attention, and it is di cult for article to be published if it does not have high topicality. Therefore, as the countermeasure using newspaper, the insertion of public relations advertisement which has enough wide area to attract a great deal of attention in the calm period of media which enough e ect of the countermeasure is expected is one of e ective methods. The advertising activity can beimprinted to the general public without beingobstructed by news which g i v e bad in uence to sightseeing. Such countermeasure can remove negative impression of visiting the tourism spot around disaster-stricken area and can give positive impression for tourism to the general public. Moreover, the e ect to the people of all ages is expected because newspaper is read by v arious people.
In web news, it is likely that events and a airs are published as the articles for news website even if they do not have high topicality. In addition, they are reported promptly on the website. Therefore, the enforcement of lively public relations activity after calm period of media information is e ective method as the countermeasure using web news. By performing such countermeasure, the e ect of public relations activity can be obtained rstly, and then the ripple e ect by the publication of the article to news website can be expected.
Moreover, the harmful rumor by earthquake is concerned to the factor of hesitating to go sightseeing near disaster-stricken area even if the tourism area is safe. Therefore, it is required to clarify to the general public that sightseeing to the tourism area contributes to smooth rehabilitation of the disaster-stricken area.

Conclusion
In this paper, we proposed a countermeasure method for harmful rumor on the basis of the trend of disaster related information in order to realize early recovery from harmful rumor. To implement our countermeasure method, we analyzed the disaster related information of newspaper and web news in three earthquakes, from the information amount and content points of view. From the analysis results of disaster related information on newspaper, the calm period of media which is suitable for starting the countermeasure for harmful rumor could be con rmed after 3 weeks from the occurrence of earthquake in early case. The calm period was after 6 weeks in late case. On the other hand, from the analysis results of web news, it was revealed that the calm period of media was after 3 weeks in early case and it was 5 weeks in late case. The analysis results indicated that the result of contents analysis was more important to the starting periodof countermeasure. However, the content analysis requires higher cost in comparison with the amount analysis. Therefore, in order to realize a low cost and real time analysis for the countermeasure of harmful rumor, the relationship between amount and content must be clari ed. In addition, the implementation of the prediction of media trend based on the scale and feature of physical damage is required in order to realize the e ective countermeasure for harmful rumor.
In the contents analysis, the disaster related information was classi ed by the criteria which we decided in advance. Namely, it was not completely objective classi cation. Therefore, we plan to implement completely objective analysis by employing text-mining approach for contents analysis.
Moreover, in this research, we discussed the countermeasure method of harmful rumor using the media. We judged that publishing public relations advertisement having a lot of space is e ective as the countermeasure method using newspaper because newspaper has limitation for publishing space. As the countermeasure using web news, the enforcement of many public relations activities is e ective because web news postsreport about an event even if it is not impactful. We plan to investigate more detailed contents and e ect of public relations activity by performing the hearing investigation in the area which received harmful rumor generated by earthquake. These are our future work.


GernEdiT - The GermaNet Editing Tool

This paper introduces GernEdiT (short for: GermaNet Editing Tool), a new graphical user interface for the lexicographers and developers of GermaNet, the German version of the Princeton WordNet. GermaNet is a lexical-semantic net that relates German nouns, verbs, and adjectives. Traditionally, lexicographic work for extending the coverage of GermaNet utilized the Princeton WordNet development environment of lexicographer files. Due to a complex data format and no opportunity of automatic consistency checks, this process was very error prone and time consuming. The GermaNet Editing Tool GernEdiT was developed to overcome these shortcomings. The main purposes of the GernEdiT tool are, besides supporting lexicographers to access, modify, and extend GermaNet data in an easy and adaptive way, as follows: Replace the standard editing tools by a more user-friendly tool, use a relational database as data storage, support export formats in the form of XML, and facilitate internal consistency and correctness of the linguistic resource. All these core functionalities of GernEdiT along with the main aspects of the underlying lexical resource GermaNet and its current database format are presented in this paper.

Introduction
The main purpose of the GermaNet Editing Tool GernEdiT tool is to support lexicographers in accessing, modifying, and extending the Ger-maNet data (Kunze and Lemnitzer, 2002;Henrich and Hinrichs, 2010) in an easy and adaptive way and to aid in the navigation through the GermaNet word class hierarchies, so as to find the appropriate place in the hierarchy for new synsets (short for: synonymy set) and lexical units. GernEdiT replaces the traditional Ger-maNet development based on lexicographer files (Fellbaum, 1998) by a more user-friendly visual tool that supports versioning and collaborative annotation by several lexicographers working in parallel.
Furthermore, GernEdiT facilitates internal consistency of the GermaNet data such as appropriate linking of lexical units with synsets, connectedness of the synset graph, and automatic closure among relations and their inverse counterparts.
All these functionalities along with the main aspects of GernEdiT's usage and usability are presented in this paper.

The Structure of GermaNet
GermaNet is a lexical-semantic wordnet that is modeled after the Princeton WordNet for English (Fellbaum, 1998). It covers the three word categories of adjectives, nouns, and verbs and partitions the lexical space into a set of concepts that are interlinked by semantic relations. A semantic concept is modeled by a synset. A synset is a set of words (called lexical units) where all the words are taken to have (almost) the same meaning. Thus a synset is a set-representation of the semantic relation of synonymy, which means that it consists of a list of lexical units.
There are two types of semantic relations in GermaNet: conceptual and lexical relations. Conceptual relations hold between two semantic concepts, i.e. synsets. They include relations such as hyperonymy, part-whole relations, entailment, or causation. GermaNet is hierarchically structured in terms of the hyperonymy relation. Lexical relations hold between two individual lexical units. Antonymy, a pair of opposites, is an example of a lexical relation.

The GermaNet Editing Tool
The GermaNet Editing Tool GernEdiT provides a graphical user interface, implemented as a Java Swing application, which primarily allows maintaining the GermaNet data in a user-friendly way. The editor represents an interface to a relational database, where all GermaNet data is stored from now on.

Motivation
The traditional lexicographic development of GermaNet was error prone and time-consuming, mainly due to a complex underlying data format and no opportunity of automatic consistency checks. This is exactly why GernEdiT was developed: It supports lexicographers who need to access, modify, and extend GermaNet data by providing these functions through simple buttonclicks, searches, and form editing. There are several ways to search data and browse through the GermaNet graph. These functionalities allow lexicographers, among other things, to find the appropriate place in the hierarchy for the insertion of new synsets and lexical units. Last but not least, GernEdiT facilitates internal consistency and correctness of the linguistic resource and supports versioning and collaborative annotation of GermaNet by several lexicographers working in parallel. In Figure 1, a search for synsets consisting of lexical units with the word Nuss (German noun for: nut) has been executed. Accordingly, the Synsets panel displays the three resulting synsets that match the search item. The Synset Id is the unique database ID that unambiguously identifies a synset, and which can also be used to search for exactly that synset. Word Category specifies whether a synset is an adjective (adj), a noun (nomen), or a verb (verben), whereas Word Class classifies the synsets into semantic fields. The word class of the selected synset in Figure 1 is Nahrung (German noun for: food). The Paraphrase column contains a description of a synset, e.g., for the selected synset the paraphrase is: der essbare Kern einer Nuss (German phrase for: the edible kernel of a nut). The column All Orth Forms simply lists all orthographical variants of all its lexical units.

The Main User Interface
Which lexical units are listed in the Lexical Units panel depends on the selected synset in the Synsets panel. Here, Lex Unit Id and Synset Id again reflect the corresponding unique database IDs. Orth Form (short for: orthographic form) represents the correct spelling of a word according to the rules of the spelling reform Neue Deutsche Rechtschreibung (Rat für deutsche Rechtschreibung, 2006), a recently adopted spelling reform. In our example, the main orthographic form is Nuss. Orth Var may contain an alternative spelling that is admissible according to the Neue Deutsche Rechtschreibung. 1 Old Orth Form represents the main orthographic form prior to the Neue Deutsche Rechtschreibung. This means that Nuß was the correct spelling instead of Nuss before the German spelling reform. Old Orth Var contains any accepted variant prior to the Neue Deutsche Rechtschreibung. The Old Orth Var field is filled only if it is no longer allowed in the new orthography.
The Boolean values Named Entity, Artificial, and Style Marking express further properties of a lexical unit, whether the lexical unit is a named entity, an artificial concept node, or a stylistic variant.
For both the lexical units and the synsets, there are two buttons Use as From and Use as To, which help to add new relations (see the explanation of Figure 3 in section 3.6 below which explains the creation of new relations).

Search Functionalities
It is possible to search for words or synset database IDs via the search panel (see Figure 1 at the top). The check box Ignore Case offers the possibility of searching without distinguishing between upper and lower case. Via the file menu, lists of all synsets or lexical units with their properties can be accessed. To these lists, very detailed filters can be applied: e.g., filtering the lexical units or synsets by parts of their orthographical forms. Figure 2 shows a list of lexical units to which a detailed filter has been applied: verbs have been chosen (see the chosen tab) whose orthographical forms start with an a-(see starts with check box and corresponding text field) and end with the suffix -ten (see ends with check box and corresponding text field). Only verbs that have a frame that contains NN are chosen (see Frame contains check box and corresponding text field). Furthermore, the resulting filtered list is sorted in descending order by their examples (see the little triangle in the Examples header of the result table). The number in the brackets behind the word category in the tab title indicates the count of the filtered lexical units (in this example 193 verbs pass the filter).

Visualization of the Graph Hierarchy
There is the possibility to display a graph with all hyperonyms and hyponyms of a selected synset. This is shown in the bottom half of Figure 1 in the tab Graph with Hyperonyms and Hyponyms. The graph in Figure 1 visualizes a part of the hierarchical structure of GermaNet centered around the synset containing Nuss and displays the hyperonyms and hyponyms of this synset up to a certain parameterized depth (in this case depth 2 has been chosen). The Hyperonym Depth chooser allows unfolding the graph to the top up to the preselected depth. As it is not possible to visualize the whole GermaNet contents at once, the graph can be seen as a window to GermaNet.
A click on any synset node within the graph, navigates to that synset. This functionality supports lexicographers especially in finding the appropriate place in the hierarchy for the insertion of new synsets.

Modifications of Existing Items
If the lexicographers' task is to modify existing synsets or lexical units, this is done by selecting a synset or lexical unit displayed in the Synsets and the Lexical Units panels shown in Figure 1. The properties of such selected items can be edited by a click in the corresponding table cell. For example by clicking in the cell Orth Form the spelling of a lexical unit can be corrected in case of an earlier typo was made.
If lexicographers want to edit examples, frames, conceptual, or lexical relations this is done by choosing the appropriate tab indicated at the bottom of Figure 1. By clicking one of these tabs, the corresponding panel appears below these tabs. In Figure 1 the panel for Graph with Hyperonyms and Hyponyms is displayed.
It is possible to edit the examples and frames associated with a lexical unit via the Examples and Frames tab. Frames specify the syntactic valence of a lexical unit. Each frame can have an associated example that indicates a possible usage of the lexical unit for that particular frame. The tab Examples and Frames is thus particularly geared towards the editing of verb entries. By clicking on the tab all examples and frames of a lexical unit are listed and can then be modified by choosing the appropriate editing buttons. For more information about these editing functions see Henrich and Hinrichs (2010).

Editing of Relations
If lexicographers want to add new conceptual or lexical relations to a synset or a lexical unit this is done by clicking on the Conceptual Relations Editor or the Lexical Relations Editor shown in Figure 1. Figure 3 shows the panel that appears if the Conceptual Relations Editor has been chosen for the synset containing Nuss. To create a new relation, the lexicographer needs to use the buttons Use as From and Use as To shown in Figure 1. This will insert the ID of the selected synsets from the Synsets panel in the corresponding From or To field in Figure 3. The button Delete ConRel allows deletion of a conceptual relation, if all consistency checks are passed.
The Lexical Relations Editor tab supports editing all lexical relations. It is not displayed separately for reasons of space, but it is analogue to the Conceptual Relations Editor tab for editing conceptual relations.

Adding Synsets and Lexical Units
The buttons Add New Hyponym and Add New LexUnit in the Synsets panel (see Figure 1) can be used to insert a new synset or lexical unit at the selected place in the GermaNet graph, and the buttons Delete Synset and Delete LexUnit remove the selected entry, respectively.
The Synset Editor in Figure 4 (on the left) shows the window which appears after a click on Add New Hyponym. When clicking on the button Create Synset, the Lexical Unit Editor (shown in Figure 4, right) pops up. This workflow forces the parallel creation of a lexical unit while creating a synset.

Consistency Checks
GernEdiT facilitates internal consistency of the GermaNet data. This is achieved by the workflow-oriented design of the editor. It is not possible to create a synset without creating a lexical unit in parallel (as described in section 3.7). Furthermore, it is not possible to insert a new synset without specifying the place in the GermaNet hierarchy where the new synset should be added. This is achieved by the button Add New Hyponym (see Figure 1) which forces the user to identify the appropriate hyperonym for the new synset to be added. Furthermore, it is not possible to insert a lexical unit without specifying the corresponding synset. On deletion of a synset, all corresponding data such as conceptual relations, lexical units with their lexical relations, frames, and examples, are deleted automatically.
Consistency checks also take effect for the table cell editing in the Synsets and Lexical Units panels of the main user interface (see Figure 1), e.g., the main orthographic form of a lexical unit may never be empty.
All buttons in GernEdiT are enabled only if the corresponding functionalities meet the consistency requirements, e.g., if a synset consists only of one lexical unit, it is not possible to delete that lexical unit and thus the button Delete LexUnit is disabled. Also, if the deletion of a synset or a relation would violate the complete connectedness of the GermaNet graph, it is not possible to delete that synset.

Further Functionalities
There are further functionalities available through the file menu. Besides retrieving the upto-date statistics of GermaNet, an editing history makes it possible to list all modifications on the GermaNet data, with the information about who made the change and how the modified item looked before.
GernEdiT supports various export functionalities. For example, it is possible to export all GermaNet contents into XML files, which are used as an exchange format of GermaNet, or to export a list of all verbs with their corresponding frames and examples.

Tool Evaluation
In order to assess the usefulness of GernEdiT, we conducted in depth interviews with the Germa-Net lexicographers and with the senior researcher who oversees all lexicographic development. At the time of the interview all of these researchers had worked with the tool for about eight months. The present section summarizes the feedback about GernEdiT that was obtained in this way.
The initial learning curve for getting familiar with GernEdiT is considerably lower compared to the learning curve required for the traditional development based on lexicographer files. Moreover, the GermaNet development with GernEdiT is both more efficient and accurate compared to the traditional development along the following dimensions: 1. The menu-driven and graphics-based navigation through the GermaNet graph is much easier compared to finding the correct entry point in the purely text-based format of lexicographer files.
2. Lexicographers no longer need to learn the complex specification syntax of the lexicographer files. Thereby, syntax errors in the specification language -a frequent source of errors prior to development with GernEdiT -are entirely eliminated.
3. GernEdiT facilitates automatic checking of internal consistency and correctness of the GermaNet data such as appropriate linking of lexical units with synsets, connectedness of the synset graph, and automatic closure among relations and their inverse counterparts.
4. It is now even possible to perform further queries, which were not possible before, e.g., listing all hyponyms of a synset.
5. Especially for the senior researcher who is responsible for coordinating the GermaNet lexicographers, it is now much easier to trace back changes and to verify who was responsible for them.
6. The collaborative annotation by several lexicographers working in parallel is now easily possible and does not cause any management overhead as before.
In sum, the lexicographers of GermaNet gave very positive feedback about the use of Gern-EdiT and also made smaller suggestions for improving its user-friendliness further. This underscores the utility of GernEdiT from a practical point of view.

Conclusion and Future Work
In this paper we have described the functionality of GernEdiT. The extremely positive feedback of the GermaNet lexicographers underscores the practical benefits gained by using the GernEdiT tool in practice.
At the moment, GernEdiT is customized for maintaining the GermaNet data. In future work, we plan to adapt the tool so that it can be used with wordnets for other languages as well. This would mean that the wordnet data for a given language would have to be stored in a relational database and that the tool itself can handle the language specific data structures of the wordnet in question.


Tree analogical learning. Application in NLP

In Artificial Intelligence, analogy is used as a non exact reasoning technique to solve problems, for natural language processing, for learning classification rules, etc. This paper is interested in the analogical proportion, a simple form of the reasoning by analogy, and presents some of its uses in machine learning for NLP. The analogical proportion is a relation between four objects that expresses that the way to transform the first object into the second is the same as the way to transform the third in the fourth. We firstly give definitions about the general notion of analogical proportion between four objects. We give a special focus on objects structured as ordered and labeled trees, with an original definition of analogy based on optimal alignment. Secondly, we present two algorithms which deal with tree analogical matching and solving analogical equations between trees. We show their use in two applications : the learning of the syntactic tree (parsing) of a sentence and the generation of prosody for synthetic speech.

Introduction
The concept of analogy has been studied as one of the modality of reasoning since Aristotle ( (Lepage, 2003) ; (Holyoak, 2005)). It is a form of reasoning by generalization, but neither abductive nor inductive, which models a third form of learning. Recently, a growing interest has been manifested for a formal point of view on the analogical proportion. This concept is now rigorously defined and its applications in representation spaces of various kinds have been developed, with interesting operational results. Its application to learning and generation is conceptually simple ; however, as in many areas of artificial intelligence, the complexity of some algorithmic problems remains to surmount. In this paper we consider the problem of analogical learning using dissimilarity between trees, which we define as a multiple alignment of four ordered labeled trees, according to the notion of analogical proportion. We extend the concept of alignment defined by (Jiang et al., 1994) to more than two trees. When four trees are considered, we propose to apply the concept of analogical proportion to trees and we extend it to that of analogical dissimilarity. In the next section, we present the general notion of analogical proportion between four objects. In the third section, we describe our approach, starting from several original definitions to define the analogical dissimilarity between trees. Section 4 presents two algorithms performing analogical tasks in the universe of trees. In the last section, we apply these algorithms to the learning of the syntactic tree of a sentence and give hints to use it to predict prosody in speech synthesis.

The Analogical Proportion and its Applications
The analogical proportion is a relation between four objects which expresses that the way to transform the first object into the second is the same as the way to transform the third in the fourth. Let us call the objects O 1 , O 2 , O 3 and O 4 . An analogical proportion is generally written as :  A nice formulation of the analogical proportion according to these axioms, based on the notion of factorisation, has been given in (Stroppa & Yvon, 2005).

Semantics and examples
The relation A : B :: C : D is generally interpreted as "A is to B as C is to D", which means that to transform A into B, one has to make the same operations than to transform C in D. The analogical proportion has been studied and its semantics explored especially in the following domains : {0, 1} d . Four objects defined by a vector of binary attribute are in analogical proportion when, on each coordinate, one has one among the six proportions : 0 : 0 :: 1 : 1, 1 : 1 :: 0 : 0, 1 : 0 :: 1 : 0, 0 : 1 :: 0 : 1, 0 : 0 :: 0 : 0 or 1 : 1 :: 1 : 1.
R d . Four objects defined as vectors of numerical attributes are in additive analogical proportion when Σ . Some theory and algorithms about the analogical proportion on strings and its use can be found in (Lepage, 2003;Stroppa & Yvon, 2005;Miclet et al., 2008;Hofstadter, 1994;). An analogical proportion on strings is, for example : overlook is to looked as overcook is to cooked.

Analogical proportion and trees
With the same principles that (Stroppa & Yvon, 2005) and (Miclet et al., 2008) for strings, we present in this paragraph our methodology to define an analogical proportion between ordered and labelled trees. The only prerequisite is that there exists an analogical proportion in the alphabet of the label of the nodes, augmented with the empty word λ. A node with label λ is also denoted λ and is called an empty node.
Definition 3.1 (Alignment between two trees (Jiang et al., 1994)) An alignment between two trees T 1 , T 2 whose labels are in Σ λ = Σ ∪ λ is a tree with labels in (Σ λ ) × (Σ λ )/(λ, λ) which first projection is T 1 , where the empty nodes λ are ignored and which second projection is T 2 , where the empty node λ are ignored. Informally, an alignment represents a one to one node matching between two trees, in which some empty nodes may be inserted. The cost of an alignment is the sum of all nodes matching costs.
This definition can straightforwardly be extended to the alignment of any number of trees. When aligning four trees, we can apply the concept of analogical proportion to trees.
Definition 3.2 (Analogical proportion between trees) Let x, y, z and t be four trees whose labels are in Σ λ . We suppose that an analogical proportion exists in Σ λ . We say that these trees are in analogical proportion if there is an alignment of the four trees x, y, z and t, with labels in Σ 4 λ , such that : for every node i of the alignment, the analogical proportion x i : y i :: z i : t i of the labels holds true ( figure 1 (a),(b)).

Analogical Dissimilarity between trees
In this section, we are interested in defining what could be a relaxed analogy, which linguistic expression would be "A is to B almost as C is to D". To remain coherent with our previous definitions, we measure the term "almost as" by some positive real value, equal to 0 when the analogical proportion is true, and increasing when the four objects are less likely to be in proportion. We call this value "analogical dissimilarity", in short AD.
This measure has been introduced on binary vectors, numerical vectors and sequences in (Miclet et al., 2008), and we want now to extend it to trees. We present in the following our definition of AD between four trees and we give its properties. This definition uses the notion of alignment between four trees. We assume there is some analogical dissimilarity existing on the alphabet of the nodes labels Σ λ . Let a, b, c and d be node labels in Σ λ . We have AD(a, b, c, d) = 0 iff a : b :: c : d and AD(a, b, c, d) > 0 in the other case. Thus, the Analogical Dissimilarity between four ordered labeled trees can be defined by : Definition 3.4 (AD between trees) Let X, Y , Z and T be four trees with labels ∈ Σ λ . The analogical dissimilarity AD(X, Y, Z, T ) is the cost of the alignment of minimum cost between the four trees. This alignment is a tree A, and the cost (or analogical dissimilarity) of an alignment is defined as : Definition 3.5 (Best approximate solution to an analogical equation) Let T 1 : T 2 : : T 3 : X be an analogical equation in trees. The set of best approximate solution to this equation is given by :

Algorithms
We have described in (BenHassena & Miclet, 2010) two algorithms based on dynamic programming, called AnaTree and SolvTree that allow : -from four trees, to compute their AD and their optimal alignment, according to definition 3.4 ; this procedure is in O(|T | 4 ), where |T| is the number of nodes of the bigger tree. -from three trees T 1 , T 2 and T 3 , to compute a fourth tree T 4 such that AD(T 1 , T 2 , T 3 , T 4 ) is minimal, according to definition 3.5. This procedure is in O(|T | 3 ).

Analogical syntactic parser
We apply these algorithms of analogical matching between structured objects to automatic parsing. Our hypothesis is simple : if four sentences have their sequences in analogical proportion (or with a low AD), then their syntactic trees are also in analogical proportion (or with a low AD). We test this hypothesis on a corpus of parsed sentences, each of these sentences being associated to its syntactic tree. The sentences are composed as sequences of grammatical categories, which are found as labels of the syntactic tree leaves. The labels of the tree nodes are syntactic labels as the "noun phrase (NP)", etc. Figure 1 (b) shows an example of parsing.
This assumption leads to a method for automatically generating syntactic tree (parsing automatic). We consider a sentence P 0 , which sequence S 0 of grammatical categories is known and which syntactic structure T 0 is searched for. Let AP a learning set of sentences (S, T ), each sentence consisting of a sequence and a syntactic structure. The process of prediction by analogy of the parse tree T 0 is as follows : 1. Search for a triple of sentences (P 1 , P 2 , P 3 ) with sequences (S 1 , S 2 , S 3 ) and syntactic structures (T 1 , T 2 , T 3 ) such as the sequences S 0 , S 1 , S 2 and S 3 define an analogical proportion S 0 : S 1 : S 2 : S 3 The corpus at our disposal consists of 316 sentences extracted from the base The Wall Street Journal Penn Treebank (Marcus et al., 1993). Since the data available is limited, we have used the leave-one-out technique to evaluate the results. Preliminaries results give an exact or almost exact (with a AD lower than 2) restitution of the parsing tree from the sequence in 82 % of cases. Note that, since we have kept in the learning set only sentences that have different sequences of grammatical categories, a simple nearest neighbor method would have given an null accuracy at a null distance. This shows that the analogical proportion takes profit of the recombination of subsequences and of subtrees.

Analogical prosody prediction
We present here ongoing work on prosody prediction for speech synthesis. This approach considers sentences as tree structures and infers the prosody from a corpus of such structures using a machine learning technique. The prediction is achieved from the prosody of the closest (at minimal AD) sentences of the corpus through tree analogical dissimilarity measurements, using also the analogy-based approach. Given three known tree structures T 1 , T 2 , T 3 and a new one T 0 , an analogical proportion would be expressed as : T 1 is to T 2 as T 3 is to T 0 if and only if the set of operations transforming T 1 into T 2 is equivalent to the set of operations transforming T 3 into T 0 . This relation can be relaxed according to the notion of analogical dissimilarity. Next, the analogical transfer would apply on the prosodic string associated to T 3 the transformation defined between the prosodic strings associated to T 1 and T 2 to produce the prosody of T 0 . From these two notions, the analogical inference would be therefore defined as : -firstly, retrieve all analogical proportions involving T 0 and three trees in the corpus ; -secondly, compute the analogical transfer for each 3-tuple of the corresponding prosodic strings, and store the result in a set of possible outputs if the transfer succeeds. Experiments are currently under process to qualify this approach.

Conclusion
In this paper, we have proposed a new learning method based on the analogical proportion between trees, and its approximation called "analogical dissimilarity". As an application we have firstly proposed a casebased parsing system, with preliminary promising results. Secondly, we have presented hints on a new prosody prediction method. Further investigations will be conducted, taking into account that the proposed brute force method is time-consuming, but can be ameliorated, as shown in  and (Miclet et al., 2008).


Aspects and challenges of mashup creator design

With the advent of Web 2.0, an increasing number of web sites has started offering their data over the web in standard formats and exposed their functionality as APIs. A new type of applications has taken advantage of the new data and services available by mixing them, in order to generate new applications fast and efficiently, getting its name from its own architectural style: mashups. A set of applications that aims to help a user create, deploy and manage his mashups has also emerged, using various approaches. In this paper we discuss the key factors that should be taken into consideration when designing a mashup creator, along with the most important challenges that offer a field for research.

INTRODUCTION
Over the last decade there has been an explosion in the use of new web technologies that has lead to an increase of the available data and functionality over the Web. Numerous attempts have been made to utilize this increasing volume. Service-oriented architectures, portals and, recently, mashup technologies aim to create space for combinations of such functionality and data. Although the term mashup remains to this day loosely defined, in most cases it describes the act of combining functionality and data from different sources. In the past few years, there have been efforts to make such acts easily accessible to individuals with less technical expertise, safe, and, above all, available at lower cost than the traditional programming approach requires.
Quoting [1], "mashup makers (creators) are development environments for mashups". However, the notion of a mashup is used in many diverse ways. In general, mashups are applications, either standalone or embedded in an environment, that allow integration of different data sources and/or services that are available on the Web. The first mashups used to combine geographic data with online map services, but the combination of data/services has extended to different areas of interest. Mashup creators are tools that intend to facilitate the process of combining data and services, and -in some cases -offer the environment for executing the resulting mashup.
In this paper we inspect the key factors that should be taken into account when designing a mashup creation environment. We are, then, going to explore a range of attempts made to create such environments, focusing on the way the design aspects were considered. Finally, we discuss the challenges that are yet to be fulfilled.

II. ASPECTS OF MASHUP CREATOR DESIGN
The solutions currently offered by mashup creation tools focus on subsets of the problem of mashup creation/generation, each addressing problem-specific needs. In this paragraph we attempt to define the problems and decisions that play a major role in designing a mashup creation tool.

A. Mashup Lifecycle
One important aspect is the life duration of the resulting mashup. The life cycle of a mashup can span from minutes to years, depending on various factors. Short-lived mashups are used mostly in cases where the user wants to combine data from different sources in order to get a helpful visualization of the data. Such cases can include data sources available on the Internet (i.e. maps and data) or information stored in enterprise systems (databases, SAP etc), in order to generate quick reports. Long-lived mashups are usually part of rich Internet applications. Another factor that affects the duration of a mashup is the availability or changes to its building blocks. Services used to compose a mashup may stop functioning or be exposed using a different protocol, while the format that data are provided can change.

B. Execution environment
Another major distinction is the actual execution environment of the mashup. The first mashups were deployed as web applications. The actual mash of data and/or services was performed using one of three alternate techniques: • on the server side using the underlying software platform (i.e. J2EE, .NET, Rails), • on the client side (the browser) by utilizing JavaScript and XMLHTTPRequest or • a hybrid solution utilizing both of the previous solutions.
However, different execution environments have emerged. Although the browser still plays an important role, it is utilized in different ways. Resulting mashups can be applications based on frameworks such as Microsoft's Silverlight, JavaFX and Flash or can be browser-specific plug-ins that create a new local page eor customize an existing web page according to a script written in a scripting language (e.g. Greasemonkey, http://www.greasespot.net), in order to generate the mashup. Domain specific languages (mostly XML) have also appeared, offering the means to define the components of the mashup, their interactions and the operations required to generate the result. DSLs are commonly used as an intermediate format for describing a mashup, with an underlying platform performing the actual operations. The major advantage of mashups described in a DSL is that they are portable and reusable. Generated mashups can be stand-alone applications running on personal computers, mobile phones and other Internet-enabled devices, with some of the mashup creators allowing exporting the final mashup in more than one of the above forms.
Another approach is to allow mashups to be added to an existing site as applications or widgets, allowing the user to customize the appearance and functionality of his personal page. In such cases, the user's homepage becomes a dashboard that he can manage by adding the building blocks that are offered to him. Mashups added to his page can be either isolated or interact with each other, depending on the underlying architecture.

C. Intended user audience
An important point of variation among mashup creators is the user level. Different mashup creators target different audiences and the experience they have in creating applications or mashups. In [1] the users are divided into three categories, depending on their programming skills. The first group contains users with good programming skills that can use a mashup creator, in order to prototype their mashup or save development time. The second group consists of users that understand the notion of data types and flows, while the third group represents the ones with average understanding of computers and Internet. Most mashup creators try to leverage off of the users the effort required to code a mashup. The most common approach is using a GUI design tool. However, this doesn't always simplify the mashup creation process for all the types of users equally. For example, a GUI design tool might require the user to be familiar with the concepts of regular expressions, XPath or other technologies. Alternatives have been proposed by various mashup creators, including the idea of mashup by example [6] (or sample [3]). In this case, the mashup creator asks the user to navigate the Web pages containing the data he will use and it attempts to collect information for available data sources or services.

D. Data Source and Service Discovery
The key ingredient for building mashups is to combine data and services. In order for mashup creators to be efficient, they need to know which services and data the user wants to use. Different approaches include repositories, gathering information by allowing a user to browse the sites he wants to use or by providing technical details directly.
Repositories provide a catalogue of services and/or data sources. Apart from the actual data/service metadata, the stored information may contain details, such as ratings, comments, similarity indicators that can help the user locate useful services. Indexing can be performed through using simple solutions like keywords or a hierarchical structure, or more complex, using ontologies to manage the relationships among data. These repositories can be either local, used by few users, or centralized, offering advanced functionality for exposing and sharing services and mashups.
Programming by example is a different approach thatas mentioned above -targets mostly users with less programming knowledge. The user visits the Web pages containing the data. Simpler solutions allow defining the desired data by selecting them, while more intelligent ones attempt to understand the page by analyzing its structure or intercepting calls to remote services.
A feature offering added value to mashup creators is to enable reuse of previously created mashups. Existing mashups can be customized or used as building blocks for new ones, either by directly embedding them in the user interface or by invoking the functions that generate the results presented on it.

E. Supported technologies
Content sources and services available on the Web can be accessed using a plethora of technologies. Data can be accessed in multiple forms, with XML based standards like Atom and RSS being extremely popular. However, it can also be retrieved in various formats (i.e. JSON, microformats) or directly as HTML by performing simple HTTP requests. Other resources include comma-separated files, spreadsheet programs or even databases. Services are also exposed using various standardized protocols like REST or SOAP. A mashup may be composed by any of these technologies, or even from another, non-standard, limited by the restrictions applied on the execution environment and the capability of the mashup creator to support these technologies. Another popular feature is to allow a mashup to obtain data from internal resources, such as Excel files or databases using SQL.

F. Consumer-oriented or Enterprise
Another distinction can be made by the target group of the resulting mashups. The first mashup creators aimed to allow resource composition for resources available on the Web. However, the ability of mashups to combine data and generate information on demand, led to the design of mashup creators aiming for the enterprise sector. Enterprise mashups can also be seen as an extension of Service Oriented Architecture (SOA), allowing orchestration of both external (available on the Web) and internal (databases, enterprise services) resources, in order to offer situational applications that can help in decision-making. Another distinction between the two types of mashup creators is made in [2], mentioning that consumer-oriented aim mainly towards individuals that want to aggregate data i.e. for their homepage, while enterprise mashups target members of the enterprise that can access more stable resources.

III. ASPECT INTERRELATIONS
Although the above aspects are important on their own, it is important to note that there's a connection among some of them. Design decisions on one of them may affect one or more of the rest.
One of the most important decisions, when designing a mashup creation tool, is if it will be consumer or enterprise oriented. Internal resources in enterprises offer more wellstructured data, obey well-established standards (i.e. SOA related standards) and are more persistent than the external resources. Enterprise mashup creators should provide the means for utilizing these standards, while their persistent nature allows them to be indexed in repositories, allowing faster discovery. Repositories can, also, store the mashups, in order to enable reuse or fast access from other members of the enterprise. Reusability requirements and higher availability of the mashed resources usually result in longer life spans of the resulting mashup.
The lifecycle of the resulting mashup may interact with the execution environment. Apart from when and how the implementation requires data to support the existence of the service, if the repositories remain unavailable, the whole of the mashup will remain loose. This impact may lead to the decision which concludes in the election of server-side data execution, when we intend to produce long-term mashup applications.
The target user level is, also, one of the most affecting aspects. Τhere's usually a tradeoff between the simplicity and the level of customizations that can be performed by the mashup creator. Targeting users with average understanding of computers limits the technologies involved in the mashup creation to the ones that the user can understand in a visual manner (i.e. extract data only from HTML), or the execution environment, while it leads to short-lived mashups that are not reusable.

IV. MASHUP CREATORS
The elements described earlier in this paper have affected the design of the most popular mashup creation tools. Although development in some of them has terminated or is in pause, we focus on how design decisions have affected the result and not on the success of the result.
Yahoo Pipes! (http://pipes.yahoo.com) borrows the metaphor of piping, common in the unix world, indicating its functionality. It is a tool that allows you to create data mashups by combining and manipulating feeds, before outputing them in a manner, nearly as fast and as convenient as in the unix pipes. While these mashups can be used only once, the application allows the mechanism to be saved, published and re-used as a feed in new mashups. The application, also, creates space for situational uses of the feeds created, by providing the options to geocode the feed or gets the output in forms acceptable by map visualizations such as KML.
In another approach proposed by d.mix ( [3]), the time spent on mashup data was considered the most important factor. To make the generation of mashups rapid, they employed a mechanism divided into two parts. The first part was the ability of the environment, utilizing a service-to-site map, to track the service calls made by a web site's elements by monitoring the elements selected visually (e.g. click) by the user. The second was a server-side active wiki, which hosted scripts that could be accessed via the browser and be personalized. This technique, called programming by sample, has aimed to allow faster mashup creation than the similar programming by example. Thus, d.mix focused on the ability to create short-lived mashups, while providing the ability to add code which could extend its functionality.
In a similar fashion, Intel Mash Maker ( [4]) comes as a plug in to the browser and runs mostly on the client side. This enables it to be able to monitor user activity and, thus, to provide more personalized suggestions on how content can be mashed while, the user is browsing the Web. Mashups themselves are described internally by a functional language. The application utilizes a collaboratively maintained database of extractors, in order to assist the user in extracting data from the raw HTML of particular kinds of pages. The extractor database can be edited by the users, while on the other hand it keeps track of changes, so they won't disable previous functionality stored in the database.
Another effort to create a mashup environment was Vegemite, presented in [5]. It combined a somehow improved version of CoScripter plugin with a set of tables (VegeTables), providing a client side environment that could record user's actions, represent them as scripts in a language resembling English and re-run them on the set of data placed in the tables. The tables utilized an XPath scheme to extract rules and relations among the data put there by the user. While running mostly on the client side, Vegemite provided a mechanism to store scripts in a central repository, in order for them to be reused by other users. Similarly, it provided a mechanism for the table instances to be stored in a repository, in order to be available from different computers by the same user.
Karma ( [6]), on the other hand, focused on automating the process of data extraction from Web sites. Relying heavily on XPath, it proposed a mechanism to extract the data, utilize a model on them, bring them in a consistent form, create rules so that they can be integrated with other data and, finally, proposed a method to visualize them.
Presto (available at http://www.jackbe.com/products/) is an enterprise mashup creation environment offered by JackBe. Its focus is mostly on enterprise mashups that can be built in a matter of "3 clicks versus 3 months". To achieve this, presto includes a sophisticated visual environment, allowing the combination of resources drawn from inside or outside the enterprise, which are presented as parts of the GUI. JackBe offers many service calls modeled as building blocks in the GUI, which the designer can configure using their various parameters. It, also, offers the ability to describe a service call in the visual environment and edit its output.. The main concept of the GUI is similar to Yahoo Pipes! wiring, but its functionality is far from being limited to feeds. It, also, offers the ability to extract data from sources outside the Web through the use of various "connectors" (http://www.jackbe.com/products/connectors.php). In the meantime, it has many ways of visualizing the data in the stages before the mashup is completed, thus it makes the design easier. Finally, it provides mechanisms to visualize the result of the mashup V. CHALLENGES Mashups seem to have created a rush of interest, especially after the popularity enjoyed by Google Maps. This excitement was directed to certain areas that could enhance mashup making and, perhaps, create broader mashup developer communities. In order to turn this interest into advantage, a mashup environment should be designed carefully, considering various factors that are relevant to Web application design, but remain somewhat different as well. The mashup creator environment can be viewed both as a system, being an application, but also as something more. Its users constitute a network that not only uses the system, but can also expand its functionality and enrich its databases.

A. Mashup Creator Environment as a System
From a designer's perspective, the mashup creator environment can be viewed as a system which has a number of acceptable input types, is able to perform a number of transformations on them and, finally, outputs a result. In this context, we attempt to present some of the challenges faced when designing a mashup creator environment.

1) Input
The first challenging part of designing such an environment is the way it treats its data input. The broader the variety of the data types the application is able to support, the more diverse types of mashups it can produce. Seeing data as the input in such a system brings forth three major difficulties. The first is that the data available on the Web can be in forms that are not predictable. This fact raises the difficulty of assessing them to produce a standard output. The second is that data can be in places that are and should remain protected, such as intranets or sites that require some kind of authentication to access them. Some solutions provided by the applications examined were either intelligent algorithms for data extraction on the first part of the problem or another level of abstraction that could treat data input, regardless of their type, leaving the specifics to other pieces of software. The third difficulty is the availability of data. There are many cases where the mashup creating software acts as the middle man between data and the mashup. This is where there must be a way to monitor changes in the sources, so that mashups remain functional.
The other aspect of mashup resources is services provided by different vendors in the form of APIs. This, also, presents challenges similar to those data retrieval, integration and sustainability does. Services can be exposed either in standardized ways or using custom protocols and technologies. It is, also, extremely possible (if not sure) that new standards will arise. On many occasions, instead of performing message exchange over an abstract protocol, the mashup creation requires embedding scripts written on a specific programming language (such as JavaScript for Google maps). It is also usual for services to require some kind of configuration (i.e. developer key), which the environment should somehow be able to handle. This is also something that raises the complexity and, perhaps, should be considered as a separate aspect of the design, maybe handled by a repository or some similar mechanism. Finally, similarly to the data, services are bound to change their availability status in various ways. The environment should be able to monitor these changes in status and provide solutions or alternatives to its users, both in terms of design and execution time.

2) Output
The way a mashup environment structures its output is important in various ways. Output can be in a format that can be consumed by other applications or it can be an application by itself. In the first case, the flow of information on the Web is facilitated, while in the second one more logic, in terms of quantity or diversity, is added to the Web.
Regardless of the above classification, the final form of the mashup plays an important role on whether the mashup can be reused as a building block by itself in the environment and, in this way, extending the environment's building blocks for new mashups or if it can be deployed or integrated in sites outside the environment.
As seen in many of the consumer mashups that have appeared up to this day, there are many limitations presented either by the client-server architectural models or by the mechanisms employed, in order to make the environment usable by people with little or no technical expertise. On the other hand, enterprise mashup creating environments have to face important security limitations when they attempt to combine internal to the enterprise data and functionality with those available on the Web.
Perhaps the most important challenge, in terms of the reusability of the mashups produced, either in a consumer or in enterprise environments, is the lack of standardized ways to achieve this production. This is considered to be one of the most important limitations of mashup creation by most of the vendors. Some of them, in order to overcome this limitation, have joined their forces towards creating an Open Mashup Alliance ( [7]), which aims to the creation of an open standard for achieving mashup creation. Whether this effort is going to facilitate innovation or not is still under debate due to various issues, such as current licensing.

3) Transformations
The way a mashup creator functions upon its input is quite strictly related to the mechanisms it provides to its users to manipulate input through the user interface. UI can act as a limiting factor, especially due to the mashup making main concept: it should require less time than it would if a similar application were to be developed by a programmer. The effort to keep the way the environment's functionality is presented to the users under graspable concepts acts in an antagonistic manner to the type of the functionality itself. This is a good reason why many of the mashup making environments (either consumer or enterprise) failed to gather people into big enough communities to support and extend them. On the other hand, through realizing this and focusing on providing solutions by functionality that aims to smaller problems can produce a good, yet limited, environment.
Again, this antagonistic relation between what concept (represented in the UI) is graspable by the users and the functionality this can support is amplified by the lack of standards that could loosen the relations between those two design aspects.

B. Mashup Creator Environment as a Network
Regarding the environment's users, the designer should take into account not only how it will be accessible and easy to use, but how it will also facilitate the exchange of information between the users in manners that can expand its functionality and spark innovation.
Between the various definitions of what a mashup really is exists a difficulty in defining the user base of an environment aiding the creation of mashups. During design time, the target group should be decided. This is, among other things, a decision about the kind of the community that will later be formed around the environment. Taking into account that technologies around mashup making are far from mature we assume that carefully selecting and attracting the right user base and managing to maintain an active community around the tool is vital not only for the tool's survival and growth, but also for the evolution of the technologies involved.

VI. SUMMARY
The present paper is a review of our research on an attempt to create our own mashup creator environment. While numerous attempts have been made in the past, we reference only a number of them as examples of the designing aspects, the difficulties involved and how they can be overcome. We believe that mashup making environments can attract research on various fields, since the technologies involved are still far from mature. Open Mashup Alliance is a first step to create an Open Standard and to form an active community around it. The evolution of the browsers, as envisioned by Google, will play a serious role in future mashup making environments. Finally we expect that many of the design difficulties will be overcome by the adoption of HTML 5.