extfieldsofstudy:
Computer Science
Mathematics

text:
TDCS-based Cognitive Radio Networks with Multiuser Interference Avoidance

For overlay cognitive radio networks (CRNs), transform domain communication system (TDCS) has been proposed to support multiuser communications through spectrum bin nulling and frequency domain spreading. In TDCS-based CRNs, each user is assigned a specific pseudorandom spreading sequence. However, the existence of multiuser interference (MUI) is one of main concerns, due to the non-zero cross-correlations between any pair of TDCS signals. In this paper, a novel framework of TDCS-based CRNs with the joint design of sequences and modulation schemes is presented to realize MUI avoidance. With the uncertainty of spectrum sensing results in CRNs, we first introduce a unique sequence design through two-dimensional time-frequency synthesis and obtain a class of almost perfect sequences. That is, periodic auto-correlation and cross-correlations are identically zero for most circular shifts. These correlation properties are further exploited in conjunction with a specially-designed cyclic code shift keying in order to achieve the advantage of MUI avoidance. Numerical results demonstrate that the proposed TDCS-based CRNs are considered as preferable candidates for decentralized networks against the near-far problem.

Index Terms
Cognitive radio network, transform domain communication system, multiuser interference, periodic correlation function.

I. INTRODUCTION
Due to the scarcity of available spectrum, cognitive radio (CR) is considered to be a promising paradigm to provide the capability of using or sharing the spectrum in an opportunistic manner [1]. Multicarrier modulations are preferable candidates for realizing CR applications in which arbitrarily selected subcarriers are disabled to avoid using the occupied spectrum bands [2].
Following a general analytic framework that is spectrally modulated and spectrally encoded [3] [4], various multicarrier waveforms can be generated based on CR user needs, e.g., orthogonal frequency division multiplex (OFDM) and multicarrier code division multiple access (MC-CDMA) [5]. As another type of overlay CR, transform domain communication system (TDCS) has been proposed to support reliable communications with low spectral density through spectrum bin nulling and frequency domain spreading [6]- [9]. Hence, the TDCS becomes attractive as a smart anti-jammer transmission scheme when some available spectrum bands are occupied by intentional jammers [10].
To achieve multiple access capability, CR networks (CRNs) share all available resources by the different protocols, e.g., time division multiple access or orthogonal frequency division multiple access [11]. If the code dimension is interpreted as a part of the spectrum space, new opportunities for spectrum usage can be created at a given time based on spectrum spreading [12]. Since secondary users in CRNs have to identify the presence of primary users and vacate the occupied spectrum bands immediately whenever primary users are active, the spectrum opportunity in this manner naturally results in the uncertainty of spectrum utilization pattern.
Similarly in traditional TDCS-based CRNs, when each user is assigned a specific pseudorandom polyphase sequence [17], multiuser interference (MUI) becomes a main factor of bit error rate (BER) performance degradation due to the non-zero crosscorrelations between any pair of TDCS signals. This is especially true in decentralized wireless networks in which the phenomenon known as near-far effect has been seen to disrupt communications.
With the uncertainty of spectrum utilization pattern in CRNs, a novel framework of TDCSbased CRNs is presented in this paper to achieve MUI avoidance from the viewpoint of sequence design. Instead of only frequency spreading used in traditional schemes, we first introduce a sequence design through two-dimensional time-frequency synthesis. It is shown that if two short sequences are carefully chosen, a class of almost perfect Kronecker sequences is obtained. That is, periodic autocorrelation and crosscorrelation functions (ACF/CCF) are identically zero for most circular shifts. Importantly, such correlation properties are always guaranteed for any spectrum utilization pattern in CRNs. In addition, since the periodic CCF between any pair of TDCS signals is highly dependent on cyclic code shift keying (CCSK), sufficient attention should be paid for the joint design of almost perfect sequences and modulation schemes. Accordingly, a specially-designed CCSK over a limited shift range is addressed in order to guarantee the mutual orthogonality of TDCS signals for the advantage of MUI avoidance.
This paper is organized as follows. Section II reviews TDCS multiple access applications in order to briefly explain the disadvantages of traditional TDCS-based CRNs. Section III first presents the sequence design through two-dimensional time-frequency synthesis. Then, a specially-designed CCSK is addressed to guarantee the mutual orthogonality of TDCS signals for the advantage of MUI avoidance. In Section IV, multiuser capability and aggregated throughput are discussed respectively. Finally, simulation results are presented in Section V.

II. OVERVIEW OF TDCS MULTIPLE ACCESS
In CR systems, the entire spectrum band is divided into N spectrum bins and a spectrum marking vector, S = {S(0), S(1), · · · , S(N − 1)}, is used to indicate the status of spectrum bins. For example, the value of S(k) is set to 1 (or 0) if the spectrum sensing output for the k-th bin is smaller (or larger) than a given threshold. We assume the set of N C available spectrum bins as Ω C , i.e., S(k) = 1, k ∈ Ω C , and the same spectrum marking vector is obtained by the spectrum sensing facilities on the receiver side.
On the TDCS transmitter side, a spectral vector, B, is obtained by the operation of elementby-element multiplication, i.e., B = S · diag (P), where P = e jm(0) , e jm(1) , · · · , e jm(N −1) is a pseudorandom polyphase sequence, and m(k), k ∈ {0, 1, · · · , N − 1}, is the phase shift for the k-th bin. Then, a fundamental modulation waveform ( where λ = N/N C is a normalization for the transmitted energy. When M-ary CCSK is adopted, the transmitted signal, x, is obtained by shifting b cyclically to the left by τ ∈ {0, 1, · · · , M − 1} places, where · N denote N-point cyclic shift. On the TDCS receiver side, the received signal, r = {r(0), r(1), · · · , r(N − 1)}, is periodically correlated with the replica of FMW to recover data symbols by detecting the correlation peak, which can be performed by using the fast Fourier transform (FFT) to minimize the computational complexity [18]. Since the information on τ is hidden in the background noise by spreading over all available spectrum bins, TDCS signals have a low probability of being intercepted by DRAFT November 21, 2013 unauthorized listeners. More detailed information on the transmission and reception of TDCSs is available in [10].
Let us consider a U-user traditional TDCS-based CRN in which each user is assigned a specific pseudorandom polyphase sequence to share available spectrum resources. A class of polyphase sequences is given by [17] where P i denotes the pseudorandom sequence for the i-th user and e jm i (k) denotes the k-th sequence element of P i . Based on (1), a class of FMWs assigned to multiple users is given by From the previously reported results in [17], we have the periodic CCF between any pair of FMWs (i, j) as follows, where (·) * denotes the complex conjugate and mod (x, y) denotes the remainder of x divided by y.
Observed from (5), it is clear that the MUI always exists in traditional TDCS-based CRNs due to the non-zero periodic crosscorrelations. Especially, the phenomenon known as near-far effect in decentralized wireless networks, such as CR Ad-hoc wireless sensor networks, further aggravates the MUI, leading to significant BER performance degradation. Therefore, the aim of this paper is to discuss how to design TDCS-based CRNs with MUI avoidance.

III. TDCS-BASED CRNS WITH MUI AVOIDANCE
In this paper, a novel framework of TDCS-based CRNs with the joint design of sequences and modulation schemes is presented to realize MUI avoidance. With the uncertainty of spectrum sensing results in CRNs, we first introduce a sequence design through two-dimensional timefrequency synthesis and obtain a class of almost perfect sequences. Then, a specially-designed modulation scheme is discussed in order to achieve the advantage of MUI avoidance. (1), · · · , a(L − 1)} be a polyphase sequence of length L having perfect periodic ACF as follows, [14] ϕ

A. Design of almost perfect FMWs
By taking the sequence, A, and the basis FMWs, b, from (4), we obtain a class of Kronecker sequences, c, constructed through two-dimensional time-frequency synthesis as shown in Fig. 1, According to the correlation property of Kronecker sequences in [19], the periodic CCF ϕ c i ,c j (τ ) between two sequences c i and c j is given by between two sequences u and v of length N as Substituting (6) into (8), we obtain the periodic CCF between two designed sequences c i and c j as follows, Note that, the periodic ACF of the i-th designed sequence is ϕ c i ,c i (τ ).
One particularly valuable property of the designed sequences is that the periodic auto/cross correlation functions are identically zero for (L − 2) N + 1 different values of τ , as shown in Fig. 2. Importantly, the correlation property is independent on the basis FMWs. In other words, it is always guaranteed for any spectrum utilization pattern in CRNs. In addition, even for |τ | < N, both periodic ACF/CCF sidelobes are trivial compared to the periodic autocorrelation mainlobe. Consequently, it is reasonable to consider the designed Kronecker sequences as a class of almost perfect sequences under CR constraints. In the following contents, let us discuss how to utilize the designed sequences in TDCS-based CRNs to achieve the advantage of MUI avoidance. Especially, two scenarios of single-path and multipath fading channels are discussed, respectively.

B. Design of modulation schemes in single-path fading channels
For U-user synchronous TDCS-based CRNs, each user chooses one of the designed sequences in (7) as the FMW. When M-ary CCSK is adopted, the transmitted signal, x i , of the i-th user is derived by shifting the i-th FMW, c i , cyclically to the left by τ i ∈ {0, 1, · · · , M − 1} places, When TDCS transmitted signals from different users pass through different single-path fading channels, the received signal for the i-th user, where γ i,j is the path gain between the i-th and j-th users and n i is the additive white Gaussian noise (AWGN) vector. Following the receiving procedure of traditional TDCS, the received signal, r i , is periodically correlated with the local reference FMW, c i , to obtain The first item represents the periodic ACF of the i-th user's FMW with the effects of the cyclic shift τ i and the path gain γ i,i . Note that there is a desired periodic autocorrelation peak at τ = τ i corresponding to transmitted data symbols. The second item represents the periodic CCF between the i-th user's local reference FMW, c i , and the received signals from other users, {x j , j = i}.
Generally speaking, the second item means the MUI of the i-th user. The third item represents the correlation output of AWGN vector.
From the correlation property of the designed sequences in (9), the interference from the j-th user can be rewritten as follows, For the i-th user, the interference from the j-th user can be eliminated if and only if By generalizing (14), the TDCS-based CRN with MUI avoidance can be achieved if and only if, for the FMW of length LN. However, the shift range of MUI-free TDCS-based CRNs must satisfy the constraints defined in (15), although the designed FMWs are also of length LN. In this paper, the specially-designed CCSK over a limited shift range is termed as partial cyclic code shift keying (P-CCSK).

C. Design of modulation schemes in multipath fading channels
Now we consider the design of modulation scheme in multipath fading channels, of which the channel response can be modeled as a discrete-time finite impulse response denoted as h p , where p ∈ {0, 1, · · · , T max }, and T max is the maximal channel order. Note here that the indexing for calculating periodic correlation functions is based on the modulo operation on the sequence length. This results in the circular operations that can be achieved in practice by introducing cyclic prefix of appropriate length commonly seen in OFDM systems. For the TDCS transmitter shown in Fig. 1, a cyclic prefix, which is a repetition of the last T g ≥ T max samples in a data block, is inserted at the beginning of each transmission data block.
We assume that all transmitted signals in multipath fading channels are same as that in singlepath fading channels given in (10). When passing through multipath fading channels, the received signal of the i-th user after removing cyclic prefix is given by where h i,j p is the p-th path gain between the i-th and j-th users. The received signal, r i , is periodically correlated with the local reference FMW, c i , to obtain The first item represents the periodic ACF of the i-th user's FMW with the effects of multipath fading channels, while the second item represents the MUI from other users also with the effects of multipath fading channels. Focusing on the first item, there are a few periodic autocorrelation peaks in the range of [τ i , τ i + T max ] corresponding to each path of the multipath fading channel.
Similarly with the scenario of single-path fading channels discussed above, the i-th user's receiver can avoid the interference from the j-th user if and only if Hence, we have By generalizing (19), the TDCS-based CRN with MUI avoidance in multipath fading channels can be achieved if and only if, for i = 1, 2, ..., U. By following the constraints in (20), (17) can be rewritten as DRAFT November 21,2013 Note that the scheme provides MUI-free transmission whenever the maximum delay spread of the channel does not exceed the specified limit. Meanwhile, it converts the multiple access problem over a multipath fading channel to a traditional single-user CDMA problem over a multipath fading channel. As shown in Fig. 1, the maximal-ratio combining (MRC)-RAKE receiver can be employed here to exploit channel diversity.

A. Multiuser capability
Multiuser capability plays an important role when measuring a specific network. For the sake of simplicity in this paper, only the multiuser capability in single-path fading channels is derived by following the constraints in (15), and that in multipath fading channels can be derived in the same way under the constraints in (20).
where ⌊p/N⌋ denotes the largest integer smaller than p/N. Table I

B. Aggregated throughput
Now we discuss the aggregated throughput of MUI-free TDCS-based CRNs. Since the order of P-CCSK must be a power of 2, i.e., 2 k for k = 1, 2, · · · , the maximal possible order of P-CCSK for a given number of users, U, is derived from (22) as follows, From [7], since the spectrum efficiency of each user is given by where β denotes the portion of available spectrum bins, the achievable aggregated throughput can be expressed as According to the aggregated throughput shown in Fig. 4, the following remarks are relevant.
• Increasing the number of spectrum bins, N, results in the lower aggregated throughput.  Consequently, the above observations provide a rule of thumb for MUI-free TDCS-based CRNs to satisfy the requirement of desired number of users and aggregated throughput.

V. SIMULATION RESULTS
Performances of different random-spreading-based CRNs, i.e., MC-CDMA, traditional TDCS and MUI-free TDCS, are demonstrated via simulations, and system parameters are shown in Table II. In order to make a fair comparison, Zadoff-Chu sequences are used for MC-CDMA systems since they produce significantly better average bit error probability than Walsh and Gold sequences [13]. For MUI-free TDCS-based CRNs, the steps to generate a class of almost perfect  which is less than log 2 (LN) bits in the single-user case. This performance loss is not avoidable.
For example, the MUI-free TDCS with U = 4 and U = 8 suffer from 0.85dB and 1.35dB performance loss in terms of E b /N 0 . be considered as a preferable candidate when power control techniques cannot be used.

C. Spectrum sensing mismatch
According to IEEE 802.22 [20], channel uncertainties are likely to produce a mismatch between the spectrum bins identified by the spectrum sensing results obtained by the transmitter and receiver. To discuss the performance with imperfect spectrum sensing, we use the correlation coefficient η to quantify the mismatch, as shown in [21] [22]. With a small number of users, i.e., U = 4, each user achieves a BER performance similar to that with perfect spectrum sensing, with only 0.15dB degradation in terms of E b /N 0 at BER = 10 −3 . However, with a larger number of users, i.e., U = 8, the BER performance is obviously worse than that with perfect spectrum sensing. This is because the constraints in (15) for MUI avoidance are no longer satisfied in the spectrum sensing mismatch scenario, and the residual MUI degrades the BER performance.

D. BER performance in multipath fading channels
Now we discuss BER performance of different random-spreading-based CRNs in multipath fading channels such as the COST207RAx6 channel [23]. In this simulation, the length 1/4 cyclic prefix is adopted to eliminate the effects of multipath fading channels, and minimal mean square error frequency-domain equalization (MMSE-FDE) is considered for MC-CDMA and traditional TDCS. As shown in Fig. 9, MC-CDMA and traditional TDCS still suffer the MUI due to the non-zero periodic CCF between any pair of transmitted signals, while the MUI-free TDCS achieves the same BER performance as that of the single-user case. In addition, the MRC-RAKE receiver can effectively exploit the channel diversity of multipath fading channels.
This simulation verifies that, even in case of multipath fading channels, the MUI-free TDCS is also an effective solution against the near-far problem and multiuser interference.


extfieldsofstudy:
Mathematics
Computer Science

text:
The Anchors Hierachy: Using the triangle inequality to survive high dimensional data

This paper is about metric data structures in high-dimensional or non-Euclidean space that permit cached sufficient statistics accelerations of learning algorithms. It has recently been shown that for less than about 10 dimensions, decorating kd-trees with additional"cached sufficient statistics"such as first and second moments and contingency tables can provide satisfying acceleration for a very wide range of statistical learning tasks such as kernel regression, locally weighted regression, k-means clustering, mixture modeling and Bayes Net learning. In this paper, we begin by defining the anchors hierarchy - a fast data structure and algorithm for localizing data based only on a triangle-inequality-obeying distance metric. We show how this, in its own right, gives a fast and effective clustering of data. But more importantly we show how it can produce a well-balanced structure similar to a Ball-Tree (Omohundro, 1991) or a kind of metric tree (Uhlmann, 1991; Ciaccia, Patella,&Zezula, 1997) in a way that is neither"top-down"nor"bottom-up"but instead"middle-out". We then show how this structure, decorated with cached sufficient statistics, allows a wide variety of statistical learning algorithms to be accelerated even in thousands of dimensions.

It has recently been shown that for less than about 10 dimensions, decorating kd trees with additional "cached sufficient statis tics" such as fi rst and second moments and contingency tables can provide satisfying ac celeration for a very wide range of statistical learning tasks such as kernel regression, lo cally weighted regression, k-means clustering, mixture modeling and Bayes Net learning.
In this paper, we begin by defining the an chors hierarchy-a fast data structure and algorithm for localizing data based only on a triangle-inequality-obeying distance metric. We show how this, in its own right, gives a fast and effective clustering of data. But more importantly we show how it can pro duce a well-balanced structure similar to a Ball-Tree (Omohundro, 1991) or a kind of metric tree (Uhlmann, 1991;Ciaccia, Patella, & Zezula, 1997) in a way that is neither "top down" nor "bottom-up" but instead "middle out" . We then show how this structure, dec orated with cached sufficient statistics, al lows a wide variety of statistical learning al gorithms to be accelerated even in thousands of dimensions. 1

Cached Sufficient Statistics
This paper is not about new ways of learning from data, but instead how to allow a wide variety of cur rent learning methods, case-based tools, and statistics methods to scale up to large datasets in a computa-tionally tractable fashion. A cached sufficient statis tics representation is a data structure that summarizes statistical information from a large dataset. For exam ple, human users, or statistical programs, often need to query some quantity (such as a mean or variance) about some subset of the attributes (such as size, posi tion and shape) over some subset of the records. When this happens, we want the cached sufficient statistic representation to intercept the request and, instead of answering it slowly by database accesses over huge numbers of records, answer it immediately.
For all-discrete (categorical) datasets, cached sufficient statistics structures include frequent sets (Agrawal, Mannila, Srikant, Toivonen, & Verkamo, 1996) (which accelerate certain counting queries given very sparse high dimensional data), datacubes (Harinarayan, Ra jaraman, & Ullman, 1996) (which accelerate count ing given dense data up to about 7 dimensions), and all-dimensions-trees (Moore & Lee, 1998;Anderson & Moore, 1998) (which accelerate dense data up to about 100 dimensions). The acceleration of counting means that entropies, mutual information and corre lation coefficients of subsets of attributes can be com puted quickly, and (Moore & Lee, 1998) show how this can mean 1000-fold speed-ups for Bayes net learning and dense association rule learning.
But what about real-valued data? By means of mrkd trees (multiresolution k-dimensional trees) (Deng & Moore, 1995;Moore, Schneider, & Deng, 1997;Pelleg & Moore, 1999, 2000 (an extension of kd-trees (Fried man, Bentley, & Finkel, 1977)) we can perform clus tering, and a very wide class of non-parametric statis tical techniques on enormous data sources hundreds of times faster than previous algorithms (Moore, 1999), but only up to about 8-10 dimensions.
This paper replaces the kd-trees with a certain kind of Metric tree (Uhlmann, 1991) and investigates the ex tent to which this replacement allows acceleration on real-valued queries in higher dimensions. To achieve this, in Section 3 we introduce a new tree-free ag-glomerative method for very quickly computing a spa tial hierarchy (called the anchors hierarchy) -this is needed to help generate an efficient structure for the metric tree. And while investigating the effectiveness of metric trees we introduce three new cached suffi cient statistics algorithms as examples of a much wider range of possibilities for exploiting these structures while implementing statistical and learning operations on large data.

Metric Trees
Metric Trees, closely related to Ball trees (Omohundro, 1991), are a hierarchical structure for representing a set of points. They only make the assumption that the distance function between points is a metric: Metric trees do not need to assume, for example, that the points are in a Euclidean space in which vector components of the datapoints can be addressed di rectly. Each node n of the tree represents a set of datapoints, and contains two fields: npivot and nradi u s· The tree is constructed to ensure that node n has n radius = maxxEn D(npivot , x) meaning that if x is owned by node n, then If a node contains no more than some threshold Rmin number of points, it is a leaf node, and contains a list of pointers to all the points that it owns.
If a node contains more than Rmin points, it has two child nodes, called Child1 ( n) and Child2 ( n). The points owned by the two children partition the points owned by n: How are the child pivots chosen? There are numer ous schemes in the Metric tree literature. One simple method is as follows: Let fi be the datapoint inn with greatest distance from npivot. Let h be the datapoint in n with greatest distance from fi. Give the set of points closest to fi to Child1 ( n), the set of points clos est of /2 to Child2(n), and then set Childt(n) p i vo t equal to the centroid of the points owned by Child1 ( n) and set Child2 ( n) pivo t equal to the centroid of the points owned by Child2 ( n). This method has the merit that the cost of splitting n is only linear in the number of points owned by n. Entries 0 with prob 2/3, 1 with prob 1/3 Attributes 201 .. 1000 All entries 0 with probability 0.5 1 with probability 0.5 All entries 0 with probability 0.5 1 with probability 0.5 Figure 1: A spreadsheet with 100,000 rows and 1000 columns. In the rightmost 80 percent of the dataset all values are completely random. In the leftmost 20 percent there are more 1 's than 0 's in the top half and more O's than 1's in the bottom half. kd-trees structure this poorly. Metric trees structure it well.
kd-trees, upon which earlier accelerations were based, are similar in spirit to decision trees. Each kd-tree node has two children, specified by a splitting dimen sion, nsplitdim, and a splitting value, nspli t val. A point is owned by child 1 if its nsplitdim 'th component is less than nsplitval, and by child 2 otherwise. Notice kd trees thus need to access vector components directly. kd-trees grow top-down. Each node's children are cre ated by splitting on the widest (or highest entropy) dimension.
kd-trees are very effective in low dimensions at quickly localizing datapoints: after travelling down a few lev els in the tree, all the datapoints in one leaf tend to be much closer to each other than to datapoints not in the same leaf (this loose description can be formal ized). That in turn leads to great accelerations when kd-trees are used for their traditional purposes (nearest neighbor retrieval and range searching) and also when they are used with cached sufficient statistics. But in high dimensions this property disappears. Consider the dataset in Figure 1. The datapoints come from two classes. In class A, attributes 1 through 200 are independently set to 1 with probability 1/3. In class B, attributes 1 through 200 are independently set to 1 with probability 2/3. In both classes attributes 201 through 1000 are independently set to 1 with proba bility 1/2. The marginal distribution of each attribute is half 1's and half O's, so the kd-tree does not know which attributes are best to split on. And even if it split on one of the first 200 attributes, its left child would only contain 2/3 of class A and 1/3 of class B (with converse proportions for the right child). The kd tree would thus need to split at least 10 times (mean ing thousands of nodes) until at least 99 percent of the datapoints were in a node in which 99 percent of the datapoints were from the same class.
For a metric tree, it is easy to show that the very first split will, with very high probability, put 99 percent of class A into one child and 99 percent of class B into the other. The consequence of this difference is that for a nearest neighbor algorithm, a search will only need to visit half the datapoints in a metric tree, but many more in a kd-tree. We similarly expect cached sufficient statistics to benefit from metric trees. 3

The Anchors Hierarchy
Before describing the fi rst of our metric-tree-based cached sufficient statistics algorithms, we introduce the Anchors Hierarchy, a method of structuring the metric tree that is intended to quickly produce nodes that are more suited to our task than the simple top down procedure described earlier. As we will see, cre ating this hierarchy is similar to performing the statis tical operation of clustering-one example of the kind of operation we wish to accelerate. This creates a chicken and egg problem: we'd like to use the met ric tree to find a good clustering and we'd like to fi nd a good clustering in order to build the metric tree. The solution we give here is a simple algorithm that creates an effective clustering cheaply even in the absence of the tree.
The algorithm maintains a set of anchors A {a 1 , .. a k }. The i'th anchor, a i , has a pivot a ; pivot, and an explicit list of the set of points that are closer to a i than any other anchor: (3) where Vi, j, p, This list is sorted in decreasing order of distance to a i , and so we can define the radius of a i to be the furthest distance of any of the points owned by a i to its pivot simply as At each iteration, a new anchor is added to A, and the points it must own (according to the above con straints) are computed efficiently. The new anchor, a new , attempts to steal points from each of the exist ing anchors. To steal from a i , we iterate through the sorted list of points owned by a i . Each point is tested to decide whether it is closer to a i or a new . However, if we reach a point in the list at which we inspect x� and we discover that (6) we can deduce that the remainder of the points in a i 's list cannot possibly be stolen because for k 2: 0: so D (x�+k,a i pivot ) :::; D (a new pivot,X�+k ). This saving gets very significant when there are many anchors be cause most of the old anchors discover immediately that none of their points can be stolen by a new .
How is the new anchor a new chosen? We simply find the current anchor am a x rad with the largest radius, and choose the pivot of a new to be the point owned by     To create k anchors in this fashion reqmres no pre existing cached statistics or tree. Its cost can be as high as Rk for R datapoints, but in low dimensions, or for non-uniformly-distributed data, it requires an expected O(R log k) distance comparisons for k << R.

3.1
Middle-out building of a Cached statistic metric tree We now describe how we build the metric trees used in this paper. Instead of "top-down" or "bottom up" (which, for R datapoints is an O(R2) operation, though can be reduced in cost by approximations) we build it "middle-out" . We create an anchors hierarchy containing VR anchors. These anchors are all assigned to be nodes in the tree. Then the most compatible pair of nodes are merged to form a parent node. The compatibility of two nodes is defined to be the radius of the smallest parent node that contains them both completely-the smaller the better.
This proceeds bottom up from the VR anchors until all nodes have been agglomerated into one tree. When this is completed we must deal with the fact that each of the leaf nodes (there are VR of them) contains VR points on average. We will subdivide them further. This is achieved by, for each of the leaves, recursively calling this whole tree building procedure (including this bit), on the set of datapoints in that leaf. The base case of the recursion are nodes containing fewer than R min points. Figures 7-10 give an example.    We use the following cached statistics: each node con tains a count of the number of points it owns, and the centroid of all the points it owns1.
We first describe the naive K-means algorithm for pro ducing a clustering of the points in the input into [{ clusters. It partitions the data-points into [{ subsets such that all points in a given subset "belong" to some center. The algorithm keeps track of the centroids of the subsets, and proceeds in iterations. Before the first iteration the centroids are initialized to random values. The algorithm terminates when the centroid locations stay fixed during an iteration. In each iteration, the following is performed: 1. For each point x, find the centroid which is closest to x. Associate x with this centroid.
2. Re-estimate centroid locations by taking, for each centroid, the center of mass of points associated with it.
The K-means algorithm is known to converge to a local minimum of the distortion measure (that is, average squared distance from points to their class centroids). It is also known to be too slow for very large databases. Much of the related work does not attempt to con front the algorithmic issues directly. Instead, different methods of subsampling and approximation are pro posed.
1 In order for the concept of centroids to be meaningful we do require the ability to sum and scale datapoints, m addition to the triangle inequality Instead, we will use the metric trees, along with their statistics, to accelerate K-means with no approxima tion. This uses a similar approach to (Pelleg & Moore, 1999)'s kd-tree-based acceleration. Each pass of this new efficient K-means recurses over the nodes in the metric tree. The pass begins by a call to the following procedure with n set to be the root node, C set to be the set of centroids, and Cands set to also be the full set of centroids.
I<meansStep(node n, CentroidSet C, CentroidSet Cands) Invariant: we assume on entry that Cands are those members of C who are provably the only possible owners of the points in node n. Formally, we assume that Cands � C, and Vx En, (argminc E cD(x, c)) E Cands.
1. Reduce Cands: We attempt to prune the set of centroids that could possibly own datapoints from n. First, we identify c * E Cands, the candidate centroid closest to n p ivot. Then all other candi dates are judged relative to c * . For c E Cands, if D(c * , n pivo t) + R::; D(c, n p ivot) -R then delete c from the set of candidates, where R = nradius is the radius of node n. This cutoff rule will be discussed shortly.

Update statistics about new centroids:
The purpose of the K-means pass is to generate the centers of mass of the points owned by each cen troid. Later, these will be used to update all the centroid locations. In this step of the algorithm we accumulate the contribution to these centers of mass that are due to the datapoints inn. Depend ing on circumstances we do one of three things: • If there is only one candidate in Cands, we need not look at n's children. Simply use the information cached in the node n to award all the mass to this one candidate. • Else, if n is a leaf, iterate through all its dat apoints, awarding each to its closest centroid in Cands. Note that even if the top-level call had ]{ = 1000 centroids, we can hope that at the levels of leaves there might be far fewer centroids remaining in Cands, and so will see accelerations over conventional K means even if the search reaches the leaves. and soc cannot own any x inn.

Anomaly Detection
As an example of a non-parametric statistics operation that can be accelerated, consider a test for anomalous datapoints that proceeds by identifying points in low density regions. One such test consists of labeling a point as anomalous if the number of neighboring points within some radius is less than some threshold.
This operation requires counts within the nodes as the only cached statistic. Given a query point x, we again recurse over the tree in a depth first manner, trying the child closer to x before the further child. We main tain a count of the number of points discovered so far within the range, and another count-an upper bound on the number of points that could possibly be within range. At each point in the search we have an impres sive number of possibilities for pruning the search: 1. If the current node is entirely contained within the query radius, we simply add ncount to the count.
2. If the current node is entirely outside the query radius, we simply ignore this node, decrement ing the upper bound on the number of points by ncount · 3. If the count of the number of points found ever exceeds the threshold, we simply return FALSE the query is not an anomaly.
4. If the upper bound on the count ever drops be low threshold then return TRUE-the query is an anomaly.

Example 3: Grouping Attributes
The third example is designed to illustrate an impor tant use of high dimensional methods. Consider a dataset represented as a matrix in which rows corre spond to datapoints and columns correspond to at tributes. Occasionally, we may be more interested in groupings among attributes than among datapoints. If so, we can transpose the dataset and build the metric tree on attributes instead of datapoints.
For example, suppose we are interested in finding pairs of attributes that are highly positively correlated. Re member that the correlation coefficient between two attributes x and y is p(x, y) = :L)x;x)(y;y)/((J'x(J'y) where x; is the value of attribute x in the ith record. If we subtract the attribute means and divide by their standard deviations we may defi ne normalized values x i= (x;x ) /(J'x and Yi = (y;y)/(J'y· Then p(x,y) = l: xfyf = 1-D2(x*,y*)/2 (8) using Euclidean distance. Thus, for example, finding all pairs of attributes correlated above a certain level p corresponds to finding pairs with distances below �· There is no space to describe the details of the al gorithm using metric trees to collect all these close pairs. It is a special case of a general set of "all-pairs" algorithms described (albeit on conventional kd-trees) by (Gray & Moore, 2000) and related to the celebrated Barnes-Hut method (Barnes & Hut, 1986) for efficient R-hody simulation.

Empirical Results
The following results used the datasets in Table 1.
Each dataset had K-means applied to it, the non parametric anomaly detector, and all-pairs. For the latter two operations suitable threshold parameters were chosen so that the results were "interesting" (e.g. in the case of anomalies, so that about 10 percent of all datapoints were regarded as anomalous). This is im portant: all the algorithms do very well (far greater ac celerations) in extreme cases because of greater prun ing possibilities, and so our picking of "interesting" cases was meant to tax the acceleration algorithms as much as possible. For K-means, we ran three exper iments for each dataset in which J{ (the number of centroids) was varied between 3, 20 and 100.
The results in Table 2 show three numbers for each experiment. First, the number of distance compar isons needed by a regular (i.e. treeless) implemen tation of the algorithm. Second, the number of dis tance comparisons needed by the accelerated method using the cached-statistics-supplemented metric tree. And third, in bold, the speedup (the first number di vided by the second). For the artificial datasets, we restricted K-means experiments to those in which J{, the number of clusters being searched for, matched the actual number of clusters in the generated dataset.
The speedups in the two dimensional datasets are all excellent, but of course in two dimensions regu lar statistics-caching kd-trees would have given equal or better results. The higher dimensional cell and covtype datasets are more interesting-the statis tics caching metric trees give a substantial speedup whereas in other results we have established that kd trees do not. Notice that in several results, K=20 gave a worse speedup than K=3 or K= 100. Whether this is significant remains to be investigated.
The Reuters dataset gave poor results. This only has 10,000 records and appears to have little intrin sic structure. Would more records have produced bet ter results? Extra data was not immediately avail able at the time of writing and so, to test this the ory, we resorted to reduci ng the amount of data. The Reuters50 dataset has only half the documents, and its speedups are indeed worse. This gives some cre dence to the argument that if the amount of data was increased the anti-speedup of the metric trees would be reduced, and eventually might become profitable.
On anomaly detection and all-pairs, all methods per formed well, even on Reuters. There is wild variation in the speedup. This is an artifact of the choice of thresholds for each algorithm. If too large or too small pruning becomes trivial and the speedup is enormous. Table 3 investigates whether the "anchors" approach to building the tree has any advantage over the sim pler top-down approach. For the four datasets we tested, using K-means as the test, the speedups of us ing the anchors-constructed tree over the top-down constructed tree were modest (ranging from 20 per cent to 180 percent) but consistently positive. Similar results comparing the two tree growth methods for all pairs and anomalies give speedups of 2-fold to 6-fold.
As an aside, Table 4 examines the quality of the clustering created by the anchors algorithm. In all experiments so far, K-means was seeded with ran dom centroids. What if the anchors algorithm was used to generate the starting centroids? Table 4 shows, in the middle four columns, the distortion (sum squared distance from datapoints to their near est centroids) respectively for randomly-chosen cen troids, centroids chosen by anchors, centroids started randomly followed by 50 iterations of K-means and centroids started with anchors followed by 50 itera tions of K-means. Both before and after K-means, anchors show a substantial advantage except for the Reuters dataset.  Ta ble 2: Results on various datasets. Non-bold numbers show the number of distance computations needed in each experiment. Bold-face numbers show the speedup-how many times were the statistics-caching metric trees faster than conventional implementations in terms of numbers of distance computations? The columns labeled k = 3, k = 20 and k = 100 are for K-means.  "Random Start" are the distortion measures for randomly chosen centroids. "Anchors Start" are the distortion measures obtained when using the anchors hierarchy to generate initial centroids. The next two columns show the resulting distortion of random-start and anchors-start respectively after 50 iterations of K-means. The final two columns summarize the relative merits of anchors versus random: by what factor is anchor's distortion better than random's? "Start Benefit" shows the factor for the initial centroids. "End benefit" shows the factor for the final centroids.
Dataset k=3 k=20 k=100 cell 1.3 1.2 1.2 covtype 1.3 1.3 1.3 squiggles 1.6 1.5 1.6 gen10000-k20 2.8 2.7 2.7 Table 3: The factor by which using anchors to build the metric tree improves over using top-down building in terms of number of distance calculations needed.

6
Accelerating other learning algorithms The three cached-statistic metric tree algorithms in troduced in this paper were primarily intended as ex amples. A very wide range of both parametric and non-parametric methods are amenable to acceleration in a similar way. As further examples, and on our short-list for future work are: • Dependency trees (Meila, 1999), by modifying the all-pairs method above to the case of Kruskal's al gorithm for minimum spanning tree in Euclidean space (equivalently maximum spanning tree in correlation space). Additionally, although Mutual Information does not obey the triangle inequality, it can be bounded above (Meila, 2000) and below by Euclidean distance and so it should also be possible to apply this method to entropy based tree building for high-dimensional discrete data.
• Mixtures of spherical, axis aligned or general Gaussians. These are all modifications of the K means algorithm above and the mrkd-tree-based 7 acceleration of mixtures of Gaussians described in (Moore, 1999).
• Mixtures of multinomials for high dimensional discrete data.
• There are numerous other non-parametric statis tics, including n-point correlation functions used in astrophysics that we will apply these techniques to. In addition, Gaussian processes, certain neu ral net architectures, and case-based reasoning systems may be accelerated.

Discussion
The purpose of this paper has been to describe, discuss and empirically evaluate the use of metric trees to help statistical and learning algorithms scale up to datasets with large numbers of records and dimensions. In so doing, we have introduced the anchors hierarchy for building a promising first cut at a set of tree nodes effi ciently before the tree has been created. We have given three examples of cached-sufficient-statistics-based al gorithms built on top of these structures.
If there is no underlying structure in the data (e.g. if it is uniformly distributed) there will be little or no acceleration in high dimensions no matter what we do. This gloomy view, supported by recent theoret ical work in computational geometry (Indyk, Amir, Efrat, & Samet, 1999), means that we can only accel erate datasets that have interesting internal structure.
Resorting to empirical results with real datasets, how ever, there is room for some cautious optimism for real-world use.


MT Quality Estimation: The CMU System for WMT'13

In this paper we present our entry to the WMT’13 shared task: Quality Estimation (QE) for machine translation (MT). We participated in the 1.1, 1.2 and 1.3 sub-tasks with our QE system trained on features from diverse information sources like MT decoder features, n-best lists, mono- and bi-lingual corpora and giza training models. Our system shows competitive results in the workshop shared task.

Introduction
As MT becomes more and more reliable, more people are inclined to use automatically translated texts. If coming across a passage that is obviously a mistranslation, any reader would probably start to doubt the reliability of the information in the whole article, even though the rest might be adequately translated. If the MT system had a QE component to mark translations as reliable or possibly erroneous, the reader would know to use information from passages marked as bad translations with caution, while still being able to trust other passages. In post editing a human translator could use translation quality annotation as an indication to whether editing the MT output or translating from scratch might be faster. Or he could use this information to decide where to start in order to improve the worst passages first or skip acceptable passages altogether in order to save time. Confidence scores can also be useful for applications such as cross lingual information retrieval or question answering. Translation quality could be a valuable ranking feature there.
Various classifiers and regression models have been used in QE in the past. Gandrabur and Foster (2003) compare single layer to Multi Layer Perceptron (MLP), Quirk et al. (2004) report that Linear Regression (LR) produced the best results in a comparison of LR, MLP and SVM, Gamon et al. (2005) use SVM, Soricut and Echihabi (2010) find the M5P tree works best among a number of regression models, while Bach et al. (2011) define the problem as a word sequence labeling task and use MIRA.
The QE shared task was added to the WMT evaluation campaign in 2012 (Callison-Burch et al., 2012), providing standard training and test data for system development.

WMT'13 Shared Task
In this WMT Shared Task for Quality Estimation 1 there were tasks for sentence and word level QE. We participated in all sub-tasks for Task 1: Sentence-level QE.
Task 1.1: Scoring and ranking for post-editing effort focuses on predicting HTER per segment for the translations of one specific MT system. Task 1.2: System selection/ranking required to predict a ranking for up to five translations of the same source sentence by different MT systems. The training data provided manual labels for ranking including ties. Task 1.3: Predicting postediting time participants are asked to predict the time in seconds a professional translator will take to post edit each segment.
Besides the training data with labels, for each of these tasks additional resources were provided. These include bilingual training corpora, language models, 1000-best lists, models from giza and moses training and various other statistics and models depending on task and language pair.

Language Models
To calculate language model (LM) features, we train traditional n-gram language models with ngram lengths of four and five using the SRILM toolkit (Stolcke, 2002). We calculate our features using the KenLM toolkit (Heafield, 2011). We normalize all our features with the target sentence length to get an average word feature score, which is comparable for translation hypotheses of different length. In addition to the LM probability we record the average n-gram length found in the language model for the sentence, the total number of LM OOVs and OOVs per word, as well as the maximum and the minimum word probability of the sentence, six features total.
We use language models trained on source language data and target language data to measure source sentence difficulty as well as translation fluency.

Distortion Model
The moses decoder uses one feature from a distance based reordering model and six features from a lexicalized reordering model: Given a phrase pair, this model considers three events Monotone, Swap, and Discontinuous in two directions Left and Right. This results in six events: LM (left-monotone), LS (left-swap), LD (leftdiscontinuous) and RM (right-monotone), RS, RD.
These distortion features are calculated for each phrase. For a total sentence score we normalize by the phrase count for each of the seven features.

Phrase Table
From the phrase table we use the features from the moses decoder output: inverse phrase translation probability, inverse lexical weighting, direct phrase translation probability and direct lexical weighting. For a total sentence score we normalize by the phrase count. We use the number of phrases used to generate the hypothesis and the average phrase length as additional features, six features total.

Statistical Word Lexica
From giza training we use IBM-4 statistical word lexica in both directions. We use six probability based features as described in Hildebrand and Vogel (2008): Normalized probability, maximum word probability and word deletion count from each language direction.
To judge the translation difficulty of each word in the source sentence we collect the number of lexicon entries for each word similar to Gandrabur and Foster (2003). The intuition is, that a word with many translation alternatives in the word-toword lexicon is difficult to translate while a word with only a few translation choices is easy to translate.
In fact it is not quite this straight forward. There are words in the lexicon, which have many lexicon entries, but the probability for them is not very equally distributed. One entry has a very high probability while all others have a very low one -not much ambiguity there. Other words on the other hand have several senses in one language and therefore are translated frequently into two or three different words in the target language. There the top entries in the lexicon might each have about 30% probability. To capture this behavior we do not only count the total number of entries but also the number of entries with a probability over a threshold of 0.01.
For example one word with a rather high number of different translations in the English-Spanish statistical lexicon is the period (.) with 1570 entries. It has only one translation with a probability over the threshold which is the period (.) in Spanish at a probability of 0.9768. This shows a clear choice and rather little ambiguity despite the high number of different translations in the lexicon.
For each word we collect the number of lexicon entries, the number of lexicon entries over the threshold, the highest probability from the lexicon and whether or not the word is OOV. If a word has no lexicon entry with a probability over the threshold we exclude the word from the lexicon for this purpose and count it as an OOV. As sentence level features we use the sum of the word level features normalized by the sentence length as well as the total OOV count for the sentence, which results in five features.

Sentence Length Features
The translation difficulty of a source sentence is often closely related to the sentence length, as longer sentences tend to have a more complex structure. Also a skewed ratio between the length of the source sentence and its translation can be an indicator for a bad translation.
We use plain sentence length features, namely the source sentence length, the translation hypothesis length and their ratio as introduced in Quirk (2004).
Similar to Blatz et al. (2004) we use the n-best list as an information source. We calculate the average hypothesis length in the n-best list for one source sentence. Then we compare the current hypothesis to that and calculate both the diversion from that average as well as their ratio. We also calculate the source-target ratio to this average hypothesis length.
To get a representative information on the length relationship of translations from the source and target languages in question, we use the parallel training corpus. We calculate the overall language pair source to target sentence length ratio and record the diversion of the current hypothesis' source-target ratio from that.
The way sentences are translated from one language to another might differ depending on how complex the information is, that needs to be conveyed, which in turn might be related to the sentence length and the ratio between source and translation. As a simple way of capturing this phenomenon we divide the parallel training corpus into three classes (short, medium, long) by the length of the source language sentence. The boundaries of these classes are the mean 26.84 plus and minus the standard deviation 14.54 of the source sentence lengths seen in the parallel corpus. We calculate the source/target length ratio for each of the three classes separately. The resulting statistics for the parallel training corpora can be found in Table 1. For English -Spanish the ratio for all classes is close to one, for other language pairs these differ more clearly.
As features for each hypothesis we use a binary indicator for its membership to each class and its deviation from the length ratio of its class. This results in 12 sentence length related features in total. The length of words is often related to whether they are content words and how frequently they are used in the language. Therefore we use the maximum and average word length as features. Similar to Blatz et al. (2004) we sort the vocabulary of the source side of the training corpus by occurrence frequency and then divide it into four parts, each of which covers 25% of all tokens. As features we use the percentage of words in the source sentence that fall in each quartile. Additionally we use the number and percentage of source words in the source sentence that are OOV or very low frequency, using count 2 as threshold. We also collect all bigram statistics for the corpus and calculate the corresponding features for the source sentence based on bigrams. This adds up to fourteen features from source word and corpus statistics.

N-Best List Agreement & Diversity
We use the three types of n-best list based features described in Hildebrand and Vogel (2008): Position Dependent N-best List Word Agreement, Position independent N-best List N-gram Agreement and N-best List N-gram Probability.
To measure n-best list diversity, we compare the top hypothesis to the 5th, 10th, 100th, 200th, 300th, 400th and 500th entry in the n-best list (where they exist) to see how much the translation changes throughout the n-best list. We calculate the Levenshtein distance (Levenshtein, 1966) between the top hypothesis and the three lower ranked ones and normalize by the sentence length of the first hypothesis. We also record the n-best list size and the size of the vocabulary in the nbest list for each source sentence normalized by the source sentence length.
Fifteen agreement based and nine diversity based features add up to 24 n-best list based features.

Source Parse Features
The intuition is that a sentence is harder to translate, if its structure is more complicated. A simple indicator for a more complex sentence structure is the presence of subclauses and also the length of any clauses and subclauses. To obtain the clause structure, we parse the source language sentence using the Stanford Parser 2 (Klein and Manning, 2003). Features are: The number of clauses and subclauses, the average clause length, and the number of sentence fragments found. If the parse does not contain a clause tag, it is treated as one clause which is a fragment.

Source-Target Word Alignment Features
A forced alignment algorithm utilizes the trained alignment models from the MT systems GIZA (Och and Ney, 2003) training to align each source sentence to each translation hypothesis.
We use the score given by the word alignment models, the number of unaligned words and the number of NULL aligned words, all normalized by the sentence length, as three separate features. We calculate those for both language directions. Hildebrand and Vogel (2010) successfully applied these features in n-best list re-ranking.

Cohesion Penalty
Following the cohesion constraints described in Bach et al. (2009) we calculate a cohesion penalty for the translation based on the dependency parse structure of the source sentence and the word alignment to the translation hypothesis. To obtain these we use the Stanford dependency parser (de Marneffe et al., 2006) and the forced alignment from Section 3.9.
For each head word we collect all dependent words and also their dependents to form each complete sub-tree. Then we project each sub-tree onto the translation hypothesis using the alignment. We test for each sub-tree, whether all projected words in the translation are next to each other (cohesive) or if there are gaps. From the collected gaps we subtract any unaligned words. Then we count the number of gaps as cohesion violations as well as how many words are in each gap. We go recursively up the tree, always including all sub-trees for each head word. If there was a violation in one of the sub-trees it might be resolved by adding in its siblings, but if the violation persists, it is counted again.

Classifiers
For all experiments we used the Weka 3 data mining toolkit described in Hall et. al. (2009) to compare four different classifiers: Linear Regression (LR), M5P tree (M5Ptree), Multi Layer Perceptron (MLP) and Support Vector Machine for Regression (SVM). Each of these has been identified as effective in previous publications. All but one of the Weka default settings proved reliable, changing the learning rate for the MLP from default: 0.3 to 0.01 improved the performance considerably. We report Mean Absolute Error (MAE) and Root Mean Squared Error (RMSE) for all results.

Experiment Results
For Tasks 1.1 and 1.3 we used the 1000-best output provided. As first step we removed duplicate entries in these n-best list. This brought the size down to an average of 152.9 hypotheses per source sentence for the Task 1.1 training data, 172.7 on the WMT12 tests set and 204.3 hypotheses per source sentence on the WMT13 blind test data. The training data for task 1.3 has on average 129.0 hypothesis per source sentence, the WMT13 blind test data 129.8.
In addition to our own features described above we extracted the 17 features used in the WMT12 baseline for all sub-tasks via the software provided for the WMT12-QE shared task.

Task 1.1
Task 1.1 is to give a quality score between 0 and 1 for each segment in the test set, predicting the HTER score for the segment and also to give a rank for each segment, sorting the entire test set from best quality of translation to worst.
For Task 1.1 our main focus was the scoring task. We did submit a ranking for the blind test wmt12-test: WMT12 manual quality labels  In Table 2 we show the results for some experiments comparing the performance of different feature sets and classifiers. For development we used the WMT12-QE test set and both the WMT12 manual labels as well as HTER as target class. We compared the impact of removing the 17 WMT12-baseline features "no WMT12-base" and training a "slim" system by removing nearly half the features, which showed to have a smaller impact on the overall performance in preliminary experiments. Among the removed features are n-best list based features, redundant features between ours, the moses based and the base17 features and some less reliable features like e.g. the lexicon deletion features, who's thresholds need to be calibrated carefully for each new language pair. We submitted the full+MLP and the no-WMT12-base+SVM output to the shared task, shown in bold in the table.
The official result for our system for task 1.1 on the WMT13 blind data is MAE 13.84, RMSE 17.46 for the no-WMT12-base+SVM system and MAE 15.25 RMSE 18.97 for the full+MLP system. Surprising here is the fact that our full system clearly outperforms the 17-feature baseline on the WMT12 test set, but is behind it on the WMT13 blind test set. (Baseline bb17 SVM: MAE 14.81,RMSE 18.22) Looking at the WMT13 test set results, we should have chosen the slim+SVM system variant.

Task 1.2
Task 1.2 asks to rank different MT systems by translation quality on a segment by segment basis.
Since the manually annotated ranks in task 1.2 allowed ties, we treated them as quality scores and ran the same QE system on this data as we did for task 1.1. We submitted the full-MLP output with the only difference that for this data set the decoder based features were not available. We rounded the predicted ranks to integer. Since the training data contains many ties we did not employ a strategy to resolve ties.
As a contrastive approach we ran the hypothesis selection system described in Hildebrand and Vogel (2010) using the BLEU MT metric as ranking criteria. For this system it would have been very beneficial to have access to the n-best lists for the different system's translations. The BLEU score for the translation listed as the first system for each source sentence would be 30.34 on the entire training data. We ran n-best list re-ranking using MERT (Och, 2003) for two feature sets: The full feature set, 100 features in total and a slim feature set with 59 features. For the slim feature set we removed all features that are solely based on the source sentence, since those have no impact on re-ranking an n-best list. The BLEU score for the training set improved to 45.25 for the full feature set and to 45.76 for the slim system. Therefore we submitted the output of the slim system to the shared task. This system does not predict ranks directly, but estimates ranking according to BLEU gain on the test set. Therefore the new ranking is always ranks 1-5 without ties.
The official result uses Kendalls tau with and without ties penalized. Our two submissions score: −0.11 / −0.11 for the BLEU optimized system and −0.63 / 0.23 for the classifier system. The classifier system is the best submission in the "ties ignored" category.

Task 1.3
Task 1.3 is to estimate post editing time on a per segment basis.
In absence of a development test set we used 10-fold cross-validation on the training data to determine the best feature set and classifier for the two submissions. Table 3 shows the results on our preliminary tests for four classifiers and three feature sets. The "no pr." differs from the full feature set only by removing the provided features, in this case the 17 WMT12-baseline features and the "translator ID" and "nth in doc" features. For the "slim" system run the feature set size was cut in half in order to prevent overfitting to the training data since the training data set is relatively small. We used the same criteria as in Task 1.1. For the shared task we submitted the full+SVM and slim+LR variants, shown in bold in the table.
The official result for our entries on the WMT13 blind set in MAE and RMSE are: 53.59 -92.21 for the full system and 51.59 -84.75 for the slim system. The slim system ranks 3rd for both metrics and outperforms the baseline at 51.93 -93.36.

Conclusions
In this WMT'13 QE shared task we submitted to the 1.1, 1.2 and 1.3 sub-tasks. In development we focused on the scoring type tasks.
In general there don't seem to be significant differences between the different classifiers.
Surprising is the fact that our full system for task 1.1 clearly outperforms the 17-feature baseline on the WMT12 test set, but is behind it on the WMT13 blind test set. This calls into question whether the performance on the WMT12 test set was the right criterium for selecting a system variant for submission.
The relative success of the "slim" system variant over the full feature set shows that our system would most likely benefit from a sophisticated feature selection method. We plan to explore this in future work.


extfieldsofstudy:
Computer Science
Medicine

text:
The method to divide a sentence of requirement into individual requirements and the development of requirement specification editor which can describe individual requirements

Background Agile software development gains requirements from the direct discussion with customers and the development staff each time, and the customers evaluate the appropriateness of the requirement. If the customers divide the complicated requirement into individual requirements, the engineer who is in charge of software development can understand it easily. This is called division of requirement. However, the customers do not understand how much and how to divide the requirements. Results This paper proposes the method to divide a complicated requirement into individual requirements. Also, it shows the development of requirement specification editor which can describe individual requirements. Conclusions The engineer who is in charge of software development can understand requirements easily.

Introduction
Generally, the software is developed according to a lifecycle model (Boehm 1988;DeMarco 1979). Any life-cycle models certainly have the software requirement specification(SRS) and software test. The purpose of SRS is to gain requirements from customers (Karl 2003;IEEE Computer Society 1990), and the purpose of software test is to improve the quality (Beck 2003). The test cases used by a software test are generated based on the SRS. If the engineer who takes charge of SRS and the engineer who takes charge of software test have a different understanding from the same SRS, they may generate low-quality test cases. It will also lead to low-quality software.
Recently, MBT model-based testing (Doungsa-ard et al. 2007;Kakaji et al. 2009) has been proposed. MBT is the method to test using test case which create based on *Correspondence: s12g463@stmail.eng.kagawa-u.ac.jp; rihito@eng.kagawa-u.ac.jp 1 Graduate school of Engineering, Kagawa University, Takamatsu-city, Kagawa, Japan 2 Faculty of Engineering, Kagawa University, Takamatsu-city, Kagawa, Japan Full list of author information is available at the end of the article model of software behavior. A method is suggested under this situation. It describes the requirement specification of software as a model, and create a test case based on the model. In order to describe the requirement specification as a model, it is necessary to divide the various forms of requirements and make the model correctly.
Agile software development gains requirements from the direct discussion with customers and the development staff each time, and the customers evaluate the appropriateness of the requirement. If the customers divide the complicated requirement into individual requirements, the engineer who is in charge of software development can understand it easily. This is called division of requirement (Sillitti and Succi 2005). However, the customers do not understand how much and how to divide the requirements.
A part of 1.2 scope shows the requirement sentences which is written on the requirement specification. These sentences include several requirements such as "The teacher can send a mail" and "The staff can receive a mail". However, it does not have the rule about how much the http://www.springerplus.com/content/2/1/145 user should divide the requirement sentences. It depended on the person who made the requirement specification. If one of the requirement sentences include several requirements, the developer cannot understand the requirement of system correctly. A software which does not satisfy the customer's requirement will be developed, and it causes the return during the software development.
The test case in software test is generally creates based on the requirement specification. If one of the requirement sentences includes several requirements, the engineer in charge of the software test cannot understand the requirement. Then, the test case is creates although the customer's requirement is not correctly confirmed. It becomes a cause to decay the quality of software.
Recently, the software test make wide use of test management system. TestLink (Teamst 2012) is a famous test management system. TestLink is a web-based test management system that facilitates software quality assurance. It is developed and maintained by Teamst. The platform offers the support for test cases, test suits, test plans, test projects and user management, as well as various reports and statistics. TestLink has the function which relates requirement specification document to test case. Normally, a sentence of requirement specification document has some requirements. TestLink can only relate a sentence of requirement specification to a test case. TestLink needs the division of requirements to relate the customer's requirement to the test case correctly.
This paper proposes the method to divide the requirements by establishing how to describe the division requirements. This paper describes that the sentence of SRS can be divided into six parts, 5W1H, (Actor(Who), Time(When), Location(Where), Reason(Why), Object of target(What)), and SRS has the tag which 5W1H are written as semantic information. We developed the Software requirement specification(SRS) editor system with semantic information. Since the system which we developed can have semantic information, the engineer who takes charge of SRS and the engineer who takes charge of software test have the same understanding.

The method to divide a complicated requirement sentence into individual requirements
A part of 1.2 scope shows that the people who belong to university can send and receive a mail. However, this requirement sentence does not show who these people are clearly. Figure 1 shows an example which this requirement is divided into individual requirements. If they are teachers, staffs and students, the requirement can be divided into "The teachers can send and receive a mail. ", "The staffs can send and receive a mail. " and "The students can send and receive a mail. " Also, "Send and Receive" can be divided into "Send" and "Receive". We can understand this sentence is divided into 6 individual requirements, "The teachers can send a mail. ", "The teachers can receive a mail. ", "The staffs can send a mail. ", "The staffs can receive a mail. ", "The students can send a mail. " and "The students can receive a mail. " In order to divide a complicated requirement into individual requirements, this chapter suggests the method to describe the individual requirements. Sugimoto (Sugimoto et al. 2007) described that the sentence of SRS can be divided into five parts, 4W+non-functional requirement (Actor(Who), Time(When), Location( where), Reason(Why), and non-functional requirement). This paper proposes that the sentence of SRS can be divided into six parts, 5W1H, (Actor(Who), Time(When), Location(where), Reason(Why), Object of target(What)) based on Sugimoto's proposal, and SRS has the tag which 5W1H (Media Awareness Network 2008) are written as semantic information. 5W1H are questions whose answers are considered basic in information-gathering. They are often mentioned in journalism (cf. news style), research, and police investigations. Because our method use 5W1H.
The semantic information is described by the tag of XML form. The user can define the several tags by XML, and give the meanings to these information. Also, it is easy to share the structured documents and data among different information system, especially via internet. XML enables us to write the structured documents. We can define the minimum of individual requirement. Figure 2 shows the sample which several requirements are divided into individuals. However, semantic information does not have the description about the degree of requirement. It is possible for the engineer who takes charge of SRS and the engineer who takes charge of software test to have the different understanding. This paper proposes are to divide the sentence of SRS into the six parts, to give the degree of requirement in SRS, and to have the degree of requirement as semantic information. This paper also proposes the sentence of SRS to define four degree requirement. This paper shows that the degree of requirement can be divided into four, those are Must, Shall, Will, Can. However, the system of SRS editor can set up the degree of requirement freely, for example, a number can also be used.
Subsection 'The SRS with semantic tag in XML' is the example which a requirement sentence is described by a tag of XML and a tag of requirement degree is added. This example shows not only the requirement that " The student can send a mail. " but also when and where this requirement should be satisfied. It means that the requirement is the student can always receives a mail not only at school but also at any places. Also, this requirement has the tag of "must". It means that this requirement must be realized. http://www.springerplus.com/content/2/1/145 Figure 1 The method to divide a complicated requirement sentence into individual requirements.
A part of 1.2 scope

Scope
The software system is available that users concerned the schools send and receive e-mail.

Requirement specification editor system with semantic information
The requirement specification editor which we developed can not only make SRSs based on IEEE std 830-1998830- (IEEE 1998, but also make SRSs with semantic information by use of tag. The editor is used in the situation which acquisition of the requirement from a customer finished. Figure 3 shows requirement specification editor, and subsection The SRS with semantic tag in XML shows requirement specification which requirement specification editor create. Subsection The SRS with semantic tag in XML shows that the system written in this SRSs can send e-mail, but one can not understand that user who can send(student?, professor?, staff?). The system which we developed have semantic information with tag, the system can be find out lack of description.
Requirement Specification don't know "when user can send e-mail", "where user can send e-mail", "how user can send e-mail". But the requirement specification editor which we developed not only divide a complicated requirement sentence into individual requirements, but also can know "when user can send e-mail", "where user can send e-mail", "how user can send e-mail". This means that student can send e-mail "any time" and "anywhere". And that is, Student can send e-mail not only inside campus, and also outside campus. The requirement specification editor which we developed can express detail of Requirement. And This XML have tag of <must></must>. This tag means the degree of requirement. <must></must> means the requirement which must be attained. Requirement specification can not express degree of requirement. Software test check satisfaction of customer requirement. Generally, customer have many kind of requirement. for example, requirement which customer must satisfy, and so on. The requirement specification editor which we developed can express degree of requirement.

The function which reuses the inputted the description and the function which shows the relationship of the descriptions
This section describes the function which reuses the inputted the description and the function which shows Figure 4 The function which shows the relationship of the descriptions. http://www.springerplus.com/content/2/1/145 the relationship of the descriptions. There are many problems such someone who operate are not indicated and a different description is used in the same meaning, and expression is ambiguous in SRSs. The Editor which we developed have the function which reuses the inputted the description. This function has an effect which prevents using description which is different in the same meaning.
Change of SRS sometimes takes place. However, it is difficult to know the influence by change of a requirement. The system which we developed have the function which shows the relationship of the descriptions. Figure 4 shows the function which shows the relationship of the descriptions. The staff of a school is education staff and administrative staff. If administrative staff changes, the staff of a school may also change and the people involved in the school may also change. In this way, by describing the association between the word, you can find a lack of information.

Conclusion
This paper proposed the method to divide a complicated requirement into individual requirements. Also, it presented the development of requirement specification editor which can describe individual requirements. This paper described that the sentence of Software requirement specification(SRS) can be divided into six parts, 5W1H, (Actor(Who), Time(When), Location(where), Reason(Why), Object of target(What) and requirement specificaton have tag which 5W1H was written as semantic information. This paper also describes how to given the degree of requirement, and describes the methods to have tag which the degree of requirement was written as semantic information. This paper describes the Requirement Specification editor system which we developed with semantic information, the function which reuses the inputted the description, the function which shows the relationship of the descriptions.