OpenRaiser/Intern-Atlas huggingface dataset:
A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
Venue: arXiv cs.IT 2014
Year: 2014

The alternating direction method of multipliers (ADMM) has been popular for solving many signal processing problems, convex or nonconvex. In this paper, we study an asynchronous implementation of the ADMM for solving a nonconvex nonsmooth optimization problem, whose objective is the sum of a number of component functions. The proposed algorithm allows the problem to be solved in a distributed, asynchronous and incremental manner. First, the component functions can be distributed to different computing nodes, who perform the updates asynchronously without coordinating with each other. Two sources of asynchrony are covered by our algorithm: one is caused by the heterogeneity of the computational nodes, and the other arises from unreliable communication links. Second, the algorithm can be viewed as implementing an incremental algorithm where at each step the (possibly delayed) gradients of only a subset of component functions are update d. We show that when certain bounds are put on the level of asynchrony, the proposed algorithm converges to the set of stationary solutions (resp. optimal solutions) for the nonconvex (resp. convex) problem. To the best of our knowledge, the proposed ADMM implementation can tolerate the highest degree of asynchrony, among all known asynchronous variants of the ADMM. Moreover, it is the first ADMM implementation that can deal with nonconvexity and asynchrony at the same time.
CITlab ARGUS for Arabic Handwriting
Venue: arXiv cs.CV 2014
Year: 2014

In the recent years it turned out that multidimensional recurrent neural networks (MDRNN) perform very well for offline handwriting recognition tasks like the OpenHaRT 2013 evaluation DIR. With suitable writing preprocessing and dictionary lookup, our ARGUS software completed this task with an error rate of 26.27% in its primary setup.
The Sample Allocation Problem and Non-Uniform Compressive Sampling
Venue: arXiv cs.IT 2014
Year: 2014

This paper discusses sample allocation problem (SAP) in frequency-domain Compressive Sampling (CS) of time-domain signals. An analysis that is relied on two fundamental CS principles; the Uniform Random Sampling (URS) and the Uncertainty Principle (UP), is presented. We show that CS on a single- and multi-band signals performs better if the URS is done only within the band and suppress the out-band parts, compared to ordinary URS that ignore the band limits. It means that sampling should only be done at the signal support, while the non-support should be masked and suppressed in the reconstruction process. We also show that for an N-length discrete time signal with K-number of frequency components (Fourier coefficients), given the knowledge of the spectrum, URS leads to exact sampling on the location of the K-spectral peaks. These results are used to formulate a sampling scheme when the boundaries of the bands are not sharply distinguishable, such as in a triangular- or a stacked-band- spectral signals. When analyzing these cases, CS will face a paradox; in which narrowing the band leads to a more number of required samples, whereas widening it leads to lessen the number. Accordingly; instead of signal analysis by dividing the signal's spectrum vertically into bands of frequencies, slicing horizontally magnitude-wise yields less number of required sample and better reconstruction results. Moreover, it enables sample reuse that reduces the sample number even further. The horizontal slicing and sample reuse methods imply non-uniform random sampling, where larger-magnitude part of the spectrum should be allocated more sample than the lower ones.
Whoo.ly: Facilitating Information Seeking For Hyperlocal Communities Using Social Media
Venue: arXiv cs.HC 2014
Year: 2014

Social media systems promise powerful opportunities for people to connect to timely, relevant information at the hyper local level. Yet, finding the meaningful signal in noisy social media streams can be quite daunting to users. In this paper, we present and evaluate Whoo.ly, a web service that provides neighborhood-specific information based on Twitter posts that were automatically inferred to be hyperlocal. Whoo.ly automatically extracts and summarizes hyperlocal information about events, topics, people, and places from these Twitter posts. We provide an overview of our design goals with Whoo.ly and describe the system including the user interface and our unique event detection and summarization algorithms. We tested the usefulness of the system as a tool for finding neighborhood information through a comprehensive user study. The outcome demonstrated that most participants found Whoo.ly easier to use than Twitter and they would prefer it as a tool for exploring their neighborhoods.
Efficient Decision-Making by Volume-Conserving Physical Object
Venue: arXiv cs.AI 2014
Year: 2014

We demonstrate that any physical object, as long as its volume is conserved when coupled with suitable operations, provides a sophisticated decision-making capability. We consider the problem of finding, as accurately and quickly as possible, the most profitable option from a set of options that gives stochastic rewards. These decisions are made as dictated by a physical object, which is moved in a manner similar to the fluctuations of a rigid body in a tug-of-war game. Our analytical calculations validate statistical reasons why our method exhibits higher efficiency than conventional algorithms.
The Computational Theory of Intelligence: Applications to Genetic Programming and Turing Machines
Venue: arXiv cs.NE 2014
Year: 2014

In this paper, we continue the efforts of the Computational Theory of Intelligence (CTI) by extending concepts to include computational processes in terms of Genetic Algorithms (GA's) and Turing Machines (TM's). Active, Passive, and Hybrid Computational Intelligence processes are also introduced and discussed. We consider the ramifications of the assumptions of CTI with regard to the qualities of reproduction and virility. Applications to Biology, Computer Science and Cyber Security are also discussed.
Automated Objective Surgical Skill Assessment in the Operating Room Using Unstructured Tool Motion
Venue: arXiv cs.CV 2014
Year: 2014

Previous work on surgical skill assessment using intraoperative tool motion in the operating room (OR) has focused on highly-structured surgical tasks such as cholecystectomy. Further, these methods only considered generic motion metrics such as time and number of movements, which are of limited instructive value. In this paper, we developed and evaluated an automated approach to the surgical skill assessment of nasal septoplasty in the OR. The obstructed field of view and highly unstructured nature of septoplasty precludes trainees from efficiently learning the procedure. We propose a descriptive structure of septoplasty consisting of two types of activity: (1) brushing activity directed away from the septum plane characterizing the consistency of the surgeon's wrist motion and (2) activity along the septal plane characterizing the surgeon's coverage pattern. We derived features related to these two activity types that classify a surgeon's level of training with an average accuracy of about 72%. The features we developed provide surgeons with personalized, actionable feedback regarding their tool motion.
An approach for improving the concept of Cyclomatic Complexity for Object-Oriented Programming
Venue: arXiv cs.SE 2014
Year: 2014

Measuring software complexity plays an important role to meet the demands of complex software. The cyclomatic complexity is one of most used and renowned metric among the other three proposed and researched metrics that are namely: Line of code, Halstead measure and cyclomatic complexity. Although cyclomatic complexity is very popular but also serves some of the problems which has been identified and showed in a tabular form in this research work. It lacks the calculation of coupling between the object classes for object oriented programming and only calculates the complexity on the basis of the conditional statements. Thus there is requirement to improve the concept of cyclomatic complexity based on coupling. Paper includes the proposed algorithm to handle the above stated problem.
A characterization of the capacity of online (causal) binary channels
Venue: arXiv cs.IT 2014
Year: 2014

In the binary online (or "causal") channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword $\mathbf{x} =(x_1,\ldots,x_n) \in \{0,1\}^n$ bit by bit via a channel limited to at most $pn$ corruptions. The channel is "online" in the sense that at the $i$th step of communication the channel decides whether to corrupt the $i$th bit or not based on its view so far, i.e., its decision depends only on the transmitted bits $(x_1,\ldots,x_i)$. This is in contrast to the classical adversarial channel in which the error is chosen by a channel that has a full knowledge on the sent codeword $\mathbf{x}$. In this work we study the capacity of binary online channels for two corruption models: the {\em bit-flip} model in which the channel may flip at most $pn$ of the bits of the transmitted codeword, and the {\em erasure} model in which the channel may erase at most $pn$ bits of the transmitted codeword. Specifically, for both error models we give a full characterization of the capacity as a function of $p$. The online channel (in both the bit-flip and erasure case) has seen a number of recent studies which present both upper and lower bounds on its capacity. In this work, we present and analyze a coding scheme that improves on the previously suggested lower bounds and matches the previously suggested upper bounds thus implying a tight characterization.
SPySort: Neuronal Spike Sorting with Python
Venue: arXiv cs.CE 2014
Year: 2014

Extracellular recordings with multi-electrode arrays is one of the basic tools of contemporary neuroscience. These recordings are mostly used to monitor the activities, understood as sequences of emitted action potentials, of many individual neurons. But the raw data produced by extracellular recordings are most commonly a mixture of activities from several neurons. In order to get the activities of the individual contributing neurons, a pre-processing step called spike sorting is required. We present here a pure Python implementation of a well tested spike sorting procedure. The latter was designed in a modular way in order to favour a smooth transition from an interactive sorting, for instance with IPython, to an automatic one. Surprisingly enough - or sadly enough, depending on one's view point -, recoding our now 15 years old procedure into Python was the occasion of major methodological improvements.
Computing solutions of the multiclass network equilibrium problem with affine cost functions
Venue: arXiv cs.GT 2014
Year: 2014

We consider a nonatomic congestion game on a graph, with several classes of players. Each player wants to go from its origin vertex to its destination vertex at the minimum cost and all players of a given class share the same characteristics: cost functions on each arc, and origin-destination pair. Under some mild conditions, it is known that a Nash equilibrium exists, but the computation of an equilibrium in the multiclass case is an open problem for general functions. We consider the specific case where the cost functions are affine. We show that this problem is polynomially solvable when the number of vertices and the number of classes are fixed. In particular, it shows that the parallel-link case with a fixed number of classes is polynomially solvable. On a more practical side, we propose an extension of Lemke's algorithm able to solve this problem.
KF metamodel formalization
Venue: arXiv cs.AI 2014
Year: 2014

The KF metamodel is a comprehensive unifying metamodel covering the static structural entities and constraints of UML Class Diagrams (v2.4.1), ER, EER, ORM, and ORM2, and intended to boost interoperability of common conceptual data modelling languages. It was originally designed in UML with textual constraints, and in this report we present its formalisations in FOL and OWL, which accompanies the paper that describes, discusses, and analyses the KF metamodel in detail. These new formalizations contribute to give a precise meaning to the metamodel, to understand its complexity properties and to provide a basis for future implementations.
Visualizing and Comparing Convolutional Neural Networks
Venue: arXiv cs.CV 2014
Year: 2014

Convolutional Neural Networks (CNNs) have achieved comparable error rates to well-trained human on ILSVRC2014 image classification task. To achieve better performance, the complexity of CNNs is continually increasing with deeper and bigger architectures. Though CNNs achieved promising external classification behavior, understanding of their internal work mechanism is still limited. In this work, we attempt to understand the internal work mechanism of CNNs by probing the internal representations in two comprehensive aspects, i.e., visualizing patches in the representation spaces constructed by different layers, and visualizing visual information kept in each layer. We further compare CNNs with different depths and show the advantages brought by deeper architecture.
Artifact Centric Business Process Management Logging Schema
Venue: arXiv cs.SE 2014
Year: 2014

Understanding the evolution of business artifacts will enable business analyst to discover more insight from process execution data. In this context, describing how the artifacts are wired, helps in understanding, predicting and optimizing the behavior of dynamic processes. In many cases, however, process artifacts evolve over time, as they pass through the business's operations. Consequently, understanding the evolution of artifacts becomes challenging and requires analyzing the provenance of business artifacts. In this paper our aim is to analyze and classify existing challenges in artifact centric business processes. We propose to extend Provenance techniques to artifact centric BPMs in order to perform cross cutting concerns on BPMs. Provenance is pre-requirement of addressing cross cutting concerns, which will provide information regarding artifact instance creation and its evolution during its life cycle. Due to dynamic nature of dynamic processes and declarative structure of Artifact Centric BPM systems, it's vital to make sure how an artifact instance actually executed and evolved during its processing in run time.
Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources
Venue: arXiv cs.CC 2014
Year: 2014

A Santha-Vazirani (SV) source is a sequence of random bits where the conditional distribution of each bit, given the previous bits, can be partially controlled by an adversary. Santha and Vazirani show that deterministic randomness extraction from these sources is impossible. In this paper, we study the generalization of SV sources for non-binary sequences. We show that unlike the binary case, deterministic randomness extraction in the generalized case is sometimes possible. We present a necessary condition and a sufficient condition for the possibility of deterministic randomness extraction. These two conditions coincide in "non-degenerate" cases. Next, we turn to a distributed setting. In this setting the SV source consists of a random sequence of pairs $(a_1, b_1), (a_2, b_2), \ldots$ distributed between two parties, where the first party receives $a_i$'s and the second one receives $b_i$'s. The goal of the two parties is to extract common randomness without communication. Using the notion of maximal correlation, we prove a necessary condition and a sufficient condition for the possibility of common randomness extraction from these sources. Based on these two conditions, the problem of common randomness extraction essentially reduces to the problem of randomness extraction from (non-distributed) SV sources. This result generalizes results of Gács and Körner, and Witsenhausen about common randomness extraction from i.i.d. sources to adversarial sources.
Defeating jamming with the power of silence: a game-theoretic analysis
Venue: arXiv cs.GT 2014
Year: 2014

The timing channel is a logical communication channel in which information is encoded in the timing between events. Recently, the use of the timing channel has been proposed as a countermeasure to reactive jamming attacks performed by an energy-constrained malicious node. In fact, whilst a jammer is able to disrupt the information contained in the attacked packets, timing information cannot be jammed and, therefore, timing channels can be exploited to deliver information to the receiver even on a jammed channel. Since the nodes under attack and the jammer have conflicting interests, their interactions can be modeled by means of game theory. Accordingly, in this paper a game-theoretic model of the interactions between nodes exploiting the timing channel to achieve resilience to jamming attacks and a jammer is derived and analyzed. More specifically, the Nash equilibrium is studied in the terms of existence, uniqueness, and convergence under best response dynamics. Furthermore, the case in which the communication nodes set their strategy and the jammer reacts accordingly is modeled and analyzed as a Stackelberg game, by considering both perfect and imperfect knowledge of the jammer's utility function. Extensive numerical results are presented, showing the impact of network parameters on the system performance.
Polarities & Focussing: a journey from Realisability to Automated Reasoning
Venue: arXiv cs.LO 2014
Year: 2014

This dissertation explores the roles of polarities and focussing in various aspects of Computational Logic. These concepts play a key role in the the interpretation of proofs as programs, a.k.a. the Curry-Howard correspondence, in the context of classical logic. Arising from linear logic, they allow the construction of meaningful semantics for cut-elimination in classical logic, some of which relate to the Call-by-Name and Call-by-Value disciplines of functional programming. The first part of this dissertation provides an introduction to these interpretations, highlighting the roles of polarities and focussing. For instance: proofs of positive formulae provide structured data, while proofs of negative formulae consume such data; focussing allows the description of the interaction between the two kinds of proofs as pure pattern-matching. This idea is pushed further in the second part of this dissertation, and connected to realisability semantics, where the structured data is interpreted algebraically, and the consumption of such data is modelled with the use of an orthogonality relation. Most of this part has been proved in the Coq proof assistant. Polarities and focussing were also introduced with applications to logic programming in mind, where computation is proof-search. In the third part of this dissertation, we push this idea further by exploring the roles that these concepts can play in other applications of proof-search, such as theorem proving and more particularly automated reasoning. We use these concepts to describe the main algorithm of SAT-solvers and SMT-solvers: DPLL. We then describe the implementation of a proof-search engine called Psyche. Its architecture, based on the concept of focussing, offers a platform where smart techniques from automated reasoning (or a user interface) can safely and trustworthily be implemented via the use of an API.
Discrete Conformal Deformation: Algorithm and Experiments
Venue: arXiv cs.CG 2014
Year: 2014

In this paper, we introduce a definition of discrete conformality for triangulated surfaces with flat cone metrics and describe an algorithm for solving the problem of prescribing curvature, that is to deform the metric discrete conformally so that the curvature of the resulting metric coincides with the prescribed curvature. We explicitly construct a discrete conformal map between the input triangulated surface and the deformed triangulated surface. Our algorithm can handle the surface with any topology with or without boundary, and can find a deformed metric for any prescribed curvature satisfying the Gauss-Bonnet formula. In addition, we present the numerical examples to show the convergence of our discrete conformality and to demonstrate the efficiency and the robustness of our algorithm.
Friendship Paradox and Attention Economics
Venue: arXiv cs.SI 2014
Year: 2014

The friendship paradox is revisited by considering both local and global averages of friends. How the economics of attention affects the recruitment of friends is examined. Statistical implications of varying individual attentions are investigated and it is argued that this is one reason why the mean of friends is higher than the median in social networks. The distribution of friends skews to the right for two other reasons: (i) the presence of institutional nodes that increase the mean; and (ii) the dormancy of many of the nodes. The difference between friends and friends of friends is a measure of the structural information about the network.
Bayesian Optimisation for Machine Translation
Venue: arXiv cs.CL 2014
Year: 2014

This paper presents novel Bayesian optimisation algorithms for minimum error rate training of statistical machine translation systems. We explore two classes of algorithms for efficiently exploring the translation space, with the first based on N-best lists and the second based on a hypergraph representation that compactly represents an exponential number of translation options. Our algorithms exhibit faster convergence and are capable of obtaining lower error rates than the existing translation model specific approaches, all within a generic Bayesian optimisation framework. Further more, we also introduce a random embedding algorithm to scale our approach to sparse high dimensional feature sets.
A web-based tool to Analyze Semantic Similarity Networks
Venue: arXiv cs.CE 2014
Year: 2014

In computational biology, biological entities such as genes or proteins are usually annotated with terms extracted from Gene Ontology (GO). The functional similarity among terms of an ontology is evaluated by using Semantic Similarity Measures (SSM). More recently, the extensive application of SSMs yielded to the Semantic Similarity Networks (SSNs). SSNs are edge-weighted graphs where the nodes are concepts (e.g. proteins) and each edge has an associated weight that represents the semantic similarity among related pairs of nodes. The analysis of SSNs may reveal biologically meaningful knowledge. For these aims, the need for the introduction of tool able to manage and analyze SSN arises. Consequently we developed SSN-Analyzer a web based tool able to build and preprocess SSN. As proof of concept we demonstrate that community detection algorithms applied to filtered (thresholded) networks, have better performances in terms of biological relevance of the results, with respect to the use of raw unfiltered networks.