OpenRaiser/Intern-Atlas huggingface dataset:
Reconstruction of gene regulatory network of colon cancer using information theoretic approach
Venue: arXiv cs.CE 2013
Year: 2013

Reconstruction of gene regulatory networks or 'reverse-engineering' is a process of identifying gene interaction networks from experimental microarray gene expression profile through computation techniques. In this paper, we tried to reconstruct cancer-specific gene regulatory network using information theoretic approach - mutual information. The considered microarray data consists of large number of genes with 20 samples - 12 samples from colon cancer patient and 8 from normal cell. The data has been preprocessed and normalized. A t-test statistics has been applied to filter differentially expressed genes. The interaction between filtered genes has been computed using mutual information and ten different networks has been constructed with varying number of interactions ranging from 30 to 500. We performed the topological analysis of the reconstructed network, revealing a large number of interactions in colon cancer. Finally, validation of the inferred results has been done with available biological databases and literature.
Energy Storage System Design for a Power Buffer System to Provide Load Ride-through
Venue: arXiv cs.SY 2013
Year: 2013

The design of a power buffer to mitigate the negative impact of constant power loads on voltage stability as well as enhancing ride-through capability for the loads during upstream voltage disturbances is examined. The power buffer adjusts its front-end converter control so that the buffer-load combination would appear as a constant impedance load to the upstream supply system when depressed voltage occurs. A battery energy-storage back-up source within the buffer is activated to maintain the load power demand. It is shown that the buffer performance is affected by the battery state of discharge and discharge current. Analytical expressions are also derived to relate the buffer-load ride-through capability with the battery state-of-discharge. The most onerous buffer-battery condition under which the load-ride through can be achieved has been identified.
Z-source Inverter Based Grid-interface For Variable-speed Permanent Magnet Wind Turbine Generators
Venue: arXiv cs.SY 2013
Year: 2013

A Z-source inverter based grid-interface for a variable-speed wind turbine connected to a permanent magnet synchronous generator is proposed. A control system is designed to harvest maximum wind energy under varied wind conditions with the use of a permanent magnet synchronous generator, a diode-rectifier and a Z-source inverter. Control systems for speed regulation of the generator and for DC- and AC- sides of the Z-source inverter are implemented. Laboratory experiments are used to verify the efficacy of the proposed approach.
The Fundamental Learning Problem that Genetic Algorithms with Uniform Crossover Solve Efficiently and Repeatedly As Evolution Proceeds
Venue: arXiv cs.NE 2013
Year: 2013

This paper establishes theoretical bonafides for implicit concurrent multivariate effect evaluation--implicit concurrency for short---a broad and versatile computational learning efficiency thought to underlie general-purpose, non-local, noise-tolerant optimization in genetic algorithms with uniform crossover (UGAs). We demonstrate that implicit concurrency is indeed a form of efficient learning by showing that it can be used to obtain close-to-optimal bounds on the time and queries required to approximately correctly solve a constrained version (k=7, η=1/5) of a recognizable computational learning problem: learning parities with noisy membership queries. We argue that a UGA that treats the noisy membership query oracle as a fitness function can be straightforwardly used to approximately correctly learn the essential attributes in O(log^1.585 n) queries and O(n log^1.585 n) time, where n is the total number of attributes. Our proof relies on an accessible symmetry argument and the use of statistical hypothesis testing to reject a global null hypothesis at the 10^-100 level of significance. It is, to the best of our knowledge, the first relatively rigorous identification of efficient computational learning in an evolutionary algorithm on a non-trivial learning problem.
Algebraic Complexity Classes
Venue: arXiv cs.CC 2013
Year: 2013

This survey describes, at an introductory level, the algebraic complexity framework originally proposed by Leslie Valiant in 1979, and some of the insights that have been obtained more recently.
Modified SPLICE and its Extension to Non-Stereo Data for Noise Robust Speech Recognition
Venue: arXiv cs.LG 2013
Year: 2013

In this paper, a modification to the training process of the popular SPLICE algorithm has been proposed for noise robust speech recognition. The modification is based on feature correlations, and enables this stereo-based algorithm to improve the performance in all noise conditions, especially in unseen cases. Further, the modified framework is extended to work for non-stereo datasets where clean and noisy training utterances, but not stereo counterparts, are required. Finally, an MLLR-based computationally efficient run-time noise adaptation method in SPLICE framework has been proposed. The modified SPLICE shows 8.6% absolute improvement over SPLICE in Test C of Aurora-2 database, and 2.93% overall. Non-stereo method shows 10.37% and 6.93% absolute improvements over Aurora-2 and Aurora-4 baseline models respectively. Run-time adaptation shows 9.89% absolute improvement in modified framework as compared to SPLICE for Test C, and 4.96% overall w.r.t. standard MLLR adaptation on HMMs.
Reading the Correct History? Modeling Temporal Intention in Resource Sharing
Venue: arXiv cs.IR 2013
Year: 2013

The web is trapped in the "perpetual now", and when users traverse from page to page, they are seeing the state of the web resource (i.e., the page) as it exists at the time of the click and not necessarily at the time when the link was made. Thus, a temporal discrepancy can arise between the resource at the time the page author created a link to it and the time when a reader follows the link. This is especially important in the context of social media: the ease of sharing links in a tweet or Facebook post allows many people to author web content, but the space constraints combined with poor awareness by authors often prevents sufficient context from being generated to determine the intent of the post. If the links are clicked as soon as they are shared, the temporal distance between sharing and clicking is so small that there is little to no difference in content. However, not all clicks occur immediately, and a delay of days or even hours can result in reading something other than what the author intended. We introduce the concept of a user's temporal intention upon publishing a link in social media. We investigate the features that could be extracted from the post, the linked resource, and the patterns of social dissemination to model this user intention. Finally, we analyze the historical integrity of the shared resources in social media across time. In other words, how much is the knowledge of the author's intent beneficial in maintaining the consistency of the story being told through social posts and in enriching the archived content coverage and depth of vulnerable resources?
A Conceptual Framework for Definition of the Correlation Between Company Size Categories and the Proliferation of Business Information Systems in Hungary
Venue: arXiv cs.CY 2013
Year: 2013

Based on a conceptual model, this paper aims to explore the background of the decision-making process leading to the introduction of business information systems among enterprises in Hungary. Together with presenting the problems arising in the course of the implementation of such systems, their usage patterns are also investigated. A strong correlation is established between the size of an enterprise, the scope of its business activities and the range of the business information systems it applies.
A Safe Screening Rule for Sparse Logistic Regression
Venue: arXiv cs.LG 2013
Year: 2013

The l1-regularized logistic regression (or sparse logistic regression) is a widely used method for simultaneous classification and feature selection. Although many recent efforts have been devoted to its efficient implementation, its application to high dimensional data still poses significant challenges. In this paper, we present a fast and effective sparse logistic regression screening rule (Slores) to identify the 0 components in the solution vector, which may lead to a substantial reduction in the number of features to be entered to the optimization. An appealing feature of Slores is that the data set needs to be scanned only once to run the screening and its computational cost is negligible compared to that of solving the sparse logistic regression problem. Moreover, Slores is independent of solvers for sparse logistic regression, thus Slores can be integrated with any existing solver to improve the efficiency. We have evaluated Slores using high-dimensional data sets from different applications. Extensive experimental results demonstrate that Slores outperforms the existing state-of-the-art screening rules and the efficiency of solving sparse logistic regression is improved by one magnitude in general.
Energy Saving and Survival Routing Protocol for Mobile Ad Hoc Networks
Venue: arXiv cs.NI 2013
Year: 2013

In this paper we propose a method to enhance the life time as well as improve the performance of the mobile ad hoc networks (MANET). Since MANET consists of devices that run on batteries, having limited amount of energy and due to the self-configuring and dynamic change of topology, all operations are performed by the node itself.
A Model of Human Cooperation in Social Dilemmas
Venue: arXiv cs.GT 2013
Year: 2013

Social dilemmas are situations in which collective interests are at odds with private interests: pollution, depletion of natural resources, and intergroup conflicts, are at their core social dilemmas. Because of their multidisciplinarity and their importance, social dilemmas have been studied by economists, biologists, psychologists, sociologists, and political scientists. These studies typically explain tendency to cooperation by dividing people in proself and prosocial types, or appealing to forms of external control or, in iterated social dilemmas, to long-term strategies. But recent experiments have shown that cooperation is possible even in one-shot social dilemmas without forms of external control and the rate of cooperation typically depends on the payoffs. This makes impossible a predictive division between proself and prosocial people and proves that people have attitude to cooperation by nature. The key innovation of this article is in fact to postulate that humans have attitude to cooperation by nature and consequently they do not act a priori as single agents, as assumed by standard economic models, but they forecast how a social dilemma would evolve if they formed coalitions and then they act according to their most optimistic forecast. Formalizing this idea we propose the first predictive model of human cooperation able to organize a number of different experimental findings that are not explained by the standard model. We show also that the model makes satisfactorily accurate quantitative predictions of population average behavior in one-shot social dilemmas.
Ameba-inspired Self-organizing Particle Systems
Venue: arXiv cs.DC 2013
Year: 2013

Particle systems are physical systems of simple computational particles that can bond to neighboring particles and use these bonds to move from one spot to another (non-occupied) spot. These particle systems are supposed to be able to self-organize in order to adapt to a desired shape without any central control. Self-organizing particle systems have many interesting applications like coating objects for monitoring and repair purposes and the formation of nano-scale devices for surgery and molecular-scale electronic structures. While there has been quite a lot of systems work in this area, especially in the context of modular self-reconfigurable robotic systems, only very little theoretical work has been done in this area so far. We attempt to bridge this gap by proposing a model inspired by the behavior of ameba that allows rigorous algorithmic research on self-organizing particle systems.
The Fitness Level Method with Tail Bounds
Venue: arXiv cs.NE 2013
Year: 2013

The fitness-level method, also called the method of f-based partitions, is an intuitive and widely used technique for the running time analysis of randomized search heuristics. It was originally defined to prove upper and lower bounds on the expected running time. Recently, upper tail bounds were added to the technique; however, these tail bounds only apply to running times that are at least twice as large as the expectation. We remove this restriction and supplement the fitness-level method with sharp tail bounds, including lower tails. As an exemplary application, we prove that the running time of randomized local search on OneMax is sharply concentrated around n ln n - 0.1159 n.
On the Complexity of a Matching Problem with Asymmetric Weights
Venue: arXiv cs.CC 2013
Year: 2013

We present complexity results regarding a matching-type problem related to structural controllability of dynamical systems modelled on graphs. Controllability of a dynamical system is the ability to choose certain inputs in order to drive the system from any given state to any desired state; a graph is said to be structurally controllable if it represents the structure of a controllable system. We define the Orientation Control Matching problem (OCM) to be the problem of orienting an undirected graph in a manner that maximizes its structural controllability. A generalized version, the Asymmetric Orientation Control Matching problem (AOCM), allows for asymmetric weights on the possible directions of each edge. These problems are closely related to 2-matchings, disjoint path covers, and disjoint cycle covers. We prove using reductions that OCM is polynomially solvable, while AOCM is much harder; we show that it is NP-complete as well as APX-hard.
Satisfiability of ATL with strategy contexts
Venue: arXiv cs.LO 2013
Year: 2013

Various extensions of the temporal logic ATL have recently been introduced to express rich properties of multi-agent systems. Among these, ATLsc extends ATL with strategy contexts, while Strategy Logic has first-order quantification over strategies. There is a price to pay for the rich expressiveness of these logics: model-checking is non-elementary, and satisfiability is undecidable. We prove in this paper that satisfiability is decidable in several special cases. The most important one is when restricting to turn-based games. We prove that decidability also holds for concurrent games if the number of moves available to the agents is bounded. Finally, we prove that restricting strategy quantification to memoryless strategies brings back undecidability.
Universally Elevating the Phase Transition Performance of Compressed Sensing: Non-Isometric Matrices are Not Necessarily Bad Matrices
Venue: arXiv cs.IT 2013
Year: 2013

In compressed sensing problems, $\ell_1$ minimization or Basis Pursuit was known to have the best provable phase transition performance of recoverable sparsity among polynomial-time algorithms. It is of great theoretical and practical interest to find alternative polynomial-time algorithms which perform better than $\ell_1$ minimization. \cite{Icassp reweighted l_1}, \cite{Isit reweighted l_1}, \cite{XuScaingLaw} and \cite{iterativereweightedjournal} have shown that a two-stage re-weighted $\ell_1$ minimization algorithm can boost the phase transition performance for signals whose nonzero elements follow an amplitude probability density function (pdf) $f(\cdot)$ whose $t$-th derivative $f^{t}(0) \neq 0$ for some integer $t \geq 0$. However, for signals whose nonzero elements are strictly suspended from zero in distribution (for example, constant-modulus, only taking values `$+d$' or `$-d$' for some nonzero real number $d$), no polynomial-time signal recovery algorithms were known to provide better phase transition performance than plain $\ell_1$ minimization, especially for dense sensing matrices. In this paper, we show that a polynomial-time algorithm can universally elevate the phase-transition performance of compressed sensing, compared with $\ell_1$ minimization, even for signals with constant-modulus nonzero elements. Contrary to conventional wisdoms that compressed sensing matrices are desired to be isometric, we show that non-isometric matrices are not necessarily bad sensing matrices. In this paper, we also provide a framework for recovering sparse signals when sensing matrices are not isometric.
RSP-Based Analysis for Sparsest and Least $\ell_1$-Norm Solutions to Underdetermined Linear Systems
Venue: arXiv cs.IT 2013
Year: 2013

Recently, the worse-case analysis, probabilistic analysis and empirical justification have been employed to address the fundamental question: When does $\ell_1$-minimization find the sparsest solution to an underdetermined linear system? In this paper, a deterministic analysis, rooted in the classic linear programming theory, is carried out to further address this question. We first identify a necessary and sufficient condition for the uniqueness of least $\ell_1$-norm solutions to linear systems. From this condition, we deduce that a sparsest solution coincides with the unique least $\ell_1$-norm solution to a linear system if and only if the so-called \emph{range space property} (RSP) holds at this solution. This yields a broad understanding of the relationship between $\ell_0$- and $\ell_1$-minimization problems. Our analysis indicates that the RSP truly lies at the heart of the relationship between these two problems. Through RSP-based analysis, several important questions in this field can be largely addressed. For instance, how to efficiently interpret the gap between the current theory and the actual numerical performance of $\ell_1$-minimization by a deterministic analysis, and if a linear system has multiple sparsest solutions, when does $\ell_1$-minimization guarantee to find one of them? Moreover, new matrix properties (such as the \emph{RSP of order $K$} and the \emph{Weak-RSP of order $K$}) are introduced in this paper, and a new theory for sparse signal recovery based on the RSP of order $K$ is established.
Hyperspectral fluorescence microscopy based on Compressive Sampling
Venue: arXiv cs.IT 2013
Year: 2013

The mathematical theory of compressed sensing (CS) asserts that one can acquire signals from measurements whose rate is much lower than the total bandwidth. Whereas the CS theory is now well developed, challenges concerning hardware implementations of CS-based acquisition devices-especially in optics-have only started being addressed. This paper presents an implementation of compressive sensing in fluorescence microscopy and its applications to biomedical imaging. Our CS microscope combines a dynamic structured wide-field illumination and a fast and sensitive single-point fluorescence detection to enable reconstructions of images of fluorescent beads, cells, and tissues with undersampling ratios (between the number of pixels and number of measurements) up to 32. We further demonstrate a hyperspectral mode and record images with 128 spectral channels and undersampling ratios up to 64, illustrating the potential benefits of CS acquisition for higher-dimensional signals, which typically exhibits extreme redundancy. Altogether, our results emphasize the interest of CS schemes for acquisition at a significantly reduced rate and point to some remaining challenges for CS fluorescence microscopy.
Compilation for QCSP
Venue: arXiv cs.PL 2013
Year: 2013

We propose in this article a framework for compilation of quantified constraint satisfaction problems (QCSP). We establish the semantics of this formalism by an interpretation to a QCSP. We specify an algorithm to compile a QCSP embedded into a search algorithm and based on the inductive semantics of QCSP. We introduce an optimality property and demonstrate the optimality of the interpretation of the compiled QCSP.
An application of Khovanov homology to quantum codes
Venue: arXiv cs.IT 2013
Year: 2013

We use Khovanov homology to define families of LDPC quantum error-correcting codes: unknot codes with asymptotical parameters [[3^(2l+1)/sqrt(8πl);1;2^l]]; unlink codes with asymptotical parameters [[sqrt(2/2πl)6^l;2^l;2^l]] and (2,l)-torus link codes with asymptotical parameters [[n;1;d_n]] where d_n>\sqrt(n)/1.62.
DASH: Dynamic Approach for Switching Heuristics
Venue: arXiv cs.AI 2013
Year: 2013

Complete tree search is a highly effective method for tackling MIP problems, and over the years, a plethora of branching heuristics have been introduced to further refine the technique for varying problems. Recently, portfolio algorithms have taken the process a step further, trying to predict the best heuristic for each instance at hand. However, the motivation behind algorithm selection can be taken further still, and used to dynamically choose the most appropriate algorithm for each encountered subproblem. In this paper we identify a feature space that captures both the evolution of the problem in the branching tree and the similarity among subproblems of instances from the same MIP models. We show how to exploit these features to decide the best time to switch the branching heuristic and then show how such a system can be trained efficiently. Experiments on a highly heterogeneous collection of MIP instances show significant gains over the pure algorithm selection approach that for a given instance uses only a single heuristic throughout the search.
Says who? Automatic Text-Based Content Analysis of Television News
Venue: arXiv cs.CL 2013
Year: 2013

We perform an automatic analysis of television news programs, based on the closed captions that accompany them. Specifically, we collect all the news broadcasted in over 140 television channels in the US during a period of six months. We start by segmenting, processing, and annotating the closed captions automatically. Next, we focus on the analysis of their linguistic style and on mentions of people using NLP methods. We present a series of key insights about news providers, people in the news, and we discuss the biases that can be uncovered by automatic means. These insights are contrasted by looking at the data from multiple points of view, including qualitative assessment.
Video Text Localization using Wavelet and Shearlet Transforms
Venue: arXiv cs.CV 2013
Year: 2013

Text in video is useful and important in indexing and retrieving the video documents efficiently and accurately. In this paper, we present a new method of text detection using a combined dictionary consisting of wavelets and a recently introduced transform called shearlets. Wavelets provide optimally sparse expansion for point-like structures and shearlets provide optimally sparse expansions for curve-like structures. By combining these two features we have computed a high frequency sub-band to brighten the text part. Then K-means clustering is used for obtaining text pixels from the Standard Deviation (SD) of combined coefficient of wavelets and shearlets as well as the union of wavelets and shearlets features. Text parts are obtained by grouping neighboring regions based on geometric properties of the classified output frame of unsupervised K-means classification. The proposed method tested on a standard as well as newly collected database shows to be superior to some existing methods.