Monte Carlo Random Walk Simulations Based on Distributed Order Differential Equations with Applications to Cell Biology

Mathematics Subject Classification: 65C05, 60G50, 39A10, 92C37

A Random Walk down Main Street

US suburbs have often been characterized by their relatively low walk accessibility compared to more urban environments, and US urban environments have been characterized by low walk accessibility compared to cities in other countries. Lower overall density in the suburbs implies that activities, if spread out, would have a greater distance between them. But why should activities be spread out instead of developed contiguously? This brief research note builds a positive model for the emergence of contiguous development along “Main Street” to illustrate the trade-offs that result in the built environment we observe. It then suggests some policy interventions to place a “thumb on the scale” to choose which parcels will develop in which sequence to achieve socially preferred outcomes.

Testing the random walk hypothesis with variance ratio statistics

Mestrado em Finanças

Random walk with restart over dynamic graphs

Random Walk with Restart (RWR) is an appealing measure of proximity between nodes based on graph structures. Since real graphs are often large and subject to minor changes, it is prohibitively expensive to recompute proximities from scratch. Previous methods use LU decomposition and degree reordering heuristics, entailing O(|V|^3) time and O(|V|^2) memory to compute all (|V|^2) pairs of node proximities in a static graph. In this paper, a dynamic scheme to assess RWR proximities is proposed: (1) For unit update, we characterize the changes to all-pairs proximities as the outer product of two vectors. We notice that the multiplication of an RWR matrix and its transition matrix, unlike traditional matrix multiplications, is commutative. This can greatly reduce the computation of all-pairs proximities from O(|V|^3) to O(|delta|) time for each update without loss of accuracy, where |delta| (<<|V|^2) is the number of affected proximities. (2) To avoid O(|V|^2) memory for all pairs of outputs, we also devise efficient partitioning techniques for our dynamic model, which can compute all pairs of proximities segment-wisely within O(l|V|) memory and O(|V|/l) I/O costs, where 1<=l<=|V| is a user-controlled trade-off between memory and I/O costs. (3) For bulk updates, we also devise aggregation and hashing methods, which can discard many unnecessary updates further and handle chunks of unit updates simultaneously. Our experimental results on various datasets demonstrate that our methods can be 1–2 orders of magnitude faster than other competitors while securing scalability and exactness.

Exponentiated gradient algorithms for conditional random fields and max-margin Markov Networks

Log-linear and maximum-margin models are two commonly-used methods in supervised machine learning, and are frequently used in structured prediction problems. Efficient learning of parameters in these models is therefore an important problem, and becomes a key factor when learning from very large data sets. This paper describes exponentiated gradient (EG) algorithms for training such models, where EG updates are applied to the convex dual of either the log-linear or max-margin objective function; the dual in both the log-linear and max-margin cases corresponds to minimizing a convex function with simplex constraints. We study both batch and online variants of the algorithm, and provide rates of convergence for both cases. In the max-margin case, O(1/ε) EG updates are required to reach a given accuracy ε in the dual; in contrast, for log-linear models only O(log(1/ε)) updates are required. For both the max-margin and log-linear cases, our bounds suggest that the online EG algorithm requires a factor of n less computation to reach a desired accuracy than the batch EG algorithm, where n is the number of training examples. Our experiments confirm that the online algorithms are much faster than the batch algorithms in practice. We describe how the EG updates factor in a convenient way for structured prediction problems, allowing the algorithms to be efficiently applied to problems such as sequence learning or natural language parsing. We perform extensive evaluation of the algorithms, comparing them to L-BFGS and stochastic gradient descent for log-linear models, and to SVM-Struct for max-margin models. The algorithms are applied to a multi-class problem as well as to a more complex large-scale parsing task. In all these settings, the EG algorithms presented here outperform the other methods.

Productivity, Technical and Efficiency Change in Singapore’s Services Sector, 2005 to 2008

The current study was motivated by statements made by the Economic Strategies Committee that Singapore’s recent productivity levels in services were well below countries such as the US, Japan and Hong Kong. Massive employment of foreign workers was cited as the reason for poor productivity levels. To shed more light on Singapore’s falling productivity, a nonparametric Malmquist productivity index was employed which provides measures of productivity change, technical change and efficiency change. The findings reveal that growth in total factor productivity was attributed to technical change with no improvement in efficiency change. Such results suggest that gains from TFP were input-driven rather than from a ‘best-practice’ approach such as improvements in operations or better resource allocation.

Productivity, technical and efficiency change in Singapore’s services sector, 2005 to 2008

The current study was motivated by statements made by the Economic Strategies Committee that Singapore’s recent productivity levels in services were well below countries such as the US, Japan and Hong Kong. Massive employment of foreign workers was cited as the reason for poor productivity levels. To shed more light on Singapore’s falling productivity, a nonparametric Malmquist productivity index was employed which provides measures of productivity change, technical change and efficiency change. The findings reveal that growth in Total Factor Productivity (TFP) was attributed to technical change with no improvement in efficiency change. Such results suggest that gains from TFP were input-driven rather than from a ‘best-practice’ approach such as improvements in operations or better resource allocation.

Modeling random effect and excess zeros in road traffic accident prediction

Poisson distribution has often been used for count like accident data. Negative Binomial (NB) distribution has been adopted in the count data to take care of the over-dispersion problem. However, Poisson and NB distributions are incapable of taking into account some unobserved heterogeneities due to spatial and temporal effects of accident data. To overcome this problem, Random Effect models have been developed. Again another challenge with existing traffic accident prediction models is the distribution of excess zero accident observations in some accident data. Although Zero-Inflated Poisson (ZIP) model is capable of handling the dual-state system in accident data with excess zero observations, it does not accommodate the within-location correlation and between-location correlation heterogeneities which are the basic motivations for the need of the Random Effect models. This paper proposes an effective way of fitting ZIP model with location specific random effects and for model calibration and assessment the Bayesian analysis is recommended.

Identify disorders in health records using Conditional Random Fields and Metamap: AEHRC at ShARe/CLEF 2013 eHealth Evaluation Lab Task 1

The Australian e-Health Research Centre (AEHRC) recently participated in the ShARe/CLEF eHealth Evaluation Lab Task 1. The goal of this task is to individuate mentions of disorders in free-text electronic health records and map disorders to SNOMED CT concepts in the UMLS metathesaurus. This paper details our participation to this ShARe/CLEF task. Our approaches are based on using the clinical natural language processing tool Metamap and Conditional Random Fields (CRF) to individuate mentions of disorders and then to map those to SNOMED CT concepts. Empirical results obtained on the 2013 ShARe/CLEF task highlight that our instance of Metamap (after ltering irrelevant semantic types), although achieving a high level of precision, is only able to identify a small amount of disorders (about 21% to 28%) from free-text health records. On the other hand, the addition of the CRF models allows for a much higher recall (57% to 79%) of disorders from free-text, without sensible detriment in precision. When evaluating the accuracy of the mapping of disorders to SNOMED CT concepts in the UMLS, we observe that the mapping obtained by our ltered instance of Metamap delivers state-of-the-art e ectiveness if only spans individuated by our system are considered (`relaxed' accuracy).

Short signature without random oracles and the SDH assumption in bilinear groups

We describe a short signature scheme that is strongly existentially unforgeable under an adaptive chosen message attack in the standard security model. Our construction works in groups equipped with an efficient bilinear map, or, more generally, an algorithm for the Decision Diffie-Hellman problem. The security of our scheme depends on a new intractability assumption we call Strong Diffie-Hellman (SDH), by analogy to the Strong RSA assumption with which it shares many properties. Signature generation in our system is fast and the resulting signatures are as short as DSA signatures for comparable security. We give a tight reduction proving that our scheme is secure in any group in which the SDH assumption holds, without relying on the random oracle model.

Estimating local stream fish assemblage attributes: Sampling effort and efficiency at two spatial scales

As part of a wider study to develop an ecosystem-health monitoring program for wadeable streams of south-eastern Queensland, Australia, comparisons were made regarding the accuracy, precision and relative efficiency of single-pass backpack electrofishing and multiple-pass electrofishing plus supplementary seine netting to quantify fish assemblage attributes at two spatial scales (within discrete mesohabitat units and within stream reaches consisting of multiple mesohabitat units). The results demonstrate that multiple-pass electrofishing plus seine netting provide more accurate and precise estimates of fish species richness, assemblage composition and species relative abundances in comparison to single-pass electrofishing alone, and that intensive sampling of three mesohabitat units (equivalent to a riffle-run-pool sequence) is a more efficient sampling strategy to estimate reach-scale assemblage attributes than less intensive sampling over larger spatial scales. This intensive sampling protocol was sufficiently sensitive that relatively small differences in assemblage attributes (<20%) could be detected with a high statistical power (1-β > 0.95) and that relatively few stream reaches (<4) need be sampled to accurately estimate assemblage attributes close to the true population means. The merits and potential drawbacks of the intensive sampling strategy are discussed, and it is deemed to be suitable for a range of monitoring and bioassessment objectives.

Waste generations and efficiency measures in Japan

This study measures the efficiencies incorporating waste generation using Japanese prefecture level data. We apply and compare several models using directional distance functions. There are wide variations in the efficiency scores between the two orientations, "input, desirable and undesirable output orientation" and "undesirable output orientation". However, the difference in abatement factor does not result in wide variations in the efficiency scores. Our results show that there are wide differences in the efficiency scores among prefectures. © 2012 Springer.