A hierarchical approach with feature selection for emotion recognition from speech

We examine speaker independent emotion classification from speech, reporting experiments on the Berlin database across six basic emotions. Our approach is novel in a number of ways: First, it is hierarchical, motivated by our belief that the most suitable feature set for classification is different for each pair of emotions. Further, it uses a large number of feature sets of different types, such as prosodic, spectral, glottal flow based, and AM-FM ones. Finally, it employs a two-stage feature selection strategy to achieve discriminative dimensionality reduction. The approach results to a classification rate of 85%, comparable to the state-of-the-art on this dataset.

Introduction
Automatic emotion recognition from speech has attracted significant interest in recent years, aiming at improved human-computer interaction. Several approaches have been proposed in the literature, varying in the types and number of features employed, the classifier used, and the system developed. For example, there have been works using traditional features from the speech recognition literature or higher level voice quality ones (He et al., 2010), some adopting flat and simple systems, and others that employ complex classifiers and systems of a hierarchical form (Mao and Zhan, 2010;Shaukat and Chen, 2008). Up to now, most of the highest performing speaker independent emotion recognition systems use large feature sets and rather complex classifiers (Schuller et al., 2006;Lee and Narayanan, 2005). For example, Schuller et al. (2006) extract a large set of 4k features, achieving an average recognition rate of 87% on the Berlin database of emotional speech (Burkhardt et al., 2005). The proposed approach in this paper achieves comparable performance with the best research efforts by using only 112 features in total. We accomplish this by designing a system that is based on smaller and more specially trained sub-systems that focus on pairs of emotions. We also use a two-stage feature selection scheme, in contrast to the stateof-the-art simple sequential selection. We finally involve feature sets that are not typically employed in the emotion recognition literature, such as glottal flow features and AM-FM ones. Thus, although the total number of features remains small, there is much variety in their types. The rest of the paper is organized as follows: First, in Section 2, we describe the different feature sets considered, together with their basic theoretical background. In Section 3, we present our two-stage feature selection approach, and, in Section 4, we explain how the final system works. Following these, in Section 5, we present our experiments and associated results. Finally, we conclude the paper with a short summary in Section 6.

Feature Extraction
A number of feature sets are considered in our approach. In more detail they fall within the following four categories:

Prosodic Features
Such features are strongly related to the emotional state of the speaker and are extensively used in the literature. In this paper, we extract two features relevant to prosody intonation and intensity. First, we calculate the pitch contour of the utterance using the RAPT algorithm (Talkin, 1995), and, second, we compute signal energy to obtain information about speech intensity.

Spectral Features
As in the state-of-the-art in speech recognition, we employ the Mel frequency cepstral coefficients (MFCCs), together with their first-order derivatives (Young et al., 2002). In addition, we compute the zero crossing rate (ZCR) of each frame (Young et al., 2002).

Glottal Flow Features
The volume velocity of air-flow through the glottis is the excitation source for voiced speech. The glottal flow is related with several voice quality features, such as breathiness, harshness, and creakiness, and therefore it provides useful information about the emotional state of the speaker. The estimation of the glottal flow is based on Fant's sourcefilter theory, according to which the voice excitation and the vocal tract are linearly separable. In this manner, speech production can be modeled by a cascade of linearly separable filters. In order to obtain the glottal flow, we perform inverse filtering by using the IAIF algorithm, which employs the discrete all pole (DAP) method to model the vocal tract and then cancels it iteratively to obtain an estimate of the glottal flow waveform (Airas et al., 2005). Once the glottal flow is obtained, we extract time and frequency based features from its waveform, such as the: [ 112 ] [ 40 ] [ 10 ]

Feature Selection ( 2 stages )
MRMR selection backward feature selection wrapper Figure 1: The two-stage feature selection scheme employed here. Numbers in brackets depict feature dimensionality.
• Open quotient, which is the ratio of the time in which the vocal folds are open and the whole pitch period duration.
• Speed quotient, defined as the ratio of rise and fall time of the glottal flow.
• Normalized amplitude quotient that is used to parametrize the glottal closing phase.
• Harmonic richness factor, which is the ratio of higher harmonics to the first harmonic.
In total, we extract 18 time based and 4 frequency based features.

AM-FM Features
The AM-FM model considers decomposing the speech signal into a series of a few instantaneous frequency and amplitude signals. These signals can be considered as timefrequency distributions, containing acoustic information that is not captured by the linear speech model (Potamianos and Maragos, 1999). Following the approach in (Dimitriadis and Maragos, 2005), we model each speech sound by six AM-FM signals, estimating their parameters by the energy separation algorithm (ESA). At the end, twelve (2×6) parameters are obtained for each utterance frame.
We should note that, for all aforementioned feature sets, we only utilize their first and second order statistics (mean and variance).

Feature Selection Strategy
Feature selection is a very crucial step in pattern recognition problems to counter the curse of dimensionality. It does so, avoiding feature transformations such as PCA or LDA, obtaining instead a subset from the initial set of features that is most relevant to the classification problem at hand. In general, this requires a search strategy to select candidate subsets and an objective function to evaluate such candidates. Depending on their objective function, feature selection algorithms can be divided into filters and wrappers. Filters evaluate feature subsets by their information content, typically statistical dependence or informationtheoretic measures. Wrappers, in contrast, evaluate the subsets by their classification rate on test data. One can claim that filters have better generalization properties, as they are not related to any classifier. On the other hand, wrappers can interact with a specific classifier and find a subset that is also appropriate for the problem at hand. Two of the simplest and most used wrappers belong to sequential feature selection algorithms, and are forward feature selection (FFS) and backward feature selection (BFS). FFS starts from the empty set and sequentially adds the feature that results in the highest recognition rate, when combined with the features that have already been selected. In contrast, BFS starts from the full feature set and sequentially removes the feature that leaves a subset with the highest recognition rate. Both constitute greedy approaches and may be trapped in local minima. In our experiments, we compare these two wrappers and show that BFS performs better, especially when the initial set of features is large. In our system we use a two-step feature selection scheme that takes advantage of both generalization properties of filter algorithms and classifier-adaptive properties of wrappers. As a filter we employ the maximum relevanceminimum redundancy (MRMR) algorithm (Peng et al., 2005). This method tries to select a feature set that has maximum relevance with the two emotions involved in each two-class emotion classification sub-problem (see Section 4), as well as minimum intra-redundancy in terms of mutual information between its features. In more detail, if S denotes a set of selected features within the set of all possible features Ω, then a measure of its redundancy is given by where I(i, j) represents the mutual information between features i and j, and |S| denotes the number of features in set S. The minimum redundancy criterion seeks the set of features S that minimizes W S . Next, if c ∈ C denotes the class of interest (for the two-class emotion classification problem we will have C = {c 1 , c 2 }), we can calculate the relevance of feature set S as The maximum relevance criterion seeks feature set S that maximizes V C, S for the specific classification problem C.
The MRMR algorithm then tries to achieve both of the two previous criteria by maximizing the following quotient: .
Obtaining the optimal solution to the above through exhaustive search is clearly intractable. In practice, one proceeds with a sequential, incremental, non-optimal approach, by first selecting as the first feature the one that maximizes the relevance criterion, and subsequently adding happiness anger neutral sadness fearanxiety boredom Figure 3: The five sub-systems for recognizing "happiness", denoted by the five lines connecting the circles.
one feature at a time, similarly to the FSS approach mentioned earlier. Assuming that the selected set at the current iteration is S, then feature i ∈ Ω − S will be selected as The process terminates, once we arrive at the desired feature set size. We should also note that, in the above, all mutual information quantities are computed after appropriate discretization of all continued-valued features. The two-stage feature selection scheme employed in our approach is depicted in Figure 1.

Final System
Our emotion classification system has a hierarchical structure, as it is composed from multiple specialized systems. Each one of the smaller systems is trained to distinguish between only one pair of emotions (e.g., fear vs. happiness, anger vs. happiness, etc.), and it is trained separately, as depicted in Figures 2 and 3. Since, in this paper, we concentrate on six basic emotions (see Section 5), the proposed approach gives rise to 15 sub-systems. Each such sub-system is implemented based on a simple linear support vector machine (SVM) classifier. Majority voting over the sub-system classification results is then used to provide the final classification. In addition, we use the a-priori knowledge of gender information, as such has been shown to play an important role in emotion recognition in the literature.

Experiments and Results
In our experiments we used the well-known Berlin database of emotional speech. The corpus has been recorded at the Technical University of Berlin, and it consists of 493 utterances by 10 professional actors (5 male and 5 female). It contains seven emotions (acted), namely anger, happiness, sadness, fear, boredom, neutral, and disgust (Burkhardt et al., 2005), of which we concentrate on the first six in accordance with similar work in the literature. We follow a leaveone-speaker-out experimental paradigm to provide speaker independence. In the following tables we present results in the form of confusion matrices for several different experiments. From these, we can immediately observe the superiority of the gender dependent vs. the gender independent approach. Clearly, a-priori gender knowledge significantly improves   algorithm performance. Furthermore, we observe the gradual improvement of recognition accuracy of almost all emotion classes, first when applying the BFS scheme in place of FSS, and subsequently when employing the proposed twostage approach that includes the MRMR algorithm. One should note that these results are in par with human emotion perception experiments reported at 84.3% by Schuller et al. (2007). Next, in Figure 4, we show some results on the several subsystems performance with different initial features sets. As we can observe, the addition of glotal and AM-FM features lead to better recognition results. In a few sub-systems performance is somewhat better when using only MFCC and prosodic features. This demonstrates that such features are sufficient for the specific sub-systems. Finally, concerning the types of features selected by the proposed algorithm, it should be noted that different feature combinations are selected for each subsystem, a fact that backs our hierarchical approach. For example, when one of the two classes of interest is fear, more glottal features are selected.

Conclusions
In this paper, we proposed a hierarchical classification system that is based on the discriminative power of its appropriately trained sub-systems. These sub-systems employ feature sets of various types appropriately selected through a two-stage feature selection algorithm. Finally we took advantage of the well-established method of gender dependent systems to achieve better results.
Our final system achieved an overall classification accuracy of 85.18% that is comparable to the state-of-the-art in the field. Both glottal flow and AM-FM features were selected by the feature selection scheme employed and indeed improved recognition results in comparison to the state-of-   Table 4: Confusion matrix for the gender independent experiment with the final proposed feature selection scheme (backward selection followed by MRMR). The overall accuracy is 80.09%.
the-art systems that employ only MFCCs and prosodic features. Finally, the combination of the MRMR filter based algorithm with the BFS wrapper based one outperformed simple sequential feature selection.
In future work, we will investigate the use of temporal feature information (feature contours), as opposed to just their means and variances. Furthermore, we will consider larger datasets and spontaneous speech data.


extfieldsofstudy:
Computer Science
Physics

text:
New Tools for Decomposition of Sea Floor Pressure Data - A Practical Comparison of Modern and Classical Approaches

In recent years more and more long-term broadband data sets are collected in geosciences. Therefore there is an urgent need of algorithms which semi-automatically analyse and decompose these data into separate periods which are associated with different processes. Often Fourier and Wavelet Transform is used to decompose the data into short and long period effects but these fail often because of their simplicity. In this paper we investigate the novel approaches Empircial Mode Decomposition and Sparse Decomposition for long-term sea floor pressure data analysis and compare them with the classical ones. Our results indicate that none of the methods fulfils all the requirements but Sparse Decomposition performed best except for computing efficiency.

Motivation
Long-term monitoring of earth processes becomes more and more essential and indispensable as only long records will reveal small changes which may eventually have large societal impact in the near future. These processes encompasses geohazards like monitoring of potential landslides and volcanic activity but also processes related to earthquake precursors and climatic signals. In addition real-time observations of tectonic processes with high-precision GPS measurements and satellite based observations of the magnetic and gravity field of the earth give new insights into geological processes at local, regional and plate-size scales. As these signals are mostly small in amplitude and often buried in large-amplitude signals caused by other sources or only visible after major corrections to the field observations have been made it is a major challenge to separate the wanted from the unwanted signal components.
Broadband data acquisition is now very common as data storage capacity is no major obstacle today and low power data acquisition with autonomous monitoring systems over considerably long time periods (i.e. years) in remote places like the deep ocean floor become more and more feasible. In addition large observational networks -either regionally only temporary like EarthScope (http://www.earthscope.org/) -or permanent like Neptune Canada (http://www.neptunecanada.ca/) or national or international geodetic GPS observation networks deliver continuously time series whose information content is not completely taken advantage of. All time series contain signal periods from short (several seconds) to long (several month to years); origin and cause of some signal components is sometimes quite well known (deterministic) as e.g. tides from various origins but in a lot of cases especially long-term changes are not well understood. In addition instrumental behaviour like drift and effects of environmental changes severely alter the signal.
In earth science seismology has faced this problem for a long time which became even more pressing over the last decade during which the number of seismological stations increased accompanied by a tremendous increase of digital storage capacity and a rapid decrease in storage cost. In seismology robust methods were established to extract earthquakes from long data sets automatically and also detect phases and locate earthquakes. This highly automated processing can be achieved because the characteristics of the signals are well-known and years of research have been spend until these algorithms were developed (Bormann, 2002).
Traditional tools for data analysis are mostly based on spectral analysis methods which are well established and available with a lot of software tools. However they tend to introduce unwanted effects especially at short periods due to filters and finite length of time series. Also their requirement of a stationary time series is often not fulfilled in the case of long-term records. Therefore new data exploration tools are needed which enable us to separate the different signal components. These tools should be capable of analysing long time series efficiently and help to identify different signal contributions originating from different processes.
In this paper we present the results of time series analysis using four different methods. The times series analysed are sea floor pressure records from two different locations (details see section 1.2). The motivation for this investigation came from the fact that the sea floor pressure signal is dominated by a large deterministic tidal pressure signal but due to the high pressure resolution and a technically possible sampling interval of down to 2 seconds, small and short transient signals can be observed. Superimposed on these tides are also long-period transient changes, associated with tectonic and/or oceanographic phenomena but also short period signals originating from local or teleseismic events. The problem was and still is to separate the deterministic from the small-amplitude non-deterministic signals. Traditional tidal analysis methods as described e.g. in Pawlowicz et al. (2002) and available as Matlab R toolbox (http://www.eos.ubc.ca/~rich/) do not always fulfil the requirements.
We tested four methods in total: the traditional (1) Harmonic Decomposition, (2) Wavelet Decomposition, (3) Empirical Mode Decomposition (EMD) and a novel approach (4) Sparse Decomposition. The last two methods used are rather new and their potential use in time series analysis needs still to be explored. All times series were analysed in the same way with the four methods. After a short description of the methods we present the results and compare the results with respect to their capability of signal decomposition.

Data
We used four data sets to test the four methods for time series decomposition. The first data set (SYN) is a synthetic data set which is composed of a tidal signal calculated with a published Matlab R -script (Pawlowicz et al., 2002), a long-term ramp function and two short-period events. In addition noise with an RMS of 49.16 P a is added. A step in the middle of the time series simulates a tectonic or oceanographic event. The second time series (MAR) consists of sea floor pressure observations from the Logatchev Hydrothermal Field, located at the Mid-Atlantic Ridge (Gennerich and Villinger, 2011). Sea floor pressure measurements at this site were made in order to monitor the magmatic and hydrothermal activity of the field which might express themselves as changes in sea floor pressure either due to subsidence or uplift or by tremor-like signals related to hydrothermal processes in the subsurface. The third and fourth records (CORK1 and CORK2) come from a so called CORK (Becker and Davis, 2005) installed at the sea floor off Vancouver Island. A CORK (Circulation Obviation Retrofit Kit) is a sea floor installation which is placed on top of a drill hole and isolates the hydrological -and pressure -regime inside the drill hole from the ocean. The main purpose of this installation is the long-term monitoring of pressure signals inside the drill hole in order to identify either slow earthquakes i.e. long period changes in the sub sea floor stress field or the response of the formation to seismic events which reveal the hydrological and permeability structure of the oceanic crust (e.g. Davis et al. (2011)). At every CORK installation sea floor pressures are recorded in addition to the downhole pressures to provide a local pressure reference signal.
In all cases (MAR, CORK1 and CORK2) pressures were recorded with high-resolution absolute pressure sensors (http://www.paroscientific.com/ uwapp.htm) with a resolution of 7 P a which is about 7 mm equivalent water hight change. More details on location and sample intervals can be found in table 1. The classical methods Harmonic and Wavelet Decomposition are well known. Therefore we have chosen them to have a comparison for the new methods Empirical Mode Decomposition and Sparse Decomposition.
All methods have in common that they seek for a new reprensentation, as a superposition of several patterns, of the data, in most cases by basis transformation.

Harmonic Decomposition
The Harmonic Decomposition uses the Fourier Transform with its efficient implementation as Fast Fourier Transform (FFT). It is known since almost fifty years and used in many data processing routines. The basic idea is to transform the given time signal into the frequency space. In other words we are looking for a reprensentation with sinusiod pattern with different frequencies. We refer to Gröchenig (2001) as a reference for a detailed introduction to Fourier Analysis. A much shorter introduction of the Fourier Transform is given in nearly every book about signal analysis, like Stark (2005).
Decomposition of our time series with the help of Fourier Analysis starts with a FFT. As we know the frequencies and amplitudes of the tides from theoretical considerations and from observations, we can decompose the data into several components and remove the unwanted and deterministic ones. The remaining spectrum is transformed into a time series which contains only the non-tidal components. Another technique for decomposing the data is the Wavelet Decomposition which uses the Wavelet Transform. It is not as old as the Fourier Transform but it is also known very well. Like the Fourier Transform, it transfers the given time signal in another space. This time the basis vectors are scalings and translational displacements of a basic pattern, called mother wavelet, hence in this space the coefficients encode when an effect is measured and how long this effect was. Therefore we can again decompose our data in features of a short and long period of time. Just like for the Fourier Transform there are fast implementations for the Wavelet Transform. For further informations about wavelets see Louis et al. (1997) or Stark (2005).

Wavelet Decomposition
First of all we have to choose the mother wavelet and a number of levels in which we want to decompose our signal. Unlike the Fourier Transform where the orthogonal functions are pre-defined, we have to choose the mother wavelet a priori. If we have extra knowledge about the data, we can improve the results by choosing a wavelet which is 'similar' to the data or rather the features we would like to extract. In our case the Wavelets Daubechies 10 -Daubechies 40 (often abbreviated by db10 and db40) fit the tidal components very well. After performing the Wavelet Transform with these wavelets, we obtained the best results by using db40, which is shown in figure 1.

Empirical Mode Decomposition
The third method we would like to introduce is the Empirical Mode Decomposition and its enhancement the Ensemble Empirical Mode Decomposition (EEMD). The EMD is a new method, invented by Huang et al. (1998), for decomposing a time signal. Since it is not as basic as the Fourier and Wavelet Transform, we present the algorithm here. The idea is to decompose the given time signal into a finite number of Intrinsic Mode Functions (IMF), which are functions which satisfy two conditions: 1. The number of extrema and the number of zero crossings must differ at most by one. 2. The mean value of the upper and lower envelope is zero at any time, where the upper envelope is computed by interpolating the maxima and the lower envelope by interpolating the minima.
The task of the EMD is to find these IMF's and is done by the following sifting process, also shown in figure 2.
1. Find all extrema of the given data. 2. If the number of extrema is one or less, we have found all IMFs and terminate the algorithm. 3. Compute the upper and lower envelope by interpolation the maxima and minima and the mean of these.
4. If the mean value is zero, we have found an IMF. Start the sifting process again with the data substracted by this IMF. Otherwise start the sifting process again with the data substracted by the mean.  Also the EMD can be seen as a basis transformation, but this time the patterns, which are the IMFs, depend on the data.
As we have seen we have done no a priori choices but choosing the interpolating scheme, which is predefined by cubic splines. Since abstracting an IMF reduces the number of extrema this algorithm terminates for every finite time signal. A disadvantage of this method is that it is empirical and has no solid theoretical foundation. Compared to the Fourier and Wavelet Transform the computing effort to decompose the data by EMD is higher but still tolerable. A detailed introduction to EMD is given in Huang et al. (1998).
A challenge in decomposing time series is to prevent mode mixing. Phenomena of similar time scale should be in the same mode (here: IMF) and vice versa phenomena with a totally different scale are expected to have a different mode. For this purpose Wu and Huang suggested in 2009 a noise assisted data analysis method, called EEMD (Wu and Huang, 2009). For a given signal white noise is added to the signal and then decomposed using the EMD. At the end -after numerous trials -we take the mean of the IMF's. "By adding finite noise, the EEMD elimated largely the mode mixing problem and preserve physical uniqueness of decomposition. Therefore, the EEMD represents a major improvement of the EMD method." (Wu and Huang, 2009). Of course this is more time consuming than the usual EMD and we have to check if this is worthwhile in our application or not.

Sparse Decomposition
The last method we would like to present is the Sparse Decomposition. We assume that the given data is a superposition of some processes. Then we can find these by minimizing the residual where k 1 , . . . , k n are the possible patterns. Writing k 1 , . . . , k n as the columns of a matrix K, then this is the same as The Fourier and the Wavelet Transform can also be written as such a minimization problem by choosing the patterns as harmonics or wavelets respectivly. The advantage compared to the Fourier and Wavelet Transform is that we are not restricted to only one basis to find our decomposition, but we can incorporate several bases, which is called a dictionary. For our purposes we have chosen a dictionary with translational displacements and scalings of the pattern in figure 3, hence we combine the capability of the Fourier and Wavelet Transform. Furthermore, we can also add any other pattern to increase the physical meaning of the decomposition.
We are looking for a solution which has a small residual and is sparse, i.e. it uses only a few patterns. A decomposition of the data into only a few patterns is likely to have physical meaning, especially when the patterns are chosen according to physical effects. This can be achieved by minimizing see Daubechies et al. (2004). The last term x 1 , called penalty term, is the sum of the absolute values of x. The notion of Sparse Decomposition is also investigated in an applied manner in Chen et al. (1999).  Lee et al. (2007), to minimize these functional.
The choice of the dictionary is an advantage and disadvantage at the same time. If we have special knowledge of our data, like in most cases, we can improve the decomposition by choosing 'good' pattern. On the other hand an algorithm which requires many input parameters is often difficult to handle. A disadvantage is that the algorithm is much more demanding and complex compared to the other methods. We will see later on that this is worthwhile.
Further information and the full algorithm is given by Jin et al. (2009).

Results
In this section we present and discuss our results. First of all we have to mention that the used data is preprocessed by subtracting the mean value, so the important features are emphasized.
Our results for Harmonic and Wavelet Decomposition are obtained by using Matlab R 's functions fft and wavedec respectivly. For EMD and EEMD we have used the algorithms by Rilling (2007) and Wu (downloaded 04/2011). The RFSS implementation, used for the Sparse Decomposition, was according to Schiffler (2009). All algorithms can be found on the world wide web, see our references.
The tidal extraction from the data sets is done very well by all algorithms, hence this does not distinguish the methods and is not discussed in the following.

Decomposition of SYN
The results of the decomposition of the synthetic data are shown in figure  4. Since it is a synthetic data set we can compare the computed decomposition by the real one to evaluate their quality.
As we see the methods' ability to decompose this data varies substantially. Harmonic and Wavelet Decomposition are able to decompose the data into features of three different types. The noise and the short effects are in the same component. The methods EMD and EEMD are not able to extract the high frequency features from the signal. All algorithms were able to separate the long-term effects from the rest but failed to distinguish between the trend and the step.
Harmonic and Wavelet Decomposition as well as the Sparse Decomposition correctly detect the short time features as well in time as in amplitude. Only large boundary effects in the results obtained by Harmonic and Wavelet degrade their quality. Methodically we can not obtain boundary effects in the results of the Sparse Decomposition, since we have chosen our dictionary to contain local and global pattern. Hence local features do not have to be reconstructed by global pattern. Additionally the RFSS is not based on filtering, which often causes boundary effects. Overall the Sparse Decomposition performs best in detecting the short time features.
The last aim was to extract the long time effects. All algorithms perform quite well, but again the boundary effects degrade the Harmonic and Wavelet results. Sparse Decomposition is capable of extracting the trend and the step very well whereas EMD and EEMD reproduce only the trend satisfactorily.

Decomposition of MAR
The next data set to test is the one from the Mid-Atlantic Ridge and the results can be seen in figure 5. This time all algorithms provide a good decomposition into the short-, medium-and long-period features. Only the Sparse Decomposition is able to extract also the noise from the short-period components. There are just a few peaks visible in the short-period decomposition by Harmonic Decomposition and EMD which are probably aliased local eartquake signals. These are also extracted very well by the Sparse Decomposition. The short-period features given by Wavelet show again some boundary effects. The decomposition by the EEMD has a basic noise level which is much too high. This is a result of the white noise added in every step of the algorithm but which is clearly not faded away with 100 runs of the EMD.
The trend and long-term feature extraction of the five methods are all nearly the same. In all cases pressures decrease initially over the first week and then increase by about 0.4 kP a over the rest of the time window. The Wavelet results differ from the others by significant boundary effects.

Decomposition of CORK1
The results of the third data set, CORK1, are given in figure 6. This time every method is again capable to decompose the data into the three main features. In this data set there are two short time effects whose amplitudes are a lot higher than the amplitudes of the other effects so we have also showed the short period effects zoomed in.
The similarity between the short period features detected by Harmonic and Wavelet Decomposition is worth mentioning. The EMD and EEMD detect these features very similar in time but differ in detecting the amplitude. Also the EEMD is not able to detect short period features with a small amplitude since the added noise prevents this. The Sparse Decomposition is able to detect these features as well and separates them additionally from the noise.
The trends detected by all methods are again quite similar. Only the Wavelet trend has huge boundary effects. The behaviour of Harmonic Decomposition at the boundary could be interpreted as a boundary effect, but we guess this is not the case, since Sparse Decomposition predict the same and is methodically unaffected by boundary effects. The same behaviour can be obtained from the EEMD's trend.

Decomposition of CORK2
For the last data set the results are given in figure 7. Since this is a long data set and the sampling interval is only 60 min we focus on the long period effects. On the other hand we can not expect short time features with a shorter duration than 60 min, like earthquakes, to appear in this data set, hence the short time components obtained from this data set has to be interpreted very carefully.
Like with the dataset SYN, which sampling interval was also 60 min, EMD and EEMD are not capable to decompose the features with higher frequencies than the tides. Contrary this is done very well by Harmonic, Wavelet and Sparse Decomposition. There are one huge and some smaller short period signals associated to earthquakes, which are again detracted from the noise by Sparse Decomposition.
The trends detected by all methods look quite similar. In any case we obtain first a downdrift of 3.5 kP a over 2 years, followed by an updrift the same amount in the next seven years. As seen at the other data sets the boundary effects are very high at the Wavelet Decomposition.

Discussion
A summary of the observations described in the previous sections is given in table 2. The evaluation of the different decomposition methods was based on the following more or less qualitative criteria: • How successful was the algorithm in decomposing the signal into a long and short period components?
• Did the algorithm find a short period event in the presence of background noise?
• Does the algorithm create large effects at the boundaries of the time window?
• How much CPU time is needed for the decomposition?
From looking at table 2 one can conclude that none of the used methods for decomposition is perfect in every aspect. Harmonic and Wavelet are able to detect the short period features and perform also quite well in detracting the trend but their results, especially the results of Wavelet, show massive boundary effects. Because of this there is a high uncertainty if the shown decomposition is physically reasonable or not. On the other hand their computing efficiency is so high that the Harmonic and Wavelet Decomposition is nearly not restricted by the length of the given data.
The performance of EMD and EEMD is directly opposite to Harmonic and Wavelet. The EMD and EEMD perform very well on detracting the tides and show only small influences of boundary effects but their capability of separating components with higher frequencies than the tides is restricted. At least when the data is recorded with a sampling interval of 60 minutes. Especially the EEMD fails because the added noise does not fade away in our experiments. Overall we have seen in every data set that the large additional computational effort of the EEMD compared to the EMD is not worthwhile for the analysis of sea floor pressure data.
Very impressive is the capability of the Sparse Decomposition. It was able to detract the short period components as well as the large period components Computing efficiency • ± ± in every case. Contrary to the other methods, it was also able to detract the noise from the meaningful short period components. A hugh advantage is also that the Sparse Decomposition does not have any boundary effects. Only the computing efficiency needs to be improved.

Conclusion
To conclude our investigation we have to state that no method is perfect for every time series. For our data sets we got the best results by using the Sparse Decomposition. But at the moment it is not recommendable for time series with more than 200,000 measurements. For this kind of time series we recommend the EMD for long period contributions and the Harmonic Decomposition for the short ones. EEMD fails to improve the EMD in detecting and is not recommended due to ist large computational needs. We obtained sometimes good results using the Wavelet Decomposition but they were never better than the results obtained by the Harmonic Decomposition, even in detecting earthquakes which is classically done by Wavelets.
It is obvious that the comparison of the computing efficiency is somewhat unfair as algorithms to calculate the FFT and Wavelet Transform are highly optimized whereas algorithms for EMD, EEMD and especially RFSS are not yet written for speed. However it is very likely that FFT and Wavelet Transform will always be faster however the difference to EMD, EEMD and RFSS will most likely shrink in the near future due to the improvement of the algorithms and maybe by developing parallel algorithms for them.


Error Detection for Post-editing Rule-based Machine Translation

The increasing role of post-editing as a way of improving machine translation output and a faster alternative to translating from scratch has lately attracted researchers’ attention and various attempts have been proposed to facilitate the task. We experiment with a method to provide support for the post-editing task through error detection. A deep linguistic error analysis was done of a sample of English sentences translated from Portuguese by two Rule-based Machine Translation systems. We designed a set of rules to deal with various systematic translation errors and implemented a subset of these rules covering the errors of tense and number. The evaluation of these rules showed a satisfactory performance. In addition, we performed an experiment with human translators which confirmed that highlighting translation errors during the post-editing can help the translators perform the post-editing task up to 12 seconds per error faster and improve their efficiency by minimizing the number of missed errors.

Introduction
Since its introduction Machine Translation (MT) has improved considerably and recently it has started gaining recognition in the translation industry. However, translations of MT systems have not yet reached the level of human quality. One of the ways of improving MT outputs is by performing the task of post-editing (PE), which nowadays, is becoming a common practice. According to Suzuki (2011), "to make the best of machine translation humans are urged to perform post-editing efficiently and effectively". As a starting point, in this study, we focus on Rulebased Machine Translation (RBMT), since we believe these systems produce errors in a more systematic manner, which makes capturing these errors more feasible.
In their outputs RBMT systems tend to repeat the same mistakes. Therefore, while post-editing, humans are forced to correct the same mistakes repeatedly and this makes the post-editing task draining and monotonous. In this study we aim at investigating a way of providing support for the post-editors by designing linguistically motivated rules for error detection that could be integrated into a post-editing tool. Our hypothesis is that these rules could help post-editors by indicating problems in the output which need to be fixed, and as a consequence help minimise post-editing time.
Recent work has addressed error detection and its visualization following shallow, statistic approaches for the error detection and focusing mostly on SMT. Koehn and Haddow (2009) introduced a tool for the assistance of human translators with functionalities such as prediction of sentence completion, options from the translation table and post-editing. Experiments with a Statistical Machine Translation (SMT) system and ten translators revealed that the translators were fastest when post-editing with the tool. Xiong et al. (2010) proposed the integration of two groups of linguistic features, i.e. lexical and syntactic features, into error detection for Chinese-English SMT. These features were put together with word posterior probability features using a classifier to predict if a word was correct or incorrect. Various experiments were carried out and the results revealed that the integration of linguistic features was very useful for the process of error detection because the linguistic features outperformed word posterior probability in terms of confidence estimation in error detection. Bach et al. (2011) proposed a framework to predict SMT errors at word and sentence levels for Arabic-English translation. They used a large dataset with words and phrases that had been previously post-edited as features for training the error detection model. As part of their experiments they also introduced a visualization prototype for errors in order to improve the productivity of posteditors by helping them quickly identify sentences that might have been translated incorrectly and need correction. Their method was based on confidence scores, i.e. predictions at phrase and word level for good, bad and medium quality translations. The results showed that the MT error prediction accuracy has increased from 69.1 to 72.2 in F-score.
While our goal is very similar to that of these papers, we address the error detection of the MT output from a more linguistically motivated perspective. We derive linguistic rules from an error analysis of Portuguese-English sentences from two text domains and two variants of Portuguese (European and Brazilian) translated by two RBMT systems -Systran 1 and PROMT. 2 We consider detection rules to be a practical and potentially helpful solution for RBMT systems, since these are known for making repetitive mistakes. In other words, if a system cannot cope with some specific language phenomenon, for example, recognizing a certain word or a 1 http://www.systran.co.uk/ 2 http://www.promt.com/ construction in a source language (SL), it is likely to keep making the same mistake whenever that phenomenon is encountered. In addition to understanding whether we can successfully detect the errors with these rules and whether highlighting them can help human translators, we are interested in assessing how general the rules (and the errors made by the systems) are across MT systems of the same type (rule-based) and across significantly different text domains.
In the remainder of this paper, we first describe our linguistic analysis (Section 2), to then describe the implementation of the rules (Section 3) and present a post-editing experiment with human translators (Section 4).

Linguistic Analysis
For the linguistic analysis we randomly selected 300 Portuguese sentences from two corpora: 150 sentences from Europarl (Koehn 2005), which is a collection of parliamentary speeches representing European Portuguese, and 150 from Fapesp , which is a collection of scientific news for Brazilian Portuguese. The minimum length of Europarl sentences was 3 words, maximum -115, average -27; whereas the minimum length of Fapesp sentences was 3 words, maximum -88, and average 31. We then translated these sentences into English using Systran and PROMT, totalling 8,455 words.
The linguistic analysis was carried out as follows. First, we manually analyzed each sentence, identified various translation errors and assigned them to different error categories. We identified errors by correcting the sentences until they were of acceptable quality but at the same time trying to keep them as close as possible to their machine translated versions. In cases when errors co-occurred, i.e. two categories could have been applied for the same issue, these were counted twice. The error classification introduced in this paper was inspired by the classification schemes introduced by Flanagan (1994), Farrús (2010. Table 1 presents the error classification. The current analysis showed that the Portuguese-English translation outputs contained the most frequent and typical language-independent MT errors, such as "Incorrect lexical choice", "Inflectional errors", "Untranslated words". On the other hand, we also identified some languagespecific errors, typical to the Portuguese-English language pair. Table 2 illustrates a subset of these: the most frequent error categories identified during the linguistic analysis. An interesting example of language-specific category is the "Incorrect translation of Portuguese weekdays". In Portuguese, names of weekdays except sábado (Saturday) and domingo (Sunday) are compounds made of two individual words: a numeral and a noun. For instance, segunda-feira (Monday), quinta-feira (Thursday), etc. However, both systems failed to produce correct translations for these compounds. Instead, Systran produced a literal translation for both individual words (quinta-feira was translated as fifth-fair); whereas, PROMT translated them as equivalent weekdays in English but also added a verb phrase which was not present in the source text and did not make sense in the given context (quinta-feira was translated as Thursday-sells at a fair).
Based on the frequency of the errors in each category and on an analysis on the feasibility of creating rules for them, we selected 20 categories (marked * in Table 1) for which we designed the rules that later could be implemented and used to support the post-editing task.
We created the rules by analysing the errors of the target language (TL) sentences and comparing these to their corresponding SL sentences. In total, we produced a set of 40 contrastive rules which covered various problematic linguistic issues. For instance, if the systems made mistakes while dealing with present, past and future verb tenses and chose incorrect tenses for the TL translations, rules were designed for these specific issues. It is important to emphasize that although the two variants of Portuguese are considerably different, we focused on creating the rules that apply for both.
Rules are of the if-then type: if in Portuguese <...>, then in English <...>. For example, "If the verb X is in the past simple tense in Portuguese, then in English the translation of the same verb X must be in the past simple tense".
We then selected a subset of these rules which could be implemented for a pilot study. We took the following rules dealing with tense and number errors for the inflectional category due to the availability of the necessary pre-processing tools for the two languages and because they represented one of the most frequent error types in the output sentences: If the noun X is in singular/plural in Portuguese, the translation of the noun X should also be in singular/plural in English.
If the verb X is in the 1 st /2 nd /3 rd person singular/plural in Portuguese, the translation of the verb X should also be in the 1 st /2 nd /3 rd person singular/plural in English; If the verb X is in the infinitive/ present simple tense/past simple tense/future simple tense in Portuguese, the translation of X in English should also be in the infinitive/ present simple tense/past simple tense/future simple tense; If the Portuguese construction contains "ir (to go) + infinitive", then the English translation should be the future simple tense "(subjective pronoun) + will + simple verb/(subjective pronoun) / to be + going to + infinitive" (e.g. vou falar = I will speak; vamos verificar = we are going to check); If the Portuguese verb construction contains "não + V prs + 3 rd person sg", the English equivalent should be the construction "(subjective pronoun) + auxiliary verb + 3 rd p. sg. + not + infinitive" (e.g. não fala = (subj. pronoun) does not speak); If a Portuguese verb phrase is of progressive aspect, i.e. "estar + a + infinitive", it should be in the present continuous tense in English "subjective pronoun + the form of to be + V ing " (e.g. está a falar = (s)he is speaking).
If the Portuguese verb construction is the following "Vprs +3 rd p. sg. + a + infinitive, in English it should be the English construction V prs +3 rd p. sg. + infinitive" (e.g. ajuda a conter = helps to contain).

Evaluation of the Categories and Rules
In order to analyse how systematic the selected categories are and check the coverage of the rules created and the ones selected for the implementation, we performed two small scale experiments on two new datasets. For the first experiment we randomly selected 100 additional sentences from the original corpora: 50 from Europarl and 50 from Fapesp, and translated them using Systran and PROMT. The output of both datasets resulted in 5,676 words. The minimum length of Europarl sentences was 3 words, maximum -68, average -26; whereas the minimum length of Fapesp sentences was 3 words, maximum -62, average -30.
During the analysis, we fixed the translations to identify translation errors as before and assigned them to our error categories. The results revealed that out of our 30 categories, 26 were present in the new dataset, despite its smaller size. Only four categories -"Missing if-clause", "Incorrect adjective translation", "Missing subjects/predicates" and "Incorrect translation of Portuguese weekdays" -were not found in the new dataset. It is also important to emphasize that no new categories were identified in this dataset. From these results it can be concluded that the error classification for the Portuguese-English language pair in Table 1 is representative of these two text domains and RBMT systems.
Furthermore, we checked the frequency of all errors and in particular those of the inflectional category. The translations in the new dataset contained 393 errors, out of which 54 were attributed to the inflectional error category. To verify the coverage of the rules and in particular of those dealing with inflectional errors, we computed the percentage of errors in the new dataset that could be dealt with by the rules derived for the original dataset. The coverage was computed by dividing the number of errors for which there were no rules created by the total number of errors. The results showed that the coverage of the whole set of rules was 98.21%, while the coverage of the rules of the inflectional category was 92.59%.
For the second evaluation experiment we randomly selected 100 sentences from two new corpora: 50 sentences from CETEMPublico 3 which covers news in European Portuguese, and 50 sentences from CETENFolha 4 which covers news in Brazilian Portuguese. The minimum length of CETEMPublico sentences was 6 words, maximum -58, average -27; whereas the minimum length of CETENFolha sentences was 11 words, maximum -51, average -24.
We translated the sentences using both RBMT systems, resulting in 5,039 words. Once again, we checked the coverage of the categories and rules. The results revealed that all 30 categories introduced in the error classification were present in this dataset and no new categories were identified. In total, the output sentences contained 513 errors, with 39 of them of the inflectional category. The coverage of the whole set of rules was 93.67%, while the coverage of the inflectional rules selected for implementation was 87.18%.
From these results we can conclude that it is possible to systematically categorise errors in RBMT systems and that linguistic rules with sufficient coverage can be created in new datasets for such categories.

Implementation and evaluation of rules
A few pre-processing tasks were performed in order to obtain certain linguistic information necessary for the implementation of the rules, such as a part-of-speech, lemma, morphological information (number and gender). First we performed word alignment between the Portuguese-English sentence pairs by using the aligner GIZA++ (Och and Ney, 2003). GIZA++ aligns sentences at the token level producing in this case four pairs of the alignment datasets. As some incorrect alignments were found in the sentences, we manually corrected them in order to obtain a "clean" dataset, that is, a dataset that allows evaluating the rules themselves, isolating any effect of low quality word alignments. Each aligned sentence pair was checked and the necessary corrections were performed, i.e. some incorrect aligned links were deleted, while other necessary links were inserted.
The sentences were also parsed in order to obtain their morphological information. For this purpose we used the parsers Palavras 5 for Portuguese and ENGCG 6 for English, both available online. The Palavras parser was reported to have 99.2% correct morphological tagging (Bick, 2000) and ENGCC was reported 99.8% recall in morphological tagging (Voutilainen and Heikkilä 1994). Any other parser producing morphological information could in principle be used. For this pilot study, seven rules dealing with errors of tense and number agreement were implemented using Python.
We then analysed the performance of the rules manually, i.e. each output sentence was checked individually to find out how many translation errors the system identified correctly, how many were missed and if it identified any false positives.
Precision, Recall and F-measure were calculated. The results are shown in Table 3.
The system found a high number of false positives in the output sentences. The main reasons for this is parser errors and inconsistencies and the fact that often more than one rule can be applied and no rule precedence scheme was defined at first. An example of a case where multiple rules could be applied is the following Portuguese construction "the present tense form of ir (to go) + infinitive". It expresses a future action and usually is translated into English using the future simple tense i.e. vou / vais / vai / vamos / vão + falar = I / you /(s)he / we / they will speak. However, when the system encountered this construction, it identified the correct English translation as incorrect. For example: (1-PT): Vou verificar se nada de isso foi efectivamente feito.
(1-EN): I will check if nothing of that was effectively an act.
This happened because the first rule processed by the system (by default) stated that "if the verb X is in the present simple tense, the English translation of the same verb X should be in the present simple too". Therefore, when the system encountered vou verificar, it did not recognize the pattern of vou + verificar as a future tense construction but rather only the verb in the present simple tense vou and in the English side it expected to find I go + check. However, further in the list there was a rule explaining this specific pattern and indicating the correct translation. Defining rule precedence schemes is not a trivial problem. While this was possible for our small set of rules, this issue will require further investigation as this set grows to incorporate other linguistic phenomena. . The largest number of false positives occurred due to the flaws of the parsers. Example (2) illustrates a false positive case due to errors of the parser. The system flags the English verb comments (3 rd person singular) as an error although it was correctly translated. This happened because the parser identified comments as a plural noun, and not as a verb. Therefore, when the system found comenta (comments) as a verb in present tense (3 rd person singular), it expected to find a verb in the English side. Some examples when the rules correctly detect translation errors include the incorrect tense and number translation (4) and the incorrect translation (5), i.e. a noun instead of a verb:
But in that moment we were covering (we covered) almost only projects with support of the Fapesp, which was not the case. The implementation and the evaluation of the system showed that it is possible to have a working rule-based system which can detect certain translation errors using linguistic rules. Although in the current version some errors still remain to be captured due to their complexity and the limitations of the approach (the rules cover a small range of translation problems and only a sentence boundaries), we believe that error detection based on linguistic information is a promising direction to improve MT quality. While having a large number of false positives can still be an issue, this is less problematic than missing true errors. Although further experiments are necessary in that direction, our preliminary analysis in Section 6 indicates that translators can miss certain errors if these are not highlighted.

Experiments with Human Translators
A post-editing experiment was carried out with human translators in order to determine the usefulness of having errors highlighted in the RBMT output. Here we aim to investigate whether it is possible to help the human translators perform the task of post-editing faster and more efficiently when the MT errors are detected and highlighted.
To proceed with the experiment, we used the post-editing system PET (Aziz et al., 2012). 7 The tool gathers various useful effort indicators while post-editing is performed. We measured the time translators spent post-editing sentences. The tool also renders HTML, so highlighting errors was trivial.
For the test set in this experiment we randomly selected 60 sentence pairs from both Europarl and Fapesp. These sentences were then manually annotated, i.e. translation errors in the English as well as their corresponding source segments in the Portuguese sentences were marked. We resorted to manual highlighting rather using the errors detected by our system due to its limited coverage (only certain inflectional errors) and its relatively low performance.
After the manual error annotation, the sentence pairs were given to six human translators. We divided the test set into two parts, i.e. 30 sentence pairs with no errors highlighted and 30 sentence pairs with errors highlighted. All translators postedited sentences with and without highlights. As the sentences were randomly selected, they contained different numbers of mistakes. Therefore, we analysed time on a per error (and not per sentence) basis. The errors were highlighted using different colours, each colour representing an individual error type from the set of 20 categories.
We produced guidelines in order to help human translators perform their task by explaining in detail how to use the post-editing tool and how they were expected to perform the task. All participants were native speakers of Portuguese. They were fluent in English and had some experience with translation tasks. European Portuguese translators were given European Portuguese sentences, whereas Brazilian translators post-edited Brazilian Portuguese sentences. We asked translators to post-edit machine translated sentences by making as few changes as possible and in such a way that the sentences would be grammatically correct and understandable. For sentences with errors highlighted, translators were also asked to evaluate the usefulness of having errors highlighted by choosing one of three possible options: Very useful.
Some of them were useful.
Not useful at all.
Translators were given one week to perform the task.

Results
were computed for three main aspects: the number of correctly identified and missed errors, the time taken to post-edit sentences in both datasets and the translators' evaluation of the usefulness of the highlights.
We manually analysed each translator's work by comparing their post-edited sentences with the previously annotated sentences. The results revealed that in the test set of the non-highlighted (NH) sentences the range of correctly identified errors by translators varies from 90% to 95.56%. The results for the sentences with the highlights (WH) showed a noticeable improvement, i.e. from 95.24% to 100%. It can thus be concluded that the performance of the translators improved when post-editing sentences with errors highlighted as the number of errors missed was significantly reduced. The reasons for translators missing errors in the non-highlighted sentences could be various, including the fact that perhaps the translators got used to having errors highlighted and the fact that some errors were not very significant for adequacy purposes, for example an incorrect extra article. However, the experiment showed that highlighting errors can be very helpful in attracting the attention of translators.
In order to find out if there was any significant difference between performing the two tasks in terms of time, we counted each translator's average time per error for both datasets. To get these estimates we divided the total time spent for postediting each dataset (WH and NH) for each translator by the total number of errors in that dataset. The results are shown in Figure 1.
As it can be seen from Figure 1, translators' time per error NH and WH varies from 33 to 23 seconds (Translator 2), from 43 to 31 seconds (Translator 5) and from 27 to 17 seconds (Translator 6). These translators post-edited the WH sentences 10-12 seconds faster than the NH sentences.
For the rest of the translators, the results were less significant. The time of Translators 3 and 4 for the WH sentences was slightly better than for the NH sentences, varying from 22 to 24 seconds, and from 17 to 19 seconds respectively. On the other Figure 1. Time per error taken to post-edit the sentences hand, Translator's 1 time was 36 seconds for the NH sentences and 35 seconds for the WH sentences. This could be explained by the fact that these translators missed a considerable number of errors, thus it is not surprising that there was no improvement in their results in terms of time. Although these improvements seem to be modest, we believe that when one extrapolates them to thousands of sentences with potentially dozens of errors, having errors highlighted can make a considerable difference in productivity.
The final factor which we analysed in this experiment was the opinion of the translators about the usefulness of the highlighted errors. As mentioned before, after post-editing each sentence with highlights, translators were asked how useful the highlights were. The results show that in 68% of the cases the highlights were found to be very useful, in 27% of the cases -some of them were found to be useful, and in only 5% they were found not to be useful at all.
The results of the experiments with human translators showed that the having errors highlighted can help human translators perform the task of post-editing faster and more efficiently. The highlights were also positively evaluated by translators.

Conclusions and Future Work
We have shown that one can systematically categorize translation errors which RBMT systems make and create linguistic rules for the error categories identified. We also showed that the rules apply across MT systems and text domains, and that one can implement a system detecting certain translation errors on the basis of those rules. Having a linguistically motivated approach for the error detection has also been shown to be helpful for the post-editing task. The results of a postediting experiment with human translators revealed that the highlighted errors in the RBMT output helped to perform the PE task faster up to 10-12 seconds per error and improve translators' efficiency in identifying errors by reducing the number of errors missed. In addition, the highlighted errors were positively evaluated by the translators. Thus it can be concluded that the approach for post-editing based on the error analysis and the automatic error detection is promising and should be elaborated further.
The major challenge for future work is to scale up the approach. In order to implement the remaining rules, more levels of linguistic preprocessing will be necessary, such as named entity recognition. More robust ways of dealing with flaws in linguistic processors (such as the current parser issues) are also necessary.