Specification and Verification of Side Channel Declassification

Side channel attacks have emerged as a serious threat to the security of both networked and embedded systems -- in particular through the implementations of cryptographic operations. Side channels can be difficult to model formally, but with careful coding and program transformation techniques it may be possible to verify security in the presence of specific side-channel attacks. But what if a program intentionally makes a tradeoff between security and efficiency and leaks some information through a side channel? In this paper we study such tradeoffs using ideas from recent research on declassification. We present a semantic model of security for programs which allow for declassification through side channels, and show how side-channel declassification can be verified using off-the-shelf software model checking tools. Finally, to make it simpler for verifiers to check that a program conforms to a particular side-channel declassification policy we introduce a further tradeoff between efficiency and verifiability: by writing programs in a particular"manifest form"security becomes considerably easier to verify.

Introduction
One of the pillars of computer security is confidentiality -keeping secrets secret. Much recent research in language based security has focused on how to ensure that information flows within programs do not violate the intended confidentiality properties [SM03]. One of the difficulties of tracking information flows is that information may flow in various indirect ways. Over 30 years ago, Lampson [Lam73] coined the phrase covert channel to describe channels which were not intended for information transmission at all. At that time the concern was unintended transmission of information between users on timeshared mainframe computers. In much security research that followed, it was not considered worth the effort to consider covert channels. But with the increased exposure of sensitive information to potential attackers, and the ubiquitous use of cryptographic mechanisms, covert channels have emerged as a serious threat to the security of modern systems -both networked and embedded. The following key papers provide a view of the modern side-channel threat landscape: • Kocher [Koc96] showed that by taking timing measurements of RSA cryptographic operations one could discover secret keys. Later [KJJ99] it was shown that one could do the same by measuring power consumption. • Based on Kocher's ideas numerous smart card implementations of cryptographic operations have shown to be breakable. See e.g. [MDS99]. • Brumley and Boneh [BB05] showed that timing attacks were not just relevant to smart cards and other physical cryptographic tokens, but could be effective across a network; they developed a remote timing attack on an SSL library commonly used in web servers.
What is striking about these methods is that the attacks are on the implementations and not features of the basic intended functionality. Mathematically, cryptographic methods are adequately secure, but useless if the functionally correct implementation has timing or other side channels.

Simple Timing Channels
Timing leaks often arise from the fact that computation involves branching on the value of a secret. Different instructions are executed in each branch, and these give rise to a timing leak or a power leak (whereby a simple power analysis [MS00] can reveal information about e.g. control flow paths).
One approach is to ensure that both branches take the same time [Aga00], or to eliminate branches altogether [MPSW05] -an approach that is also well known from real-time systems where it is used to make worst case execution time easy to determine [PB02].   Figure 1 representing a naïve implementation of modular exponentiation, which we will use as our running example throughout the paper.
The data that goes in to this function is typically secret. A common scenario is that the variable x is part of a secret which is to be encrypted or decrypted and variable d is the key (viewed here as an array of bits). It is important that these remain secret. (On the other hand, m, the length of the key, is usually considered public knowledge.) However, as this function is currently written it is possible to derive some or all of the information about the key using either a timing or power attack. The length of the loop will always reveal the size of the key -and this is accepted. In the body of the loop there is a conditional statement which is executed depending on whether the current bit in the key is set or not. This means that each iteration of the loop will take different amount of time depending on the value of the key. A timing attack measuring the time it takes to compute the whole result can be used to learn the hamming weight of the key, i.e. the number of 1's. With control over the key and repeated runs this is sufficient to leak the key [Koc96]. A power analysis could in principle even leak the key in a single run.

Timing and Declassification
Often the run-time cost of securing an algorithm against timing attacks using a general purpose method is higher than what we are prepared to pay.
For example, using a table-lookup instead of a branch [Cor99] the conditional can be replaced by the code to the left. This fixes the timing leak, but the algorithm becomes considerably slower -even after eliminating the common subexpression. Another even more costly approach is Agat's cross copying idea, whereby (roughly speaking) every branch on a secret value if h then A else B is trans- is a ghost copy of A which takes the same time to compute but otherwise has no effect. There are optimisations of this approach using unification [KM06], or by making the padding probabilistic [DHW08], but efficiency wise the improvements offered by those techniques are probably not sufficient in this context.

Fig. 2. Protected exponentiation
A potential solution to this tension between security and efficiency is to make a tradeoff between the two. For this reason it is not uncommon for algorithms to have some side channel leakage. An example of this is the following variation on modular exponentiation, adapted from [CMCJ04], which is intended to provide some (unspecified) degree of protection against simple power analysis attacks (but still leaks the hamming weight of the key).
Research Goals and Approach Our research goal is to determine how to express this tradeoff. There are three key issues to explore: • Security Policies: how should we specify side-channel declassification? • Security Mechanisms: how to derive programs which achieve the tradeoff? • Security Assurance: how can we show that programs satisfy a given policy, with a rigorous specification and formal verification?
This paper deals primarily with the first and the third point. The first step -a prerequisite to a rigorous specification -is to specify our attacker model. A model sets the boundaries of our investigation (and as always with covert channels, there are certainly attacks which fall outside). We choose (as discussed in Section 3) the program counter security model [MPSW05]. This model captures attackers performing simple power and timing analysis.
To specify a security policy we turn to work on declassification. The concept of declassification has been developed specifically to allow the programmer to specify what, where, or when a piece of information is allowed to leak (and by whom). A simple example is a program which requires a password based login. For this program to work it must declassify (intentionally leak) the value of the comparison between the actual and the user supplied password strings.
Declassification has been a recent hot topic in information flow security (see [SS05] for an overview). The standard techniques for declassification seem largely applicable to our problem, but there are some differences. The reason being that (in the context of cryptographic algorithms in particular) we may be interested in the distinction between declassifying some data directly (something which has potentially zero cost to the attacker), and declassifying the data but only through a side channel -the latter is what we call side channel declassification.
We will adapt existing declassification concepts to specify what information we are willing to leak through timing channels (Section 4) . More specifically, we use small programs as a specification of what information is leaked. This follows the style of delimited release [SM04]. As an example, we might want to specify that a program does not leak more that the hamming weight of the key. This can be achieved by using the program fragment in Figure 3 as a specification: it explicitly computes the hamming weight of the key. The formal definition of side-channel declassification (Section 4) is that if the attacker knows the information leaked by the declassifier then nothing more is learned by running the program.
We then turn to the question of verification. We investigate the use of off-shelf automatic program verification tools to verify sidechannel declassification policies. The first step is to reify the side channel by transforming the program to represent the side-channel as part of the program state (Section 5). This reduces the specification of side-channel declassification to an extensional program property.
The next step is to observe that in many common cases we can simplify the side-channel instrumentation. This simplification (described in Section 5.1) does not need to be semantics preserving -it simply needs to preserve the side-channel declassification condition.
As we aim to use automatic off-the-shelf model checkers we need one final transformation to make our programs amenable to verification. We use self composition to reduce the verification problem to a safety property of a transformed program. Section 6 describes the approach and experiments with software model checkers.
For various reasons the side-channel declassification property of algorithms can still be hard to verify. The last part of this work (Section 7) introduces a tradeoff which makes verification much simpler. The idea is to write programs in what we call manifest form. In manifest form the program is written in two parts: a declassifier first computes what is to be released, and then using this information a side-channel secure program computes the rest.
The verification problem amounts to showing that the second part of the program is indeed side-channel secure (this can be rather straightforward due to the strength of the side-channel security condition), and that the declassifier satisfies the property that it does not leak more through its side channel than it leaks directly. We call these manifest declassifiers. Since declassifiers are much simpler (and quite likely useful in many different algorithmic contexts) verification of manifest declassifiers is relatively simple. We show how this technique can overcome the verification limitations of certain verification tools.
An extended version of this article containing material left out for reasons of space constraints is available as technical report no. 2009:13 from Department of Computing Science and Engineering at and from arxiv.org/.... www.cse. chalmers.se/~josefs.

Preliminaries
In this section we present the language we are going to use and set up the basic machinery in order to define our notion of security.
Since we target cryptographic algorithms we will be using a small while language with arrays. It's syntax is defined below: The commands of the program should not require much explanation as they are standard for a small while language.
One particular form of expression that we have chosen to include that may not look very standard (for a toy language) is the ternary operator borrowed from the language C. It's a conditional expression that can choose between the value of two different register based on the value of a third register. We have restricted it to only operate on registers since allowing it to choose between evaluating two general expressions may give rise to side channels. This kind of operation can typically be implemented to take a constant amount of time so that it doesn't exhibit a side channel by using conditional assignment that is available in e.g. x86 machine code.
The semantics of programs is completely standard. We defer the definition until the next section where an operational semantics is given together with some additional instrumentation.

Baseline Security Model
In this section we present the semantic security model which we use to model the attacker and to define the baseline notion of declassification-free security. For a good balance between simplicity and strength we adopt an existing approach: the program counter security model [MPSW05]. This attacker model is strong enough to analyze simple power analysis attacks [KJJ99] -where the attacker is assumed to be able to make detailed correlations between the power profile of a single run with the instructions executed during that run.
The idea of the program counter security model is to assume the attacker can observe a transcript consisting of the sequence of program counter positions. This is slightly stronger than an attacker who could perfectly deduce the sequence of instructions executed from a (known) program given a power consumption profile of an execution. It does, however, assume that the power consumption of a particular operation does not depend on the data it manipulates. In particular it does not model differential power analysis.
Suppose a program operates on a state which can be partitioned into a low (public) part, and a high (secret) part. A program is said to be Transcript-secure if given any two states whose low parts are equal, running the program on these respective states yields equal transcripts and final states which also agree on their low parts. 1 To specialise this definition to our language we note that it is sufficient for the attacker to observe the sequence of branch decisions in a given run in order to be able to deduce the sequence of instructions that were executed. To this end, in Figure 3 we give an instrumented semantics for our language which makes this model of side channels concrete. Apart from the instrumentation (in the form of labels on the transitions) this is a completely standard small-step operational semantics. The transition labels, o, are either a silent step (τ ), a 0 or a 1. A zero or one is used to record which branch was taken in an if or while statement.
Definition 1 (Transcript). Let d 1 , d 2 , . . . range over {0, 1}. We say that a configuration C, S has a transcript d 1 , . . . , d n if there exist configurations C i , S i , i ∈ [1, n] such that In the above case we will write For the purpose of this paper (and the kinds of algorithms in which we are interested in this context) we will implicitly treat [

[C]] and [[C]]
T as functions rather than partial functions, thus ignoring programs which do not always terminate. Now we can formally define the baseline security definition, which following [MPSW05] we call Transcript-security: Note that Transcript-security, as we have defined it, is a very strong condition and also very simple to check. A sufficient condition for Transcript-security is that the program in question (i) does not assign values computed using high variables to low variables, and (ii) does not contain any loops or branches on expressions containing high variables. The main contribution of [MPSW05] is a suite of methods for transforming programs into this form. Unfortunately the transformation can be too costly in general, but that method is nicely complemented by use of declassification.

Side Channel Declassification
To weaken the baseline definition of security we adopt one of the simplest mechanisms to specify what information may be leaked about a secret: delimited release [SM04]. The original definition of delimited release specified declassification by placing declassify labels on various expressions occurring in a program. The idea is that the attacker is permitted to learn about (at most) the values of those expressions in the initial state, but nothing more about the high part of the state.
We will reinterpret delimited release using a simple program rather than a set of expressions. The idea will be to specify a (hopefully small and simple) program D which leaks information from high variables to low ones. A program is Transcript-secure modulo declassifier D if it leaks no more than D, and this leak occurs through the side channel.
Definition 3 (Side Channel Declassification). Let D be a program which writes to variables distinct from all variables occurring in C. We define C to be Transcript-secure modulo D if for all R and S such that R = L S we have The condition on the variables written by D is purely for convenience, but is without loss of generality. The first clause of the definition says that the only information leak can be through the side channel. The second clause says that the leak is no more than what is directly leaked by D. It is perhaps helpful to consider this clause in contrapositive form: S. This means that if there is an observable difference in the transcripts of two runs then that difference is manifest in the corresponding runs of the declassifier. Note that if we had omitted the condition [[C]]R = L [[C]]S then we would have the weaker property that C would be allowed to leak either through the store or through the side channel -but we wouldn't know which. From an attackers point of view it might take quite a bit more effort to attack a program if it only leaks though the side channel so it seems useful to make this distinction. Clearly there are other variations possible involving multiple declassifiers each leaking through a particular subset of observation channels.

Reifying the side channel
In the previous sections we have a definition of security that enables us to formally establish the security of programs with respect to side channel declassification. We now turn to the problem of verifying that particular programs fulfil the security condition. In order to avoid having to develop our own verification method we have chosen to use off-the-shelf software verification tools.
Software verification tools work with the standard semantics of programs. But recall that our security condition uses an instrumented semantics which involves a simple abstraction of side channels. In order to make it possible to use off-the-shelf tools for our security condition we must reify the transcript so that it becomes an explicit value in the program which the tools can reason about. It is easy to see how to do this: we add a list-valued variable t to the program, and transform, inductively, each conditional if e then C else C' into if e then t = t++"1"; C else t = t++"0"; C' and each while loop while e do C into (while e do t = t++"1"; C); t= t++"0" and inductively transform the subexpressions C and C'.

Simplifying the instrumentation
Reifying the transcript from the instrumented semantics in this way will create a dynamic data structure (a list) which is not bounded in size in general. Such data structures make programs more difficult to reason about, especially if we want some form of automation in the verification process. Luckily, there are several circumstances which help us side step this problem. Concretely we use two facts to simplify the reification of the side channel.
The first simplification we use depends on the fact that we do not have to preserve the transcript itself -it is sufficient that it yields the same lowequivalence on programs. Suppose that P T is the reified variant of the program P and that the reification is through the addition of some low variables. In order to use P T for verification of side-channel security properties it is sufficient for it to satisfy the following property: We call such a P T an adequate reification of P . The second simplification that we can perform in the construction of a reified program is that we are specifically targeting cryptographic algorithms. A common structure among the ones we have tried to verify is that the while loops contain straight line code (but potentially conditional expressions). If it is the case that while loops don't contain any nested branching or looping constructs then we can avoid introducing a dynamic data structure to model the transcript. Let us refer to such programs as unnested. For unnested programs it is simply enough to use one fresh low variable for each occurrence of a branch or loop. Thus the reification transformation for unnested programs is defined by applying the two transformation rules below to each of the loops and branches respectively: The program in Figure 5 is an instrumented version of the program in Figure 2. The only change is the new (low) variable t which keeps track of the number of iterations in the while loop.

Self Composition
Standard automatic software model checking tools cannot reason about multiple runs of a program. They deal exclusively with safety properties which involves reasoning about a single run. As is well-known, noninterference properties (like side-channel declassification) are not safety properties -they are defined as properties of pairs of computations rather than individual ones. However, a recent technique has emerged to reduce noninterference properties to safety properties for the purpose of verification. The idea appeared in [DHS03], and was explored extensively in [BDR04] where the idea was dubbed self composition. Suppose C is the program for which we want to verify noninterference. Let θ be a bijective renaming function to a disjoint set of variables from those used in C. Let C θ denote a variable renamed copy of C. Then the standard noninterference property of C can be expressed as a safety property of C; C θ viz. the Hoare triple To extend this to deal with side-channel declassification, let us suppose that C T is an adequate reification of C. Then we can verify Transcript-security modulo D by the Hoare triple above (non side-channel security) in conjunction with: where W denotes the variables written by D. Here we take advantage of the assumption that the variables written by D are disjoint from those used in C T . This enables us to get away with a single renaming. Note that since D is a program and not an expression we cannot simply use it in the precondition of the Hoare triple (c.f. [BDR04,TA05]).

Experiments using Self Composition
As Terauchi and Aiken discovered when they used self composition, it often resulted in verification problems that were too hard for the model checkers to handle [TA05]. As a result of this they developed a series of techniques for making the result of self composition easier to verify. The main technique is the observation that the low part of the two initial states must be equal and hence any computation that depends only on the low part can safely be shared between the two copies of the program. This was reported to help verifying a number of programs. We employ the same technique in our experiments.
We have used the model checkers Blast [HJMS03] and Dagger [GR06] and applied them to self composed version of the cryptographic algorithms. In particular we have tried to verify the instrumented modular exponentiation algorithm in Figure 5 secure modulo the hamming weight of the key (Figure 3). We have also tried all the algorithms proposed in [CMCJ04] since they all exhibit some form of side-channel leak and therefore have to be shown to be secure relative that leak. None of the model checkers were powerful enough to automatically verify the programs secure.
The main reason these tools fail seems to be that they do not reason about the contents of arrays. Being able to reason about arrays is crucial for our running example, as it involves computing the hamming weight of an array.
Another problem comes from the fact that the programs we wish to prove secure may be very different from its declassifier. Relating two different programs with each other is a very difficult task and not something that current software model checkers are designed to do. By helping the model checkers with some manual intervention it is possible to verify the programs secure. Blast has a feature which allows the user to supply their own invariants. Given the correct invariants it will succeed with the verification. However, these predicates are not checked for correctness and coming up with them can be a highly non-trivial task. We have therefore developed another method for verification which we will explore in the next section.

Manifest form
In this section we introduce a new way to structure programs to make verification considerably easier: Manifest Form. In manifest form the program is written in two parts: a declassifier first computes what is to be released, and then using this information a Transcript-secure program computes the rest. Manifest form represents a tradeoff: writing a program in manifest form may make it less efficient. The idea is that the program makes the declassification explicit in its structure (this is similar to the specification of relaxed noninterference [LZ05]). But for this to be truly explicit declassification the declassifier itself should not leak through its side channel -or more precisely, the declassifier should not leak more through its side channel than it does directly through the store. The program in Figure 6 is written in manifest form but otherwise it represents the same algorithm as the program in Figure 2. The first part of the program (lines 1-6) computes the hamming weight of the key, d, and this (using low variable hamming) is then used in the second part of the program to determine the number of loop iterations.

Manifest Security Theorem
Armed with the definitions of sound manifest declassifiers we can now state the theorem which is the key to the way we verify side-channel declassification.
Theorem 1. Given a program P = D; Q with D being a sound manifest declassifier and Q is transcript secure then P is transcript secure modulo D This theorem helps us decompose and simplify the work of verifying that a program in manifest form is secure. First, showing that Q is transcript secure is straightforward as explained in section 3. Verifying that D is a sound manifest declassifier, which might seem like a daunting task given the definition, is actually something that is within the reach of current automatic tools for model checking.
We apply the same techniques of reifying the side channel and self composition to the problem of verifying sound manifest declassifiers. When doing so we have been able to verify that our implementation of the hamming weight computation in Figure 3 is indeed a sound manifest declassifier and thereby establishing the security of the modular exponentiation algorithm in Figure 6. We have had the same success 2 with all the algorithms presented in [CMCJ04].

Related Work
The literature on programming language techniques for information flow security is extensive. Sabelfeld and Myers survey [SM03] although some seven years old remains the standard reference in the field. It is notable that almost all of the work in the area has ignored timing channels. However any automated security checking that does not model timing will accept a program which leaks information through timing, no matter how blatant the leak is.
Agat [Aga00] showed how a type system for secure information flow could be extended to also transform out certain timing leaks by padding the branches of appropriate conditionals. Köpf and Mantel give some improvements to Agat's approach based on code unification [KM06]. In a related line, Sabelfeld and Sands considered timing channels arising from concurrency, and made use of Agat's approach [SS00]. Approximate and probabilistic variants of these ideas have also emerged [PHSW07,DHW08]. The problem with padding techniques in general is that they do not change the fundamental structure of a leaky algorithm, but use the "worst-case principle" [AS01] to make all computation paths equally slow. For cryptographic algorithms this approach is probably not acceptable from a performance perspective.
Hedin and Sands [HS05,Hed08] consider applying Agat's approach in the context of Java bytecode. One notable contribution is the use of a family of time models which can abstract timing behaviour at various levels of accuracy, for example to model simple cache behaviour or instructions whose time depends on runtime values (e.g. array allocation). The definitions and analysis are parameterised over the time models. The program counter security model [MPSW05] can be seen as an instance of this parameterised model.
More specific to the question of declassification and side channels, as we mentioned above, [DHW08] estimates the capacity of a side channel -something which can be used to determine whether the leak is acceptable -and propose an approximate version of Agat's padding technique. Giacobazzi and Mastroeni [GM05] recently extended the abstract noninterference approach to characterising what information is leaked to include simple timing channels. Their theoretical framework could be used to extend the present work. In particular they conclude with a theoretical condition which, in principle, could be used to verify manifest declassifiers. Köpf and Basin's study of timing channels in synchronous systems [KB06] is the most closely related to the current paper. They study a Per model for expressing declassification properties in a timed setting -an abstract counterpart to the more programmer-oriented delimited release approach used here. They also study verification for deterministic systems by the use of reachability in a product automaton -somewhat analogous to our use of self composition. Finally their examples include leaks of hamming weight in a finite-field exponentiation circuit.


An Improved Genetic Algorithm Based on Adaptive Repair Operator for Solving the Knapsack Problem

Problem statement: Knapsack problem is a typical NP complete problem. During last few decades, Knapsack problem has been studied through different approaches, according to the theoretical development of combinatorial optimization. Approach: In this study, modified evolutionary algorithm was presented for 0/1 knapsack problem. Results: A new objective_func_evaluation operator was proposed which employed adaptive repair function named as repair and elitism operator to achieve optimal results in place of problem specific knowledge or domain specific operator like penalty operator (which are still being used). Additional features had also been incorporated which allowed the algorithm to perform more consistently on a larger set of problem instances. Conclusion/Recommendations: This study also focused on the change in behavior of outputs generated on varying the crossover and mutation rates. New algorithm exhibited a significant reduction in number of function evaluations required for problems investigated.

I. INTRODUCTION
Knapsack problem is a well known and well studied problem in combinatorial optimization being widely used in areas like network planning, network routing, parallel scheduling and budgeting [1] . Mathematically the 0-1 Knapsack problem may be formulated as: where, x j the number of each kind of item is restricted to one or zero indicating its presence or absence in the knapsack. c is the capacity of the knapsack into which n types of objects may be placed. The object of type i has a profit p i and weight w i , associated with it.
Since the Knapsack problem is NP problem, various approaches presently available such as dynamic programming, backtracking, branch and bound etc. are not very useful for solving it. These exact algorithms have a running time that is bounded by an exponential function of length of input data, thus it is very difficult to obtain the exact solutions in case of many large scale knapsack instances which come from practical applications [2] . Hence, for those large scale instances, it has to rely on heuristic algorithms to obtain the near optimal solutions to them.
Amongst the Heuristic algorithms for knapsack problem, genetic algorithm is an effective method to solve the knapsack instances approximately. Genetic algorithm is a search technique to find exact or approximate solutions to optimization and search problems. Genetic algorithms are categorized as global search heuristics [3,4] . They work on the Darwin's principle of natural selection and survival of the fittest. Evolutionary algorithm produces initial population with individuals selected at random. The fitness value of each individual of the population is worked out. If it does not satisfy the goal criterion then it is improved through crossover and mutation operators. Because of the incompatibility between the speed of convergence and the action for searching for the best solution, the simple evolutionary algorithm always behave slowly in convergence, easily in prematurity and plunges into local optimizations. The Evolutionary algorithm with adaptive repair operator is proposed in this study. It leads the search direction of the population by collecting some better individuals from every generation by using the elitism operator and hence results in improving the searching efficiency. Furthermore, the computational cost implications of using adaptive repair function in the algorithm have also been evaluated.
Evolutionary algorithm with adaptive repair operator: A modified algorithm called KNAP-GA is described in this section for solving KP using elitist GAs. The structure of the proposed KNAP-GA is presented in Fig. 1.
Here P represents the population {P 0 , P 1 , P 2 …..P max } where each population comprises of m entries {S 1 , S 2 ,…..S m } and each entry S i = {J k such that 1≤k≤n and J k = {0 ,1}} . Let J = {J 1 , J 2 , J 3 ,……J n } represents the set of unique items that are available . The selected items are represented by value 1 and the not selected ones are represented by value 0. The fitness values of the chromosomes in a population are evaluated based on the profits associated with the items. The best fit chromosome generated from a given population is stored in S * . The crossover and mutation rate are varied to study the impact of varying these operators on the outputs obtained. The working, the characteristics and the need of objective_func_evaluation operator is explained in the preceding section. Each generation of the population yields a set of unique items that would result in maximum profit, thus modifying the solution vector in each step by proceeding towards the best fit solution.
The objective_func_evaluation is a function which evaluates the fitness of chromosomes in the new population. For the Knapsack problem, we calculate the fitness of each chromosome by summing up the benefits of the items that are included in the knapsack, restricting the total weight of the selected items to the capacity of knapsack. If the total weight of the items in the chromosome generated by the crossover and mutation procedure is greater than the capacity of the knapsack then that solution is infeasible and the Repair Operator and the elitism come into play. The Objective_func_evaluation operator is basically a combination of Elitism and Repair operator which is simple to implement and provides us with similar results as obtained with other operators which need complex computations. The outline of the algorithm is given in Fig. 2.

MATERIALS AND METHODS
The test data represents various instances of the 0/1 Knapsack problem as available in the literature [1] . The data sets consist of varying correlation types between profits and weights.

Correlation types:
Data set Uncorrelated (UC) w i = (uniformly) random (1…v) and p i = (uniformly) random (1…v) Data set Weakly Correlated (WC) w i = (uniformly) random (1…v) and p i = w i + (uniformly) random ( -r..r) Data set Strongly Correlated (SC) w i = (uniformly) random (1…v) and p i = w i + r The experiments have been conducted without sorting the items on p i /w i values. Knapsack problem instances were studied on data sets with 100, 250 and 500 items for each of the three correlation types and the three types of Knapsack capacities. However, due to space limitation we are presenting only the case with 250 items.
KNAP-GA was implemented on Pentium-4 (1.7 Ghz) and the results were compared with those obtained by the dynamic programming algorithm. We ran 100 instances of the random sets. Each table entry is the average of 30 runs.

RESULTS
The effects of varying crossover and mutation rates have been studied and is presented in Table 1. When the crossover and mutation rates are both set to 0, the population has obviously contained copies of the strategies randomly generated at the beginning. In other words, with no with no crossover or mutation, all the children looked exactly like one of their parents.
However, on setting crossover rate equal to zero and varying the mutation rate it was observed that the mutation rate of n/100 (where n can be anything between 0-9) yields the best results. Due to space constraint we have shown only 3 instances of the mutation rate i.e., 03, 0.003, 0.70. Experimental results do not show the case when mutation is turned off, because it does not matter much what the crossover rate is when mutation is turned off as mutation is a function which is an integral part of crossover operator and if mutation is off, it yields the same results as when crossover and mutation are set equal to zero.
The second observation worth noticing from Table 1 is that crossover rate between 60 and 70 yields best solution with mutation rate having negligible impact on the output. On examining the three cases, without Elitism and Repair operator, with Repair operator and with elitism and Repair operator, we observed that the mere presence of Repair operator improved the final solution than the one that we were getting in the absence of Elitism and Repair operators and by clubbing the Elitism and Repair operators i.eby using objective_func_evaluation operator ∆, considerable improvement in the final solution has been found.

DISCUSSION
The objective_func_evaluation operator incorporating the new adaptive repair operator has been found to be more cost effective than the existing techniques that have been used in the past to handle chromosomes yielding infeasible solutions. As per the philosophy Richardson et al. [5] , (employing penalty method) infeasible bred strings (or chromosomes) were allowed to join the population however by reducing the string strength by adding penalty terms to the fitness. The farther the string is from feasibility, the higher is the penalty term. In the other approach flags were used to signal the feasibility of final solution. If after several runs on the same problem instance, the flag consistently indicated an infeasible string then one had to either bias the random number generator so as to produce strings in which the number of zeros is greater than the number of one's [6] or use some other heuristic such as greedy one, to generate a solution [7] . Both the methods, the penalty method or using flags increase the computation overhead because in addition to estimating the fitness of chromosomes in a population the track of unfit chromosomes had to be kept by assigning varying penalties and again estimating the strength in each iteration. Whereas if flags were used then one had to keep track of the status of the flag amongst several problem instances and if the same value persists then greedy approach is used thus increasing computational cost multi folds.
The algorithm employing objective_func_evaluation operator ∆ provides a much efficient approach of reaching an optimal solution by using a simple to implement adaptive repair operator which incorporates a strategy of making all bits of the chromosome equal to zero from the point where the fitness exceeds the capacity and by employing elitism to get a small percentage of the best chromosomes from the old population to the new population. Thus the evolutionary algorithm with adaptive repair operator proposed in this study, leads the search direction of the population by collecting the few best individuals from every generation by using the elitism operator. It has resulted in improving the search efficiency.

CONCLUSION
The results obtained with the newly designed genetic operators in algorithm are encouraging, on the practical data sets. Rather than augmenting the genetic algorithm with domain specific knowledge, we have introduced a fitness function employing adaptive repair operator and elitism which is simple to use. In order to further the results, application of the developed KNAP-GA to real life problems, hybridization of local search techniques with other heuristic or meta heuristic techniques for solving the Knapsack problem may be studied. Future work may address whether the proposed algorithm can be applied to other constraint optimization problems such as the maximum clique or the degree constrained minimum spanning tree problems.


extfieldsofstudy:
Computer Science
Medicine

text:
Getting Started in Text Mining: Part Two

We are, in a sense, drowning in information. Today, it is unusual for scientists even to read a journal cover to cover—much less to personally parse all information pertinent to even a narrow research area. Increasingly complex content, large digital supplements, and a staggering volume of publications are now threatening old-fashioned scientific reading with extinction. But by using computers to sift through and scour published articles, the nascent technology of text mining promises to automate the rote information-gathering stage—hopefully leaving to human minds the more challenging (and rewarding) activity of higher thinking.

This article is intended to continue where Cohen and Hunter [1] left off in “Getting Started in Text Mining,” an introduction in the January 2008 issue of PLoS Computational Biology which covered the actual mining of text and its digestion into small quanta of computer-manageable information (http://www.ploscompbiol.org/doi/pcbi.0040020). In this overview of the field, we begin by summarizing the major stages of current text-processing pipelines. We now focus on the downstream questions scientists can ask using text-mining and literature-mining engines. At times, we (deliberately) blur the boundary between today's approaches and tomorrow's possibilities.

Figure 1 shows a high-level overview of the stages in text mining, with a focus on its applications. We begin at the top left of the figure, which shows the process of information retrieval—how we select relevant documents [2]. Unfortunately, free full-text access remains impossible for a large portion of scientific journals. In some fields, such as chemistry, even article abstracts are inaccessible for a large-scale analysis. The obvious outcome is that articles published in open-access journals have a better chance of being identified as relevant hits than others appearing in traditional “closed-access” journals. Electronic access to text obviously impacts all stages of text mining.

Figure 1

Major techniques and applications of text mining.

Once the documents have been chosen by an information retrieval engine, a computer scans the text and picks out the various entities (objects, concepts, and symbols) in each sentence. This process, called named-entity recognition [3], draws upon dictionaries of synonyms and homonyms, in addition to machine-learning tools [4], so that an individual entity (say, a protein) is recognized consistently—even though it may be referred to by several different names and acronyms [5]. Named-entity recognition is closely related to the design of controlled terminologies [6] and ontologies for the annotation of texts and experimental data [7]—a process often requiring a monumental community effort [8].

The next step is information extraction (IE) (see pp. 545–559 in [9]). Here, entities are assembled into simple phrases and clauses that capture the meaning of the mined text. To accomplish this, two or more entities are juxtaposed, and meaningful action words—called predicates—are chosen to link the entities. For instance, we might say gene X genetically interacts with gene Y, or protein A binds to protein B. Each completed clause describes a basic relationship between entities. The question then becomes, what can we do with all these simple or complex clauses?

The answer is, quite a lot—which helps explain why text mining is poised to become a powerful central pillar in scientific research and recordkeeping. The lower two-thirds of Figure 1 illustrates how the results of information extraction (IE) can be synthesized and used.

Because IE yields a collection of phrases linking entities through predicates, one of its simplest but valuable uses is to answer simple questions posed to an automated system [10]. In this approach, human questions are digested by a linguistic engine (likely using the same process as employed on original mined text) and mapped to simple phrases. These question phrases are then queried against the database of phrases already stored in the computer, which were generated through the application of IE to analyzed text. (Another mode of question answering, bypassing generation and querying of a database entirely, involves direct search and analysis of relevant texts. These texts can be stored at a local computer disk or distributed on numerous computers around the world.) Figure 1 outlines the basic process by which the machine interprets the question, queries its database of stored relationships, and returns an answer.

IE-generated knowledge often tracks closely the needs of experimental biologists. Typical IE systems are developed in direct response to acute practical problems, such as large-scale annotation of regulatory regions in genomes [11], collecting published claims about experimental evidence supporting a collection of assertions [12], and condensing sparse information about phenotypic effects of mutations in proteins [13].

Of course, IE-generated databases can be supplemented with additional data gleaned from experiment, or contributed through other non–text-mining means. A simple user interface could facilitate contributing raw experimental data or other information into the database of relationships expressed as simple phrases—again, entities linked by actions (see, for example, the REFLECT system, http://reflect.ws/). Adding more such data should correspondingly increase the effectiveness of the computer's answers to user questions.

Another major use for the database of IE-generated phrases is to employ the collection itself for the discovery of new information [14],[15]. One approach to this is to seek out “idea isomorphisms”, by which we mean identifying similar types of logical constructs across different contexts. Finding that similar small ideas (or phrases) occur in different fields might allow researchers to bridge different areas of inquiry. Such bridging of fields, in turn, might uncover new connections, thereby suggesting new and unexpected hypotheses that can then be tested experimentally.

The collection of phrases can also be used to vet and prune itself by examining the consistency among many entries. For instance, conflicting or erroneous data can be flagged. By examining each record situated within a large number of records, the preponderance of evidence could assist in identifying and resolving errors. Say, for example, that 20 distinct phrases all indicate that protein A interacts with protein B, and one phrase suggests otherwise; we might probabilistically argue, then, that the lone conflicting statement is false and should be disregarded—unless it is supported some other way.

An additional approach to using these phrases—in a mega-scale fashion—is to construct a “map of science”, a global description of the interrelationships between different fields of inquiry. This is similar conceptually to PubNet [16], which highlights connections between authors. However, the map of science would be generated not through coauthor relationships but through clustering the underlying scientific fact claims themselves, as represented in the IE phrase collection. To do this, researchers would cluster papers according to their IE-derived phrase content; any two papers can be compared in this way to derive a measure of their similarity and overlap in terms of information content. By repeating this process, researchers could create a distance map of all papers in science, and, along the way, of all the factoids that the information content of the papers themselves comprise.

In addition, researchers might track the changing nature of the IE phrases over time to examine the dynamics of scientific belief. This could involve observing as simple phrases themselves change in occurrence or content over time, or we might watch these simple ideas and truth claims crop up in the scientific literature and track their development that way.

Finally, the middle right-hand section of Figure 1 depicts a very simple type of analysis involving the IE-generated simple phrase collection. This approach involves simply looking at the phrases' occurrence in the databases, and recording which statements tend to occur more than others. This type of analysis normally generates a kind of power law–type structure, where it becomes apparent that a few phrases occur many times, but most others only occur a few times.

Text/literature mining is a powerful approach, one we expect to substantially bolster the scientific reporting and discovery process in coming years. Applying the organizational, storage, and pattern-matching capabilities of modern computers to the vast corpus of scientific information contained in the literature (present, past, and future) will not only transform the vast archives of science into rapid-access searchable computerized data, but no doubt also catalyze the discovery of much new knowledge. We hope that this brief “getting started” report highlights some of the major and promising avenues opening as a result of advances in text mining.

Note to the reader: The field of text mining is young and growing rapidly, and our own interests and experiences have in large part shaped our perspective on it. We are constrained by length limits here to (reluctantly) omit several topics, such as text mining in conjunction with image analysis, important community text-annotation efforts, and ontology engineering—each important in its own right. Furthermore, every issue touched upon in this essay comes with a rich diversity of views and approaches in the text-mining community. While we cannot possibly do justice to this complexity, the reader should reject the impression that there is but a single correct way to perform text analysis.

We are, in a sense, drowning in information. Today, it is unusual for scientists even to read a journal cover to cover-much less to personally parse all information pertinent to even a narrow research area. Increasingly complex content, large digital supplements, and a staggering volume of publications are now threatening oldfashioned scientific reading with extinction. But by using computers to sift through and scour published articles, the nascent technology of text mining promises to automate the rote informationgathering stage-hopefully leaving to human minds the more challenging (and rewarding) activity of higher thinking.
This article is intended to continue where Cohen and Hunter [1] left off in ''Getting Started in Text Mining,'' an introduction in the January 2008 issue of PLoS Computational Biology which covered the actual mining of text and its digestion into small quanta of computer-manageable information (http://www.ploscompbiol.org/doi/pcbi.0040020). In this overview of the field, we begin by summarizing the major stages of current text-processing pipelines. We now focus on the downstream questions scientists can ask using text-mining and literature-mining engines. At times, we (deliberately) blur the boundary between today's approaches and tomorrow's possibilities. Figure 1 shows a high-level overview of the stages in text mining, with a focus on its applications. We begin at the top left of the figure, which shows the process of information retrieval-how we select relevant documents [2]. Unfortunately, free full-text access remains impossible for a large portion of scientific journals. In some fields, such as chemistry, even article abstracts are inaccessible for a large-scale analysis. The obvious outcome is that articles published in open-access journals have a better chance of being identified as relevant hits than others appearing in traditional ''closed-access'' journals. Elec-tronic access to text obviously impacts all stages of text mining.
Once the documents have been chosen by an information retrieval engine, a computer scans the text and picks out the various entities (objects, concepts, and symbols) in each sentence. This process, called named-entity recognition [3], draws upon dictionaries of synonyms and homonyms, in addition to machine-learning tools [4], so that an individual entity (say, a protein) is recognized consistently-even though it may be referred to by several different names and acronyms [5]. Named-entity recognition is closely related to the design of controlled terminologies [6] and ontologies for the annotation of texts and experimental data [7]-a process often requiring a monumental community effort [8].
The next step is information extraction (IE) (see pp. 545-559 in [9]). Here, entities are assembled into simple phrases and clauses that capture the meaning of the mined text. To accomplish this, two or more entities are juxtaposed, and meaningful action words-called predicates-are chosen to link the entities. For instance, we might say gene X genetically interacts with gene Y, or protein A binds to protein B. Each completed clause describes a basic relationship between entities. The question then becomes, what can we do with all these simple or complex clauses?
The answer is, quite a lot-which helps explain why text mining is poised to become a powerful central pillar in scientific research and recordkeeping. The lower two-thirds of Figure 1 illustrates how the results of information extraction (IE) can be synthesized and used.
Because IE yields a collection of phrases linking entities through predicates, one of its simplest but valuable uses is to answer simple questions posed to an automated system [10]. In this approach, human questions are digested by a linguistic engine (likely using the same process as employed on original mined text) and mapped to simple phrases. These question phrases are then queried against the database of phrases already stored in the computer, which were generated through the application of IE to analyzed text. (Another mode of question answering, bypassing generation and querying of a database entirely, involves direct search and analysis of relevant texts. These texts can be stored at a local computer disk or distributed on numerous computers around the world.) Figure 1 outlines the basic process by which the machine interprets the question, queries its database of stored relationships, and returns an answer.
IE-generated knowledge often tracks closely the needs of experimental biologists. Typical IE systems are developed in direct response to acute practical problems, such as large-scale annotation of regulatory regions in genomes [11], collecting published claims about experimental evidence supporting a collection of assertions [12], and condensing sparse information about phenotypic effects of mutations in proteins [13].
Of course, IE-generated databases can be supplemented with additional data gleaned from experiment, or contributed through other non-text-mining means. A simple user interface could facilitate contributing raw experimental data or other information into the database of relationships expressed as simple phrases-again, entities linked by actions (see, for example, the REFLECT system, http://reflect.ws/). Adding more such data should correspondingly increase the effectiveness of the computer's answers to user questions.
Another major use for the database of IE-generated phrases is to employ the collection itself for the discovery of new information [14,15]. One approach to this is to seek out ''idea isomorphisms'', by which we mean identifying similar types of logical constructs across different contexts.
Finding that similar small ideas (or phrases) occur in different fields might allow researchers to bridge different areas of inquiry. Such bridging of fields, in turn, might uncover new connections, thereby suggesting new and unexpected hypotheses that can then be tested experimentally.
The collection of phrases can also be used to vet and prune itself by examining the consistency among many entries. For instance, conflicting or erroneous data can be flagged. By examining each record situated within a large number of records, the preponderance of evidence could assist in identifying and resolving errors. Say, for example, that 20 distinct phrases all indicate that protein A interacts with protein B, and one phrase suggests otherwise; we might probabilistically argue, then, that the lone conflicting statement is false and should be disregarded-unless it is supported some other way.
An additional approach to using these phrases-in a mega-scale fashion-is to construct a ''map of science'', a global description of the interrelationships between different fields of inquiry. This is similar conceptually to PubNet [16], which highlights connections between authors. However, the map of science would be generated not through coauthor relationships but through clustering the underlying scientific fact claims themselves, as represented in the IE phrase collection. To do this, researchers would cluster papers according to their IEderived phrase content; any two papers can be compared in this way to derive a measure of their similarity and overlap in terms of information content. By repeating this process, researchers could create a distance map of all papers in science, and, along the way, of all the factoids that the information content of the papers themselves comprise.
In addition, researchers might track the changing nature of the IE phrases over time to examine the dynamics of scientific belief. This could involve observing as simple phrases themselves change in occurrence or content over time, or we might watch these simple ideas and truth claims crop up in the scientific literature and track their development that way.
Finally, the middle right-hand section of Figure 1 depicts a very simple type of analysis involving the IE-generated simple phrase collection. This approach involves simply looking at the phrases' occurrence in the databases, and recording which statements tend to occur more than others. This type of analysis normally generates a kind of power law-type structure, where it becomes apparent that a few phrases occur many times, but most others only occur a few times.
Text/literature mining is a powerful approach, one we expect to substantially bolster the scientific reporting and discovery process in coming years. Applying the organizational, storage, and patternmatching capabilities of modern computers to the vast corpus of scientific information contained in the literature (present, past, and future) will not only transform the vast archives of science into rapidaccess searchable computerized data, but no doubt also catalyze the discovery of much new knowledge. We hope that this brief ''getting started'' report highlights some of the major and promising avenues opening as a result of advances in text mining.
Note to the reader: The field of text mining is young and growing rapidly, and our own interests and experiences have in large part shaped our perspective on it. We are constrained by length limits here to (reluctantly) omit several topics, such as text mining in conjunction with image analysis, important community text-annotation efforts, and ontology engineeringeach important in its own right. Furthermore, every issue touched upon in this essay comes with a rich diversity of views and approaches in the text-mining community. While we cannot possibly do justice to this complexity, the reader should reject the impression that there is but a single correct way to perform text analysis.


Using a dependency parser to improve SMT for subject-object-verb languages

We introduce a novel precedence reordering approach based on a dependency parser to statistical machine translation systems. Similar to other preprocessing reordering approaches, our method can efficiently incorporate linguistic knowledge into SMT systems without increasing the complexity of decoding. For a set of five subject-object-verb (SOV) order languages, we show significant improvements in BLEU scores when translating from English, compared to other reordering approaches, in state-of-the-art phrase-based SMT systems.

Introduction
Over the past ten years, statistical machine translation has seen many exciting developments. Phrasebased systems (Och, 2002;Koehn et.al., 2003;Och and Ney, 2004) advanced the machine translation field by allowing translations of word sequences (a.k.a., phrases) instead of single words. This approach has since been the state-of-the-art because of its robustness in modeling local word reordering and the existence of an efficient dynamic programming decoding algorithm.
However, when phrase-based systems are used between languages with very different word orders, such as between subject-verb-object (SVO) and subject-object-verb (SOV) languages, long distance reordering becomes one of the key weaknesses. Many reordering methods have been proposed in recent years to address this problem in different aspects.
The first class of approaches tries to explicitly model phrase reordering distances. Distance based distortion model (Och, 2002;Koehn et.al., 2003) is a simple way of modeling phrase level reordering. It penalizes non-monotonicity by applying a weight to the number of words between two source phrases corresponding to two consecutive target phrases. Later on, this model was extended to lexicalized phrase reordering (Tillmann, 2004;Koehn, et.al., 2005;Al-Onaizan and Papineni, 2006) by applying different weights to different phrases. Most recently, a hierarchical phrase reordering model (Galley and Manning, 2008) was proposed to dynamically determine phrase boundaries using efficient shift-reduce parsing. Along this line of research, discriminative reordering models based on a maximum entropy classifier (Zens and Ney, 2006;Xiong, et.al., 2006) also showed improvements over the distance based distortion model. None of these reordering models changes the word alignment step in SMT systems, therefore, they can not recover from the word alignment errors. These models are also limited by a maximum allowed reordering distance often used in decoding.
The second class of approaches puts syntactic analysis of the target language into both modeling and decoding. It has been shown that direct modeling of target language constituents movement in either constituency trees (Yamada and Knight, 2001;Galley et.al., 2006;Zollmann et.al., 2008) or dependency trees (Quirk, et.al., 2005) can result in significant improvements in translation quality for translating languages like Chinese and Arabic into English. A simpler alternative, the hierarchical phrase-based approach (Chiang, 2005;Wu, 1997) also showed promising results for translating Chinese to English. Similar to the distance based reordering models, the syntactical or hierarchical approaches also rely on other models to get word alignments. These models typically combine machine translation decoding with chart parsing, therefore significantly increase the decoding complexity. Even though some recent work has shown great improvements in decoding efficiency for syntactical and hierarchical approaches (Huang and Chiang, 2007), they are still not as efficient as phrase-based systems, especially when higher order language models are used.
Finally, researchers have also tried to put source language syntax into reordering in machine translation. Syntactical analysis of source language can be used to deterministically reorder input sentences (Xia and McCord, 2004;Collins et.al., 2005;Wang et.al., 2007;Habash, 2007), or to provide multiple orderings as weighted options (Zhang et.al., 2007;Li et.al., 2007;Elming, 2008). In these approaches, input source sentences are reordered based on syntactic analysis and some reordering rules at preprocessing step. The reordering rules can be either manually written or automatically extracted from data. Deterministic reordering based on syntactic analysis for the input sentences provides a good way of resolving long distance reordering, without introducing complexity to the decoding process. Therefore, it can be efficiently incorporated into phrase-based systems. Furthermore, when the same preprocessing reordering is performed for the training data, we can still apply other reordering approaches, such as distance based reordering and hierarchical phrase reordering, to capture additional local reordering phenomena that are not captured by the preprocessing reordering. The work presented in this paper is largely motivated by the preprocessing reordering approaches.
In the rest of the paper, we first introduce our dependency parser based reordering approach based on the analysis of the key issues when translating SVO languages to SOV languages. Then, we show experimental results of applying this approach to phrasebased SMT systems for translating from English to five SOV languages (Korean, Japanese, Hindi, Urdu and Turkish). After showing that this approach can also be beneficial for hierarchical phrase-based sys-John can hit ball the .
. Figure 1: Example Alignment Between an English and a Korean Sentence tems, we will conclude the paper with future research directions.

Translation between SVO and SOV Languages
In linguistics, it is possible to define a basic word order in terms of the verb (V) and its arguments, subject (S) and object (O). Among all six possible permutations, SVO and SOV are the most common. Therefore, translating between SVO and SOV languages is a very important area to study. We use English as a representative of SVO languages and Korean as a representative for SOV languages in our discussion about the word orders. Figure 1 gives an example sentence in English and its corresponding translation in Korean, along with the alignments between the words. Assume that we split the sentences into four phrases: (John , t@), (can hit ,` ˆµ È ä), (the ball , ø õ D) and (. , .). Since a phrase-based decoder generates the translation from left to right, the following steps need to happen when we translate from English to Korean: • Starts from the beginning of the sentence, translates "John" to "t@"; • Jumps to the right by two words, translates "the ball" to "ø õD"; • Jumps to the left by four words, translates "can hit" to "` ˆµÈä"; • Finally, jumps to the right by two words, translates "." to ".".
It is clear that in order for the phrase-based decoder to successfully carry out all of the reordering steps, a very strong reordering model is required. When the sentence gets longer with more complex structure, the number of words to move over during decoding can be quite high. Imagine when we translate the sentence "English is used as the first or second language in many countries around the world .". The decoder needs to make a jump of 13 words in order to put the translation of "is used" at the end of the translation. Normally in a phrase-based decoder, very long distance reordering is not allowed because of efficiency considerations. Therefore, it is very difficult in general to translate English into Korean with proper word order. However, knowing the dependency parse trees of the English sentences may simplify the reordering problem significantly. In the simple example in Figure 1, if we analyze the English sentence and know that "John" is the subject, "can hit" is the verb and "the ball" is the object, we can reorder the English into SOV order. The resulting sentence "John the ball can hit ." will only need monotonic translation. This motivates us to use a dependency parser for English to perform the reordering. Figure 2 shows the dependency tree for the example sentence in the previous section. In this parse, the verb "hit" has four children: a subject noun "John", an auxiliary verb "can", an object noun "ball" and a punctuation ".". When transforming the sentence to SOV order, we need to move the object noun and the subtree rooted at it to the front of the head verb, but after the subject noun. We can have a simple rule to achieve this. However, in reality, there are many possible children for a verb. These children have some relative ordering that is typically fixed for SOV languages. In order to describe this kind of ordering, we propose precedence reordering rules based on a dependency parse tree. All rules here are based English and Korean examples, but they also apply to other SOV languages, as we will show later empirically.

Precedence Reordering Based on a Dependency Parser
A precedence reordering rule is a mapping from T to a set of tuples {(L, W, O)}, where T is the part-of-speech (POS) tag of the head in a dependency parse tree node, L is a dependency label for a child node, W is a weight indicating the order of that child node and O is the type of order (either NORMAL or REVERSE). The type of order is only used when we have multiple children with the same weight, while the weight is used to determine the relative order of the children, going from largest to smallest. The weight can be any real valued number. The order type NORMAL means we preserve the original order of the children, while REVERSE means we flip the order. We reserve a special label self to refer to the head node itself so that we can apply a weight to the head, too. We will call this tuple a precedence tuple in later discussions. In this study, we use manually created rules only.
Suppose we have a precedence rule: VB → (nsubj, 2, NORMAL), (dobj, 1, NORMAL), (self, 0, NORMAL). For the example shown in Figure 2, we would apply it to the ROOT node and result in "John the ball can hit .".
Given a set of rules, we apply them in a dependency tree recursively starting from the root node. If the POS tag of a node matches the left-hand-side of a rule, the rule is applied and the order of the sentence is changed. We go through all children of the node and get the precedence weights for them from the set of precedence tuples. If we encounter a child node that has a dependency label not listed in the set of tuples, we give it a default weight of 0 and default order type of NORMAL. The children nodes are sorted according to their weights from highest to lowest, and nodes with the same weights are ordered according to the type of order defined in the rule.

Verb Precedence Rules
Verb movement is the most important movement when translating from English (SVO) to Korean (SOV). In a dependency parse tree, a verb node can potentially have many children. For example, auxiliary and passive auxiliary verbs are often grouped together with the main verb and moved together with it. The order, however, is reversed after the movement. In the example of Figure 2, the correct Korean . Figure 3: Dependency Parse Tree with Alignment for a Sentence with Preposition Modifier word order is "`(hit) ˆµ µ µÈ È Èä ä ä(can) . Other categories that are in the same group are phrasal verb particle and negation.
If the verb in an English sentence has a prepositional phrase as a child, the prepositional phrase is often placed before the direct object in the Korean counterpart. As shown in Figure 3, ")Ýt \" ("with a bat") is actually between "t@" ("John") and "ø õD" ("the ball").
Another common reordering phenomenon is when a verb has an adverbial clause modifier. In that case, the whole adverbial clause is moved together to be in front of the subject of the main sentence. Inside the adverbial clause, the ordering follows the same verb reordering rules, so we recursively reorder the clause.
Our verb precedence rule, as in Table 1, can cover all of the above reordering phenomena. One way to interpret this rule set is as follows: for any node whose POS tag is matches VB* (VB, VBZ, VBD, VBP, VBN, VBG), we group the children node that are phrasal verb particle (prt), auxiliary verb (aux), passive auxiliary verb (auxpass), negation (neg) and the verb itself (self) together and reverse them. This verb group is moved to the end of the sentence. We move adverbial clause modifier to the beginning of the sentence, followed by a group of noun subject (nsubj), preposition modifier and anything else not listed in the table, in their original order. Right before the verb group, we put the direct object (dobj). Note that all of the children are optional.

Adjective Precedence Rules
Similar to the verbs, adjectives can also take an auxiliary verb, a passive auxiliary verb and a negation  as modifiers. In such cases, the change in order from English to Korean is similar to the verb rule, except that the head adjective itself should be in front of the verbs. Therefore, in our adjective precedence rule in the second panel of Table 1, we group the auxiliary verb, the passive auxiliary verb and the negation and move them together after reversing their order. They are moved to right after the head adjective, which is put after any other modifiers. For both verb and adjective precedence rules, we also apply some heuristics to prevent excessive movements. In order to do this, we disallow any movement across punctuation and conjunctions. Therefore, for sentences like "John hit the ball but Sam threw the ball", the reordering result would be "John the ball hit but Sam the ball threw", instead of "John the ball but Sam the ball threw hit".

Noun and Preposition Precedence Rules
In Korean, when a noun is modified by a prepositional phrase, such as in "the way to happiness", the prepositional phrase is usually moved in front of the noun, resulting in "‰ ‰ ‰õ õ õ (happiness) < < <\ \ \ " " " 8 8 8 (to the way)" . Similarly for relative clause modifier, it is also reordered to the front of the head noun. For preposition head node with an object modifier, the order is the object first and the preposition last. One example is "with a bat" in Figure 3. It corresponds to ") ) )Ý Ý Ýt t t (a bat) \ \ \(with)". We handle these types of reordering by the noun and preposition precedence rules in the third and fourth panel of Table 1.
With the rules defined in Table 1, we now show a more complex example in Figure 4. First, the ROOT node matches an adjective rule, with four children nodes labeled as (csubj, cop, advcl, p), and with precedence weights of (0, -2, 1, 0). The ROOT node itself has a weight of -1. After reordering, the sentence becomes: "because we do n't know what the future has Living exciting is .". Note that the whole adverbial phrase rooted at "know" is moved to the beginning of the sentence. After that, we see that the child node rooted at "know" matches a verb rule, with five children nodes labeled as (mark, nsubj, aux, neg, ccomp), with weights (0, 0, -2, -2, 0). In this case, the verb itself also has weight -2. Now we have two groups of nodes, with weight 0 and -2, respectively. The first group has a NORMAL order and the second group has a REVERSE order. After reordering, the sentence becomes: "because we what the future has know n't do Living exciting is .". Finally, we have another node rooted at "has" that matches the verb rule again. After the final reordering, we end up with the sentence: "because we the future what has know n't do Living exciting is .". We can see in Figure 4 that this sentence has an almost monotonic alignment with a reasonable Korean translation shown in the figure 1 .

Related Work
As we mentioned in our introduction, there have been several studies in applying source sentence reordering using syntactical analysis for statistical machine translation. Our precedence reordering approach based on a dependency parser is motivated by those previous works, but we also distinguish from their studies in various ways.
Several approaches use syntactical analysis to provide multiple source sentence reordering options through word lattices (Zhang et.al., 2007;Li et.al., 2007;Elming, 2008). A key difference between their approaches and ours is that they do not perform reordering during training. Therefore, they would need to rely on reorder units that are likely not violating "phrase" boundaries. However, since we reorder both training and test data, our system operates in a matched condition. They also focus on either Chinese to English (Zhang et.al., 2007;Li et.al., 2007) or English to Danish (Elming, 2008), which arguably have less long distance reordering than between English and SOV languages.
Studies most similar to ours are those preprocessing reordering approaches (Xia and McCord, 2004;Collins et.al., 2005;Wang et.al., 2007;Habash, 2007). They all perform reordering during preprocessing based on either automatically extracted syntactic rules (Xia and McCord, 2004;Habash, 2007) or manually written rules (Collins et.al., 2005;Wang et.al., 2007). Compared to these approaches, our work has a few differences. First of all, we study a wide range of SOV languages using manually extracted precedence rules, not just for one language like in these studies. Second, as we will show in the next section, we compare our approach to a very strong baseline with more advanced distance based reordering model, not just the simplest distortion model. Third, our precedence reordering rules, like those in Habash, 2007, are more flexible than those other rules. Using just one verb rule, we can perform the reordering of subject, object, preposition modifier, auxiliary verb, negation and the head verb. Although we use manually written rules in this study, it is possible to learn our rules automatically from alignments, similarly to Habash, 2007. However, unlike Habash, 2007, our manually written rules handle unseen children and their order naturally because we have a default precedence weight and order type, and we do not need to match an often too specific condition, but rather just treat all children independently. Therefore, we do not need to use any backoff scheme in order to have a broad coverage. Fourth, we use dependency parse trees rather than constituency trees.
There has been some work on syntactic word order model for English to Japanese machine translation (Chang and Toutanova, 2007). In this work, a global word order model is proposed based on features including word bigram of the target sentence, displacements and POS tags on both source and tar- get sides. They build a log-linear model using these features and apply the model to re-rank N -best lists from a baseline decoder. Although we also study the reordering problem in English to Japanese translation, our approach is to incorporate the linguistically motivated reordering directly into modeling and decoding.

Experiments
We carried out all our experiments based on a stateof-the-art phrase-based statistical machine translation system. When training a system for English to any of the 5 SOV languages, the word alignment step includes 3 iterations of IBM Model-1 training and 2 iterations of HMM training. We do not use Model-4 because it is slow and it does not add much value to our systems in a pilot study. We use the standard phrase extraction algorithm (Koehn et.al., 2003) to get all phrases up to length 5. In addition to the regular distance distortion model, we incorporate a maximum entropy based lexicalized phrase reordering model (Zens and Ney, 2006) as a feature used in decoding. In this model, we use 4 reordering classes (+1, > 1, −1, < −1) and words from both source and target as features. For source words, we use the current aligned word, the word before the current aligned word and the next aligned word; for target words, we use the previous two words in the immediate history. Using this type of features makes it possible to directly use the maximum entropy model in the decoding process (Zens and Ney, 2006). The maximum entropy models are trained on all events extracted from training data word alignments using the LBFGS algorithm (Malouf, 2002  to 30 features, whose weights are optimized using MERT (Och, 2003), with an implementation based on the lattice MERT (Macherey et.al., 2008). For parallel training data, we use an in-house collection of parallel documents. They come from various sources with a substantial portion coming from the web after using simple heuristics to identify potential document pairs. Therefore, for some documents in the training data, we do not necessarily have the exact clean translations. Table 2 shows the actual statistics about the training data for all five languages we study. For all 5 SOV languages, we use the target side of the parallel data and some more monolingual text from crawling the web to build 4gram language models.
We also collected about 10K English sentences from the web randomly. Among them, 9.5K are used as evaluation data. Those sentences were translated by humans to all 5 SOV languages studied in this paper. Each sentence has only one reference translation. We split them into 3 subsets: dev contains 3,500 sentences, test contains 1,000 sentences and the rest of 5,000 sentences are used in a blindtest set. The dev set is used to perform MERT training, while the test set is used to select trained weights due to some nondeterminism of MERT training. We use IBM BLEU (Papineni et al., 2002) to evaluate our translations and use character level BLEU for Korean and Japanese.

Preprocessing Reordering and Reordering Models
We first compare our precedence rules based preprocessing reordering with the maximum entropy based lexicalized reordering model. In Table 3, Baseline is our system with both a distance distortion model and the maximum entropy based lexicalized reordering model. For all results reported in this section, we used a maximum allowed reordering distance of 10. In order to see how the lexicalized reordering model performs, we also included systems with and without it (-LR means without it). PR is our proposed approach in this paper. Note that since we apply precedence reordering rules during preprocessing, we can combine this approach with any other reordering models used during decoding. The only difference is that with the precedence reordering, we would have a different phrase table and in the case of LR, different maximum entropy models. In order to implement the precedence rules, we need a dependency parser. We choose to use a deterministic inductive dependency parser (Nivre and Scholz, 2004) for its efficiency and good accuracy. Our implementation of the deterministic dependency parser using maximum entropy models as the underlying classifiers achieves 87.8% labeled attachment score and 88.8% unlabeled attachment score on standard Penn Treebank evaluation.
As our results in Table 3 show, for all 5 languages, by using the precedence reordering rules as described in Table 1, we achieve significantly better BLEU scores compared to the baseline system. In the table, We use two stars ( * * ) to mean that the statistical significance test using the bootstrap method (Koehn, 2004) gives an above 95% significance level when compared to the baselie. We measured the statistical significance level only for the blindtest data.
Note that for Korean and Japanese, our precedence reordering rules achieve better absolute BLEU score improvements than for Hindi, Urdu and Turkish. Since we only analyzed English and Korean sentences, it is possible that our rules are more geared toward Korean. Japanese has almost exactly the same word order as Korean, so we could assume  the benefits can carry over to Japanese.

Reordering Constraints
One of our motivations of using the precedence reordering rules is that English will look like SOV languages in word order after reordering. Therefore, even monotone decoding should be able to produce better translations. To see this, we carried out a controlled experiment, using Korean as an example. Clearly, after applying the precedence reordering rules, our English to Korean system is not sensitive to the maximum allowed reordering distance anymore. As shown in Figure 5, without the rules, the blindtest BLEU scores improve monotonically as the allowed reordering distance increases. This indicates that the order difference between English and Korean is very significant. Since smaller allowed reordering distance directly corresponds to decoding time, we can see that with the same decoding speed, our proposed approach can achieve almost 5% BLEU score improvements on blindtest set.

Preprocessing Reordering and Hierarchical Model
The hierarchical phrase-based approach has been successfully applied to several systems (Chiang,  Zollmann et.al., 2008). Since hierarchical phrase-based systems can capture long distance reordering by using a PSCFG model, we expect it to perform well in English to SOV language systems. We use the same training data as described in the previous sections for building hierarchical systems. The same 4-gram language models are also used for the 5 SOV languages. We adopt the SAMT package (Zollmann and Venugopal, 2006) and follow similar settings as Zollmann et.al., 2008. We allow each rule to have at most 6 items on the source side, including nonterminals and extract rules from initial phrases of maximum length 12. During decoding, we allow application of all rules of the grammar for chart items spanning up to 12 source words.
Since our precedence reordering applies at preprocessing step, we can train a hierarchical system after applying the reordering rules. When doing so, we use exactly the same settings as a regular hierarchical system. The results for both hierarchical systems and those combined with the precedence reordering are shown in Table 4, together with the best normal phrase-based systems we copy from Table 3. Here again, we mark any blindtest BLEU score that is better than the corresponding hierarchical system with confidence level above 95%. Note that the hierarchical systems can not use the maximum entropy based lexicalized phrase reordering models.
Except for Hindi, applying the precedence reordering rules in a hierarchical system can achieve statistically significant improvements over a normal hierarchical system. We conjecture that this may be because of the simplicity of our reordering rules.   Table 3, while Hier is the hierarchical system.) Other than the reordering phenomena covered by our rules in Table 1, there could be still some local or long distance reordering. Therefore, using a hierarchical phrase-based system can improve those cases. Another possible reason is that after the reordering rules apply in preprocessing, English sentences in the training data are very close to the SOV order. As a result, EM training becomes much easier and word alignment quality becomes better. Therefore, a hierarchical phrase-based system can extract better rules and hence achievesbetter translation quality. We also point out that hierarchical phrase-based systems require a chart parsing algorithm during decoding. Compared to the efficient dynamic programming in phrase-based systems, it is much slower. This makes our approach more appealing in a realtime statistical machine translation system.

Conclusion
In this paper, we present a novel precedence reordering approach based on a dependency parser. We successfully applied this approach to systems translating English to 5 SOV languages: Korean, Japanese, Hindi, Urdu and Turkish. For all 5 languages, we achieve statistically significant improvements in BLEU scores over a state-of-the-art phrasebased baseline system. The amount of training data for the 5 languages varies from around 17M to more than 350M words, including some noisy data from the web. Our proposed approach has shown to be robust and versatile. For 4 out of the 5 languages, our approach can even significantly improve over a hierarchical phrase-based baseline system. As far as we know, we are the first to show that such reordering rules benefit several SOV languages.
We believe our rules are flexible and can cover many linguistic reordering phenomena. The format of our rules also makes it possible to automatically extract rules from word aligned corpora. In the future, we plan to investigate along this direction and extend the rules to languages other than SOV.
The preprocessing reordering like ours is known to be sensitive to parser errors. Some preliminary error analysis already show that indeed some sentences suffer from parser errors. In the recent years, several studies have tried to address this issue by using a word lattice instead of one reordering as input (Zhang et.al., 2007;Li et.al., 2007;Elming, 2008). Although there is clearly room for improvements, we also feel that using one reordering during training may not be good enough either. It would be very interesting to investigate ways to have efficient procedure for training EM models and getting word alignments using word lattices on the source side of the parallel data. Along this line of research, we think some kind of tree-to-string model (Liu et.al., 2006) could be interesting directions to pursue.