OpenRaiser/Intern-Atlas huggingface dataset:
Finite Element Procedures for Enzyme, Chemical Reaction and 'In-Silico' Genome Scale Networks
Venue: arXiv cs.CE 2015
Year: 2015

The capacity to predict and control bioprocesses is perhaps one of the most important objectives of biotechnology. Computational simulation is an established methodology for the design and optimization of bioprocesses, where the finite elements method (FEM) is at the state-of-art engineering multi-physics simulation system, with tools such as Finite Element Analysis (FEA) and Computational Fluid Dynamics (CFD). Although FEA and CFD are currently applied to bioreactor design, most simulations are restricted to the multi-physics capabilities of the existing sofware packages. This manuscript is a contribution for the consolidation of FEM in computational biotechnology, by presenting a comprehensive review of finite element procedures of the most common enzymatic mechanisms found in biotechnological processes, such as, enzyme activation, Michaelis Menten, competitive inhibition, non-competitive inhibition, anti-competitive inhibition, competition by substrate, sequential random mechanism, ping-pong bi-bi and Theorel-Chance. Most importantly, the manuscript opens the possibility for the use of FEM in conjunction with «in-silico» models of metabolic networks, as well as, chemical networks in order to simulate complex bioprocesses in biotechnology, putting emphasis into flux balance analysis, pheno-metabolomics space exploration in time and space, overcoming the limitations of assuming chemostat conditions in systems biology computations.
Hyperorthogonal well-folded Hilbert curves
Venue: arXiv cs.CG 2015
Year: 2015

R-trees can be used to store and query sets of point data in two or more dimensions. An easy way to construct and maintain R-trees for two-dimensional points, due to Kamel and Faloutsos, is to keep the points in the order in which they appear along the Hilbert curve. The R-tree will then store bounding boxes of points along contiguous sections of the curve, and the efficiency of the R-tree depends on the size of the bounding boxes---smaller is better. Since there are many different ways to generalize the Hilbert curve to higher dimensions, this raises the question which generalization results in the smallest bounding boxes. Familiar methods, such as the one by Butz, can result in curve sections whose bounding boxes are a factor $Ω(2^{d/2})$ larger than the volume traversed by that section of the curve. Most of the volume bounded by such bounding boxes would not contain any data points. In this paper we present a new way of generalizing Hilbert's curve to higher dimensions, which results in much tighter bounding boxes: they have at most 4 times the volume of the part of the curve covered, independent of the number of dimensions. Moreover, we prove that a factor 4 is asymptotically optimal.
Web Search Result Clustering based on Heuristic Search and k-means
Venue: arXiv cs.IR 2015
Year: 2015

Giving user a simple and well organized web search result has been a topic of active information Retrieval (IR) research. Irrespective of how small or ambiguous a query is, a user always wants the desired result on the first display of an IR system. Clustering of an IR system result can render a way, which fulfills the actual information need of a user. In this paper, an approach to cluster an IR system result is presented.The approach is a combination of heuristics and k-means technique using cosine similarity. Our heuristic approach detects the initial value of k for creating initial centroids. This eliminates the problem of external specification of the value k, which may lead to unwanted result if wrongly specified. The centroids created in this way are more specific and meaningful in the context of web search result. Another advantage of the proposed method is the removal of the objective means function of k-means which makes cluster sizes same. The end result of the proposed approach consists of different clusters of documents having different sizes.
Experimental Demonstration of Nonlinear Frequency Division Multiplexed Transmission
Venue: arXiv cs.IT 2015
Year: 2015

We experimentally demonstrate an NFDM optical system with modulation over nonlinear discrete spectrum. Particularly, each symbol carries 4-bits from multiplexing two eigenvalues modulated by QPSK constellation. We show a low error performance using NFT detection with 4Gbps rate over 640km.
Efficient Path Interpolation and Speed Profile Computation for Nonholonomic Mobile Robots
Venue: arXiv cs.RO 2015
Year: 2015

This paper studies path synthesis for nonholonomic mobile robots moving in two-dimensional space. We first address the problem of interpolating paths expressed as sequences of straight line segments, such as those produced by some planning algorithms, into smooth curves that can be followed without stopping. Our solution has the advantage of being simpler than other existing approaches, and has a low computational cost that allows a real-time implementation. It produces discretized paths on which curvature and variation of curvature are bounded at all points, and preserves obstacle clearance. Then, we consider the problem of computing a time-optimal speed profile for such paths. We introduce an algorithm that solves this problem in linear time, and that is able to take into account a broader class of physical constraints than other solutions. Our contributions have been implemented and evaluated in the framework of the Eurobot contest.
Intrinsic Properties of Complete Test Suites
Venue: arXiv cs.SE 2015
Year: 2015

Completeness is a desirable property of test suites. Roughly, completeness guarantees that a non-equivalent implementation under test will always be identified. Several approaches proposed sufficient, and sometimes also necessary, conditions on the specification model and on the test suite in order to guarantee completeness. Usually, these approaches impose several restrictions on the specification and on the implementations, such as requiring them to be reduced or complete. Further, test cases are required to be non-blocking --- that is, they must run to completion --- on both the specification and the implementation models. In this work we deal test cases that can be blocking, we define a new notion that captures completeness, and we characterize test suite completeness in this new scenario. We establish an upper bound on the number of states of implementations beyond which no test suite can be complete, both in the classical sense and in the new scenario with blocking test cases.
Editing to a Planar Graph of Given Degrees
Venue: arXiv cs.DS 2015
Year: 2015

We consider the following graph modification problem. Let the input consist of a graph $G=(V,E)$, a weight function $w\colon V\cup E\rightarrow \mathbb{N}$, a cost function $c\colon V\cup E\rightarrow \mathbb{N}$ and a degree function $δ\colon V\rightarrow \mathbb{N}_0$, together with three integers $k_v, k_e$ and $C$. The question is whether we can delete a set of vertices of total weight at most $k_v$ and a set of edges of total weight at most $k_e$ so that the total cost of the deleted elements is at most $C$ and every non-deleted vertex $v$ has degree $δ(v)$ in the resulting graph $G'$. We also consider the variant in which $G'$ must be connected. Both problems are known to be NP-complete and W[1]-hard when parameterized by $k_v+k_e$. We prove that, when restricted to planar graphs, they stay NP-complete but have polynomial kernels when parameterized by $k_v+k_e$.
Benchmarking of LSTM Networks
Venue: arXiv cs.NE 2015
Year: 2015

LSTM (Long Short-Term Memory) recurrent neural networks have been highly successful in a number of application areas. This technical report describes the use of the MNIST and UW3 databases for benchmarking LSTM networks and explores the effect of different architectural and hyperparameter choices on performance. Significant findings include: (1) LSTM performance depends smoothly on learning rates, (2) batching and momentum has no significant effect on performance, (3) softmax training outperforms least square training, (4) peephole units are not useful, (5) the standard non-linearities (tanh and sigmoid) perform best, (6) bidirectional training combined with CTC performs better than other methods.
On the Convergence of SGD Training of Neural Networks
Venue: arXiv cs.NE 2015
Year: 2015

Neural networks are usually trained by some form of stochastic gradient descent (SGD)). A number of strategies are in common use intended to improve SGD optimization, such as learning rate schedules, momentum, and batching. These are motivated by ideas about the occurrence of local minima at different scales, valleys, and other phenomena in the objective function. Empirical results presented here suggest that these phenomena are not significant factors in SGD optimization of MLP-related objective functions, and that the behavior of stochastic gradient descent in these problems is better described as the simultaneous convergence at different rates of many, largely non-interacting subproblems
Possible Mechanisms for Neural Reconfigurability and their Implications
Venue: arXiv cs.NE 2015
Year: 2015

The paper introduces a biologically and evolutionarily plausible neural architecture that allows a single group of neurons, or an entire cortical pathway, to be dynamically reconfigured to perform multiple, potentially very different computations. The paper shows that reconfigurability can account for the observed stochastic and distributed coding behavior of neurons and provides a parsimonious explanation for timing phenomena in psychophysical experiments. It also shows that reconfigurable pathways correspond to classes of statistical classifiers that include decision lists, decision trees, and hierarchical Bayesian methods. Implications for the interpretation of neurophysiological and psychophysical results are discussed, and future experiments for testing the reconfigurability hypothesis are explored.
Analysis on Cache-enabled Wireless Heterogeneous Networks
Venue: arXiv cs.IT 2015
Year: 2015

Caching the popular multimedia content is a promising way to unleash the ultimate potential of wireless networks. In this paper, we contribute to proposing and analyzing the cache-based content delivery in a three-tier heterogeneous network (HetNet), where base stations (BSs), relays and device-to-device (D2D) pairs are included. We advocate to proactively cache the popular contents in the relays and parts of the users with caching ability when the network is off-peak. The cached contents can be reused for frequent access to offload the cellular network traffic. The node locations are first modeled as mutually independent Poisson Point Processes (PPPs) and the corresponding content access protocol is developed. The average ergodic rate and outage probability in the downlink are then analyzed theoretically. We further derive the throughput and the delay based on the \emph{multiclass processor-sharing queue} model and the continuous-time Markov process. According to the critical condition of the steady state in the HetNet, the maximum traffic load and the global throughput gain are investigated. Moreover, impacts of some key network characteristics, e.g., the heterogeneity of multimedia contents, node densities and the limited caching capacities, on the system performance are elaborated to provide a valuable insight.
Learning to Hire Teams
Venue: arXiv cs.HC 2015
Year: 2015

Crowdsourcing and human computation has been employed in increasingly sophisticated projects that require the solution of a heterogeneous set of tasks. We explore the challenge of building or hiring an effective team, for performing tasks required for such projects on an ongoing basis, from an available pool of applicants or workers who have bid for the tasks. The recruiter needs to learn workers' skills and expertise by performing online tests and interviews, and would like to minimize the amount of budget or time spent in this process before committing to hiring the team. How can one optimally spend budget to learn the expertise of workers as part of recruiting a team? How can one exploit the similarities among tasks as well as underlying social ties or commonalities among the workers for faster learning? We tackle these decision-theoretic challenges by casting them as an instance of online learning for best action selection. We present algorithms with PAC bounds on the required budget to hire a near-optimal team with high confidence. Furthermore, we consider an embedding of the tasks and workers in an underlying graph that may arise from task similarities or social ties, and that can provide additional side-observations for faster learning. We then quantify the improvement in the bounds that we can achieve depending on the characteristic properties of this graph structure. We evaluate our methodology on simulated problem instances as well as on real-world crowdsourcing data collected from the oDesk platform. Our methodology and results present an interesting direction of research to tackle the challenges faced by a recruiter for contract-based crowdsourcing.
Ellipses and Lambda Definability
Venue: arXiv cs.LO 2015
Year: 2015

Ellipses are a meta-linguistic notation for denoting terms the size of which are specified by a meta-variable that ranges over the natural numbers. In this work, we present a systematic approach for encoding such meta-expressions in the Î-calculus, without ellipses: Terms that are parameterized by meta-variables are replaced with corresponding Î-abstractions over actual variables. We call such Î-terms arity-generic. Concrete terms, for particular choices of the parameterizing variable are obtained by applying an arity-generic Î-term to the corresponding numeral, obviating the need to use ellipses. For example, to find the multiple fixed points of n equations, n different Î-terms are needed, every one of which is indexed by two meta-variables, and defined using three levels of ellipses. A single arity-generic Î-abstraction that takes two Church numerals, one for the number of fixed-point equations, and one for their arity, replaces all these multiple fixed-point combinators. We show how to define arity-generic generalizations of two historical fixed-point combinators, the first by Curry, and the second by Turing, for defining multiple fixed points. These historical fixed-point combinators are related by a construction due to BÃhm: We show that likewise, their arity-generic generalizations are related by an arity-generic generalization of BÃhm's construction. We further demonstrate this approach to arity-generic Î-definability with additional Î-terms that create, project, extend, reverse, and map over ordered n-tuples, as well as an arity-generic generator for one-point bases.
A Hausdorff dimension for finite sets
Venue: arXiv cs.DM 2015
Year: 2015

The classical Hausdorff dimension of finite or countable sets is zero. We define an analog for finite sets, called finite Hausdorff dimension which is non-trivial. It turns out that a finite bound for the finite Hausdorff dimension guarantees that every point of the set has "nearby" neighbors. This property is important for many computer algorithms of great practical value, that obtain solutions by finding nearest neighbors. We also define an analog for finite sets of the classical box-counting dimension, and compute examples. The main result of the paper is a Convergence Theorem. It gives conditions under which, if a sequence of finite sets converges to a compact set (convergence of compact subsets of Euclidean space under the Hausdorff metric), then the finite Hausdorff dimension of the finite sets will converge to the classical Hausdorff dimension of the compact set.
WearWrite: Orchestrating the Crowd to Complete Complex Tasks from Wearables (We Wrote This Paper on a Watch)
Venue: arXiv cs.HC 2015
Year: 2015

In this paper we introduce a paradigm for completing complex tasks from wearable devices by leveraging crowdsourcing, and demonstrate its validity for academic writing. We explore this paradigm using a collaborative authoring system, called WearWrite, which is designed to enable authors and crowd workers to work together using an Android smartwatch and Google Docs to produce academic papers, including this one. WearWrite allows expert authors who do not have access to large devices to contribute bits of expertise and big picture direction from their watch, while freeing them of the obligation of integrating their contributions into the overall document. Crowd workers on desktop computers actually write the document. We used this approach to write several simple papers, and found it was effective at producing reasonable drafts. However, the workers often needed more structure and the authors more context. WearWrite addresses these issues by focusing workers on specific tasks and providing select context to authors on the watch. We demonstrate the system's feasibility by writing this paper using it.
From Cutting Planes Algorithms to Compression Schemes and Active Learning
Venue: arXiv cs.LG 2015
Year: 2015

Cutting-plane methods are well-studied localization(and optimization) algorithms. We show that they provide a natural framework to perform machinelearning ---and not just to solve optimization problems posed by machinelearning--- in addition to their intended optimization use. In particular, theyallow one to learn sparse classifiers and provide good compression schemes.Moreover, we show that very little effort is required to turn them intoeffective active learning methods. This last property provides a generic way todesign a whole family of active learning algorithms from existing passivemethods. We present numerical simulations testifying of the relevance ofcutting-plane methods for passive and active learning tasks.
Matching-based Spectrum Allocation in Cognitive Radio Networks
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, a novel spectrum association approach for cognitive radio networks (CRNs) is proposed. Based on a measure of both inference and confidence as well as on a measure of quality-of-service, the association between secondary users (SUs) in the network and frequency bands licensed to primary users (PUs) is investigated. The problem is formulated as a matching game between SUs and PUs. In this game, SUs employ a soft-decision Bayesian framework to detect PUs' signals and, eventually, rank them based on the logarithm of the a posteriori ratio. A performance measure that captures both the ranking metric and rate is further computed by the SUs. Using this performance measure, a PU evaluates its own utility function that it uses to build its own association preferences. A distributed algorithm that allows both SUs and PUs to interact and self-organize into a stable match is proposed. Simulation results show that the proposed algorithm can improve the sum of SUs' rates by up to 20 % and 60 % relative to the deferred acceptance algorithm and random channel allocation approach, respectively. The results also show an improved convergence time.
The Strange Case of Privacy in Equilibrium Models
Venue: arXiv cs.GT 2015
Year: 2015

We study how privacy technologies affect user and advertiser behavior in a simple economic model of targeted advertising. In our model, a consumer first decides whether or not to buy a good, and then an advertiser chooses an advertisement to show the consumer. The consumer's value for the good is correlated with her type, which determines which ad the advertiser would prefer to show to her---and hence, the advertiser would like to use information about the consumer's purchase decision to target the ad that he shows. In our model, the advertiser is given only a differentially private signal about the consumer's behavior---which can range from no signal at all to a perfect signal, as we vary the differential privacy parameter. This allows us to study equilibrium behavior as a function of the level of privacy provided to the consumer. We show that this behavior can be highly counter-intuitive, and that the effect of adding privacy in equilibrium can be completely different from what we would expect if we ignored equilibrium incentives. Specifically, we show that increasing the level of privacy can actually increase the amount of information about the consumer's type contained in the signal the advertiser receives, lead to decreased utility for the consumer, and increased profit for the advertiser, and that generally these quantities can be non-monotonic and even discontinuous in the privacy level of the signal.
Generation of Multimedia Artifacts: An Extractive Summarization-based Approach
Venue: arXiv cs.AI 2015
Year: 2015

We explore methods for content selection and address the issue of coherence in the context of the generation of multimedia artifacts. We use audio and video to present two case studies: generation of film tributes, and lecture-driven science talks. For content selection, we use centrality-based and diversity-based summarization, along with topic analysis. To establish coherence, we use the emotional content of music, for film tributes, and ensure topic similarity between lectures and documentaries, for science talks. Composition techniques for the production of multimedia artifacts are addressed as a means of organizing content, in order to improve coherence. We discuss our results considering the above aspects.
Scheduling Chained Multiprocessor Tasks onto Large Multiprocessor System
Venue: arXiv cs.DC 2015
Year: 2015

In this paper, we proposed an effective approach for scheduling of multiprocessor unit time tasks with chain precedence on to large multiprocessor system. The proposed longest chain maximum processor scheduling algorithm is proved to be optimal for uniform chains and monotone (non-increasing/non-decreasing) chains for both splitable and non-splitable multiprocessor unit time tasks chain. Scheduling arbitrary chains of non-splitable multiprocessor unit time tasks is proved to be NP-complete problem. But scheduling arbitrary chains of splitable multiprocessor unit time tasks is still an open problem to be proved whether it is NP-complete or can be solved in polynomial time. We have used three heuristics (a) maximum criticality first, (b) longest chain maximum criticality first and (c) longest chain maximum processor first for scheduling of arbitrary chains. Also compared performance of all three scheduling heuristics and found out that the proposed longest chain maximum processor first performs better in most of the cases.
Information-theoretic Bounds on Matrix Completion under Union of Subspaces Model
Venue: arXiv cs.IT 2015
Year: 2015

In this short note we extend some of the recent results on matrix completion under the assumption that the columns of the matrix can be grouped (clustered) into subspaces (not necessarily disjoint or independent). This model deviates from the typical assumption prevalent in the literature dealing with compression and recovery for big-data applications. The results have a direct bearing on the problem of subspace clustering under missing or incomplete information.