OpenRaiser/Intern-Atlas huggingface dataset:
Discovery Radiomics for Pathologically-Proven Computed Tomography Lung Cancer Prediction
Venue: arXiv cs.CV 2017
Year: 2017

Lung cancer is the leading cause for cancer related deaths. As such, there is an urgent need for a streamlined process that can allow radiologists to provide diagnosis with greater efficiency and accuracy. A powerful tool to do this is radiomics: a high-dimension imaging feature set. In this study, we take the idea of radiomics one step further by introducing the concept of discovery radiomics for lung cancer prediction using CT imaging data. In this study, we realize these custom radiomic sequencers as deep convolutional sequencers using a deep convolutional neural network learning architecture. To illustrate the prognostic power and effectiveness of the radiomic sequences produced by the discovered sequencer, we perform cancer prediction between malignant and benign lesions from 97 patients using the pathologically-proven diagnostic data from the LIDC-IDRI dataset. Using the clinically provided pathologically-proven data as ground truth, the proposed framework provided an average accuracy of 77.52% via 10-fold cross-validation with a sensitivity of 79.06% and specificity of 76.11%, surpassing the state-of-the art method.
Rectilinear Convex Hull with minimum area
Venue: arXiv cs.CG 2017
Year: 2017

Let $P$ be a planar set of $n$ points in general position. We consider the problem of computing an orientation of the plane for which the Rectilinear Convex Hull of $P$ has minimum area. Bae et al. (Computational Geometry: Theory and Applications, Vol. 42, 2009) solved the problem in quadratic time and linear space. We describe an algorithm that reduces this time complexity to $Θ(n \log n)$.
Recurrent Neural Network Based Modeling of Gene Regulatory Network Using Bat Algorithm
Venue: arXiv cs.AI 2017
Year: 2017

Correct inference of genetic regulations inside a cell is one of the greatest challenges in post genomic era for the biologist and researchers. Several intelligent techniques and models were already proposed to identify the regulatory relations among genes from the biological database like time series microarray data. Recurrent Neural Network (RNN) is one of the most popular and simple approach to model the dynamics as well as to infer correct dependencies among genes. In this paper, Bat Algorithm (BA) is applied to optimize the model parameters of RNN model of Gene Regulatory Network (GRN). Initially the proposed method is tested against small artificial network without any noise and the efficiency is observed in term of number of iteration, number of population and BA optimization parameters. The model is also validated in presence of different level of random noise for the small artificial network and that proved its ability to infer the correct inferences in presence of noise like real world dataset. In the next phase of this research, BA based RNN is applied to real world benchmark time series microarray dataset of E. coli. The results prove that it can able to identify the maximum number of true positive regulation but also include some false positive regulations. Therefore, BA is very suitable for identifying biological plausible GRN with the help RNN model.
Array Layouts for Comparison-Based Searching
Venue: arXiv cs.DS 2017
Year: 2017

We attempt to determine the best order and search algorithm to store $n$ comparable data items in an array, $A$, of length $n$ so that we can, for any query value, $x$, quickly find the smallest value in $A$ that is greater than or equal to $x$. In particular, we consider the important case where there are many such queries to the same array, $A$, which resides entirely in RAM. In addition to the obvious sorted order/binary search combination we consider the Eytzinger (BFS) layout normally used for heaps, an implicit B-tree layout that generalizes the Eytzinger layout, and the van Emde Boas layout commonly used in the cache-oblivious algorithms literature. After extensive testing and tuning on a wide variety of modern hardware, we arrive at the conclusion that, for small values of $n$, sorted order, combined with a good implementation of binary search is best. For larger values of $n$, we arrive at the surprising conclusion that the Eytzinger layout is usually the fastest. The latter conclusion is unexpected and goes counter to earlier experimental work by Brodal, Fagerberg, and Jacob (SODA~2003), who concluded that both the B-tree and van Emde Boas layouts were faster than the Eytzinger layout for large values of $n$. Our fastest C++ implementations, when compiled, use conditional moves to avoid branch mispredictions and prefetching to reduce cache latency.
Fast Gaussian Process Regression for Big Data
Venue: arXiv cs.LG 2017
Year: 2017

Gaussian Processes are widely used for regression tasks. A known limitation in the application of Gaussian Processes to regression tasks is that the computation of the solution requires performing a matrix inversion. The solution also requires the storage of a large matrix in memory. These factors restrict the application of Gaussian Process regression to small and moderate size data sets. We present an algorithm that combines estimates from models developed using subsets of the data obtained in a manner similar to the bootstrap. The sample size is a critical parameter for this algorithm. Guidelines for reasonable choices of algorithm parameters, based on detailed experimental study, are provided. Various techniques have been proposed to scale Gaussian Processes to large scale regression tasks. The most appropriate choice depends on the problem context. The proposed method is most appropriate for problems where an additive model works well and the response depends on a small number of features. The minimax rate of convergence for such problems is attractive and we can build effective models with a small subset of the data. The Stochastic Variational Gaussian Process and the Sparse Gaussian Process are also appropriate choices for such problems. These methods pick a subset of data based on theoretical considerations. The proposed algorithm uses bagging and random sampling. Results from experiments conducted as part of this study indicate that the algorithm presented in this work can be as effective as these methods. Model stacking can be used to combine the model developed with the proposed method with models from other methods for large scale regression such as Gradient Boosted Trees. This can yield performance gains.
TransG : A Generative Mixture Model for Knowledge Graph Embedding
Venue: arXiv cs.CL 2017
Year: 2017

Recently, knowledge graph embedding, which projects symbolic entities and relations into continuous vector space, has become a new, hot topic in artificial intelligence. This paper addresses a new issue of multiple relation semantics that a relation may have multiple meanings revealed by the entity pairs associated with the corresponding triples, and proposes a novel Gaussian mixture model for embedding, TransG. The new model can discover latent semantics for a relation and leverage a mixture of relation component vectors for embedding a fact triple. To the best of our knowledge, this is the first generative model for knowledge graph embedding, which is able to deal with multiple relation semantics. Extensive experiments show that the proposed model achieves substantial improvements against the state-of-the-art baselines.
Syntactic complexity of regular ideals
Venue: arXiv cs.FL 2017
Year: 2017

The state complexity of a regular language is the number of states in a minimal deterministic finite automaton accepting the language. The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of regular languages is the worst-case syntactic complexity taken as a function of the state complexity $n$ of languages in that class. We prove that $n^{n-1}$, $n^{n-1}+n-1$, and $n^{n-2}+(n-2)2^{n-2}+1$ are tight upper bounds on the syntactic complexities of right ideals and prefix-closed languages, left ideals and suffix-closed languages, and two-sided ideals and factor-closed languages, respectively. Moreover, we show that the transition semigroups meeting the upper bounds for all three types of ideals are unique, and the numbers of generators (4, 5, and 6, respectively) cannot be reduced.
On 3D Face Reconstruction via Cascaded Regression in Shape Space
Venue: arXiv cs.CV 2017
Year: 2017

Cascaded regression has been recently applied to reconstructing 3D faces from single 2D images directly in shape space, and achieved state-of-the-art performance. This paper investigates thoroughly such cascaded regression based 3D face reconstruction approaches from four perspectives that are not well studied yet: (i) The impact of the number of 2D landmarks; (ii) the impact of the number of 3D vertices; (iii) the way of using standalone automated landmark detection methods; and (iv) the convergence property. To answer these questions, a simplified cascaded regression based 3D face reconstruction method is devised, which can be integrated with standalone automated landmark detection methods and reconstruct 3D face shapes that have the same pose and expression as the input face images, rather than normalized pose and expression. Moreover, an effective training method is proposed by disturbing the automatically detected landmarks. Comprehensive evaluation experiments have been done with comparison to other 3D face reconstruction methods. The results not only deepen the understanding of cascaded regression based 3D face reconstruction approaches, but also prove the effectiveness of proposed method.
On Turnpike and Dissipativity Properties of Continuous-Time Optimal Control Problems
Venue: arXiv cs.SY 2017
Year: 2017

This paper investigates the relations between three different properties, which are of importance in optimal control problems: dissipativity of the underlying dynamics with respect to a specific supply rate, optimal operation at steady state, and the turnpike property. We show in a continuous-time setting that if along optimal trajectories a strict dissipation inequality is satisfied, then this implies optimal operation at this steady state and the existence of a turnpike at the same steady state. Finally, we establish novel converse turnpike results, i.e., we show that the existence of a turnpike at a steady state implies optimal operation at this steady state and dissipativity with respect to this steady state. We draw upon a numerical example to illustrate our findings.
Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations
Venue: arXiv cs.DM 2017
Year: 2017

Given a set $Π$ of permutation patterns of length at most $k$, we present an algorithm for building $S_{\le n}(Π)$, the set of permutations of length at most $n$ avoiding the patterns in $Π$, in time $O(|S_{\le n - 1}(Π)| \cdot k + |S_{n}(Π)|)$. Additionally, we present an $O(n!k)$-time algorithm for counting the number of copies of patterns from $Π$ in each permutation in $S_n$. Surprisingly, when $|Π| = 1$, this runtime can be improved to $O(n!)$, spending only constant time per permutation. Whereas the previous best algorithms, based on generate-and-check, take exponential time per permutation analyzed, all of our algorithms take time at most polynomial per outputted permutation. If we want to solve only the enumerative variant of each problem, computing $|S_{\le n}(Π)|$ or tallying permutations according to $Π$-patterns, rather than to store information about every permutation, then all of our algorithms can be implemented in $O(n^{k+1}k)$ space. Using our algorithms, we generated $|S_5(Π)|, \ldots, |S_{16}(Π)|$ for each $Π\subseteq S_4$ with $|Π| > 4$, and analyzed OEIS matches. We obtained a number of potentially novel pattern-avoidance conjectures. Our algorithms extend to considering permutations in any set closed under standardization of subsequences. Our algorithms also partially adapt to considering vincular patterns.
On the Min-cost Traveling Salesman Problem with Drone
Venue: arXiv cs.AI 2017
Year: 2017

Over the past few years, unmanned aerial vehicles (UAV), also known as drones, have been adopted as part of a new logistic method in the commercial sector called "last-mile delivery". In this novel approach, they are deployed alongside trucks to deliver goods to customers to improve the quality of service and reduce the transportation cost. This approach gives rise to a new variant of the traveling salesman problem (TSP), called TSP with drone (TSP-D). A variant of this problem that aims to minimize the time at which truck and drone finish the service (or, in other words, to maximize the quality of service) was studied in the work of Murray and Chu (2015). In contrast, this paper considers a new variant of TSP-D in which the objective is to minimize operational costs including total transportation cost and one created by waste time a vehicle has to wait for the other. The problem is first formulated mathematically. Then, two algorithms are proposed for the solution. The first algorithm (TSP-LS) was adapted from the approach proposed by Murray and Chu (2015), in which an optimal TSP solution is converted to a feasible TSP-D solution by local searches. The second algorithm, a Greedy Randomized Adaptive Search Procedure (GRASP), is based on a new split procedure that optimally splits any TSP tour into a TSP-D solution. After a TSP-D solution has been generated, it is then improved through local search operators. Numerical results obtained on various instances of both objective functions with different sizes and characteristics are presented. The results show that GRASP outperforms TSP-LS in terms of solution quality under an acceptable running time.
Model-independent comparison of simulation output
Venue: arXiv cs.OH 2017
Year: 2017

Computational models of complex systems are usually elaborate and sensitive to implementation details, characteristics which often affect their verification and validation. Model replication is a possible solution to this issue. It avoids biases associated with the language or toolkit used to develop the original model, not only promoting its verification and validation, but also fostering the credibility of the underlying conceptual model. However, different model implementations must be compared to assess their equivalence. The problem is, given two or more implementations of a stochastic model, how to prove that they display similar behavior? In this paper, we present a model comparison technique, which uses principal component analysis to convert simulation output into a set of linearly uncorrelated statistical measures, analyzable in a consistent, model-independent fashion. It is appropriate for ascertaining distributional equivalence of a model replication with its original implementation. Besides model-independence, this technique has three other desirable properties: a) it automatically selects output features that best explain implementation differences; b) it does not depend on the distributional properties of simulation output; and, c) it simplifies the modelers' work, as it can be used directly on simulation outputs. The proposed technique is shown to produce similar results to the manual or empirical selection of output features when applied to a well-studied reference model.
Distributed Decode-Forward for Relay Networks
Venue: arXiv cs.IT 2017
Year: 2017

A new coding scheme for general N-node relay networks is presented for unicast, multicast, and broadcast. The proposed distributed decode-forward scheme combines and generalizes Marton coding for single-hop broadcast channels and the Cover-El Gamal partial decode-forward coding scheme for 3-node relay channels. The key idea of the scheme is to precode all the codewords of the entire network at the source by multicoding over multiple blocks. This encoding step allows these codewords to carry partial information of the messages implicitly without complicated rate splitting and routing. This partial information is then recovered at the relay nodes and forwarded further. For N-node Gaussian unicast, multicast, and broadcast relay networks, the scheme achieves within 0.5N bits from the cutset bound and thus from the capacity (region), regardless of the network topology, channel gains, or power constraints. Roughly speaking, distributed decode-forward is dual to noisy network coding, which generalized compress-forward to unicast, multicast, and multiple access relay networks.
Logarithmic regret bounds for Bandits with Knapsacks
Venue: arXiv cs.DS 2017
Year: 2017

Optimal regret bounds for Multi-Armed Bandit problems are now well documented. They can be classified into two categories based on the growth rate with respect to the time horizon $T$: (i) small, distribution-dependent, bounds of order of magnitude $\ln(T)$ and (ii) robust, distribution-free, bounds of order of magnitude $\sqrt{T}$. The Bandits with Knapsacks model, an extension to the framework allowing to model resource consumption, lacks this clear-cut distinction. While several algorithms have been shown to achieve asymptotically optimal distribution-free bounds on regret, there has been little progress toward the development of small distribution-dependent regret bounds. We partially bridge the gap by designing a general-purpose algorithm with distribution-dependent regret bounds that are logarithmic in the initial endowments of resources in several important cases that cover many practical applications, including dynamic pricing with limited supply, bid optimization in online advertisement auctions, and dynamic procurement.
Graph Editing Problems with Extended Regularity Constraints
Venue: arXiv cs.CC 2017
Year: 2017

Graph editing problems offer an interesting perspective on sub- and supergraph identification problems for a large variety of target properties. They have also attracted significant attention in recent years, particularly in the area of parameterized complexity as the problems have rich parameter ecologies. In this paper we examine generalisations of the notion of editing a graph to obtain a regular subgraph. In particular we extend the notion of regularity to include two variants of edge-regularity along with the unifying constraint of strong regularity. We present a number of results, with the central observation that these problems retain the general complexity profile of their regularity-based inspiration: when the number of edits $k$ and the maximum degree $r$ are taken together as a combined parameter, the problems are tractable (i.e. in \FPT{}), but are otherwise intractable. We also examine variants of the basic editing to obtain a regular subgraph problem from the perspective of parameterizing by the treewidth of the input graph. In this case the treewidth of the input graph essentially becomes a limiting parameter on the natural $k+r$ parameterization.
How the structure of precedence constraints may change the complexity class of scheduling problems
Venue: arXiv cs.CC 2017
Year: 2017

This survey aims at demonstrating that the structure of precedence constraints plays a tremendous role on the complexity of scheduling problems. Indeed many problems can be NP-hard when considering general precedence constraints, while they become polynomially solvable for particular precedence constraints. We also show that there still are many very exciting challenges in this research area.
Petri Nets and its Polynomials
Venue: arXiv cs.LO 2017
Year: 2017

For every finite Petri net, we construct a commutative polynomial in two variables and with coefficients from the semiring of natural numbers. We also present an inverse construction and show that multiplication of polynomials correspondence to the product of the corresponding Petri nets in the category of Petri nets with Winskel's morphisms. We endow the set of all Petri nets with Zariski topology.
Rambrain - a library for virtually extending physical memory
Venue: arXiv cs.DC 2017
Year: 2017

We introduce Rambrain, a user space library that manages memory consumption of your code. Using Rambrain you can overcommit memory over the size of physical memory present in the system. Rambrain takes care of temporarily swapping out data to disk and can handle multiples of the physical memory size present. Rambrain is thread-safe, OpenMP and MPI compatible and supports Asynchronous IO. The library was designed to require minimal changes to existing programs and to be easy to use.
Approximation of boundary element matrices using GPGPUs and nested cross approximation
Venue: arXiv cs.MS 2017
Year: 2017

The efficiency of boundary element methods depends crucially on the time required for setting up the stiffness matrix. The far-field part of the matrix can be approximated by compression schemes like the fast multipole method or $\mathcal{H}$-matrix techniques. The near-field part is typically approximated by special quadrature rules like the Sauter-Schwab technique that can handle the singular integrals appearing in the diagonal and near-diagonal matrix elements. Since computing one element of the matrix requires only a small amount of data but a fairly large number of operations, we propose to use general-purpose graphics processing units (GPGPUs) to handle vectorizable portions of the computation: near-field computations are ideally suited for vectorization and can therefore be handled very well by GPGPUs. Modern far-field compression schemes can be split into a small adaptive portion that exhibits divergent control flows, and should therefore be handled by the CPU, and a vectorizable portion that can again be sent to GPGPUs. We propose a hybrid algorithm that splits the computation into tasks for CPUs and GPGPUs. Our method presented in this article is able to reduce the setup time of boundary integral operators by a significant factor of 19-30 for both the Laplace and the Helmholtz equation in 3D when using two consumer GPGPUs compared to a quad-core CPU.
Phenotyping of Clinical Time Series with LSTM Recurrent Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

We present a novel application of LSTM recurrent neural networks to multilabel classification of diagnoses given variable-length time series of clinical measurements. Our method outperforms a strong baseline on a variety of metrics.
Cross-Platform Analysis of Indirect File Leaks in Android and iOS Applications
Venue: arXiv cs.CR 2017
Year: 2017

Today, much of our sensitive information is stored inside mobile applications (apps), such as the browsing histories and chatting logs. To safeguard these privacy files, modern mobile systems, notably Android and iOS, use sandboxes to isolate apps' file zones from one another. However, we show in this paper that these private files can still be leaked by indirectly exploiting components that are trusted by the victim apps. In particular, we devise new indirect file leak (IFL) attacks that exploit browser interfaces, command interpreters, and embedded app servers to leak data from very popular apps, such as Evernote and QQ. Unlike the previous attacks, we demonstrate that these IFLs can affect both Android and iOS. Moreover, our IFL methods allow an adversary to launch the attacks remotely, without implanting malicious apps in victim's smartphones. We finally compare the impacts of four different types of IFL attacks on Android and iOS, and propose several mitigation methods.