extfieldsofstudy:
Computer Science
Mathematics

text:
Unique Decoding of General AG Codes

A unique decoding algorithm for general AG codes, namely multipoint evaluation codes on algebraic curves, is presented. It is a natural generalization of the previous decoding algorithm which was only for one-point AG codes. As such, it retains the same advantages of fast speed and regular structure with the previous algorithm. Compared with other known decoding algorithms for general AG codes, it is much simpler in its description and implementation.

I. INTRODUCTION
Goppa [1] was the first to define linear error-correcting codes on algebraic curves. For a divisor G whose support is disjoint from a set of rational points on the curve, divisor D being the sum of those rational points, he defined the evaluation code C L (D, G) and the differential code C Ω (D, G), the latter being the dual of the former. In the subsequent vast research works on Goppa's codes, now called AG codes, the focus was often on the dual of the evaluation code, that is, the differential code. The reason seems to be nothing else but the first successful decoding algorithm for AG code [2] was for the dual of the evaluation codes. Thus a lot of effort was put into finding curves with many rational points and thereon to construct differential codes with good parameters. To estimate the minimum distance of the codes, various lower bounds have been developed. For much the same reason, so-called onepoint codes that assume G = mQ for some positive integer m and a rational point Q are considered most often in the literature. These one-point differential codes can be decoded efficiently by the syndrome-based Berlekamp-Massey-Sakata algorithm with the Feng-Rao majority voting [3].
Guruswami and Sudan's list decoding [4] provided a fresh point of view that brought the evaluation codes back to the center. Using interpolation, they showed that evaluation codes can be decoded successfully beyond the capacity of the previous decoding algorithms for differential codes. Following this way of approaching the decoding problem of AG codes, the authors [5] reinterpreted Duursma's idea of the majority voting [6] in the context of the interpolation decoding, and introduced a unique decoding algorithm for one-point evaluation codes on Miura-Kamiya plane curves. The result was a combination of nice features of the interpolation-based list decoding and the performance of the classical syndrome decoding with the majority voting scheme. Shortly thereafter, Geil et al. [7] generalized the result for arbitrary one-point AG codes and for list decoding. The goal of this paper is to note that the basic idea of [5] is more widely applicable, and present an interpolation-based unique decoding algorithm for general evaluation AG codes. By general evaluation AG codes, we mean the evaluation codes C L (D, G) with an arbitrary divisor G, with the premise that there exists a rational point Q not in the support of D. These codes are often called multipoint evaluation codes. Prominent examples would be the two-point codes on maximal curves such as Hermitian, Suzuki, and Klein curves.
We find that the impact of the interpolation-based list decoding has already made Beelen and Høholdt [8] to construct a unique decoding algorithm that is very similar to ours. Their algorithm also adopts an iterative method using majority voting to find the interpolation polynomial that gives the corrected codeword. The major difference of our algorithm is that we do not need differentials to construct the algorithm and use Lagrange interpolation instead of syndromes computed from the received vector, and thus directly compute the coefficients, corresponding to the sent message, by majority voting. Thus our algorithm is much simpler to present and more streamlined to implement and deploy in practice. Fujisawa and Sakata [9] also presented a fast decoding algorithm for multipoint general AG codes using a variant of the classical Berlekamp-Massey-Sakata algorithm, but only to correct errors short of the Goppa bound. Their method, originally due to Drake and Matthews [10], is to embed the multipoint code isometrically into a onepoint code.
The core ideas of the present work that we add to [5] are all contained in the preliminary materials in Section II. For general facts and notations for algebraic curves and functions fields, we refer to [11]. Once the stage set, we describe in Section III the decoding algorithm in a parallel fashion to [5]. In Section IV, several examples and experimental results are provided. In the final Section, we conclude with some remarks.

II. PRELIMINARIES
Let X be a smooth geometrically irreducible projective curve defined over a finite field F. Let P 1 , P 2 , . . . , P n and Q be distinct rational points on X, and define D = P 1 + P 2 + · · · + P n . Let G be an arbitrary divisor on X, whose support is disjoint from that of D, but allowed to include Q.
Let F(X) be the function field of X over F. Let be the ring of all functions on X which have no poles other than Q. For f ∈ R, let ρ(f ) = −v Q (f ). The Weierstrass semigroup at Q is then It is well-known that Λ is a numerical semigroup whose number of gaps is the genus g of X. Let γ be the smallest positive integer in Λ, and let ρ(x) = γ with some x ∈ R. For each 0 ≤ i < γ, let a i be the smallest integer such that a i ≡ i (mod γ) and ρ(y i ) = a i for some y i ∈ R. Then, using the properties of ρ : R → Z ≥0 inherited from the valuation v Q , we can show that {y 0 , y 1 , . . . , y γ−1 } forms a basis of R as a free module of rank γ over F[x]. Hence {x k y i | k ≥ 0, 0 ≤ i < γ} is a vector space basis of R over F, and will be called the monomials of R. The set {a i | 0 ≤ i < γ} is usually referred to as the Apéry set of Λ. Now letR which is clearly a module over R. For f ∈R, let δ(f ) denote the smallest integer s such that f ∈ L(sQ + G). Note that simply . Thus the map δ :R → Z satisfies the following properties: Then Λ +Λ =Λ, and henceΛ contains all large enough integers. Therefore for each 0 ≤ i < γ, there exists the smallest integer b i such that b i ≡ i (mod γ) and δ(ȳ i ) = b i for someȳ i ∈R. Then using the properties of δ, we easily see that {ȳ i | 0 ≤ i < γ} forms a basis ofR as a free module of rank γ over F [x]. For s ∈Λ, if i = s mod γ and k = ( is a basis of R over F, and will be called the monomials ofR.
Let us consider the R-module where z is a variable. Note that it is also a free F[x]-module of rank 2γ with free basis Thus every element in Rz ⊕R can be written as a unique F-linear combination of the monomials in For the monomials, we will use the notations We now briefly review the Gröbner basis theory on Rz ⊕R, regarded as a free module of rank 2γ over F[x]. First we define monomial order > s . For an integer s, the weighted degree of a polynomial f z + g ∈ Rz ⊕R is defined as δ s (f z + g) = max{ρ(f ) + s, δ(g)}.
In particular, for monomials, we have For more discussion on Proposition 1 and on the general theory of Gröbner bases, we refer to [12].
The evaluation map ev :R → F n , ϕ → (ϕ(P 1 ), ϕ(P 2 ), . . . , ϕ(P n )) is linear over F. Thus the AG code is a linear code of length n over F. Let us assume |G| < n so that the functions in L(G) correspond one-to-one with the codewords in C under ev. Note that {ϕ s | s ∈Λ, s ≤ 0} is a basis of L(G) as a vector space over F. Hence the dimension of C is k = |{s ∈Λ | s ≤ 0}|. So {s ∈ Λ | s ≤ 0} = {s 0 , s 1 , . . . , s k−1 }. We will also assume the nonsystematic encoding by evaluation. Thus a message ω = (ω s0 , ω s1 , . . . , Note that the map ev is surjective onto F n . Indeed by the Riemann-Roch theorem, we see that ev(L(sQ + G)) = F n for s ≥ n − |G| + 2g − 1. Let h i ∈R be such that ev(h i ) is the ith element of the standard basis of F n . Let J be the kernel of ev. Note that J is a submodule ofR over R, and also over such that degȳ(lt(η i )) = i.
Proof: The first equality is a standard result of the Gröbner basis theory. To see the second equality, note that for all large enough s, The goal of a decoding algorithm is to recover µ, and also c if necessary, from v. We consider the interpolation module Using the Gröbner basis theory, we will extract µ from I v . Let Hence by the criterion in Proposition 1, the set is a Gröbner basis of I v with respect to > δ(hv) . The ideal of the error vector e is also a submodule of R over F[x], and has a Gröbner basis {ǫ i | 0 ≤ i < γ} with respect to > s such that deg y (lt(ǫ i )) = i. We prove the following by the same argument as before.

III. DECODING ALGORITHM
Notice that this section is adapted from the corresponding section in [5] for the present general setup, with some changes in notations. Some minor errors are also corrected.

A. Theory
The basic idea of our decoding algorithm is to iteratively compute the coefficients ω s of the function µ. For and for s ∈Λ, , for which we suppress the necessary superscript (s) for legibility.
Now let w be an element of F. For each 0 ≤ i < γ, let where the parentheses denote substitution of the variable z. The automorphism of the module Rz ⊕R induced by the substitution z → z +wϕ s preserves leading terms with respect to > s . Therefore the setB with respect to > s . However, with respect to > s−1 ,B may not be a Gröbner basis ofĨ. The following procedure modifieŝ B to obtain a Gröbner basis ofĨ with respect to > s−1 .
For each 0 ≤ i < γ, there are unique integers 0 ≤ i ′ < γ and k i satisfying such that ρ(a i,i y i ) + s ∈Λ if and only if k i ≥ 0. Let and where the bracket notation f [x k ] refers to the coefficient of the term x k in f . Observe that i ′ = (i + s) mod γ, and hence the map i → i ′ is a permutation of {0, 1, . . . , γ − 1} and that the integer c i is defined such that and if w i = w and c i > 0, let and if w i = w and c i ≤ 0, let where ν Proof: Let 0 ≤ i < γ. We consider the pair By the assumption that B (s) is a Gröbner basis of I v (s) with respect to > s , we have for 0 ≤ j < γ, Similarly we have for 0 ≤ j < γ with j = i, where the inequality is strict if and only if w = w i by the definition of w i in (4).
Now we consider the setB with respect to > s−1 . For the case that w i = w, by (6), In the case that w i = w and c i > 0, we have (7). Observe that and by (9) and (5), This implies that there is a canceling of the leading coefficients in (7). Therefore, together with (9), we have For the case that w i = w and c i ≤ 0, we have (8). By almost the same argument as above, we can show that Finally it is clear thatB still generates the moduleĨ. From (10), (11), and (12), we see thatB is a Gröbner basis ofĨ with respect to > s−1 , by the criterion in Proposition 1. For the following, it is important to keep in mind that the values w i , c i are determined only by B (s) and independent of w althoughB is clearly dependent on w.
Proof: Lemmas 9 and 10 imply where we used the equality shown by Lemma 4 and Proposition 2, and the equality shown by Proposition 3. Let for s ∈Λ, s ≤ 0. Then define Proof: Just note that ρ(ǫ i ) − ρ(y i ) ≥ 0 for 0 ≤ i < γ.
Proof: Note that To show the last equality, pick any f inR. Then for all large enough s.
a) Initialization: Let N = δ(h v ), and let B (N ) be the Gröbner basis of I v with respect to > N , Let w s = 0 for s with N < s ≤ 0, s ∈Λ. The following steps Pairing, Voting, and Rebasing are iterated for s decreasing from N to c) Voting: If s > 0 or s / ∈Λ, then for i with k i ≥ 0, let and for i with k i < 0, let w i = 0, µ i = 1. Let w = 0 in both cases. If s ≤ 0 and s ∈Λ, then for each i, let and letc i = max{c i , 0}, and let w be the element of F with the largest w=wic i , and let w s = w. d) Rebasing: For each i, do the following. If w i = w, then let g and let ν and let ν and let ν e) Output: After the iterations, output the recovered message (w s0 , w s1 , . . . , w s k−1 ).
We now give an overview of the algorithm. Note that the decoding algorithm is in one of two phases while s decreases from N to s 0 . The first phase is when s > 0 or s / ∈Λ, and the second phase is when s ≤ 0, s ∈Λ. In the first phase, the Gröbner basis In the second phase, the algorithm determines w s by majority voting and updates B (s) such that B (s−1) is a Gröbner basis of When the algorithm terminates, w s are determined for all s ∈ Λ, s ≤ 0.

Proposition 14.
For N ≥ s ≥ s 0 , the set B (s) is a Gröbner basis of I v (s) with respect to > s .
Proof: This is proved by induction on s. For s = N , this is true by (1). Now our induction assumption is that this is true for s. In the second phase, we already saw in Proposition 7 that B (s−1) is a Gröbner basis of I v (s−1) . So it remains to consider the first phase. The proof for this case is similar to that of Proposition 7. Suppose By the induction assumption, we have for 0 ≤ j < γ, Similarly, by the induction assumption, we have for 0 ≤ j < γ with j = i, δ s (a i,i y i z) > δ s (a i,j y j z) and for 0 ≤ j < γ with where the inequality is strict except when ρ(a i,i y i )+s ∈Λ and . Now in the case when w i = 0, by (14) and (17), In the case when w i = 0 and c i > 0, by (15), Observe that and by the equality in (17), Finally in the case when w i = 0 and c i ≤ 0, by (16), Then we can show that lt s−1 (f

C. Complexity
Recall that the main data with which the decoding algorithm works is essentially 2γ × 2γ array of polynomials in F[x] that represents B (s) . Each of the 2γ rows of the array are again viewed as pairs of vectors in F[x] γ . To optimize the speed complexity of the algorithm, it is necessary to precompute and store required information as vectors in F[x] γ before the error correction processing for the received vector v begins.
For the Initialization step, we precompute h i for 1 ≤ i ≤ n and η i for 0 ≤ i < γ in the vector form. Then for given v, h v is computed just as an F-linear combination of the vectors. Thus the setup of the initial Gröbner basis B (N ) is straightforward.
In the Rebasing step, the most intensive computation is the substitution of z with z + wϕ s . As ϕ s is in the form x kȳ i , the computation is facilitated if y iȳj for 0 ≤ i, j < γ is precomputed in the vector form. The necessity of the precomputation of y iȳj was first noted in [13] for the case of general one-point codes.
If the output of the algorithm at the Output step should be the corrected codeword, say, under systematic encoding, then precomputation of the vectors ev(ϕ si ) in F n for 0 ≤ i ≤ k − 1, essentially the generator matrix of the code C, would be necessary.

Proposition 16. Lagrange basis polynomial h i can be chosen such that the maximum degree of the polynomials in the vector form of h i is bounded by
Proof: By the Riemann-Roch, we can choose h i in

Proposition 17. The maximum degree of the polynomials in the vector form of η i is bounded by
Proof: Since dim FR /J = n, there can be no more than n monomials preceding lm(η i ), which implies δ(η i ) ≤ s n . Recall that Λ + s 0 ⊂Λ. Therefore s n ≤ s 0 + n + g. Suppose Since δ(ȳ j ) ≥ s 0 , we have deg(η ij ) ≤ (n + g)/γ.

Proposition 18.
The maximum degree of the polynomials in the 2γ × 2γ array during an execution is bounded by If g = 0, then it is bounded by n.
Proof: First observe that the behavior of the algorithm is such that the maximum of δ(f ) for f ∈ B (s) is monotonically decreasing through the iterations. So it suffices to consider δ(η i ) and δ(y i h v ) in the initial basis B (N ) . Since δ(h i ) ≤ n − |G| + 2g − 1 and ρ(y i ) = a i ≤ 2g + γ − 1 by the definition of a i , we have On the other hand, δ(η i ) ≤ s 0 + n + g. Hence during the execution, we have for f ∈ B (s) , δ(f ) = max{γ + n − |G| + 4g − 2, s 0 + n + g}, from which we deduce that the maximum degree of the polynomials in the array is bounded by max{1 + (n + 4g − 2)/γ, (n + g)/γ}, where the former is larger if g > 0. If g = 0, the latter is larger, and is n.

Proposition 19. The number of iterations is at most
Proposition 20. If g > 0, an execution of the decoding algorithm takes O((n + 4g)(n + 2g)g) multiplications. For g = 0, it takes O(n 2 ) multiplications. The implicit constant is absolute.
Proof: For the first phase iteration, the update for each pair of the upper and lower rows of the array takes O(n + 4g + γ) multiplications. Hence for the whole array, it takes O((n + 4g + γ)γ). For the second phase iteration, note that the maximum degree of the polynomials in the vector form of y iȳj is (4g + 2γ − 2)/γ. Hence the substitution operation for each row takes O((n + 4g)(2g + γ)/γ). For the whole array, it is O((n + 4g)(2g + γ)).
If g > 0, then γ ≤ g, so an iteration in either of first phase and second phase takes O((n + 4g)g) multiplications. Thus for N iter number of iterations, it takes O((n + 4g)(n + 2g)g) multiplications. On the other hand, γ = 1 for g = 0.
Finally the dominant part of the computation of the initial basis B (N ) is the computation of h v , which takes O(n(n + 2g)) multiplications.

IV. EXAMPLES
In this section, we give some explicit examples illustrating our decoding algorithm. We implemented the algorithm in Magma [14]. In particular, for the computation of y i andȳ i , Heß' algorithm [15] is heavily used as implemented in Magma. For the computation of η i , we used a custom FGLM algorithm [16].
Then the AG code C = C L (D, G) is a [26, 15,9] linear code over F 9 .

C. Two-Point Code on a Suzuki Curve
Let us consider the Suzuki curve over F 8 . The genus of the curve is g = 14. This curve has 65 rational points including one cusp at infinity. Let G = 15O + 24Q where O is the origin and Q is the unique place at the cusp. Let D be the sum of other 63 rational points.
Then the code C L (D, G) is a [63, 26, ≥ 25] linear code over F 8 with the best known minimum distance for codes of length 63 and dimension 26 over F 8 [17]. We have d LO = 25.
Recall that n = 63, g = 14, and γ = 8. The maximum degree of the polynomials in the vector forms of h i is 7 (N h = 11). The maximum degree of the polynomials in the vector forms of η i is 8 (N η = 9). In an experiment with 10 5 instances of decoding random errors of weight 12, the decoder performed at most 82 (N iter = 91) iterations with an 16 × 16 matrix of univariate polynomials at most 13 (N deg = 16) degree over F 8 . It took 0.0397 second to decode one instance on Macbook Pro, taking O(151606) multiplications according to Proposition 20.

D. Two-Point Reed-Solomon Code
The projective line over F 64 is a curve with genus 0 whose function field is the rational function field F 64 (x). It has 65 Note that n = 63, g = 0 and γ = 1. The maximum degree of the polynomials in the vector forms of h i is 62 = N h . The degree of the polynomial in the vector form of η 0 is 63 = N η . In an experiment with 10 5 instances of decoding random errors of weight 12, the decoder performed at most 63 = N iter iterations with 2 × 2 matrix of univariate polynomials at most 63 = N deg degree over F 64 . It took 0.0039 second to decode one instance, taking O(3969) multiplications.

V. REMARKS
We presented a unique decoding algorithm that can decode errors up to half of the bound d LO . Beelen and Høholdt's algorithm in [8] is similar in approach to ours, and can decode up to half of their generalized order bound. Thus we can speculate that d LO is related with the generalized order bound. Indeed it was shown in [7] that the bound d LO as defined in [5] coincides with the so-called Andersen-Geil bound d AG [18]. The relationship between these bounds may be treated in a separate place.
Geil and et al. [7] also showed that by a slight modification, the algorithm in [5] can be turned to a list decoding algorithm. The same can be done with the present general algorithm, but we leave out the details.


text:
Information Rates for Faster-Than-Nyquist Signaling with 1-Bit Quantization and Oversampling at the Receiver

Oversampling combined with low quantization resolutions has been shown to be a viable option when aiming for energy efficiency in multigigabit/s communications systems. This work considers the case of 1-bit quantization combined with oversampling and shows how the performance of such a system can be improved by using matched pulse shaping filters and faster than Nyquist signaling. The channel is considered with additive Gaussian noise and the performance of the system is evaluated in terms of achievable information rate under symbol-by-symbol detection.

I. INTRODUCTION
Increasing data rates of todays communications systems and thus increasing signaling bandwidths, demand for higher sampling rates at the receiver. One bottleneck, with increasing bandwidth and sampling rate, is the analog-to-digital conversion (ADC) in the receiver. Contemporary converters with fine grained quantization and high sampling rates tend to have a high power consumption [1]. This can be counteracted by limiting the resolution to fewer bits (1-3 bits). The extreme case of one bit quantization in combination with oversampling with respect to symbol rate has been shown to be applicable [2], using a certain dithering signal. It has been shown that in many scenarios an even simpler architecture also provides a remarkable performance [3], [4], [5] and is thus under further investigation in this work.
Over the last decade some investigations in regard to coarse quantization have been carried out. In [6] the optimal input distributions with average power constraint, which maximize information rates depending on the signal-to-noise ratio (SNR), have been evaluated for different quantization resolutions. It has been shown that for 1-bit quantization and additive white Gaussian noise (AWGN) channels, binary phase shift keying (BPSK) is optimal and achieves channel capacity when sampling at symbol rate. In [7] 4-QAM and 16-QAM were shown to produce good results, with the latter yielding rates above two bits per symbol for a certain SNR range when employing oversampling. It was also shown that in those cases higher order modulation schemes (i.e. 16-QAM) gain more This work has been supported in part by the German Research Foundation in the framework of the Collaborative Research Center 912 "Highly Adaptive Energy-Efficient Computing" and by the European Social Fund in the framework of the Young Investigators Group "3D Chip-Stack Intraconnects". information rate from oversampling than lower ones (i.e. 4-QAM). In [4] it was shown that it is possible to benefit from intersymbol interference (ISI) when using 1-bit quantization and oversampling, where the interference appears like dithering. Furthermore the work in [5] indicates significantly increased information rates when considering 1-bit oversampling with ISI in combination with sequence estimation receivers.
In contrast to the existing literature [4], this work also considers signaling rates above Nyquist rate. This approach is investigated as it is promising to increase the spectral efficiency. Furthermore different pulse shapes than previously have been used. It turned out that, especially when using rootraised-cosine (RRC) filters, information rates can be increased by employing signaling rates above Nyquist rate.
The paper is organized as follows: Section II gives an overview of the considered system model. In Section III the calculation of the information rate for the system is illustrated. Section IV explains the approach of signaling rates above Nyquist rate [8]. The numerical performance results and their implications are examined in V. The final Section VI concludes the paper with a brief summary of the addressed topics.
In this paper bold letters describe vectors and bold capital letters define matrices such as y k and H, furthermore sequences of symbols are denoted as x k+L/2 k−L/2 = x k−L/2 , . . . , x k+L/2 .

II. SYSTEM MODEL
The received signal z(t) of a communications system with complex input symbols drawn from a finite set x k ∈ X (symbol rate 1/T s ), two matched filters v(t), g(t) and additive white Gaussian noise n(t) is given by where both filters have unit energy. The combined channel waveform is denoted as h(t) = v(t) * g(t). The discrete quantized M -fold oversampled signal is denoted as where Q 1 [·] describes the 1-bit quantization operator and m = 1 . . . M is the running index sampling M times per symbol duration T s . The stacked M samples per symbol duration are denoted in vector notation as y k = [y k,1 , . . . , y k,M ] T .
In the corresponding discrete system model, which can be seen in Figure 1, oversampling is realized by upsampling the input symbols. It is considered that the filter h has the length of L + 1 symbols and the filter g has the length of N symbols (L and N are even). As the receive filter has unit energy the noise variance at the output of the filter is equivalent to the noise power density σ 2 n . This is modeled equivalently with i.i.d noise samples n = [n k,1 , . . . , n k,M ] T of variance σ 2 n . The system follows with where U is the upsampling matrix of the dimension (L + 2)M − 1 × L + 1. Its elements are given by The filter matrices H with dimension M × (L + 2)M − 1 and G with dimension M × (N + 1)M have a Toeplitz structure as follows They are signified by the reversed vector of the corresponding filter, i.e. h r = h (L+1)M , . . . , h 1 T respectively g r = [g N ·M , . . . , g 1 ] T , followed by zeros such that they match the defined dimensions.
III. INFORMATION RATE As a measure for the achievable throughput a lower bound on the information rate (see the Appendix) is considered. Indeed the lower bound for i.i.d. input given by corresponds to the information rate that treats the channel as an equivalent discrete memoryless channel (DMC). Albeit the present channel has memory which could be exploited, this work considers a simple receiver architecture which employs symbol-by-symbol detection. To compute this information rate, the mutual information of a DMC is used which is given by where P (x k ) and P (y k ) are the probability distributions of the sent and received symbols respectively. Caused by the waveform and oversampling each transmitted symbol interferes with every sample taken from previous and future symbols, with exception of sampling at Nyquist rate (no oversampling) and using Nyquist pulses. Therefore the transition probability is as follows where L is the number of neighboring symbols that influence the current oversampling observation y k .
The unquantized received signal z k is characterized by the additive white Gaussian noise with the specific mean and variance determined by the filters. The mean is calculated by (10) and the noise covariance matrix is given by The probability density function is then given by the multivariate complex Gaussian distribution, written as The final transition probability can be found by integrating (12) over the quantization interval where Y k = {z k |Q 1 [z k ] = y k }, which corresponds to integration limits of minus infinity and zero or zero and infinity.

IV. SIGNALING RATES ABOVE NYQUIST RATE
The following sections rely on the fact that the bandwidth B is only determined by the pulse shaping filters v(t) and g(t) included in h(t). When considering Nyquist pulses the signaling rate is conventionally chosen as 1/T s = B. Following the approach in [8] and [9], cases with faster than Nyquist signaling rate are also considered, which corresponds to Applying faster signaling rates while keeping the bandwidth constant increases the amount of intersymbol interference (ISI) between neighboring symbols. On one hand this leads to a decreased system performance, however, due to the increased signaling rate this effect can be compensated to some extent. Looking at the overall system performance it is assumed that a beneficial tradeoff between mutual information per channel use and signaling rate exists. This tradeoff corresponds to an increased spectral efficiency which might be implemented with low complexity, suitable for multigigabit/s communications. As for oversampling receivers interference is already present in general it is promising to employ faster signaling rates. In the following section those effects are investigated by carrying out numerical simulations with oversampling and 1-bit conversion.

V. NUMERICAL RESULTS
The numerical results have been obtained by considering i.i.d. symbols from the 4-QAM respectively 16-QAM alphabet. The system is assumed to be coherent.
Two pulse shaping filter types have been applied, namely the Gaussian shaped filter and the Root-Raised-Cosine filter, which are commonly used in various digital communications systems. Such filters can be designed variable and energy efficient in analog domain as it is proposed in [10] and [11]. The Gaussian and RRC filters are characterized by parameters that determine shape and bandwidth. The Gaussian filter is given by where the product B 3dB T s is the design parameter controlling the pulse shape. The RRC filter is determined by where 1/T x determines the 3 dB bandwidth and β is the roll-off factor of the pulse. It is furthermore assumed that v(t) = g(t) and h(t) = v(t) * g(t). As those filters have an infinite impulse response, an approximation with finite length of L + 1 = 9 symbol durations has been applied to reduce computational complexity, given by their discrete representations h and g. All obtained results were computed using a Monte-Carlo-Simulation in order to estimate P (y|x) and P (y). The symmetry of I and Q has been taken into account by simulating only one phase component to ease computation, which is sufficient since coherence is assumed.

A. Comparison Gauss and Root-Raised-Cosine Filters at Conventional Signaling Rate
The simulation results show that both pulses can lead to an increased information rate compared to results as reached in [7] (in Figure 2 Rectangular). This gain can be explained by an intersymbol interference based dithering utilization. For RRC pulses this effect is stronger as compared to the Gaussian pulse. According to our experience with this scenario, the benefit of increasing the oversampling rate further only leads to marginal performance gains, which can be explained by a strong correlation of the individual samples.
The results shown in Figure 2 provide an example of different parameters. Another benefit that can be seen is the stabilization of information rates at higher SNR values. This might be useful for receiver implementations that need to operate within a wide SNR range.

B. Tradeoff when employing faster signaling rates with RRC pulses
In this section the performance gain that can be achieved by signaling faster than Nyquist is going to be considered. Although the achievable rate, when considering Gaussian pulses, is rather robust against 3 dB bandwidth reduction, they are not considered because of their overall infinite bandwidth and the following investigations are only done with RRC pulses. The idea is that higher signaling rates can be achieved by fixing the pulses 3 dB bandwidth B 3dB = 1/T x and reducing the symbol duration to values smaller than the inverse of the bandwidth T x > T s . Equivalently it is possible to to reduce the 3 dB bandwidth of the system by fixing symbol duration T s while reducing bandwidth 1/T x . These two options are interchangeable since only the relation between 3 dB bandwidth and symbol duration matters, B 3dB ·T s = T s /T x . Conventional faster than Nyquist signaling is for RRC pulses achieved when holds. This method is especially promising for lower order modulation schemes and hence it was also employed with 4-QAM, which seemed feasible for the use with 1-bit quantization in previous investigations. With roll-off factor β and signaling parameter T x /T s (T x /T s = 1 is the conventional signaling case examined in Section V-A) being variable, a three dimensional optimization problem emerges when searching for maximum information rate at any given SNR. Note that the parameter T x /T s is the inverse of the parameter B 3dB · T s and thus only values greater than 1 are of interest.
From the numerical results, examples shown in Figure 3 at 5 dB and 25 dB, different observations can be made. First in most of the cases an increase of the roll-off factor improves the information rate. The second result is that the full rate of 2 bits per channel use (bpcu), when using 4-QAM, is achievable for a number of scenarios with B 3dB · T s < 1. Such a range exists for 16-QAM as well but is substantially smaller. The maximum achievable rate can, however, be higher than 2 bpcu (M = 4), but is more strongly dependent on the SNR and is hence also more susceptible to the additional interference brought by the faster than signaling approach.
Oversampling is especially beneficial in the lower SNR regime and for achieving more than 2 bpcu when using 16-QAM. Note that results for T x /T s < 1 provide similar results but would require more bandwidth and are therefore not desired for this concept.
Since faster signaling cases are applicable the achievable rate would be higher compared to systems signaling with T x = T s . Mutual information per channel use as considered before does not account for that performance increase. Therefore an information rate shall be considered that includes the gain of the increased signaling rates.
Consider that the information rate I in bpcu from Section V-A measures the information per symbol duration T s . In the scenario with variable signaling rates, with T s = T x , the effective achievable rate scales with the bandwidth. This can be taken into account by using I 3dB for the faster signaling scenarios given as Figure 4 depicts the 25 dB graphs when applying equation (18) to the results. There is a maximum for each case which is located in the signaling region T x /T s > 1, meaning that the optimal tradeoff can be achieved by using faster than conventional signaling. 4-QAM can benefit more from faster signaling rates due to its property of being more stable when using 1-bit quantization.
The comparison of the results in Figure 4b shows that for lower signaling values T x /T s , 16-QAM in combination with oversampling has the higher information rate and that 4-QAM, with or without oversampling, can achieve rates substantially higher than 16-QAM in a certain parameter range.

VI. CONCLUSION
In this paper a communications system with matched filters, 1-bit AD-conversion and oversampling has been considered. Gaussian and RRC filters were applied and their influence on the information rate of such a system was investigated. It has been shown that the information rate can be increased compared to using a rectangular pulse with wideband receiver. Furthermore the applicability of faster than Nyquist signaling for this system was explored. The results reveal that a gain in overall system performance is possible depending on the chosen pulse shape, the SNR and the modulation scheme. Furthermore a tradeoff between faster signaling rate and information rate per symbol was considered to find the combination of the two that has the best system performance. This showed that modulation schemes, whose full information rates are more easily accessible for 1-bit quantization, can benefit more from an increased signaling rate. Consequently, choosing the signaling rate wisely is a simple and efficient method to increase the achievable rate, when considering receivers with 1-bit quantization.

APPENDIX
The considered lower bound on the achievable rate can be calculated based on the entropy rates by From the i.i.d. assumption follows that H(X n ) = n k=1 H(X k ). Furthermore the equation holds as conditioning can only reduce entropy.


text:
Privacy Gain Based Multi-Iterative k-Anonymization to Protect Respondents Privacy

Huge volume of data from domain specific applications such as medical, financial, telephone, shopping records and individuals are regularly generated. Sharing of these data is proved to be beneficial for data mining application. Since data mining often involves data that contains personally identifiable information and therefore releasing such data may result in privacy breaches. On one hand such data is an important asset to business decision making by analyzing it. On the other hand data privacy concerns may prevent data owners from sharing information for data analysis. In order to share data while preserving privacy, data owner must come up with a solution which achieves the dual goal of privacy preservation as well as accuracy of data mining task mainly clustering and classification. Privacy Preserving Data Publishing (PPDP) is a study of eliminating privacy threats like linkage attack while preserving data utility by anonymizing data set before publishing. Proposed work is an extension to k-anonymization where Privacy Gain (PrGain) has been computed for selective anonymization for set of tuples. Classification and clustering characteristics of original data and anonymized data using proposed algorithm have been evaluated in terms of information loss, execution time, and privacy achieved. Algorithm has been processed against standard data sets and analysis shows that values for sensitive attributes are being preserved with minimal information loss.

INTRODUCTION
Databases today can range in size into the terabyte. Within these masses of data lies hidden information of strategic importance. The newest answer is data mining, which is being used both to increase revenues and to reduce costs. The potential returns are enormous. Innovative organizations worldwide are already using data mining to locate and appeal to higher-value customers, to reconfigure their product offerings to increase sales, and to minimize losses due to error or fraud. Data mining is a process that uses a variety of data analysis tools to discover patterns (finding interesting information) and relationships in data that may be used to make valid predictions. With more and more information accessible in electronic forms and available on the web, and with increasingly powerful data mining tools being developed and put into use, there are increasing concerns that data mining may pose a threat to privacy and data security. However, it is important to note that most of the major data mining applications focus on the development of scalable algorithms and also do not involve personal data. The focus of data mining technology is on the discovery of general patterns, not on specific information regarding individuals. In this sense, we believe that the real privacy concerns are with unconstrained access of individual records, like credit card and banking applications, for example, which must access privacy-sensitive information. For those data mining applications that do involve personal data, in many cases, privacy required to be preserve. Data mining can be valuable in many applications, but due to no sufficient protection data may be abused for other goals. The main factor of privacy breaching in data mining is data misuse. In fact, if the data consists of critical and private characteristics and/or this technique is abused, data mining can be hazardous for individuals and organizations. Therefore, it is necessary to prevent revealing not only the personal confidential information but also the critical knowledge.
Privacy Preserving Data Mining (PPDM) has been emerged to address the privacy issues in data mining. Embedding privacy into data mining has been an active and an interesting research area. Several data mining techniques, incorporating privacy protection mechanisms, have been proposed based on different approaches. Recent research in the area of PPDM has devoted much effort to determine a trade-off between privacy and the need for knowledge discovery, which is crucial in order to improve decision-making processes and other human activities. PPDM helps to protect personal, proprietary or sensitive information, to enable collaboration between different data owners and also to comply with legislative policies.

RELATED WORK
There have been several methods developed by researchers in the database community that process records in a "group-based" manner, using information about specific local records globally to transform the records in a way which preserves specific privacy metrics. These modified records can then be published without fear of reconstruction by attacks. There is an assumption that certain fields of a record contain quasiidentifiers that uniquely identify an individual associated with the record, as well as sensitive attributes that must not be linked to the individual by an untrusted third party. Three variants of grouping-based methods (k-anonymity, ℓ-diversity, and t-closeness) have been proposed that rely on achieving the final state where k records look exactly the same.  k-anonymity and its variants The k-anonymity model proposed by Samarati and Sweeney [1][2][3] achieves privacy by enforcing the constraint that every row of the released database should be indistinguishable from at least k other rows with respect to a selected set of attributes called quasiidentifiers. This is usually achieved by suppressing (removing all or part of a field value), generalizing (using some pre-specified hierarchy of values), swapping values in the database. k-anonymity protects against identity disclosure, it does not provide sufficient protection against attribute disclosure. Homogeneity attack and back ground knowledge attack create challenges to k-anonymity approaches. A variant of kanonymity known as ℓ-diversity was introduced by Machanavajjhala et al. [4]. It guarantees privacy in certain situations where k-anonymity does not, such as when there is little diversity in the sensitive attributes or when the adversary has some background information. Proposed method in [4] seems to be biased towards privacy at the cost of usability. The t-closeness model is a further enhancement on the concept k-anonymity and ℓ-diversity. One characteristic of the ℓ-diversity model is that it treats all values of a given attribute in a similar way irrespective of its distribution in the data. This is rarely the case for real data sets, since the attribute values may be much skewed. This may make it more difficult to create feasible ℓ-diverse representations.
Often, an adversary may use background knowledge of the global distribution in order to make inferences about sensitive values in the data. Furthermore, not all values of an attribute are equally sensitive. For example, an attribute corresponding to a disease may be more sensitive when the value is positive, rather than when it is negative. t-closeness requires that the distribution of a sensitive attribute in any equivalence class is close to the distribution of the attribute in the overall data set [5].  Personalized privacy preservation A corporation may have very different constraints on the privacy of its records as compared to an individual, so we may wish to treat the records in a given data set very differently for anonymization purposes. This means that the value of k for anonymization is not fixed but may vary with the record. A condensation based approach [6] has been proposed for PPDM in the presence of variable constraints on the privacy of the data records. This technique constructs groups of nonhomogeneous size from the data, such that it is guaranteed that each record lies in a group whose size is at least equal to its anonymity level. Subsequently, pseudo-data are generated from each group so as to create a synthetic data set with the same aggregate distribution as the original data set. Another interesting model of personalized anonymity is discussed in [7] in which a person can specify the level of privacy for his or her sensitive values. This technique assumes that an individual can specify a node of the domain generalization hierarchy in order to decide the level of anonymity that he can work with.  Utility based privacy preservation The loss of information can also be considered a loss of utility for data mining purposes. The problem of utility based PPDM was first studied in [8]. The idea was to improve the curse of dimensionality by separately publishing marginal tables containing attributes which have utility, but are also problematic for privacy preservation purposes. The generalizations performed on the marginal tables and the original tables in fact do not need to be the same. A method for utility based data mining using local recoding was proposed in [9]. The approach is based on the fact that different attributes have different utility from an application point of view. Most anonymization methods are global, in which a particular tuple value is mapped to the same generalized value. In local recoding, the data space is partitioned into a number of regions, and the mapping of the tuple to generalize value is local to that region. Another direction for utility based PPDM is to anonymize the data in such a way that it remains useful for particular kinds of data mining or database applications. For example, in [10], a method has been proposed for kanonymization using an information-loss metric as the utility measure. Such an approach is useful for the problem of classification.

PRIVACY GAIN BASED MULTI-ITERATIVE K-ANONYMIZATION
A. Framework Fig. 1 describes basic framework for PrGain based kanonymization. Each quasi-identifier has been generalized at minimum level to achieve privacy protection without compromising mush on data utility.
Quasi-identifiers providing maximum privacy have been selected and anonymized tuples have been marked and stored in data set . Remaining unanonymized tuples follow same procedure with minimum subsequent level of quasi-identifiers' generalization. Process terminates when entire dataset D is kanonymized or there is no further anonymization possible from dimension table on data set. To evaluate protection provided to respondents' privacy against information loss, well accepted Naïve Bayes classification algorithm has been used to test data set D and k-anonymized data set .

(b)
Step 4: Generalization is applied for each quasi-identifier on unanonymized tuples from step 3. In case of equal PrGain both sets are considered.
(a) (b) Step 5: Generalization is applied for each quasi-identifier on unanonymized tuples from step 4.

C. Algorithm
In proposed PrGain based algorithm, generalization has been applied for each quasi-identifier. PrGain has been computed for individual quasi-identifiers upon generalization based on dimension table. Quasiidentifier with maximum PrGain has been selected and tuples generalized have been marked k-anonymized. Anonymized tuples then removed from original data set D and stored into new data set D'. For rest of unanomymized tuples in D, same process has been applied until k-anonymization has been achieved for entire data set D or generalization has been applied to all quasi-identifiers to the maximum level as mentioned in dimension table and no further generalization possible on unanonymized tuples. It has been observed while applying proposed PrGain based algorithm that respondents' information has been protected with minimal data loss. Further this approach is based on multi-iteration on non k-anonymized set of tuples greatly reduces processing time. Earlier proposed works were rescanning entire data set for anonymization, we have made an attempt to provide solution with lesser execution time by proposing Privacy Gain (PrGain) concept.

CONCLUSION
Protecting respondents' privacy while data mining creates challenges to data mining community. Two ways respondents' privacy can be preserve, one by modifying sensitive information itself and second by keeping sensitive information available for data mining while eliminating identifier attributes and generalizing and/or suppressing quasi-identifiers. We have coined new term called Privacy Gain while proposing algorithm to generalizing and/or suppressing quasiidentifiers' value. Selective anonymization has been applied based on PrGain computed in subsequent iteration. Proposed algorithm has an advantage of rescanning of only subset of original data set which is not k-anonymized. We have tested proposed PrGain based algorithm against standard data set and found that respondent privacy has been protected with small amount of data loss which occurs due to anonymization. Classification results with original data sets versus classification results obtained using anonymized data sets over Naïve Bayes algorithm have been compared. Anonymization parameter has been taken as k = 2, 3, 4 while number of quasi-identifiers have been set as q = 2, 3. It has been observed that proposed approach significantly reduces execution time as total data set rescan is no more required and provides better privacy without compromising much on data utility.


s2fieldsofstudy:
Computer Science
Geography

text:
Automatic Annotation Suggestions and Custom Annotation Layers in WebAnno

In this paper, we present a flexible approach to the efficient and exhaustive manual annotation of text documents. For this purpose, we extend WebAnno (Yimam et al., 2013) an open-source web-based annotation tool. 1 While it was previously limited to specific annotation layers, our extension allows adding and configuring an arbitrary number of layers through a web-based UI. These layers can be annotated separately or simultaneously, and support most types of linguistic annotations such as spans, semantic classes, dependency relations, lexical chains, and morphology. Further, we tightly integrate a generic machine learning component for automatic annotation suggestions of span annotations. In two case studies, we show that automatic annotation suggestions, combined with our split-pane UI concept, significantly reduces annotation time.

Introduction
The annotation of full text documents is a costly and time-consuming task. Thus, it is important to design annotation tools in such a way that the annotation process can happen as swiftly as possible. To this end, we extend WebAnno with the capability of suggesting annotations to the annotator.
A general-purpose web-based annotation tool can greatly lower the entrance barrier for linguistic annotation projects, as tool development costs and preparatory work are greatly reduced. WebAnno 1.0 only partially fulfilled desires regarding generality: Although it covered already more kinds of annotations than most other tools, it supported only a fixed set of customizable annotation layers (named entities, part-of-speech, lemmata, coreference, dependencies). Thus, we also remove a limitation of the tool, which was previously bound to specific, hardcoded annotation layers.
We have generalized the architecture to support three configurable generic structures: spans, relations, and chains. These support all of the original layers and allow the user to define arbitrary custom annotation layers based on either of these structures. Additionally, our approach allows maintaining multiple properties on annotations, e.g. to support morphological annotations, while previously only one property per annotation was supported.
Automatic suggestion of annotations is based on machine learning, which is common practice in annotation tools. However, most of existing web-based annotation tools, such as GATE (Cunningham et al., 2011) or brat (Stenetorp et al., 2012), depend on external preprocessing and postprocessing plugins or on web services. These tools have limitations regarding adaptability (difficulty to adapt to other annotation tasks), reconfigurability (generating a classifier when new features and training documents are available is complicated), and reusability (requires manual intervention to add newly annotated documents into the iteration).
For our approach, we assume that an annotator actually does manually verify all annotations to produce a completely labeled dataset. This task can be sped up by automatically suggesting annotations that the annotator may then either accept or correct. Note that this setup and its goal differs from an active learning scenario, where a system actively determines the most informative yet unannotated example to be labeled, in order to quickly arrive at a high-quality classifier that is then to be applied to large amounts of unseen data.
Our contribution is the integration of machine learning into the tool to support exhaustive an-notation of documents providing a shorter loop than comparable tools (Cunningham et al., 2011;Stenetorp et al., 2012), because new documents are added to the training set as soon as they are completed by the annotators. The machine learning support currently applies to sequence classification tasks only. It is complemented by our extension allowing to define custom annotation layers, making it applicable to a wide range of annotation tasks with only little configuration effort.
Section 2 reviews related work about the utilization of automatic supports and customization of annotation schemes in existing annotation tools. The integration of automatic suggestions into WebAnno, the design principles followed, and two case studies are explained in Section 3. Section 4 presents the implementation of customizable annotation layers into the tool. Finally, Section 5 summarizes the main contributions and future directions of our work.

Related Work
Automatic annotation support The impact of using lexical and statistical resources to produce pre-annotation automatically to increase the annotation speed has been studied widely for various annotation tasks. For the task of medical named entity labeling, Lingren et al. (2013) investigate the impact of automatic suggestions on annotation speed and potential biases using dictionary-based annotations. This technique results in 13.83% to 21.5% time saving and in an inter-annotator agreement (IAA) increase by several percentage points.
WordFreak (Morton and LaCivita, 2003) includes an automation component, where instances with a low machine learning confidence are presented for annotation in an active learning setup. Beck et al. (2013) demonstrate that the use of active learning for machine translation reduces the annotation effort and show a reduced annotation load on three out of four datasets.
The GoldenGATE editor (Sautter et al., 2007) integrates NLP tools and assistance features for manual XML editing. The tool is used in correcting/editing an automatically annotated document with an editor where both text and XML markups are modified. GoldenGATE is merely used to facilitate the correction of an annotation while preannotation is conducted outside of the tool.
Automatic annotation support in brat (Stenetorp et al., 2012) was carried out for a semantic class disambiguation task to investigate how such automation facilitates the annotators' progress. They report a 15.4% reduction in total annotation time. However, the automation process in brat 1) depends on bulk annotation imports and web service configurations, which is labor intensive, 2) is task specific so that it requires a lot of effort to adapt it to different annotation tasks, 3) there is no way of using the corrected result for the next iteration of training the automatic tool.
The GATE Teamware (Bontcheva et al., 2013) automation component is most similar to our work. It is based either on plugins and externally trained classification models, or uses web services. Thus, it is highly task specific and requires extensive configuration. The automatic annotation suggestion component in our tool, in contrast, is easily configurable and adaptable to different annotation tasks and allows the use of annotations from the current annotation project.
Custom annotation layers Generic annotation data models are typically directed graph models (e.g. GATE, UIMA CAS (Götz and Suhre, 2004), GrAF (Ide and Suderman, 2007)). In addition, an annotation schema defines possible kinds of annotations, their properties and relations. While these models offer great expressiveness and flexibility, it is difficult to adequately transfer their power into a convenient annotation editor. For example, one schema may prescribe that the part-of-speech tag is a property on a Token annotation, another one may prescribe that the tag is a separate annotation, which is linked to the token. An annotator should not be exposed to these details in the UI and should be able to just edit a part-of-speech tag, ignorant of the internal representation.
This problem is typically addressed in two ways. Either, the full complexity of the annotation model is exposed to the annotator, or the annotation editor uses a simplified model. The first approach can easily lead to an unintuitive UI and make the annotation an inconvenient task. The second approach (e.g. as advocated by brat) requires the implementation of specific import and export filters to transform between the editor data model and the generic annotation data models.
We propose a third approach integrating a configurable mapping between a generic annotation model (UIMA CAS) and a simplified editing model (brat) directly into the annotation tool. Thus, we avoid exposing the full complexity of the generic model to the user and also avoid the necessity for implementing import/export filters. Similar approaches have already been used to map annotation models to visualization modules (cf. (Zeldes et al., 2009)), but have, to our knowledge, not been used in an annotation editor. Our approach is different from schema-based annotation editors (e.g. GATE), which employ a schema as a template of properties and controlled vocabularies that can be used to annotate documents, but which do not allow to map structures inherent in annotations, like relations or chains, to respective concepts in the UI.

Automatic Annotation Suggestions
It is the purpose of the automatic annotation suggestion component to increase the annotation efficiency, while maintaining the quality of annotations. The key design principle of our approach is a split-pane ( Figure 1) that displays automatic annotation suggestions in the suggestion pane (lower part) and only verified or manual ones in the annotation pane (upper part). In this way, we force the annotators to review each automatic suggestion as to avoid overlooking wrong suggestions.

Suggestion modes
We distinguish three modes of automatic annotation suggestion: Correction mode In this mode, we import documents annotated by arbitrary external tools and present them to the user in the suggestion pane of the annotation page. This mode is specifically appropriate for annotation tasks where a preannotated document contains several possibilities for annotations in parallel, and the user's task is to select the correct annotation. This allows to leverage specialized external automatic annotation components, thus the tool is not limited to the integrated automation mechanism.
Repetition mode In this mode, further occurrences of a word annotated by the user are highlighted in the suggestion pane. To accept suggestions, the user can simply click on them in the suggestion pane. This basic -yet effective -suggestion is realized using simple string matching.
Learning mode For this mode, we have integrated MIRA (Crammer and Singer, 2003), an extension of the perceptron algorithm for online machine learning which allows for the automatic suggestions of span annotations. MIRA was selected because of its relatively lenient licensing, its good performance even on small amounts of data, and its capability of allowing incremental classifier updates. Results of automatic tagging are displayed in the suggestion pane. Our architecture is flexible to integrate further machine learning tools.

Suggestion Process
The workflow to set up an automatically supported annotation project consists of the following steps.
Importing annotation documents We can import documents with existing annotations (manual or automatic). The annotation pane of the automation page allows users to annotate documents and the suggestion pane is used for the automatic suggestion as shown in Figure 1. The suggestion pane facilitates accepting correct pre-annotations with minimal effort.
Configuring features For the machine learning tool, it is required to define classification features to train a classifier. We have designed a UI where a range of standard classification features for sequence tagging can be configured. The features include morphological features (prefixes, suffixes, and capitalization), n-grams, and other layers as a feature (for example POS annotation as a feature for named entity recognition). While these standard features do not lead to state-of-the-art performance on arbitrary tasks, we have found them to perform very well for POS tagging, named entity recognition, and chunking. Figure 2 shows the feature configuration in the project settings.
Importing training documents We offer two ways of providing training documents: importing an annotated document in one of the supported file formats, such as CoNLL, TCF, or UIMA XMI; or using existing annotation documents in the same project that already have been annotated.
Starting the annotation suggestion Once features for a training layer are configured and training documents are available, automatic annotation is possible. The process can be started manually by the administrator from the automation settings page, and it will be automatically re-initiated when additional documents for training become available in the project. While the automatic annotation is running in the background, users still can work on the annotation front end without being affected. Training and creating a classifier will be repeated only when the feature configuration is changed or when a new training document is available.
Display results on the monitoring page After the training and automatic annotation are completed, detailed information about the training data such as the number of documents (sentence, tokens), features used for each layer, F-score on held-out data, and classification errors are displayed on the monitoring page, allowing an estimation whether the automatic suggestion is useful. The UI also shows the status of the training process (not started, running, or finished).

Case Studies
We describe two case studies that demonstrate language independence and flexibility with respect to sequence label types of our automatic annotation suggestions. In the first case study, we address the task of POS tagging for Amharic as an example of an under-resourced language. Second, we explore German named entity recognition.

Amharic POS tagging
Amharic is an under-resourced language in the Semitic family, mainly spoken in Ethiopia. POS tagging research for Amharic is mostly conducted as an academic exercise. The latest result reported by Gebre (2009) was about 90% accuracy using the Walta Information Center (WIC) corpus of about 210,000 tokens (1065 news documents). We intentionally do not use the corpus as training data because of the reported inconsistencies in the tagging process (Gebre, 2009). Instead, we manually annotate Amharic documents for POS tagging both to test the performance of the automation module and to produce POS-tagged corpora for Amharic. Based upon the work by Petrov et al. (2012) and Ethiopian Languages Research Center (ELRC) tagset, we have designed 11 POS tags equivalent to the Universal POS tags. The tag DET is not included as Amharic denotes definiteness as noun suffixes.
We collected some Amharic documents from an online news portal. 2 Preprocessing of Amharic documents includes the normalization of characters and tokenization (sentence and word bound- Figure 3: Example Amharic document. The red tags in the suggestion pane have not been confirmed by the annotator. ary detection). Initially, we manually annotated 21 sentences. Using these, an iterative automatic annotation suggestion process was started until 300 sentences were fully annotated. We obtained an F-score of 0.89 with the final model. Hence the automatic annotation suggestion helps in decreasing the total annotation time, since the user has to manually annotate only one out of ten words, while being able to accept most automatic suggestions. Figure 3 shows such an Amharic document in WebAnno.

German Named Entity Recognition
A pilot Named Entity Recognition (NER) project for German was conducted by Benikova et al. (2014). We have used the dataset -about 31,000 sentences, over 41,000 NE annotations -for training NER. Using this dataset, an F-score of about 0.8 by means of automatic suggestions was obtained, which leads to an increase in annotation speed of about 21% with automatic suggestion.

Customs Annotation Layers
The tasks in which an annotation editor can be employed depends on the expressiveness of the underlying annotation model. However, fully exposing the expressive power in the UI can make the editor inconvenient to use.
We propose an approach that allows the user to configure a mapping of an annotation model to concepts well-supported in a web-based UI. In this way, we can avoid to expose all details of the annotation model in the UI, and remove the need to implement custom import/export filters. WebAnno 1.0 employs a variant of the annotation UI provided by brat, which offers the concepts of spans and arcs. Based on these, WebAnno 1.2 implements five annotation layers: named entity, part-of-speech, lemmata, co-reference, and dependencies. In the new WebAnno version, we generalized the support for these five layers into three structural categories: span, relation (arc), and chain. Each of these categories is handled by a generic adapter which can be configured to simulate any of the original five layers. Based on this generalization, the user can now define custom layers (Figure 4).
Additionally, we introduced a new concept of constraints. For example, NER spans should not cross sentence boundaries and attach to whole tokens (not substrings of tokens). Such constraints not only help preventing the user from making invalid annotations, but can also offer extra convenience. We currently support four hard-coded constraints: Lock to token offsets Defines if annotation boundaries must coincide with token boundaries, e.g. named entities, lemmata, part-of-speech, etc. For the user's convenience, the annotation is automatically expanded to include the full token, even if only a part of a token is selected during annotation (span/chain layers only).
Allow multiple tokens Some kinds of annotations may only cover a single token, e.g. part-ofspeech, while others may cover multiple tokens, e.g. named entities (span/chain layers only).
Allow stacking Controls if multiple annotations of the same kind can be at the same location, e.g. if multiple lemma annotations are allowed per token. For the user's convenience, an existing annotation is replaced if a new annotation is created when stacking is not allowed.
Allow crossing sentence boundaries Certain annotations, e.g. named entities or dependency delations, may not cross sentence boundaries, while others need to, e.g. coreference chains.
Finally, we added the ability to define multiple properties for annotations to WebAnno. For example, this can be use to define a custom span-based morphology layer with multiple annotation properties such as gender, number, case, etc.

Conclusion and Outlook
We discussed two extensions of WebAnno: the tight and generic integration of automatic annotation suggestions for reducing the annotation time, and the web-based addition and configuration of custom annotation layers.
While we also support the common practice of using of external tools to automatically preannotate documents, we go one step further by tightly integrating a generic sequence classifier into the tool that can make use of completed annotation documents from the same project. In two case studies, we have shown quick convergence for Amharic POS tagging and a substantial reduction in annotation time for German NER. The key concept here is the split-pane UI that allows to display automatic suggestions, while forcing the annotator to review all of them.
Allowing the definition of custom annotation layers in a web-based UI is greatly increasing the number of annotation projects that potentially could use our tool. While it is mainly an engineering challenge to allow this amount of flexibility and to hide its complexity from the user, it is a major contribution in the transition from specialized tools towards general-purpose tools.
The combination of both -custom layers and automatic suggestions -gives rise to the rapid setup of efficient annotation projects. Adding to existing capabilities in WebAnno, such as curation, agreement computation, monitoring and finegrained annotation project definition, our contributions significantly extend the scope of annotation tasks in which the tool can be employed.
In future work, we plan to support annotation suggestions for non-span structures (arcs and chains), and to include further machine learning algorithms.


extfieldsofstudy:
Computer Science
Medicine

text:
Semi-Supervised Learning to Identify UMLS Semantic Relations

The UMLS Semantic Network is constructed by experts and requires periodic expert review to update. We propose and implement a semi-supervised approach for automatically identifying UMLS semantic relations from narrative text in PubMed. Our method analyzes biomedical narrative text to collect semantic entity pairs, and extracts multiple semantic, syntactic and orthographic features for the collected pairs. We experiment with seeded k-means clustering with various distance metrics. We create and annotate a ground truth corpus according to the top two levels of the UMLS semantic relation hierarchy. We evaluate our system on this corpus and characterize the learning curves of different clustering configuration. Using KL divergence consistently performs the best on the held-out test data. With full seeding, we obtain macro-averaged F-measures above 70% for clustering the top level UMLS relations (2-way), and above 50% for clustering the second level relations (7-way).

Introduction
Biomedical documents are abundant in relations between concepts. For example, the sentence "The long-chain n-3 polyunsaturated fatty acids have cardioprotective effects, which may be partly due to their anti-inflammatory properties." states at least two relations: the "long-chain n-3 polyunsaturated fatty acids" produces 1 "cardioprotective effects"; the "cardioprotective effects" are result_of "their antiinflammatory properties". However, such information, when locked in the narrative text, cannot be understood by computers due to lack of structure.
Mining relations from narrative text and making them accessible through a structured representation can benefit many studies, e.g., drug-drug, and drugdisease interaction studies. To this end, the Unified Medical Language System (UMLS) Semantic Network [1] can be used as a guide to align extracted structures. The network consists of the following:  A set of semantic types, which provides a categorization of all concepts represented in the UMLS Metathesaurus®.  A hierarchy of semantic relations, between semantic types. This hierarchy has been developed and populated by 1 Italic font in the main paper denotes the matching relations in the UMLS Semantic Network [1]. hand in a top-down manner and undergoes periodic manual revisions [2]. As a result, collecting annotated relation instances and discovering those instances potentially characterizing new relations needs human annotation, which is labor intensive and time consuming. Our goal is to build a system that can expedite this process by mining relation instances from biomedical narrative text with little human intervention.
For this purpose, we need to be able to automatically identify the semantic relations between biomedical named entities. This is a nontrivial task as a semantic relation can be expressed in different ways using verbs (e.g., causes), prepositions (e.g., due to), or nouns (e.g., result of). For example, to say a symptom is the result_of a disease, one can use "due to", "caused by", or "result of". In addition, solely relying on keywords themselves can be problematic because a given word can be polysemantic. For example, the word "undergo" in "patient undergoes homeopathy procedure" indicates that the patient is treated_by a treatment. The same word in "patient undergoes a severe seizure" means that the patient has_occurrence a disease/symptom. Context of the word "undergo" is necessary to characterize the relations between the named entities.
The UMLS semantic relations are organized in a hierarchy. For example, the relations disrupts, prevents, and complicates are categorized under a more generic relation affects. We focus on the top two levels of this hierarchy and test our method for identifying relations at both levels. In the rest of this paper, we first review related work, then describe the construction of our corpus. After that, we explain our automatic relation extraction method in detail, and present experimental studies.

Related Work
Sematic relation extraction from biomedical narrative text is an active area of research. Rosario et al. [3] compared five graphical models and neural networks in classifying seven relations between diseases and treatments, where the neural network outperformed all graphical models. Plake et al. [4] used finite automata to learn from training samples. Khoo et al. [5] identified causal relations with manually created syntactic patterns from MEDLINE [6]. Sibanda et al. [7] used support vector machines (SVM) [8] to recognize disease-treatment relations in discharge summaries.
Clinical NLP systems such as MedLEE [9] and SemRep [10] apply hand-crafted syntactic and semantic rules to extract UMLS semantic relations. Cooccurrence patterns in MEDLINE [6] have also been explored to identify gene and protein synonyms [11], protein-protein interactions [12] etc. (see [13] for a review). Recently, semi-supervised or unsupervised acquisition of semantic relations has gained traction in the general NLP domain, where the methods typically include clustering and co-clustering algorithms that are often augmented with seeding or subsequent supervised classification [14][15] [16]. We believe that these new developments towards demanding less annotated gold standard can shed light on the biomedical domain, where extracting the UMLS semantic relations largely depends on supervised learning.

Data Preparation
Our data set consists of the biomedical abstracts from the PubMed database [17]. We obtained the data set by crawling medical abstracts from the PubMed database that were returned in response to the query term "clinic". This query term was used to include a broad range of topics across the abstracts. We collected semantic entities mentioned in an abstract by applying the UMLS TFA parser [18] and extracting noun phrases from its phrase chunking output. We treated each noun phrase as a semantic entity and paired all phrases in one sentence. We filtered candidate semantic entity pairs based on whether a relation can exist between the semantic types of involved entities according to the UMLS Semantic Network. We focused on only the relations that are explicitly stated in the text. Two annotators, who have information science background and have completed college-level biology courses, annotated relations for each record. The annotators were presented with candidate semantic entity pairs and selected the best matching relations by following the UMLS semantic relation definitions. We found that some semantic relations in the third and fourth levels of the UMLS Semantic Network were either absent or were poorly represented in our corpus. Therefore, we limited ourselves to the seven relations in the top two levels of the UMLS Semantic Network. We performed double annotation for each semantic entity pair. The annotation lasted three months, covered 207 medical abstracts (3002 sentences) and produced 10082 semantic entity pairs. The initial Kappa statistic for interannotator agreement is 0.81 reflecting high agreement [19]. The annotators then discussed on disagreements and were able to resolve most of them. We discarded 124 pairs with irresolvable disagreements. The number of instances of each semantic relation in the gold standard data set is listed in Table 1.

Methods
We build a system that can automatically group UMLS concept pairs from biomedical narrative text into clusters where the grouping largely corresponds to the current semantic relation classes. We experiment with the k-means clustering framework under different configurations of distance metrics and seeding.

Figure 1 System workflow
In order to characterize the relation between the two semantic entities, our algorithm relies on the following features for that pair:  Semantic features that include the UMLS semantic types of the phrases, e.g., "Quantitative Con-cept" for "the high rate". This is motivated by the fact that certain semantic relation preferentially holds between specific sets of semantic types and vice versa.
 Lexical features that include all words in a sentence except for stop words. For example "high" and "rate" in the phrase "the high rate" in Figure  2. The intuition is that the words will help further distinguish semantic entities, in addition to semantic categories.
 Orthographic features that include punctuation, capitalization and the presence of digits. For example, capitalized phrase can be a proper name, often an instance of some disease, symptom etc. and likely to be in an is_a relation.
 Statistical features that include phrase length, sentence length and distance between phrases, all counted in terms of words. The intuition is that the relative distance between phrases can help differentiate semantic relations.
 Part-of-speech tags such as "verb" for "stain" and "noun" for "stain", which help distinguish that the word indicates a relation or is part of an entity.
 Syntactic features that include the syntactic links between semantic entities. Intuitively, similar link paths may indicate similar semantic relations, such as the two example link paths in Figure 2. We next give more details on syntactic features. We use the Link Parser [23] to extract syntactic links between the words in a sentence. The Link Parser identifies 106 types of syntactic links and associates words with left and right connectors. A pair of compatible connectors forms a link. To adapt the Link Parser output for our task, we convert word links to phrase level links by performing the following steps: if the words at both ends of a link are in two different phrases, then that link is regarded as an inter-phrase link and is retained; if the words on both ends of a link are in one phrase, then the link is treated as an intra-phrase link and is discarded. For example, Figure 2 shows the result of applying the above procedures on the sentence "Further studies with more samples are needed in order to explain the high rate found among the pediatric patients in this research study". In Figure 2, we color multi-word phrases as blue and inter-phrase links as red. Other links are discarded.
We observe that the link labels often have semantic implications that are useful in characterizing the relations between the connected semantic entities. To explore this observation, we generalize Sibanda's syntactic n-grams [7]. We divide phrase-level links into introductory links, intermediate links, and closing links, according to whether they are before, between, or after the entity pairs. For example, in Figure 2, the semantic entity pairs "the high rate"-"the pediatric patients" (P1) and "the high rate"-"this research study" (P2) share the relation occurs_in. These two pairs have common link types as well. Tracing the intermediate link path for the pair P2 as highlighted with green in Figure 2, the intermediate links include "Mv" (indicating participle modifiers), "MVp" (connecting verbs to modifying preposition phrases), and "Js" (connecting prepositions to their objects). A similar analysis shows that the pair P1 shares the same intermediate links (highlighted with yellow in Figure 2) once ignoring subscripts 2 , suggesting that similar relation holds here as in P2.
We construct link bigrams for all three types of links. Motivated by the observation that longer link span may lead to weaker phrasal relation, we also add the link span (defined as phrases between link endpoints) as a feature.

Figure 2 Link grammar output of an example sentence.
In this example, multi-word phrases are highlighted with blue color and inter-phrase links are highlighted with red color. Two example link paths are also highlighted with green and yellow respectively.

Clustering Semantic Relations
We use the k-means clustering algorithm as we already know the number of clusters. Denote the data set as , we want to form k disjoint clusters ̂ ̂ ̂ , that is, ̂ , and ̂ ̂ . Let be the features. These features are transformed into appropriate distance metrics between data points, which guide the formation of clusters by k-means. We use the Gmeans package [24], which minimizes an aggregated measure of intra-cluster distances called incoher-ence. We experiment on the seeded k-means with several distance metrics including the Euclidean distance, the cosine similarity, and the Kullback-Leibler (KL) divergence. Let be the center of the cluster , which is computed by averaging across all data points in that cluster. The Euclidean distance incoherence is The cosine similarity incoherence is calculated as ̂ ∑ ∑ ̂ .
The KL divergence incoherence indicates the information loss due to clustering and is formulated as where ̂ are viewed as random variables.

Experimental Results and Discussions
We evaluate our system on the top two levels of the UMLS Semantic Network. To test the generalizability of our semi-supervised clustering, we split our corpus into a training set and a testing set at a 8:2 ratio, stratified by semantic relation types at the second level (top level then automatically stratified). For each distance metric and seeding configuration, we run k-means clustering 30 times to obtain statistically robust results. For each run, we randomly draw seeds at specified fraction. We evaluate performance by creating a confusion matrix; we assign cluster labels so that we can obtain the confusion matrix with the strongest diagonal [25]. We then compute per-class as well as micro-and macro-averaged precision, recall and F-measure, which are common clustering evaluation metrics [26]. Let TP denote the number of true positives, FP denote the number of false positives and FN denote the number of false negatives, the definition of precision is , recall is , F-measure is . For each distance metric-seeding configuration, we report averaged results over the 30 runs. We find that the KL divergence consistently gives the best F-measures for varying seed fractions. Figure 3 shows the learning curves of the seeded clustering with KL divergence as the distance metric. For both levels of the UMLS semantic relation hierarchy, the performance keeps improving beyond 50% seeding, but with decreasing speed. Due to space limitation, we leave the results of the other two distance metrics in the Appendix B, which were inferior to those of the KL divergence. This suggests that the seeded clustering is sensitive to the choice of the distance metric and that the KL divergence is a suitable distance metric on our dataset. See Appendix B for more comparisons. With full seeding on the training data, our method generates a 2-way macro-averaged F-measure above 70% and a 7-way macro-averaged F-measure above 50%. With half seeding, our method still achieves a 2-way macro-averaged F-measure above 65% and a 7-way macro-averaged F-measure around 45%. This result suggests that the demand for seeding can be relaxed and our method can be used to automatically identify relation instances and provide a reasonable starting point with pre-labels to facilitate the human annotation process. We present detailed per-class evaluation on k-means algorithm using KL divergence with varying seed fractions (up to 50% 3 ) in Table 2 and Table 3. Not surprisingly, we see that the class imbalance took its toll on the clustering performance. For example, in the top level (  (Table 3), big performance drop is also seen in less populated classes such as AW 4 , PRT and TRT.

Conclusion and Future Work
We presented a semi-supervised approach to automatically identify semantic relations according to the definitions in the UMLS Semantic Network. We created a corpus of semantic entity pairs whose relations were doubly annotated according to the top two levels of the UMLS semantic relation hierarchy. We demonstrated that our semi-supervised method has reasonable accuracy and coverage at both levels of resolution. By studying the learning curves of the seeded k-means with the KL divergence as the distance metric, we showed that the demand for seeding 3 Results for seed fraction above 50% are shown in Appendix A. 4 In the second level, AW refers to those 174 instances that do not fall into *RT relations.
in the training data can be relaxed by half without greatly decreasing the performance. Therefore, our system can be used to assist with expert reviews on the semantic relation annotation task.
For future work, we note that our seeding is random and does not take into consideration how informative an example is. An active learning approach for picking the seeds could potentially further reduce the amount of required seeds and maintain similar levels of precision, recall, and F-measure.

Appendix A
This section continues the per-class evaluation for kmeans using KL divergence. Table 4 shows the continuation of Table 3 with seed fraction increasing to 100%. Table 5 shows the continuation of Table 2 with seed fraction increasing to 100%.   Figure 4 shows the learning curves of using the cosine similarity as the distance metric in clustering semantic entity pairs according to the top two levels of UMLS semantic relations. Figure 5 shows the corresponding learning curves for using the Euclidean distance as the distance metric. Comparing them to Figure 3, it can be seen that the cosine similarity and the Euclidean distance are consistently outperformed by the KL divergence distance metric when cluster seeds are given. Moreover, evaluation metrics on the cosine similarity and the Euclidean distance often have larger statistical variations (bigger confidence intervals) than those on the KL divergence. This further suggests that KL divergence as the distance metric tends to be more statistically stable on our dataset.