OpenRaiser/Intern-Atlas huggingface dataset:
Are we far from correctly inferring gene interaction networks with Lasso?
Venue: arXiv cs.CE 2015
Year: 2015

Detecting the interactions of genetic compounds like genes, SNPs, proteins, metabolites, etc. can potentially unravel the mechanisms behind complex traits and common genetic disorders. Several methods have been taken into consideration for the analysis of different types of genetic data, regression being one of the most widely adopted. Without any doubt, a common data type is represented by gene expression profiles, from which gene regulatory networks have been inferred with different approaches. In this work we review nine penalised regression methods applied to microarray data to infer the topology of the network of interactions. We evaluate each method with respect to the complexity of biological data. We analyse the limitations of each of them in order to suggest a number of precautions that should be considered to make their predictions more significant and reliable.
Scalability and Dimensioning of Network-Capacity Measurement System using Reflecting Servers
Venue: arXiv cs.NI 2015
Year: 2015

In a class of methods for measurement of available path capacity and other capacity-related metrics in a network, trains of probe packets are transmitted from a sender to a receiver across a network path, and the sequences of time stamps at sending and reception are analyzed. In large-scale implementations there may potentially be interference between the probe-packet trains corresponding to several concurrent measurement sessions, due to congestion in the network and common measurement end points. This paper outlines principles for large-scale deployments of network capacity measurement methods using standardized network functionality. Further, the paper provides an in-depth study of dimensioning and scalability challenges related to the measurement end-points of such systems. The main result is a framework for dimensioning of large-scale network capacity measurement systems based on TWAMP. The framework is based on a method for explicit calculation of queuelength and waiting-time distributions, where results from M/G/1 queuing theory are combined with Monte Carlo integration.
The Minimum Spanning Tree of Maximum Entropy
Venue: arXiv cs.CV 2015
Year: 2015

In computer vision, we have the problem of creating graphs out of unstructured point-sets, i.e. the data graph. A common approach for this problem consists of building a triangulation which might not always lead to the best solution. Small changes in the location of the points might generate graphs with unstable configurations and the topology of the graph could change significantly. After building the data-graph, one could apply Graph Matching techniques to register the original point-sets. In this paper, we propose a data graph technique based on the Minimum Spanning Tree of Maximum Entropty (MSTME). We aim at a data graph construction which could be more stable than the Delaunay triangulation with respect to small variations in the neighborhood of points. Our technique aims at creating data graphs which could help the point-set registration process. We propose an algorithm with a single free parameter that weighs the importance between the total weight cost and the entropy of the current spanning tree. We compare our algorithm on a number of different databases with the Delaunay triangulation.
Parameter-free Topology Inference and Sparsification for Data on Manifolds
Venue: arXiv cs.CG 2015
Year: 2015

In topology inference from data, current approaches face two major problems. One concerns the selection of a correct parameter to build an appropriate complex on top of the data points; the other involves with the typical `large' size of this complex. We address these two issues in the context of inferring homology from sample points of a smooth manifold of known dimension sitting in an Euclidean space $\mathbb{R}^k$. We show that, for a sample size of $n$ points, we can identify a set of $O(n^2)$ points (as opposed to $O(n^{\lceil \frac{k}{2}\rceil})$ Voronoi vertices) approximating a subset of the medial axis that suffices to compute a distance sandwiched between the well known local feature size and the local weak feature size (in fact, the approximating set can be further reduced in size to $O(n)$). This distance, called the lean feature size, helps pruning the input set at least to the level of local feature size while making the data locally uniform. The local uniformity in turn helps in building a complex for homology inference on top of the sparsified data without requiring any user-supplied distance threshold. Unlike most topology inference results, ours does not require that the input is dense relative to a {\em global} feature such as {\em reach} or {\em weak feature size}; instead it can be adaptive with respect to the local feature size. We present some empirical evidence in support of our theoretical claims.
Lossless Layout Image Compression Algorithms for Electron-Beam Direct-Write Lithography
Venue: arXiv cs.OH 2015
Year: 2015

Electron-beam direct-write (EBDW) lithography systems must in the future transmit terabits of information per second to be viable for commercial semiconductor manufacturing. Lossless layout image compression algorithms with high decoding throughputs and modest decoding resources are tools to address the data transfer portion of the throughput problem. The earlier lossless layout image compression algorithm Corner2 is designed for binary layout images on raster-scanning systems. We propose variations of Corner2 collectively called Corner2-EPC and Paeth-EPC which apply to electron-beam proximity corrected layout images and offer interesting trade-offs between compression ratios and decoding speeds. Most of our algorithms achieve better overall compression performance than PNG, Block C4 and LineDiffEntropy while having low decoding times and resources.
New Explicit Binary Constant Weight Codes from Reed-Solomon Codes
Venue: arXiv cs.IT 2015
Year: 2015

Binary constant weight codes have important applications and have been studied for many years. Optimal or near-optimal binary constant weight codes of small lengths have been determined. In this paper we propose a new construction of explicit binary constant weight codes from $q$-ary Reed-Solomon codes. Some of our binary constant weight codes are optimal or new. In particular new binary constant weight codes $A(64, 10, 8) \geq 4108$ and $A(64, 12, 8) \geq 522$ are constructed. We also give explicitly constructed binary constant weight codes which improve Gilbert and Graham-Sloane lower bounds in some range of parameters. An extension to algebraic geometric codes is also presented.
Colors $-$Messengers of Concepts: Visual Design Mining for Learning Color Semantics
Venue: arXiv cs.HC 2015
Year: 2015

This paper studies the concept of color semantics by modeling a dataset of magazine cover designs, evaluating the model via crowdsourcing, and demonstrating several prototypes that facilitate color-related design tasks. We investigate a probabilistic generative modeling framework that expresses semantic concepts as a combination of color and word distributions $-$color-word topics. We adopt an extension to Latent Dirichlet Allocation (LDA) topic modeling called LDA-dual to infer a set of color-word topics over a corpus of 2,654 magazine covers spanning 71 distinct titles and 12 genres. While LDA models text documents as distributions over word topics, we model magazine covers as distributions over color-word topics. The results of our crowdsourced experiments confirm that the model is able to successfully discover the associations between colors and linguistic concepts. Finally, we demonstrate several simple prototypes that apply the learned model to color palette recommendation, design example retrieval, image retrieval, image color selection, and image recoloring.
Model Checking Parameterized Asynchronous Shared-Memory Systems
Venue: arXiv cs.DC 2015
Year: 2015

We characterize the complexity of liveness verification for parameterized systems consisting of a leader process and arbitrarily many anonymous and identical contributor processes. Processes communicate through a shared, bounded-value register. While each operation on the register is atomic, there is no synchronization primitive to execute a sequence of operations atomically. We analyze the case in which processes are modeled by finite-state machines or pushdown machines and the property is given by a Büchi automaton over the alphabet of read and write actions of the leader. We show that the problem is decidable, and has a surprisingly low complexity: it is NP-complete when all processes are finite-state machines, and is PSPACE-hard and in NEXPTIME when they are pushdown machines. This complexity is lower than for the non-parameterized case: liveness verification of finitely many finite-state machines is PSPACE-complete, and undecidable for two pushdown machines. For finite-state machines, our proofs characterize infinite behaviors using existential abstraction and semilinear constraints. For pushdown machines, we show how contributor computations of high stack height can be simulated by computations of many contributors, each with low stack height. Together, our results characterize the complexity of verification for parameterized systems under the assumptions of anonymity and asynchrony.
Partial Gathering of Mobile Agents in Asynchronous Rings
Venue: arXiv cs.DC 2015
Year: 2015

In this paper, we consider the partial gathering problem of mobile agents in asynchronous unidirectional rings equipped with whiteboards on nodes. The partial gathering problem is a new generalization of the total gathering problem. The partial gathering problem requires, for a given integer $g$, that each agent should move to a node and terminate so that at least $g$ agents should meet at the same node. The requirement for the partial gathering problem is weaker than that for the (well-investigated) total gathering problem, and thus, we have interests in clarifying the difference on the move complexity between them. We propose three algorithms to solve the partial gathering problem. The first algorithm is deterministic but requires unique ID of each agent. This algorithm achieves the partial gathering in $O(gn)$ total moves, where $n$ is the number of nodes. The second algorithm is randomized and requires no unique ID of each agent (i.e., anonymous). This algorithm achieves the partial gathering in expected $O(gn)$ total moves. The third algorithm is deterministic and requires no unique ID of each agent. For this case, we show that there exist initial configurations in which no algorithm can solve the problem and agents can achieve the partial gathering in $O(kn)$ total moves for solvable initial configurations, where $k$ is the number of agents. Note that the total gathering problem requires $Ω(kn)$ total moves, while the partial gathering problem requires $Ω(gn)$ total moves in each model. Hence, we show that the move complexity of the first and second algorithms is asymptotically optimal.
Recognition Confidence Analysis of Handwritten Chinese Character with CNN
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we present an effective method to analyze the recognition confidence of handwritten Chinese character, based on the softmax regression score of a high performance convolutional neural networks (CNN). Through careful and thorough statistics of 827,685 testing samples that randomly selected from total 8836 different classes of Chinese characters, we find that the confidence measurement based on CNN is an useful metric to know how reliable the recognition results are. Furthermore, we find by experiments that the recognition confidence can be used to find out similar and confusable character-pairs, to check wrongly or cursively written samples, and even to discover and correct mis-labelled samples. Many interesting observations and statistics are given and analyzed in this study.
Continuous voting by approval and participation
Venue: arXiv cs.CY 2015
Year: 2015

In finding the adequate way to prioritize proposals, the Brazilian participation community agreed about the measurement of two indexes, one of approval and one of participation. Both practice and literature is constantly handled by the experts involved, and the formalization of such model and metrics seems novel. Also, the relevance of this report is strengthened by the nearby use of these indexes by the Brazilian General Secretariat of the Republic to raise and prioritize proposals about public health care in open processes.
Agile Governance Theory: conceptual development
Venue: arXiv cs.SE 2015
Year: 2015

Context: Competitiveness is the key to a sustainable development and it demands agility at the business and organizational levels, which in turn requires a flexible and customizable IT environment and effective and responsive governance in order to deliver value to the business. Objective: This paper describes the conceptual development of a theory for analyze and describe agile governance in order to increasing the success rate of their practice, achieving organizational performance and business competitiveness. Method: We adopt a multi-method research, framing the theory conceptual development using Dubin's method of theory building. Results: We have developed a conceptual framework of the theory encompassing its constructs, laws of interaction, boundaries and system states. Conclusion: This theory can provide a better understanding of the nature of agile governance, by mapping of its constructs, mediators, moderators and disturbing factors, in order to help organizations reach better results.
Geographic Partitioning Techniques for the Anonymization of Health Care Data
Venue: arXiv cs.CY 2015
Year: 2015

Hospitals and health care organizations collect large amounts of detailed health care data that is in high demand by researchers. Thus, the possessors of such data are in need of methods that allow for this data to be released without compromising the confidentiality of the individuals to whom it pertains. As the geographic aspect of this data is becoming increasingly relevant for research being conducted, it is important for an \emph{anonymization} process to pay due attention to the geographic attributes of such data. In this paper, a novel system for health care data anonymization is presented. At the core of the system is the aggregation of an initial regionalization guided by the use of a Voronoi diagram. We conduct a comparison with another geographic-based system of anonymization, GeoLeader. We show that our system is capable of producing results of a comparable quality with a much faster running time.
Accelerating Very Deep Convolutional Networks for Classification and Detection
Venue: arXiv cs.CV 2015
Year: 2015

This paper aims to accelerate the test-time computation of convolutional neural networks (CNNs), especially very deep CNNs that have substantially impacted the computer vision community. Unlike previous methods that are designed for approximating linear filters or linear responses, our method takes the nonlinear units into account. We develop an effective solution to the resulting nonlinear optimization problem without the need of stochastic gradient descent (SGD). More importantly, while previous methods mainly focus on optimizing one or two layers, our nonlinear method enables an asymmetric reconstruction that reduces the rapidly accumulated error when multiple (e.g., >=10) layers are approximated. For the widely used very deep VGG-16 model, our method achieves a whole-model speedup of 4x with merely a 0.3% increase of top-5 error in ImageNet classification. Our 4x accelerated VGG-16 model also shows a graceful accuracy degradation for object detection when plugged into the Fast R-CNN detector.
Boosting-like Deep Learning For Pedestrian Detection
Venue: arXiv cs.CV 2015
Year: 2015

This paper proposes boosting-like deep learning (BDL) framework for pedestrian detection. Due to overtraining on the limited training samples, overfitting is a major problem of deep learning. We incorporate a boosting-like technique into deep learning to weigh the training samples, and thus prevent overtraining in the iterative process. We theoretically give the details of derivation of our algorithm, and report the experimental results on open data sets showing that BDL achieves a better stable performance than the state-of-the-arts. Our approach achieves 15.85% and 3.81% reduction in the average miss rate compared with ACF and JointDeep on the largest Caltech benchmark dataset, respectively.
On the Reachability of Networked Systems
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we study networks of discrete-time linear time-invariant subsystems. Our focus is on situations where subsystems are connected to each other through a time-invariant topology and where there exists a base-station whose aim is to control the subsystems into any desired destinations. However, the base-station can only communicate with some of the subsystems that we refer to as leaders. There are no direct links between the base-station and the rest of subsystems, known as followers, as they are only able to liaise among themselves and with some of the leaders. The current paper formulates this framework as the well-known reachability problem for linear systems. Then to address this problem, we introduce notions of leader-reachability and base-reachability. We present algebraic conditions under which these notions hold. It turns out that if subsystems are represented by minimal state space representations, then base-reachability always holds. Hence, we focus on leader-reachability and investigate the corresponding conditions in detail. We further demonstrate that when the networked system parameters i.e. subsystems' parameters and interconnection matrices, assume generic values then the whole network is both leader-reachable and base-reachable.
Computationally efficient MIMO system identification using Signal Matched Synthesis Filter Bank
Venue: arXiv cs.IT 2015
Year: 2015

We propose a multi input multi output(MIMO) system identification framework by interpreting the MIMO system in terms of a multirate synthesis filter bank. The proposed methodology is discussed in two steps: in the first step the MIMO system is interpreted as a synthesis filter bank and the second step is to convert the MIMO system into a SISO system "without any loss of information", which re-structures the system identification problem into a SISO form. The system identification problem, in its new form, is identical to the problem of obtaining the signal matched synthesis filter bank (SMSFB) as proposed in Part II. Since we have developed fast algorithms to obtain the filter bank coefficients in Part II, for "the given data case" as well as "the given statistics case", we can use these algorithm for the MIMO system identification as well. This framework can have an adaptive as well as block processing implementation. The algorithms, used here, involve only scalar computations, unlike the conventional MIMO system identification algorithms where one requires matrix computations. These order recursive algorithm can also be used to obtain approximate smaller order model for large order systems without using any model order reduction algorithm. The proposed identification framework can also be used for SISO LPTV system identification and also for a SIMO or MISO system. The efficacy of the proposed scheme is validated and its performance in the presence of measurement noise is illustrated using simulation results.
Centrally Banked Cryptocurrencies
Venue: arXiv cs.CR 2015
Year: 2015

Current cryptocurrencies, starting with Bitcoin, build a decentralized blockchain-based transaction ledger, maintained through proofs-of-work that also generate a monetary supply. Such decentralization has benefits, such as independence from national political control, but also significant limitations in terms of scalability and computational cost. We introduce RSCoin, a cryptocurrency framework in which central banks maintain complete control over the monetary supply, but rely on a distributed set of authorities, or mintettes, to prevent double-spending. While monetary policy is centralized, RSCoin still provides strong transparency and auditability guarantees. We demonstrate, both theoretically and experimentally, the benefits of a modest degree of centralization, such as the elimination of wasteful hashing and a scalable system for avoiding double-spending attacks.
Presenting Finite Posets
Venue: arXiv cs.LO 2015
Year: 2015

We introduce a monoidal category whose morphisms are finite partial orders, with chosen minimal and maximal elements as source and target respectively. After recalling the notion of presentation of a monoidal category by the means of generators and relations, we construct a presentation of our category, which corresponds to a variant of the notion of bialgebra.
Needed Computations Shortcutting Needed Steps
Venue: arXiv cs.PL 2015
Year: 2015

We define a compilation scheme for a constructor-based, strongly-sequential, graph rewriting system which shortcuts some needed steps. The object code is another constructor-based graph rewriting system. This system is normalizing for the original system when using an innermost strategy. Consequently, the object code can be easily implemented by eager functions in a variety of programming languages. We modify this object code in a way that avoids total or partial construction of the contracta of some needed steps of a computation. When computing normal forms in this way, both memory consumption and execution time are reduced compared to ordinary rewriting computations in the original system.
Getting Close Without Touching: Near-Gathering for Autonomous Mobile Robots
Venue: arXiv cs.DC 2015
Year: 2015

In this paper we study the Near-Gathering problem for a finite set of dimensionless, deterministic, asynchronous, anonymous, oblivious and autonomous mobile robots with limited visibility moving in the Euclidean plane in Look-Compute-Move (LCM) cycles. In this problem, the robots have to get close enough to each other, so that every robot can see all the others, without touching (i.e., colliding with) any other robot. The importance of solving the Near-Gathering problem is that it makes it possible to overcome the restriction of having robots with limited visibility. Hence it allows to exploit all the studies (the majority, actually) done on this topic in the unlimited visibility setting. Indeed, after the robots get close enough to each other, they are able to see all the robots in the system, a scenario that is similar to the one where the robots have unlimited visibility. We present the first (deterministic) algorithm for the Near-Gathering problem, to the best of our knowledge, which allows a set of autonomous mobile robots to nearly gather within finite time without ever colliding. Our algorithm assumes some reasonable conditions on the input configuration (the Near-Gathering problem is easily seen to be unsolvable in general). Further, all the robots are assumed to have a compass (hence they agree on the "North" direction), but they do not necessarily have the same handedness (hence they may disagree on the clockwise direction). We also show how the robots can detect termination, i.e., detect when the Near-Gathering problem has been solved. This is crucial when the robots have to perform a generic task after having nearly gathered. We show that termination detection can be obtained even if the total number of robots is unknown to the robots themselves (i.e., it is not a parameter of the algorithm), and robots have no way to explicitly communicate.