extfieldsofstudy:
Computer Science
Medicine

text:
Comparing Stochastic Differential Equations and Agent-Based Modelling and Simulation for Early-Stage Cancer

There is great potential to be explored regarding the use of agent-based modelling and simulation as an alternative paradigm to investigate early-stage cancer interactions with the immune system. It does not suffer from some limitations of ordinary differential equation models, such as the lack of stochasticity, representation of individual behaviours rather than aggregates and individual memory. In this paper we investigate the potential contribution of agent-based modelling and simulation when contrasted with stochastic versions of ODE models using early-stage cancer examples. We seek answers to the following questions: (1) Does this new stochastic formulation produce similar results to the agent-based version? (2) Can these methods be used interchangeably? (3) Do agent-based models outcomes reveal any benefit when compared to the Gillespie results? To answer these research questions we investigate three well-established mathematical models describing interactions between tumour cells and immune elements. These case studies were re-conceptualised under an agent-based perspective and also converted to the Gillespie algorithm formulation. Our interest in this work, therefore, is to establish a methodological discussion regarding the usability of different simulation approaches, rather than provide further biological insights into the investigated case studies. Our results show that it is possible to obtain equivalent models that implement the same mechanisms; however, the incapacity of the Gillespie algorithm to retain individual memory of past events affects the similarity of some results. Furthermore, the emergent behaviour of ABMS produces extra patters of behaviour in the system, which was not obtained by the Gillespie algorithm.

Introduction
In previous work, three case studies using established mathematical models of immune interactions with early-stage cancer were considered in order to investigate the additional contribution of ABMS to ODE models simulation [1]. These case studies were re-conceptualised under an agent-based perspective and the simulation results were compared with those from the ODE models. Our results showed that, apart from the well known differences between these approaches (as those outlined for example, in Schieritz and Milling [2]), further insight from using ABMS was obtained, such as extra population patterns of behaviour.
In this work we apply the Gillespie algorithm [3,4], which is a variation of the Monte Carlo method, to create stochastic versions of the original ODE models investigated in [1]. We aim to reproduce the variability embedded in the ABMS systems to the mathematical formulation and verify whether results resemble each other. In addition, due to the fact that the Gillespie algorithm also regards integer quantities for their elements, we hope that this method overcomes some differences observed when comparing atomic agents represented in the ABMS with possible fractions of elements observable in the ODE results.
To the best of our knowledge, current literature regarding the direct comparison of the Gillespie algorithm and ABMS is scarce.
We want therefore to answer research questions such as: (1) Does this new stochastic formulation produce similar results to ABMS? (2) Can these methods be used interchangeably for our case studies? (3) Does the stochastic model implemented using the Gillespie algorithm also find the extra patterns revealed by the ABMS? We aim to establish a methodological discussion regarding the benefits of each approach for biological simulation, rather than provide further insights into the biological aspects of the problems studied. We therefore intend to compare the dynamics of each approach and observe the outcomes produced over time. We hope that this study provides further insights into the potential usability and contribution of ABMS to systems simulation.

Case Studies
The case studies used for our comparison regard models with different population sizes, varying modelling effort and model complexity. We hope that by tackling problems with different characteristics, a more robust analysis of our experiments is performed. The features of each case study are shown in Table 1.
The first case study considered is based on an ODE model involving interactions between generic tumour and effector cells. The second case study adds to the previous model the influence of the IL-2 cytokine molecules in the immune responses. The third case study comprises a model of interactions between effector cells, tumour cells, and IL-2 and TGF-b molecules. For all case studies, three approaches are presented: the original mathematical model, its conversion into the Gillespie algorithm model and the ABMS model. To answer our research questions, the Gillespie and ABMS approaches outcomes are compared. Our results show that for most cases the Gillespie algorithm does not produce outcomes statistically similar to the ABMS. In addition, Gillespie is incapable to reproduce the extreme patterns observed in the ABMS outcomes for the last case study.
The remainder of this paper is organized as follows. The next section introduces the literature review comparing stochastic ODE models and ABMS for different simulation domains. First, we show general work that has been carried out in areas such as economics and operations research, and then we focus on research concerned with the comparison for immunological problems. Finally, we discuss gaps in the literature regarding cancer research. In the following section we introduce our Gillespie and agentbased modelling development processes and the methods used for conducting the experimentation. Subsequently we present our case studies, comparison results and discussions. In the final section we draw our overall conclusions and outline future research opportunities.

Related Work
Current in-silico approaches used in early-stage cancer research include computational simulation of compartmental models, individual-based models and rule-based models. Compartmental models adopt an aggregate representation of the elements in the system. They include deterministic methods such as ordinary differential equation (ODE) models, system dynamics (SD) models and partial differential equation (PDE) models. These models have been largely employed in the study of dynamics between cancer cells and tumour cells [5,6], therapies for cancer [7], tumour responses to low levels of nutrients [8][9][10][11] and tumour vascularization [12,13]. Although these models have been very useful to understand and uncover various phenomena, they present several limitations. For instance, they do not encompass emergent behaviour and stochasticity. In addition, it is difficult to keep a record of individual behaviour and memory over the simulation course [14,15]. Stochastic compartmental models include Monte Carlo simulation models, which are computational algorithms that perform random sampling to obtain numerical results [16]. Amongst others, they are useful for simulating biological systems, such as cellular interactions and the dynamics of infectious diseases [17]. As these methods rely on stochastic process to produce their outputs, they overcome some of the limitations of the deterministic compartmental models, as they allow for variability of outcomes. The individuals in these models, however, do not have any sort of memory of past events. Rule-based models are a relatively new research area mostly focused on modelling and simulating biochemical reactions, molecular interactions and cellular signalling. The literature regarding the application of rule-based models to interactions between the immune system and cancer cells, however, is scarce. Individual-based models, or agent-based modelling and simulation (ABMS), relax the aggregation assumptions present in compartmental approaches and allow for the observation of the behavior of the single cells or molecules involved in the system. This approach has also been applied to early-stage cancer research [1,18].
The differences between deterministic compartmental models and individual-based models are well known in operations research [2,[19][20][21] and have also been studied in epidemiology [22,23] and system's biology [24][25][26]. Deterministic compartmental models assume continuous values for the individuals in the system, whereas in ABMS individual agents are represented. This peculiarity of each approach highly impacts the simulation results similarity depending on the size of the populations [1]. There is still however the need for further investigations between the interchangeable use of some Monte Carlo methods and ABMS.

Approaches Comparison
As mentioned previously, there are few studies that compare the Gillespie algorithm with ABMS. Most of these studies regard research in economic models and immunology. To the best of our knowledge there is no literature regarding the direct comparison of these methods to early-stage interactions between the immune system and tumour cells. This section describes relevant researches in several areas, which provided further insights into the gaps in the current literature and the research questions addressed in this paper.
There are a few attempts of re-conceptualizing agent-based models into simpler stochastic models of complex systems in economics. For instance, Daniunas et al. [27] start from simple models with established agent-based versions (which they named ''the model's microscopic version'') and try to obtain an equivalent macroscopic behavior. They consider microscopic and macroscopic versions of the herding model proposed by Kirman [28] and the diffusion of new products, proposed by Bass in [29]. They conclude that such simple models are easily replicated in a stochastic environment. In addition, the authors state that for the economics field, only very general models, such as those studied in their article, have well established agent-based versions and can be described by stochastic or ordinary differential equations. However, as the complexity of the microscopic environment increases, it becomes challenging to obtain resembling results with stochastic simulations and further developments need to be pursuit. Furthermore, the authors debate that the ambiguity present in the microscopic description in complex systems is an objective obstacle for quantitative modeling and needs further studying.
Stracquadanio et al. [30] investigate the contributions of ABMS and the Gillespie method for immune modelling. The authors, however, do not apply both methods to the same problem. Instead, for the first approach, they chose to investigate a largescale model involving interactions of immune cells and molecules. This model's objective was to simulate the immune elements interplay over time. For the Gillespie approach, the authors investigate a stochastic viral infection model. The authors point out three factors that play a major role in the modeling outcome when comparing ABMS and Gillespie: simulation time, model precision and accuracy, and model applicability. Regarding time, the authors state that stochastic models implemented with the Gillespie algorithm are preferred. On the other hand, ABMS permits more control over simulation runtime as it keeps record of the behavior of each single entity involved in the system. Regarding applicability, the authors argue that traditional Gillespie methods do not account for spatial information, which can be detrimental to the model accuracy given the fact that many immune interactions occur within specific spatial regions of the simulation environment.
Karkutla [31] compares two biological simulators: GridCell, which is a stochastic tool based on Gillespie's, and his new developed ABMSim, which is a simulation tool based on ABMS. GridCell was developed to overcome the issues in traditional Gillespie's, as pointed out by Stracquadanio et al. [30]. It is a stochastic tool able to tackle non-homogeneity effectively by addressing issues of crowding and localization. In GridCell, however, the problem of tracking individual behaviour and determining particular characteristics to each element still exists. ABMSim was therefore developed to overcome these issues. GridCell has been compared with ABMSim qualitatively and quantitatively and the two tools have produced similar results in the author experiments.
In our work we further study the differences between the approaches outcomes and investigate whether under different problem characteristics for early-stage cancer we still obtain

Methods
This section introduces the research methodology used for the development of our simulation models and for the experimentation performed in the following sections. As mentioned previously, our investigations concern the use of three cases to answer research questions regarding the application of the Gillespie algorithm and ABMS interchangeably for early-stage cancer models. For each case study, there is a well established ODE model from the literature and its correspondent agent-based model, that we previously developed in [1]. The ODE model simulations are implemented using the ODE solver module from MATLAB (2011) The Gillespie algorithm is implemented by the direct conversion of the original mathematical equations into reactions and simulating them under the COPASI 4:8 (Build35) simulator environment. The method used for the stochastic simulations is the Gillespie algorithm adapted using the next reaction method [32], with interval sizes of 0:1, integration interval between 0 and 1 and maximum internal steps of 10 6 .
ABMS is a modelling and simulation technique that employs autonomous agents that interact with each other. The agents' behaviour is described by rules that determines how they learn, interact and adapt. The overall system behaviour is given by the agents individual dynamics as well as their interactions. Our agentbased models are implemented using the AnyLogic TM 6.5 educational version (XJ Technologies 2010) [33]. This approach is developed by using state charts and tables containing each agent description. The state charts show the different possible states of an entity and define the events that cause a transition from one state to another. In order to facilitate the understanding of the agentbased model, we reproduce here the models developments, which were based on [1] (The ABMS and Gillespie models are available for download in http://anytips.cs.nott.ac.uk/wiki/index.php/ Resources).

Methodology for Results Comparison
As the Gillespie and ABMS are both stochastic simulation methods, we ran five hundred replications for each case study and calculated the mean values for the outputs. For all approaches, the rates (for cellular death, birth, etc.) employed were the same as those established by the mathematical model.
In addition, in order to investigate any statically significant differences between the ABMS and Gillespie techniques for the case studies, we implement a mixed effect model. This is a type of regression that considers both fixed and random effects. This method accounts for correlation caused by repeating the measure over time (i.e., the tumour cell count is correlated over time for each simulation run). The mixed effect analysis was implemented in the programming language R using the package NLME [34].
As a mixed effect model requires finding parameters for a regression model, it is not suitable when considering the whole time period. This is because in cases 2 and 3 the tumour dynamics has a damping oscillation and the function describing this dynamics is unknown (see pages 11 and 14). Instead, the sequence of local maxima and minima are used. It can been seen that these are converging and any statistical deviation between these sequences for the different simulation techniques indicate differences between the output of the techniques. If the simulations from the ABMS and the Gillespie technique come from the same distribution, then there would be no statistical difference between the maxima and minima over time. Therefore, we investigate two  null hypotheses. The first is that the function of local maxima is the same for the ABMS and the Gillespie algorithm simulations. And the second is that the function of local minima is the same for the ABMS and the Gillespie algorithm simulations. We use a 1% significance level.
There is no standard technique for estimating the required sample size for non-linear mixed effect models for a defined power when the measure of effect is known [35]. Therefore, the simulations are run 500 times as this will increase the statistical power and increase the probability of a true positive in the statistical analysis. A false negative is still possible if there is only a small effect size, but if the effect is small, it is of less interest.

Case 1: Interactions between Tumour Cells and Generic Effector Cells
The first case considers tumour cells growth and their interactions with general immune effector cells, as defined in [8]. According to the model, effector cells search and kill the tumour cells inside the organism. They proliferate proportionally to the number of existing tumour cells. As the quantities of effector cells increase, their capacity of eliminating tumour cells is augmented. Immune cells proliferate and die per apoptosis, which is a programmed cellular death. In the model, cancer treatment is also considered and it consists of injections of new effector cells in the organism.
Mathematically, the interactions between tumour cells and immune effector cells are defined as follows [8]:   Table 2 shows the mathematical equations converted into reactions and their respective rate laws per cell.
In the agent-based model there are two classes of agents, the tumor cells and the effector cells, as described in [1]. Table 3 shows the parameters and behaviours corresponding to each agent state. For our agents, state charts are used to represent the different states each entity is in. In addition, transitions are used to indicate how the agents move from one state to another. Events are also employed and they indicate that certain actions are scheduled to occur in the course of the simulation, such as injection of treatment. The state chart representing the tumour cells is shown in Figure 1(a), in which an agent proliferates, dies with age or is killed by effector cells. In addition, tumour cells  contribute to damage to effector cells, according to the same rate as defined by the mathematical model (Table 4). Figure 1(b) shows the state chart for the effector cells. In the figure, the cell is either alive or dead by age or apoptosis. While the cell is alive, it is also able to kill tumour cells and proliferate. In the transition rate calculations, the variable TotalTumourCells corresponds to the total number of tumour cell agents; and the variable TotalEffectorCells is the total number of effector cell agents. In the simulation model, apart from the agents, there is also an event -namely, treatment -which produces new effector cells with a rate defined by the parameter s. Experimental design for the simulations. Similarly to the experiments from [1], four scenarios are investigated. The scenarios have different rates for the death of tumour cells (defined by parameter b), effector cells apoptosis (defined by parameter d) and different treatments (parameter s). The values for these parameters are obtained from [6] (Table 5). In the first three scenarios, cancer treatment is considered, while the fourth case does not consider any treatment. The simulations for the ABMS and the Gillespie algorithm are run five hundred times and the mean values are displayed as results.
Results and discussion. Figure 2 shows the results of our experiments. In the first column we display the results from the ODE model for guidance. The second column shows the results from the Gillespie algorithm and the third column presents the ABMS results. Each row of the figure represents a different scenario.
Results for Scenario 1 appear similar for the three approaches, although the effector cells curve from the ABMS show more variability. To evaluate whether the results are significantly different for the two simulation methods, we apply a mixed effect model. The null hypothesis is that there is no significant difference between the methods (and therefore there will be no significant fixed effect for the method type). We use a 1% significance level. We are testing the similarity for the population of effector cells.
The effector cells follow a dynamic similar to 1/x for the time between 1 and 100: We apply a mixed-effect model where the simulation run is considered to have a random effect on the parameter a and the simulation method has a fixed effect on a and b. The results are presented in Table 6. At a 1% significance level the results of the two techniques are significantly different as the p-values for the fixed effect of the method on the parameters are less than 0:1.
We believe that the variability observed in the ABMS and Gillespie curves, given their stochasticity, also influenced the statistical test results. The number of effector cells for all simulations follow a similar pattern, although the similarity hypothesis was rejected. This variability of Gillespie and ABMS is very evident with regards to the effector cells population as the size of the populations involved in the first scenario is relatively small, which increases the impacts of stochasticity in the outcomes.
Results for scenario 2 are shown in the second row of Figure 2. The outcomes seem fairly different. By observing the ODE results, during about the first ten days, the tumour cells decrease and then grow up to a value of about 240 cells, subsequently reaching a  steady-state. This initial decrease is also observed in both Gillespie and ABMS curves. However, only the Gillespie method shows a similar increase in the numbers of tumour cells when compared to the ODEs. Similarly to the previous scenario, the Gillespie and ABMS simulation curves present an erratic behaviour throughout the simulation days. There is, however, an unexpected decay of tumour cells over time in the ABMS simulation, which does not happen in the Gillespie outcome. We believe the difference observed in the ABMS is due to the the individual characteristics of the agents and their growth/death rates attributed to their instantiation. While both ODEs and Gillespie are compartmental models and therefore they apply the model rates to the cells population, ABMS on the contrary, employs these rates in an individual basis. As the death rates of the tumour cells agents are defined according to the mathematical model, when the tumour cell population grows, the newborn tumour cells have higher death probabilities, which leads to a considerable number of cells dying out. This indicates that the individual behaviour of cells can lead to a more chaotic behaviour when compared to the aggregate view observed in the compartmental simulation. For scenarios 3 and 4, shown in third and fourth rows of Figure 2, respectively, the results for the three approaches differ completely. The differences are even more evident for the tumour cells outcomes. The ODEs results for scenario 3 reveal that tumour cells decreased as effector cells increased, following a predator-prey trend curve. For the ABMS, however, the number of effector cells decreased until a value close to zero was reached, while the tumour cells numbers were very different from those in the ODEs results. The ODE pattern noticed was possible given its continuous character. In the ODE simulation outcome curve for the effector cells it is therefore possible to observe, for instance, that after sixty days the number of effector cells ranges between one and two. These values could not be reflected in the ABMS simulation, as it deals with integer values. Similarly, the Gillespie approach outcomes did not resemble those from the ODE model. There is more variability in the tumour cells curve than in the ABMS outcomes, although the number of tumour cells also reaches zero after around sixty days.
In the fourth scenario, although effector cells appear to decay in a similar trend for both approaches, the results for tumour cells vary largely. In the ODE simulation, the numbers of effector cells reached a value close to zero after twenty days and then increased to a value smaller than one. For the ABMS simulation, however, these cells reached zero and never increased again. For the Gillespie model results, a similar pattern as that from the ABMS model occurs, although there seems to be less variance in the outcome curve. In addition, the mean numbers for tumour cells for the Gillespie approach seem smaller that those observed in the ABMS.
Summary. An outcome comparison between an ABMS and a Gillespie algorithm model was performed for case study 1. We considered an ODE model of tumour cells growth and their interactions with general immune effector cells as the baseline for results validation. Four scenarios considering small population numbers were investigated and results from ABMS and Gillespie were different for both populations for all scenarios. Furthermore, both approaches differed largely from the original mathematical outcomes. These results indicate that, for this case study, the stochasticity applied to the population as a whole when compared to that applied to the individual has a higher impact given the small population sizes. The result analysis also reveals that conceptualizing the stochastic approaches from the mathematical equations does not always produce statistically similar outputs.

Case 2: Interactions between Tumour Cells, Effector Cells and Cytokines IL-2
Case two regards the interactions between tumour cells, effector cells and the cytokine IL-2. It extends the previous study as it considers IL-2 as molecules mediating the immune response towards tumour cells. These molecules interfere in the proliferation of effector cells, which occurs proportionally to the number of tumour cells in the system. For this case, there are two types of treatment, the injection of effector cells or the addition of cytokines.
The mathematical model used in case 2 is obtained from [9]. The model's equations described bellow illustrate the non-spatial  dynamics between effector cells (E), tumour cells (T) and the cytokine IL-2 (I L ): Equation 10 describes the rate of change for the effector cell population E [9]. Effector cells grow based on recruitment (cT) and proliferation ( ). The parameter c represents the antigenicity of the tumour cells (T) [5,9]. m 2 is the death rate of the effector cells. p 1 and g 1 are parameters used to calibrate the recruitment of effector cells and s1 is the treatment that will boost the number of effector cells.
Equation 11 describes the changes that occur in the tumour cell population T over time. The term a(1{bT) represents the logistic growth of T (a and b are parameters that define how the tumour cells will grow) and aaET g 2 zT is the number of tumour cells killed by effector cells. a a and g 2 are parameters to adjust the model.
The IL-2 population dynamics is described by Equation 12.
determines IL-2 production using parameters p 2 and g 3 . m 3 is the IL-2 loss. s2 also represents treatment. The treatment is the injection of IL-2 in the system. Table 7 shows the mathematical model converted into reactions for the Gillespie algorithm model. The first column of the table displays the original mathematical equation, followed by the equivalent reactions and rate laws in the subsequent columns.
As described in [1], the agents represent the effector cells, tumour cells and IL-2. Their behaviours are shown in Table 8. The state charts for each agent type are shown in Figure 3. The ABMS model rates are the same as those defined in the mathematical model and are given in Table 9. In the transition rate calculations, the variable TotalTumour corresponds to the total number of tumour cell agents, the variable TotalEffector is the total number of effector cell agents and TotalIL 2 is the total number of IL-2 agents. In the simulation model, apart from the agents, there are also two events: the first event adds effector cell agents according to the parameter s1 and the second one adds IL-2 agents according to the parameter s2.
Experimental design for the simulation. The experiment is conducted assuming the same parameters as those of the mathematical model (Table 10). For the ABMS and the Gillespie algorithm model, the simulation is run five hundred times and the average outcome value for these runs is collected. Each run simulates a period equivalent to six hundred days, following the same time span used for the numerical simulation of the mathematical model.
Results and discussion. The results obtained are shown in Figure 4 for tumour cells (left), effector cells (middle) and IL-2 (right), respectively. As the figure reveals, the results for all populations are analogous; the growth and decrease of all populations occur at similar times for all approaches. ABMS has a little more variability in the results, specially regarding IL-2. We believe that for this case, the large population sizes (around 10 4 )  produce a lower variability in the outcomes of the stochastic approaches. For statistical comparison, results were contrasted by applying a non-linear mixed effect model, as shown next. The local maxima sequence follows a second order polynomial function of the form: The local minima sequence follows a second order polynomial function of the form: For the mixed-effect model, we consider a and b to have fixed effects based on the type of simulation (e.g., ABMS or Gillespie algorithm) and a and b to have random effects based on the individual simulation run. The results of the mixed effect model  are presented in Tables 11 and 12. It can been seen that there is a significant difference between the a and b parameter values for the two different techniques. We therefore reject the null hypotheses and accept that there is a significance difference between the two techniques in terms of the sequence of maxima and sequence of minima, at a 1% significance level. Furthermore, the results show that the ABMS simulations tend to have larger local maxima and smaller local minima, which is clear in Figure 5. Summary. Interactions between tumour cells, effector cells and the cytokine IL-2 were considered to investigate the potential differences and similarities of ABMS and Gillespie algorithm outcomes. Statistical comparison between the Gillespie and the ABMS results show a significant difference in the outcomes. Compared to the original ODE model used as validation, ABMS displayed a little more variability in the results, whereas the Gillespie algorithm followed mostly the same patterns as those produced by the ODEs for all populations in the simulation. As for these simulations a bigger number of individuals was required, it was also observed that, regarding the use of computational resources, ABMS was far more time-and memory-consuming than the Gillespie approach.

Case 3: Interactions between Tumour Cells, Effector Cells, IL-2 and TGF-b
Case study three comprises interactions between tumour cells and immune effector cells, as well as the immune-stimulatory and suppressive cytokines IL-2 and TGF-b [5]. According to the ODE model developed by Arciero et al. in [5], TGF-b stimulates tumour growth and suppresses the immune system by inhibiting the activation of effector cells and reducing tumour antigen expression.
The mathematical model is described by the differential equations below: Equation 15 describes the rate of change for the effector cell population E. According to [5], effector cells are assumed to be recruited to a tumour site as a direct result of the presence of tumour cells. The parameter c in cT 1zcS represents the antigenicity of the tumour, which measures the ability of the immune system to recognize  on the presence of the cytokine IL-2 and is decreased when the cytokine TGF-b is present. p 1 is the maximum rate of effector cell proliferation in the absence of TGF-b, g 1 and q 2 are halfsaturation constants, and q 1 is the maximum rate of antiproliferative effect of TGF-b.
Equation 16 describes the dynamics of the tumour cell population. The term aT 1{ T K À Á represents a logistic growth dynamics with intrinsic growth rate a and carrying capacity K in the absence of effector cells and TGF-b. The term aaET g 2 zT is the number of tumour cells killed by effector cells. The parameter a a measures the strength of the immune response to tumour cells. The third term p 2 ST g 3 zS accounts for the increased growth of tumour cells in the presence of TGF-b. p 2 is the maximum rate of increased proliferation and g 3 is the half-saturation constant, which indicates a limited response of tumour cells to this growth-stimulatory cytokine [5].   The kinetics of IL-2 are described in equation 17. The first term p 3 ET (g 4 zT)(1zaS) represents IL-2 production which reaches a maximal rate of p 3 in the presence of effector cells stimulated by their interaction with the tumour cells. In the absence of TGF-b, this is a self-limiting process with half-saturation constant g 4 S [5]. The presence of TGF-b inhibits IL-2 production, where the parameter a is a measure of inhibition. Finally, m 2 I represents the loss of IL-2.
dS dt~p Equation 18 describes the rate of change of the suppressor cytokine, TGF-b. According to [5], experimental evidence suggests that TGF-b is produced in very small amounts when tumours are small enough to receive ample nutrient from the surrounding tissue. However, as the tumour population grows sufficiently large, tumour cells suffer from a lack of oxygen and begin to produce TGF-b in order to stimulate angiogenesis and to evade the immune response once tumour growth resumes. This switch in TGF-b production is modelled by the term p 4 T 2 h 2 zT 2 , where p 4 is the maximum rate of TGF-b production and t is the critical tumour cell population in which the switch occurs. The decay rate of TGF-b is represented by the term m 3 S. Table 13 presents the Gillespie algorithm model used for our simulations. The model was obtained by converting the ODEs into reaction equations.
The agents established for the ABMS represent the effector cells, tumour cells, IL-2 and TGF-b populations, as described in [1]. The agents' behaviour is defined in Table 14. The state charts for each agent type are illustrated in Figure 6.
The ABMS model rates corresponding to the mathematical model are given in Table 15. In the transition rate calculations, the variable TotalTumour corresponds to the total number of tumour cell agents; the variable TotalEffector is the total number of effector cell agents, TotalIL 2 is the total number of IL-2 agents and TotalTGFBeta is the total TGF-b agents. This model does not include events.

Experimental Design for the Simulation
The experiment is conducted assuming the same parameters as those defined for the mathematical model (Table 16). Similarly to the previous case studies, for the ABMS and Gillespie models the simulation is run five hundred times and the average outcome value for these runs is displayed as result. Each run simulates a   Table 16.
Results and discussion. The mean results of 500 runs for the Gillespie algorithm and the ABMS contrasted with the ODE model are shown in Figure 7. The left graph in the figure presents the outcomes for tumour cells; the graph in the middle shows the outputs for effector cells; the graph on the right shows the mean IL-2 outcomes (the TGF-b results have some particularities and therefore are discussed next). The figure shows that both Gillespie and ABMS do not match properly the original results from the mathematical model. Additionally, ABMS is far more dissimilar than what was anticipated. In order to understand why the mean values were that much different from what was expected, we plotted fifty individual runs for each approach, as shown in figures 8, 9, 10 and 11. These runs illustrate the variations observed in both ABMS (left side of the figures) and Gillespie (right side of the figures) approaches, due to its stochastic character. In the figures, the ODE model results were also plotted (dashed black line) in order to highlight the range of variation produced by the stochastic approaches. As it can be observed in the figures, both Gillespie and ABMS outcomes produce various slightly distinct starting times for the growth of populations. In addition to these variations, for a few runs the populations in ABMS decreased to zero, as previously reported in [1]. This behaviour was not reflected in the Gillespie algorithm results. This indicates that it is not always possible to replicate similar results within both approaches.
The use of ABS modelling has therefore led to the discovery of additional ''rare'' patterns, which we would have not been able to derive by using analytical methods or the dynamic Monte Carlo  method, i.e. the Gillespie algorithm. These ''extreme cases'' found by ABMS suggest that there might be circumstances where the tumour cells are completely eliminated by the immune system, without the need of any cancer therapies.
We believe that ABMS when compared to Gillespie produces extra patterns because of the agents individual behaviour and their interactions. While ODEs and the Gillespie algorithm always use the same values for the parameters over the entire population aggregate, ABMS rates vary with time and number of individuals. Each agent is likely to have distinct numbers for their probabilities and therefore have its own memory of past events (Gilespie, however, does not encompass individual memory for its elements). The agents individual interactions, which give raise to the overall behaviour of the system, are also influenced by the scenario determined by the random numbers used. By running the ABMS multiple times with different sets of random numbers, the outcomes vary according to these sets and the emerging interactions of the agents also produce the rare outcome patterns.
For further statistical comparison of the results that follow the same pattern of behaviour for ABMS and Gillespie, a mixed-effect model is used. In 236 of the 500 ABMS simulations the tumour cell population dies out early in time. The remaining 264 ABMS simulations (where the tumour cell population does not die out over the [0,600] time period) is compared with the 500 Gillespie simulations by a non-linear mixed effect model.
The local maxima sequence follows a second order polynomial function of the form: The local minima sequence follows a second order polynomial function of the form: For the mixed-effect model we considered a and b to have fixed effects based on the type of simulation (e.g., ABMS or Gillespie algorithm) and a and b to have random effects based on the individual simulation run. The results of the mixed effect model are presented in Tables 17 and 18. It can been seen that there is a significant difference between the a and b parameter values for the two different techniques. We therefore reject the null hypotheses and accept that there is a significance difference between the two techniques in terms of the sequence of maxima and sequence of minima, at a 1% significance level.
Tables 17-18 and Figure 12 show that the sequence of local maxima of the ABMS diverge from that of the Gillespie algorithm over time. In the ABMS the tumour cells tend to increase to a larger count than the Gillespie algorithm simulations causing the function of local maxima for the ABMS to be significantly greater than the Gillespie. A possible explanation for this, as mentioned previously, is the fact that agents have memory and therefore the rates (death, proliferation, etc) for a certain cell are determined by the cells (and their proportions) present in the system at the moment the cell was created. For the Gillespie algorithm, instead, the rates are applied globally to the entire population and remain constant over the simulation course. Consequently, for Gillespie, the individuals do not keep a record of the previous population dynamics. This explanation is supported by the observation that the function describing the sequence of local minima of the ABMS is significantly lower than the Gillespie algorithm over time, as the same argument would account for the ABMS simulations reaching lower levels.
Regarding the TGF-b outcomes, the ODEs results reveal numbers smaller than one ( Figure 11 on the right), which is not possible to achieve with the ABMS and the Gillespie algorithm. The simulation results regarding these molecules are therefore completely different for both stochastic approaches. By observing the multiple runs graph of ABMS, however, results indicate that the TGF-b grows at around 100 and 200 days, which resembles what occurs in the ODE simulation for the first two peaks of TGFb concentration. This suggests that ABMS, as opposite to Gillespie, is capable of capturing some of the behaviours of the analytical results even when the outputs are different. We believe that these observations need to be further investigated in order to determine whether this happens in other case studies. In addition, it is necessary to investigate in what circumstances and range of values ABMS is still capable to reflect behaviours of numbers smaller than one agent present in the ODE model.

Summary
The third case study simulations investigated interactions between effector cells, tumour cells and two types of cytokines, namely IL-2 and TGF-b. When compared to the original ODE results, both Gillespie algorithm and ABMS produced more variability in the outcomes. For each of the five hundred runs, a slightly different start of population growth was observed. In addition, ABMS produced extra patterns not observed in the original mathematical model and in the Gillespie results. These extra patterns have been reported previously in [1] and with the present work we wanted to find out whether the Gillespie algorithm simulation results would be as informative. This indicates that, for this case study, both methods should not be employed interchangeably, as some extra possible population patterns of behaviour might not be uncovered without ABMS. We believe that these emergent examples occur due to the individual interactions of the agents and their chaotic character. With these results, we answer our third research question that it is not possible in this case to obtain extreme patterns using the Gillespie algorithm.

Conclusions
In this work, we employed three case studies to investigate circumstances where we can use ABMS and the Gillespie algorithm interchangeably. We aimed at reproducing the variability embedded in the ABMS systems to the mathematical formulation and verify whether results resemble. Current literature  regarding the comparison of the Gillespie algorithm and ABMS is scarce and we wanted therefore to answer the questions: (1) Does the Gillespie algorithm produce similar results to ABMS? (2) Can these two methods be used interchangeably for our case studies? (3) Does the Gillespie algorithm also find the extra patterns revealed by the ABMS in the third case study? The case studies investigated regarded models with different characteristics, such as population sizes, modelling effort demanded and model complexity.
The first case study involved interactions with general immune effector cells and tumour cells. Four different scenarios regarding distinct sets of parameters were investigated and in the first three scenarios treatment was included. ABMS and Gillespie produced different results for all scenarios. It appears that two major characteristics of this model influenced the differences obtained: (1) The small quantities of individuals considered in the simulations (especially regarding the effector population size, which was always smaller than ten) that significantly increased the variability of both stochastic approaches; and (2) the stochasticity of the Gillespie algorithm is applied to the aggregates, while in the ABMS there is individual variability.
Case study 2 referred to the investigation of a scenario containing interactions between effector cells, cytokines IL-2 and tumour cells. For this case the Gillespie and ABMS approaches produced similar outcome curves, which also matched the pattern of behaviour of the mathematical model used for validation. As populations sizes had a magnitude of 104 individuals, the erratic behaviour of both stochastic approaches was no longer evident in the outcomes. However, although results seemed similar, further statistical tests reject their similarity hypothesis. It was observed that, for case 2 in general, ABMS simulation outcome curves tend to have larger local maxima and smaller local minima.
Case study 3 includes the influence of the cytokine TGF-b in the interactions between effector cells, cytokines IL-2 and tumour cells from the previous case. The simulation outcomes for the ABMS were mostly following the same pattern as those produced by the Gillespie algorithm, although the results were statistically different. In addition, Gillespie failed to replicate the alternative outcomes found by the ABMS. This indicates that for this case study the ABMS results are more informative, as they illustrate another set of possible dynamics to be validated in real-world. Furthermore, ABMS was also able to indicate two peaks where TGF-b concentrations have grown, although the corresponding values in the mathematical model were smaller than one.
In response to our research questions, we conclude that regarding the interchangeable use of Gillespie and ABMS, population size has a positive impact on result similarity. This means that bigger populations tend to result in close simulation output patterns. However, the stochasticity of both approaches and the memory present in the ABMS produce outcome differences which are statistically significant, although visually the outcomes look similar. Finally, the emergent behaviour of ABMS can contribute additional insight (extra patterns), which was not obtained by the aggregate stochasticity present in Gillespie, given its incapacity of retaining memory of past events for their elements.
Currently, it is acknowledged that the necessary levels of detail present a system's conceptual model might require the adoption of multiple simulation approaches, under different scales of abstraction, in order to produce satisfactory outcomes. For certain cases, multi-scale and multi-modelling solutions represent the only possible manner to properly implement a set of requirements, even though these practices are generally more resource-intensive.
Several models, especially those regarding biological systems, encompass elements with distinct time and length scales coupled together. Multiple layers involving different levels of granularity need therefore to be considered. Phenomena such as cellular gradient-based chemotaxis and nutrient-dependent cell cycles are better implemented by employing numerical simulation (such as partial and ordinary differential equations). On the other hand, cellular random movement, memory, adaptability, explicit representation of space, heterogeneous populations, etc. represent suitable concepts to be represented within an agent-based approach. There are also subsets of characteristics in a system that can be implemented under more than one approach.
Despite of the well-known domains of applicability of each simulation technique, other factors such as the real-world data availability, the computing resources, the required granularity of the model, the time available to develop the simulation, the research questions and the expertise of the simulation developer also influence the decision on the paradigms to be adopted. By understanding the strengths and weaknesses of each approach, it is possible decide on which route to take and also the implications of this decision to the final outcome. We hope that our study results can assist simulation researchers on this debate.


Phrasal: A Toolkit for New Directions in Statistical Machine Translation

We present a new version of Phrasal, an open-source toolkit for statistical phrasebased machine translation. This revision includes features that support emerging research trends such as (a) tuning with large feature sets, (b) tuning on large datasets like thebitext, and(c)web-basedinteractivemachine translation. A direct comparison with Moses shows favorable results in terms of decoding speed and tuning time.

Introduction
In the early part of the last decade, phrase-based machine translation (MT) (Koehn et al., 2003) emerged as the preeminent design of statistical MT systems. However, most systems were proprietary or closedsource, so progress was initially constrained by the high engineering barrier to entry into the field. Then Moses (Koehn et al., 2007) was released. What followed was a flowering of work on all aspects of the translation problem, from rule extraction to deployment issues. Other toolkits appeared including Joshua (Post et al., 2013), Jane (Wuebker et al., 2012), cdec (Dyer et al., 2010) and the first version of our package, Phrasal (Cer et al., 2010), a Java-based, open source package. This paper presents a completely re-designed release of Phrasal that lowers the barrier to entry into several exciting areas of MT research. First, Phrasal exposes a simple yet flexible feature API for building large-scale, feature-rich systems. Second, Phrasal provides multi-threaded decoding and online tuning for learning feature-rich models on very large datasets, including the bitext. Third, Phrasal supplies the key ingredients for web-based, interactive MT: an asynchronous RESTful JSON web service implemented as a J2EE servlet, integrated pre-and post-processing, and fast search.
Revisions to Phrasal were guided by several design choices. First, we optimized the system for multi-core architectures, eschewing distributed infrastructure like Hadoop and MapReduce. While "scaling-out" with distributed infrastructure is the conventional industry and academic choice, we find that "scaling-up" on a single large-node is an attractive yet overlooked alternative (Appuswamy et al., 2013). A single "scale-up" node is usually competitive in terms of cost and performance, and multi-core code has fewer dependencies in terms of software and expertise. Second, Phrasal makes extensive use of Java interfaces and reflection. This is especially helpful in the feature API. A feature function can be added to the system by simply implementing an interface and specifying the class name on the decoder command line. There is no need to modify or recompile anything other than the new feature function.
This paper presents a direct comparison of Phrasal and Moses that shows favorable results in terms of decoding speed and tuning time. An indirect comparison via the WMT2014 shared task (Neidert et al., 2014) showed that Phrasal compares favorably to Moses in an evaluation setting. The source code is freely available at: http://nlp.stanford.edu/software/phrasal/

Standard System Pipeline
This section describes the steps required to build a phrase-based MT system from raw text. Each step is implemented as a stand-alone executable. For convenience, the Phrasal distribution includes a script that coordinates the steps.

Prerequisites
Phrasal assumes offline preparation of word alignments and at least one target-side language model.

Word Alignment
The rule extractor can accommodate either unsymmetrized or symmetrized alignments. Unsymmetrized alignments can be produced with either GIZA++ or the Berkeley Aligner (Liang et al., 2006). Phrasal then applies symmetrization on-the-fly using heuristics such as grow-diag or grow-diag-final. If the alignments are symmetrized separately, then Phrasal accepts align-ments in the i-j Pharaoh format, which indicates that source token i is aligned to target token j.
Language Modeling Phrasal can load any ngram language model saved in the ARPA format. There are two LM loaders. The Java-based loader is used by default and is appropriate for small-scale experiments and pure-Java environments. The C++ KenLM (Heafield, 2011) loader 1 is best for largescale LMs such as the unfiltered models produced by lmplz . Profiling shows that LM queries often account for more than 50% of the CPU time in a Phrasal decoding run, so we designed the Phrasal KenLM loader to execute queries mostly in C++ for efficiency. The KenLM binding efficiently passes full strings to C++ via JNI. KenLM then iterates over the string, returning a score and a state length. Phrasal can load multiple language models, and includes native support for the class-based language models that have become popular in recent evaluations (Wuebker et al., 2012;Ammar et al., 2013;Durrani et al., 2013).

Rule Extraction
The next step in the pipeline is extraction of a phrase table. Phrasal includes a multi-threaded version of the rule extraction algorithm of Och and Ney (2004). Phrase tables can be filtered to a specific data set-as is common in research environments. When filtering, the rule extractor lowers memory utilization by splitting the data into arbitrary-sized chunks and extracting rules from each chunk.
The rule extractor includes a feature API that is independent of the decoder feature API. This allows for storage of static rule feature values in the phrase table. Static rule features are useful in two cases. First, if a feature value depends on bitext statistics, which are not accessible during tuning or decoding, then that feature should be stored in the phrase table. Examples are the standard phrase translation probabilities, and the dense rule count and rule uniqueness indicators described by Green et al. (2013). Second, if a feature depends only on the rule and is unlikely to change, then it may be more efficient to store that feature value in the phrase table. An example is a feature template that indicates inclusion in a specific data domain (Durrani et al., 2013). Rule extractor feature templates must implement the FeatureExtractor interface and are loaded via reflection.
1 Invoked by prefixing the LM path with the "kenlm:".
The rule extractor can also create lexicalized reordering tables. The standard phrase orientation model (Tillmann, 2004) and the hierarchical model of Galley and Manning (2008) are available.

Tuning
Once a language model has been estimated and a phrase table has been extracted, the next step is to estimate model weights. Phrasal supports tuning over n-best lists, which permits rapid experimentation with different error metrics and loss functions. Lattice-based tuning, while in principle more powerful, requires metrics and losses that factor over lattices, and in practice works no better than n-best tuning (Cherry and Foster, 2012).
Tuning requires a parallel set {(f t , e t )} T t=1 of source sentences f t and target references e t . 2 Phrasal follows the log-linear approach to phrasebased translation (Och and Ney, 2004) in which the predictive translation distribution p(e|f ; w) is modeled directly as where w ∈ R d is the vector of model parameters, φ(·) ∈ R d is a feature map, and Z(f ) is an appropriate normalizing constant. MT differs from other machine learning settings in that it is not common to tune to log-likelihood under (1). Instead, a gold error metric G(e , e) is chosen that specifies the similarity between a hypothesis e and a reference e, and that error is minimized over the tuning set. Phrasal includes Java implementations of BLEU (Papineni et al., 2002), NIST, and WER, and bindings for TER (Snover et al., 2006) and METEOR (Denkowski and Lavie, 2011). The error metric is incorporated into a loss function that returns the loss at either the sentenceor corpus-level.
For conventional corpus-level (batch) tuning, Phrasal includes multi-threaded implementations of MERT (Och, 2003) and PRO (Hopkins and May, 2011). The MERT implementation uses the line search of Cer et al. (2008) to directly minimize corpus-level error. The PRO implementation uses a pairwise logistic loss to minimize the number of inversions in the ranked n-best lists. These batch implementations accumulate n-best lists across epochs.
Online tuning is faster and more scalable than batch tuning, and sometimes leads to better solutions for non-convex settings like MT (Bottou and Bousquet, 2011). Weight updates are performed after each tuning example is decoded, and n-best lists are not accumulated. Consequently, online tuning is preferable for large tuning sets, or for rapid iteration during development. Phrasal includes the AdaGrad-based (Duchi et al., 2011) tuner of Green et al. (2013). The regularization options are L 2 , efficient L 1 for feature selection (Duchi and Singer, 2009), or L 1 + L 2 (elastic net). There are two online loss functions: a pairwise (PRO) objective and a listwise minimum expected error objective (Och, 2003). These online loss functions require sentencelevel error metrics, several of which are available in the toolkit: BLEU+1 (Lin and Och, 2004), Nakov BLEU (Nakov et al., 2012), and TER.

Decoding
The Phrasal decoder can be invoked either programmatically as a Java object or as a standalone application. In both cases the decoder is configured via options that specify the language model, phrase table, weight vector w, etc. The decoder is multithreaded, with one decoding instance per thread. Each decoding instance has its own weight vector, so in the programmatic case, it is possible to decode simultaneously under different weight vectors.
Two search procedures are included. The default is the phrase-based variant of cube pruning (Huang and Chiang, 2007). The standard multi-stack beam search (Och and Ney, 2004) is also an option. Either procedure can be configured in one of several recombination modes. The "Pharaoh" mode only considers linear distortion, source coverage, and target LM history. The "Exact" mode considers these states in addition to any feature that declares recombination state (see section 3.3).
The decoder includes several options for deployment environments such as an unknown word API, pre-/post-processing APIs, and both full and prefixbased force decoding.

Evaluation and Post-processing
All of the error metrics available for tuning can also be invoked for evaluation. For significance testing, the toolkit includes an implementation of the permutation test of Riezler and Maxwell (2005), which was shown to be less susceptible to Type-I error than bootstrap re-sampling (Koehn, 2004 Table 1: Phrase-based MT as deductive inference. This notation can be read as follows: if the antecedents on the top are true, then the consequent on the bottom is true subject to the conditions on the right. The new item d is creating by appending r to the ordered sequence of rules that define d. Phrasal also includes two truecasing packages. The LM-based truecaser (Lita et al., 2003) requires an LM estimated from cased, tokenized text. A subsequent detokenization step is thus necessary. A more convenient alternative is the CRF-based postprocessor that can be trained to invert an arbitrary pre-processor. This post-processor can perform truecasing and detokenization in one pass.

Feature API
Phrasal supports dynamic feature extraction during tuning and decoding. In the API, feature templates are called featurizers. There are two types with associated interfaces: RuleFeaturizer and DerivationFeaturizer. One way to illustrate these two featurizers is to consider phrasebased decoding as a deductive system. Let r = f, e be a rule in a set R, which is conventionally called the phrase table. Let d = {r i } N i=1 be an ordered sequence of derivation N rules called a derivation, which specifies a translation for some source input sequence s (which, by some abuse of notation, is equivalent to f in Eq. (1)). Finally, define functions cov(d) as the source coverage set of d as a bit vector and s(·, w) as the score of a rule or derivation under w. 3 The expression r / ∈ cov(d) means that r maps to an empty/uncovered span in cov(d). Table 1 shows the deductive system.

Dynamic Rule Features
RuleFeaturizers are invoked when scoring axioms, which do not require any derivation context. The static rule features described in section 2.2 also contribute to axiom scoring, and differ only from RuleFeaturizers in that they are stored permanently in the phrase table. In contrast, RuleFeaturizers are extracted during decoding. An example feature template is the word penalty, which is simply the dimension of the target side of r (Listing 1).
Featurizable wraps decoder state from which features can be extracted. RuleFeaturizers are extracted during each phrase table query and cached, so they can be simply efficiently retrieved during decoding.
Once the feature is compiled, it is simply specified on the command-line when the decoder is executed. No other configuration is required.

Derivation Features
DerivationFeaturizers are invoked when scoring items, and thus depend on some derivation context. An example is the LM, which requires the n-gram context from d to score r when creating the new hypothesis d (Listing 2).
The LM featurizer first looks up the recombination state of the derivation, which contains the n-gram context. Then it queries the LM by passing the rule and context, and sets the new state as the result of the LM query. Finally, it returns a feature "LM" with the value of the LM query.

Recombination State
Listing 2 shows a state lookup during feature extraction. Phrase-based MT feature design differs significantly from that of convex classifiers in terms of the interaction with inference. For example, in a maximum entropy classifier inference is exact, so a good optimizer can simply nullify bad features to retain baseline accuracy. In contrast, MT feature templates affect search through both future cost heuristics and recombination state. Bad features can introduce search errors and thus decrease The interface requires a state equality operator and a hash code function. Then the search procedure will only recombine derivations with equal states. For example, the state of the n-gram LM DerivationFeaturizer (Listing 2) is the n-1 gram context, and the hashcode is a hash of that context string. Only derivations for which the equality operator of LMState returns true can be recombined.

Web Service
Machine translation output is increasingly utilized in computer-assisted translation (CAT) workbenches. To support deployment, Phrasal includes a lightweight J2EE servlet that exposes a RESTful JSON API for querying a trained system. The toolkit includes a standalone servlet container, but the servlet may also be incorporated into a J2EE server. The servlet requires just one input parameter: the Phrasal configuration file, which is also used for tuning and decoding. Consequently, after running the standard pipeline, the trained system can be deployed with one command.

Standard Web Service
The standard web service supports two types of requests. The first is TranslationRequest, which performs full decoding on a source input. The JSON message structure is: Listing 3: TranslationRequest message. The srcLang and tgtLang fields are ignored by the servlet, but can be used by a middleware proxy to route requests to Phrasal servlet instances, one per language pair. The srcText field is the source input, and properties is a Javascript associative array that can contain key/value pairs to pass to the feature API. For example, we often use the properties field to pass domain information with each request.
The second request type is RuleRequest, which enables phrase table queries. These requests are processed very quickly since decoding is not required. The JSON message structure is: Listing 5: RuleRequest message, which prompts a direct lookup into the phrase table.

Interactive Machine Translation
Interactive machine translation (Bisbey and Kay, 1972) pairs human and machine translators in hopes of increasing the throughput of high quality translation. It is an old idea that is again in focus. One challenge is to present relevant machine suggestions to humans. To that end, Phrasal supports contextsensitive translation queries via prefix decoding. Consider again the TranslationRequest message. When the tgtText field is empty, the source input is decoded from scratch. But when this field contains a prefix, Phrasal returns translations that begin with the prefix. The search procedure force decodes the prefix, and then completes the translation via conventional decoding. Consequently, if the user has typed a partial translation, Phrasal can suggest completions conditioned on that prefix. The longer the prefix, the faster the decoding, since the user prefix constrains the search space. This feature allows Phrasal to produce increasingly precise suggestions as the user works.

Experiments
We compare Phrasal and Moses by restricting an existing large-scale system to a set of common features. We start with the Arabic-English system of , which is built from 6.6M parallel segments. The system includes a 5-gram English LM estimated from the target-side of the bitext and 990M English monolingual tokens. The feature set is their dense baseline, but without lexicalized reordering and the two extended phrase table features. This leaves the nine baseline features also implemented by Moses. We use the same phrase table, phrase table query limit (20), and distortion limit (5) for both decoders. The tuning set (mt023568) contains 5,604 segments, and the development set (mt04) contains 1,075 segments.
We ran all experiments on a dedicated server with 16 physical cores and 128GB of memory. Figure 1 shows single-threaded decoding time of the dev set as a function of the cube pruning pop limit. At very low limits Moses is faster than Phrasal, but then slows sharply. In contrast, Phrasal scales linearly and is thus faster at higher pop limits. Figure 2 shows multi-threaded decoding time of the dev set with the cube pruning pop limit fixed at 1,200. Here Phrasal is initially faster, but Moses becomes more efficient at four threads. There are two possible explanations. First, profiling shows that LM queries account for approximately 75% of the Phrasal CPU-time. KenLM is written in C++, and Phrasal queries it via JNI. It appears as though multi-threading across this boundary is a source of inefficiency. Second, we observe that the Java parallel garbage collector (GC) runs up to seven threads, which become increasingly active as the number of decoder threads increases. These and other Java overhead threads must be scheduled, limiting gains as the number of decoding threads approaches the number of physical cores. Finally, Figure 3 shows tuning BLEU as a function of wallclock time. For Moses we chose the batch MIRA implementation of Cherry and Foster (2012), which is popular for tuning feature-rich systems. Phrasal uses the online tuner with the expected BLEU objective . Moses achieves a maximum BLEU score of 47.63 after 143 minutes of tuning, while Phrasal reaches this level after just 17 minutes, later reaching a maximum BLEU of 47.75 after 42 minutes. Much of the speedup can be attributed to phrase table and LM loading time: the Phrasal tuner loads these data structures just once, while the Moses tuner loads them every epoch. Of course, this loading time becomes more significant with larger-scale systems.

Conclusion
We presented a revised version of Phrasal, an opensource, phrase-based MT toolkit. The revisions support new directions in MT research including feature-rich models, large-scale tuning, and web-


Foundation for Frequent Pattern Mining Algorithms Implementation

As with the development of the IT technologies, the amount of accumulated data is also increasing. Thus the role of data mining comes into picture. Association rule mining becomes one of the significant responsibilities of descriptive technique which can be defined as discovering meaningful patterns from large collection of data. The frequent pattern mining algorithms determine the frequent patterns from a database. Mining frequent itemset is very fundamental part of association rule mining. Many algorithms have been proposed from last many decades including majors are Apriori, Direct Hashing and Pruning, FP-Growth, ECLAT etc. The aim of this study is to analyze the existing techniques for mining frequent patterns and evaluate the performance of them by comparing Apriori and DHP algorithms in terms of candidate generation, database and transaction pruning. This creates a foundation to develop newer algorithm for frequent pattern mining.

I. INTRODUCTION
Automated data collection tools and mature database technology lead to tremendous amounts of data accumulated and/or to be analysed in databases, data warehouses, and other information repositories [7]. We are drowning in data, but starving for knowledge! What is the solution for this problem? I think its Data Mining -Mining interesting knowledge (rules, regularities, patterns, constraints) from data in large databases. Data mining refers to the use of sophisticated data analysis tools to discover previously unknown, valid patterns and relationships in large data sets. [ [1] Frequent Patterns are patterns (such as itemsets) that appear in a data set frequently: A set of items, like milk and bread, that appear frequently together in a transaction dataset is a frequent itemsets. Frequent pattern mining searches for recurring relationships in a given data set. Researcher can focus on frequent patterns mining like Frequent itemsets from the small and/or from the large amount of data, where the data are either transactional or relational [7]. So many applications are there which we can be considered as frequent pattern applications like Supermarket for product placement & special promotions, Websearch for which keywords often occur together in webpages, Health care for frequent sets of symptoms for a disease, Basically works for all data that can be represented as a set of examples/objects having certain properties like patient / symptoms, movies / ratings, web pages / keywords, basket / products etc. Considering Market Basket Analysis we can find that Market basket analysis might tell a retailer that customers often purchase shampoo and conditioner together, so putting both items on promotion ISSN: 2231-2803 http://www.ijcttjournal.org Page 2160 at the same time would not create a significant increase in profit, while a promotion involving just one of the items would likely drive sales of the other. Association rule learning is a popular and well researched method for discovering interesting relations between variables in large databases [6]. It is intended to identify strong rules discovered in databases using different measures of interestingness. Based on the concept of strong rules [2], introduced association rules for discovering regularities between products in large-scale transaction data recorded by point-of-sale (POS) systems in supermarkets. The volume of data is increasing dramatically as the data generated by dayto-day activities. Therefore, mining association rules from massive amount of data in the database is interested for many industries which can help in many business decision making processes, such as cross-marketing, Basket data analysis, and promotion assortment. The problem of association rule mining is defined as: Let I = {i 1 , i 2 ,.....,i n } be a set of n binary attributes called items. Let D = = {t 1 , t 2 ,.....,t m } be a set of transactions called the database. Each transaction in D has a unique transaction ID and contains a subset of the items in I. A rule is defined as an implication of the form X==>Ywhere X, Y I and X ∩ Y = θ. The sets of items (for short itemsets) X and Y are called antecedent (left-hand-side or LHS) and consequent (right-hand-side or RHS) of the rule respectively. To illustrate the concepts, we use a small example from the supermarket domain. The set of items is I = {milk, bread, butter, beer}. An example rule for the supermarket could be {butter, bread} ==> {milk} meaning that if butter and bread are bought, customers also buy milk. In short we summaries association rule as given: Given database of transactions and each transaction is a list of items(purchased by a customer in a visit) then find all rules that correlate the presence of one set of items with that of another set of item. Example 98% of people who purchase tires and auto accessories also get automotive services done [2].

II. FREQUENT PATTERN MINING ALGORITHMS
Hundreds of algorithms have been proposed for sparse/dense data, many rows/columns, data fits/does not fit in memory etc. Among these we can filter out most useful methods which we can categorize them as scalable methods for mining frequent patterns. Scalable mining methods: Four major approaches are: Apriori : Fast Algorithms for Mining Association Rules [2], Direct Hashing and Pruning (DHP) : An Effective Hash-Based Algorithm for Mining Association Rules [3], Frequent pattern growth (FP -Growth) : Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach [4], Vertical data format approach (ECLAT): New Algorithms for Fast Discovery of Association Rules [5] A

. Apriori: A Candidate Generation-and-Test Approach
Apriori is a classic algorithm for frequent itemset mining and association rule learning over transactional databases [2]. It proceeds by identifying the frequent individual items in the database and extending them to larger and larger item sets as long as those item sets appear sufficiently often in the database. The frequent item sets determined by Apriori can be used to determine association rules which highlight general trends in the database: this has applications in domains such as market basket analysis.
Apriori is designed to operate on databases containing transactions (for example, collections of items bought by customers, or details of a website frequentation). Each transaction is seen as a set of items (an itemset). Given a threshold C, the Apriori algorithm identifies the itemsets which are subsets of at least C transactions in the database. Apriori uses a "bottom up" approach, where frequent subsets are extended one item at a time (a step known as candidate generation), and groups of candidates are tested against the data. The algorithm terminates when no further successful extensions are found. Apriori uses breadth-first search and a Hash tree structure to count candidate item sets efficiently [2]. It generates candidate item sets of length k from item sets of length k-1. Then it prunes the candidates which have an infrequent sub pattern. According to the downward closure lemma, the candidate set contains all frequent k-length item sets. After that, it scans the transaction database to determine frequent item sets among the candidates. In short, it finds the frequent itemsets : the sets of items that have minimum support and a subset of a frequent itemset must also be a frequent itemset i.e., if {AB} is a frequent itemset, both {A} and {B} should be a frequent itemset. Also iteratively find frequent itemsets with cardinality from 1 to k (k-itemset) with two step process: Join Step: C k is generated by joining L k-1 with itself and Prune Step: Any (k-1)-itemset that is not frequent cannot be a subset of a frequent k-itemset. Apriori follows the following method: (i) initially, scan DB once to get frequent 1-itemset, (ii) generate length (k+1) candidate itemsets from length k frequent itemsets, (iii) test the candidates against DB and finally (iv) terminate when no frequent or candidate set can be generated. We can note down that any subset of large itemset is large therefore to find large k-itemset: create candidates by combining large k-1 itemsets, delete those that contain any subset that is not large. Example of Generating Candidates Let L 3 ={abc, abd, acd, ace, bcd} the we can have self-joining: L 3 *L 3 abcd from abc and abd , acde from acd and ace. Also we can have pruning: Pruning: acde is removed because ade is not in L 3 and C 4 will be {abcd}. Also Apriori algorithm can be modified to improve its efficiency (computational complexity) by hashing, removal of transactions that do not contain frequent itemsets, sampling of the data, partitioning of the data, and mining frequent itemsets without generation of candidate itemsets.

B. The DHP Algorithm (Direct Hashing and Pruning) -Improvement approach towards Apriori
DHP can be used for efficient large itemset generation. It has two major features: efficient generation for large itemsets and effective reduction on transaction database. It uses hashing technique. In particular, for the large 2-itemsets, where the number of candidate large itemsets generated by DHP is, in orders of magnitude, smaller than that of by Apriori method [3]. Thus improving the performance bottleneck of the whole process. It Uses pruning technique to reduce the size of the database progressively [6].
Hashing is used to reduce the size of the candidate kitemsets, i.e., itemsets that are generated from frequent itemsets from iteration k-1, C k , for k>1. For instance, when scanning D to generate L 1 from the candidate 1-temsets in C 1 , we can at the same time generate all 2-itemsets for each transaction, hash (map) them into different buckets of the hash table structure and increase the corresponding bucket counts [1]. A 2-itemset, which corresponding bucket count is below the support threshold, cannot be frequent and thus we can remove it from the candidate set C 2 . In this way we reduce the number of candidate 2-itemsets that must be examined to obtain L 2. It finds the frequent itemsets : the sets of items that have minimum support -a subset of a frequent itemset must also be a frequent itemset i.e., if {AB} is a frequent itemset, both {A} and {B} should be a frequent itemset. DHP uses the technique due to this which is more powerful than Apriori i.e. Candidate large 2-itemsets are huge -DHP trims them using hashing and transaction database is huge that one scan per iteration is costly -DHP prunes both number of transactions and number of items in each transaction after each iteration [6].

Hash Table Construction
Consider two items sets, all items are numbered as I1, I2, …I n .

How to trim candidate itemsets
In k-iteration, hash all "appearing" k+1 itemsets in a hashtable, count all the occurrences of an itemset in the correspondent bucket. In k+1 iteration, examine each of the candidate itemset to see if its correspondent bucket value is above the support (necessary condition) [3]. Comparison of Apriori and DHP Apriori behaves like -Generate Candidate Set and Perform Count Support from Database. While DHP behaves in a sequence -Generate candidate set, perform count support from the database and make new hash table using database for the next stage.

Effective Database Pruning
Apriori -don't prune database but prune C k by support counting on the original database, while DHP -Its more efficient support counting can be achieved on pruned database [3] III. CONCLUSION Apriori is best for frequent pattern mining approach for newer algorithm development. But after implementation you can find some challenges like multiple scans of transaction database, huge number of candidates, tedious workload of support counting for candidates and we can improve Apriori with effective hash-based algorithm for the candidate itemset generation i.e. a two phase transaction database pruning and much more efficient ( time & space ) than Apriori algorithm. Following implementation statics we can find that for the below example 6-itemsets for C2 & 4-transactions for database in Apriori while 4-itemsets for C2 & only 2transactions for database in DHP.