OpenRaiser/Intern-Atlas huggingface dataset:
A Raindrop Algorithm for Searching The Global Optimal Solution in Non-linear Programming
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we apply the random walk model in designing a raindrop algorithm to find the global optimal solution of a non-linear programming problem. The raindrop algorithm does not require the information of the first or second order derivatives of the object function. Hence it is a direct method. We investigate the properties of raindrop algorithm. Besides, we apply the raindrop algorithm to solve a non-linear optimization problem, where the object function is highly irregular (neither convex nor concave). And the global optimal solution can be found with small number of iterations.
Predicting Risk-of-Readmission for Congestive Heart Failure Patients: A Multi-Layer Approach
Venue: arXiv cs.LG 2013
Year: 2013

Mitigating risk-of-readmission of Congestive Heart Failure (CHF) patients within 30 days of discharge is important because such readmissions are not only expensive but also critical indicator of provider care and quality of treatment. Accurately predicting the risk-of-readmission may allow hospitals to identify high-risk patients and eventually improve quality of care by identifying factors that contribute to such readmissions in many scenarios. In this paper, we investigate the problem of predicting risk-of-readmission as a supervised learning problem, using a multi-layer classification approach. Earlier contributions inadequately attempted to assess a risk value for 30 day readmission by building a direct predictive model as opposed to our approach. We first split the problem into various stages, (a) at risk in general (b) risk within 60 days (c) risk within 30 days, and then build suitable classifiers for each stage, thereby increasing the ability to accurately predict the risk using multiple layers of decision. The advantage of our approach is that we can use different classification models for the subtasks that are more suited for the respective problems. Moreover, each of the subtasks can be solved using different features and training data leading to a highly confident diagnosis or risk compared to a one-shot single layer approach. An experimental evaluation on actual hospital patient record data from Multicare Health Systems shows that our model is significantly better at predicting risk-of-readmission of CHF patients within 30 days after discharge compared to prior attempts.
Feature-Gathering Dependency-Based Software Clustering Using Dedication and Modularity
Venue: arXiv cs.SE 2013
Year: 2013

Software clustering is one of the important techniques to comprehend software systems. However, presented techniques to date require human interactions to refine clustering results. In this paper, we proposed a novel dependency-based software clustering algorithm, SArF. SArF has two characteristics. First, SArF eliminates the need of the omnipresent-module-removing step which requires human interactions. Second, the objective of SArF is to gather relevant software features or functionalities into a cluster. To achieve them, we defined the Dedication score to infer the importance of dependencies and utilized Modularity Maximization to cluster weighted directed graphs. Two case studies and extensive comparative evaluations using open source and industrial systems show that SArF could successfully decompose the systems fitting to the authoritative decompositions from a feature viewpoint without any tailored setups and that SArF was superior to existing dependency-based software clustering studies. Besides, the case studies show that there exist measurable authoritativeness limits and that SArF nearly reached the limits.
Asymptotic Analysis and Random Sampling of Digitally Convex Polyominoes
Venue: arXiv cs.DM 2013
Year: 2013

Recent work of Brlek \textit{et al.} gives a characterization of digitally convex polyominoes using combinatorics on words. From this work, we derive a combinatorial symbolic description of digitally convex polyominoes and use it to analyze their limit properties and build a uniform sampler. Experimentally, our sampler shows a limit shape for large digitally convex polyominoes.
Compressive Time Delay Estimation Using Interpolation
Venue: arXiv cs.IT 2013
Year: 2013

Time delay estimation has long been an active area of research. In this work, we show that compressive sensing with interpolation may be used to achieve good estimation precision while lowering the sampling frequency. We propose an Interpolating Band-Excluded Orthogonal Matching Pursuit algorithm that uses one of two interpolation functions to estimate the time delay parameter. The numerical results show that interpolation improves estimation precision and that compressive sensing provides an elegant tradeoff that may lower the required sampling frequency while still attaining a desired estimation performance.
The Holonomy Decomposition of Circular Semi-Flower Automata
Venue: arXiv cs.FL 2013
Year: 2013

Eilenberg's holonomy decomposition is useful to ascertain the structural properties of automata. Using this method, Egri-Nagy and Nehaniv characterized the absence of certain types of cycles in automata. In the direction of studying the structure of automata with cycles, this work focuses on a special class of semi-flower automata and establish the holonomy decompositions of certain circular semi-flower automata.
The Effect of Biased Communications On Both Trusting and Suspicious Voters
Venue: arXiv cs.AI 2013
Year: 2013

In recent studies of political decision-making, apparently anomalous behavior has been observed on the part of voters, in which negative information about a candidate strengthens, rather than weakens, a prior positive opinion about the candidate. This behavior appears to run counter to rational models of decision making, and it is sometimes interpreted as evidence of non-rational "motivated reasoning". We consider scenarios in which this effect arises in a model of rational decision making which includes the possibility of deceptive information. In particular, we will consider a model in which there are two classes of voters, which we will call trusting voters and suspicious voters, and two types of information sources, which we will call unbiased sources and biased sources. In our model, new data about a candidate can be efficiently incorporated by a trusting voter, and anomalous updates are impossible; however, anomalous updates can be made by suspicious voters, if the information source mistakenly plans for an audience of trusting voters, and if the partisan goals of the information source are known by the suspicious voter to be "opposite" to his own. Our model is based on a formalism introduced by the artificial intelligence community called "multi-agent influence diagrams", which generalize Bayesian networks to settings involving multiple agents with distinct goals.
Stopping Criterion for the Mean Shift Iterative Algorithm
Venue: arXiv cs.CV 2013
Year: 2013

Image segmentation is a critical step in computer vision tasks constituting an essential issue for pattern recognition and visual interpretation. In this paper, we propose a new stopping criterion for the mean shift iterative algorithm by using images defined in Zn ring, with the goal of reaching a better segmentation. We carried out also a study on the weak and strong of equivalence classes between two images. An analysis on the convergence with this new stopping criterion is carried out too.
Quantitative Security Analysis for Multi-threaded Programs
Venue: arXiv cs.CR 2013
Year: 2013

Quantitative theories of information flow give us an approach to relax the absolute confidentiality properties that are difficult to satisfy for many practical programs. The classical information-theoretic approaches for sequential programs, where the program is modeled as a communication channel with only input and output, and the measure of leakage is based on the notions of initial uncertainty and remaining uncertainty after observing the final outcomes, are not suitable to multi-threaded programs. Besides, the information-theoretic approaches have been also shown to conflict with each other when comparing programs. Reasoning about the exposed information flow of multi-threaded programs is more complicated, since the outcomes of such programs depend on the scheduler policy, and the leakages in intermediate states also contribute to the overall leakage of the program. This paper proposes a novel model of quantitative analysis for multi-threaded programs that also takes into account the effect of observables in intermediate states along the trace. We define a notion of the leakage of a program trace. Given the fact that the execution of a multi-threaded program is typically described by a set of traces, the leakage of a program under a specific scheduler is computed as the expected value of the leakages of all possible traces. Examples are given to compare our approach with the existing approaches.
Modal Specifications for Probabilistic Timed Systems
Venue: arXiv cs.LO 2013
Year: 2013

Modal automata are a classic formal model for component-based systems that comes equipped with a rich specification theory supporting abstraction, refinement and compositional reasoning. In recent years, quantitative variants of modal automata were introduced for specifying and reasoning about component-based designs for embedded and mobile systems. These respectively generalize modal specification theories for timed and probabilistic systems. In this paper, we define a modal specification language for combined probabilistic timed systems, called abstract probabilistic timed automata, which generalizes existing formalisms. We introduce appropriate syntactic and semantic refinement notions and discuss consistency of our specification language, also with respect to time-divergence. We identify a subclass of our models for which we define the fundamental operations for abstraction, conjunction and parallel composition, and show several compositionality results.
The Spectrum of Strong Behavioral Equivalences for Nondeterministic and Probabilistic Processes
Venue: arXiv cs.LO 2013
Year: 2013

We present a spectrum of trace-based, testing, and bisimulation equivalences for nondeterministic and probabilistic processes whose activities are all observable. For every equivalence under study, we examine the discriminating power of three variants stemming from three approaches that differ for the way probabilities of events are compared when nondeterministic choices are resolved via deterministic schedulers. We show that the first approach - which compares two resolutions relatively to the probability distributions of all considered events - results in a fragment of the spectrum compatible with the spectrum of behavioral equivalences for fully probabilistic processes. In contrast, the second approach - which compares the probabilities of the events of a resolution with the probabilities of the same events in possibly different resolutions - gives rise to another fragment composed of coarser equivalences that exhibits several analogies with the spectrum of behavioral equivalences for fully nondeterministic processes. Finally, the third approach - which only compares the extremal probabilities of each event stemming from the different resolutions - yields even coarser equivalences that, however, give rise to a hierarchy similar to that stemming from the second approach.
Sparse Representation-based Image Quality Assessment
Venue: arXiv cs.CV 2013
Year: 2013

A successful approach to image quality assessment involves comparing the structural information between a distorted and its reference image. However, extracting structural information that is perceptually important to our visual system is a challenging task. This paper addresses this issue by employing a sparse representation-based approach and proposes a new metric called the \emph{sparse representation-based quality} (SPARQ) \emph{index}. The proposed method learns the inherent structures of the reference image as a set of basis vectors, such that any structure in the image can be represented by a linear combination of only a few of those basis vectors. This sparse strategy is employed because it is known to generate basis vectors that are qualitatively similar to the receptive field of the simple cells present in the mammalian primary visual cortex. The visual quality of the distorted image is estimated by comparing the structures of the reference and the distorted images in terms of the learnt basis vectors resembling cortical cells. Our approach is evaluated on six publicly available subject-rated image quality assessment datasets. The proposed SPARQ index consistently exhibits high correlation with the subjective ratings on all datasets and performs better or at par with the state-of-the-art.
Map Matching with Simplicity Constraints
Venue: arXiv cs.CG 2013
Year: 2013

We study a map matching problem, the task of finding in an embedded graph a path that has low distance to a given curve in R^2. The Fréchet distance is a common measure for this problem. Efficient methods exist to compute the best path according to this measure. However, these methods cannot guarantee that the result is simple (i.e. it does not intersect itself) even if the given curve is simple. In this paper, we prove that it is in fact NP-complete to determine the existence a simple cycle in a planar straight-line embedding of a graph that has at most a given Fréchet distance to a given simple closed curve. We also consider the implications of our proof on some variants of the problem.
Random Drift Particle Swarm Optimization
Venue: arXiv cs.AI 2013
Year: 2013

The random drift particle swarm optimization (RDPSO) algorithm, inspired by the free electron model in metal conductors placed in an external electric field, is presented, systematically analyzed and empirically studied in this paper. The free electron model considers that electrons have both a thermal and a drift motion in a conductor that is placed in an external electric field. The motivation of the RDPSO algorithm is described first, and the velocity equation of the particle is designed by simulating the thermal motion as well as the drift motion of the electrons, both of which lead the electrons to a location with minimum potential energy in the external electric field. Then, a comprehensive analysis of the algorithm is made, in order to provide a deep insight into how the RDPSO algorithm works. It involves a theoretical analysis and the simulation of the stochastic dynamical behavior of a single particle in the RDPSO algorithm. The search behavior of the algorithm itself is also investigated in detail, by analyzing the interaction between the particles. Some variants of the RDPSO algorithm are proposed by incorporating different random velocity components with different neighborhood topologies. Finally, empirical studies on the RDPSO algorithm are performed by using a set of benchmark functions from the CEC2005 benchmark suite. Based on the theoretical analysis of the particle's behavior, two methods of controlling the algorithmic parameters are employed, followed by an experimental analysis on how to select the parameter values, in order to obtain a good overall performance of the RDPSO algorithm and its variants in real-world applications. A further performance comparison between the RDPSO algorithms and other variants of PSO is made to prove the efficiency of the RDPSO algorithms.
Propositional Dynamic Logic with Converse and Repeat for Message-Passing Systems
Venue: arXiv cs.LO 2013
Year: 2013

The model checking problem for propositional dynamic logic (PDL) over message sequence charts (MSCs) and communicating finite state machines (CFMs) asks, given a channel bound $B$, a PDL formula $φ$ and a CFM $\mathcal{C}$, whether every existentially $B$-bounded MSC $M$ accepted by $\mathcal{C}$ satisfies $φ$. Recently, it was shown that this problem is PSPACE-complete. In the present work, we consider CRPDL over MSCs which is PDL equipped with the operators converse and repeat. The former enables one to walk back and forth within an MSC using a single path expression whereas the latter allows to express that a path expression can be repeated infinitely often. To solve the model checking problem for this logic, we define message sequence chart automata (MSCAs) which are multi-way alternating parity automata walking on MSCs. By exploiting a new concept called concatenation states, we are able to inductively construct, for every CRPDL formula $φ$, an MSCA precisely accepting the set of models of $φ$. As a result, we obtain that the model checking problem for CRPDL and CFMs is still in PSPACE.
Enhancing Mobile Data Offloading with Mobility Prediction and Prefetching
Venue: arXiv cs.NI 2013
Year: 2013

We present procedures that exploit mobility prediction and prefetching to enhance offloading of traffic from mobile networks to WiFi hotspots, for both delay tolerant and delay sensitive traffic. We evaluate the procedures in terms of the percentage of offloaded traffic, the data transfer delay, and the cache size used for prefetching. The evaluation considers empirical measurements and shows how various parameters influence the performance of the procedures, and their robustness to time and throughput estimation errors.
Approximate Consensus Multi-Agent Control Under Stochastic Environment with Application to Load Balancing
Venue: arXiv cs.SY 2013
Year: 2013

The paper is devoted to the approximate consensus problem for networks of nonlinear agents with switching topology, noisy and delayed measurements. In contrast to the existing stochastic approximation-based control algorithms (protocols), a local voting protocol with nonvanishing step size is proposed. Nonvanishing (e.g., constant) step size protocols give the opportunity to achieve better convergence rate (by choosing proper step sizes) in coping with time-varying loads and agent states. The price to pay is replacement of the mean square convergence with an approximate one. To analyze dynamics of the closed loop system, the so-called method of averaged models is used. It allows to reduce analysis complexity of the closed loop system. In this paper the upper bounds for mean square distance between the initial system and its approximate averaged model are proposed. The proposed upper bounds are used to obtain conditions for approximate consensus achievement. The method is applied to the load balancing problem in stochastic dynamic networks with incomplete information about the current states of agents and with changing set of communication links. The load balancing problem is formulated as consensus problem in noisy model with switched topology. The conditions to achieve the optimal level of load balancing (in the sense that if no new task arrives, all agents will finish at the same time) are obtained. The performance of the system is evaluated analytically and by simulation. It is shown that the performance of the adaptive multi-agent strategy with the redistribution of tasks among "connected" neighbors is significantly better than the performance without redistribution. The obtained results are important for control of production networks, multiprocessor, sensor or multicomputer networks, etc.
Live-wire 3D medical images segmentation
Venue: arXiv cs.CV 2013
Year: 2013

This report describes the design, implementation, evaluation and original enhancements to the Live-Wire method for 2D and 3D image segmentation. Live-Wire 2D employs a semi-automatic paradigm; the user is asked to select a few boundary points of the object to segment, to steer the process in the right direction, while the result is displayed in real time. In our implementation segmentation is extended to three dimensions by performing this process on a slice-by-slice basis. User's time and involvement is further reduced by allowing him to specify object contours in planes orthogonal to the slices. If these planes are chosen strategically, Live-Wire 3D can perform 2D segmentation in the plane of each slice automatically. This report also proposes two improvements to the original method, path heating and a new graph edge feature function based on variance of path properties along the boundary. We show that these improvements lead up to a 33% reduction in interaction with the user, and improved delineation in presence of strong interfering edges.
A Short Note on Two-Variable Logic with a Linear Order Successor and a Preorder Successor
Venue: arXiv cs.LO 2013
Year: 2013

The finite satisfiability problem of two-variable logic extended by a linear order successor and a preorder successor is shown to be undecidable.
Impact of Gate Assignment on Gate-Holding Departure Control Strategies
Venue: arXiv cs.OH 2013
Year: 2013

Gate holding reduces congestion by reducing the number of aircraft present on the airport surface at any time, while not starving the runway. Because some departing flights are held at gates, there is a possibility that arriving flights cannot access the gates and have to wait until the gates are cleared. This is called a gate conflict. Robust gate assignment is an assignment that minimizes gate conflicts by assigning gates to aircraft to maximize the time gap between two consecutive flights at the same gate; it makes gate assignment robust, but passengers may walk longer to transfer flights. In order to simulate the airport departure process, a queuing model is introduced. The model is calibrated and validated with actual data from New York La Guardia Airport (LGA) and a U.S. hub airport. Then, the model simulates the airport departure process with the current gate assignment and a robust gate assignment to assess the impact of gate assignment on gate-holding departure control. The results show that the robust gate assignment reduces the number of gate conflicts caused by gate holding compared to the current gate assignment. Therefore, robust gate assignment can be combined with gate-holding departure control to improve operations at congested airports with limited gate resources.
Classifying Single-Trial EEG during Motor Imagery with a Small Training Set
Venue: arXiv cs.LG 2013
Year: 2013

Before the operation of a motor imagery based brain-computer interface (BCI) adopting machine learning techniques, a cumbersome training procedure is unavoidable. The development of a practical BCI posed the challenge of classifying single-trial EEG with a small training set. In this letter, we addressed this problem by employing a series of signal processing and machine learning approaches to alleviate overfitting and obtained test accuracy similar to training accuracy on the datasets from BCI Competition III and our own experiments.
Extended to Multi-Tilde-Bar Regular Expressions and Efficient Finite Automata Constructions
Venue: arXiv cs.FL 2013
Year: 2013

Several algorithms have been designed to convert a regular expression into an equivalent finite automaton. One of the most popular constructions, due to Glushkov and to McNaughton and Yamada, is based on the computation of the Null, First, Last and Follow sets (called Glushkov functions) associated with a linearized version of the expression. Recently Mignot considered a family of extended expressions called Extended to multi-tilde-bar Regular Expressions (EmtbREs) and he showed that, under some restrictions, Glushkov functions can be defined for an EmtbRE. In this paper we present an algorithm which efficiently computes the Glushkov functions of an unrestricted EmtbRE. Our approach is based on a recursive definition of the language associated with an EmtbRE which enlightens the fact that the worst case time complexity of the conversion of an EmtbRE into an automaton is related to the worst case time complexity of the computation of the Null function. Finally we show how to extend the ZPC-structure to EmtbREs, which allows us to apply to this family of extended expressions the efficient constructions based on this structure (in particular the construction of the c-continuation automaton, the position automaton, the follow automaton and the equation automaton).