OpenRaiser/Intern-Atlas huggingface dataset:
Structured Prediction of Sequences and Trees using Infinite Contexts
Venue: arXiv cs.LG 2015
Year: 2015

Linguistic structures exhibit a rich array of global phenomena, however commonly used Markov models are unable to adequately describe these phenomena due to their strong locality assumptions. We propose a novel hierarchical model for structured prediction over sequences and trees which exploits global context by conditioning each generation decision on an unbounded context of prior decisions. This builds on the success of Markov models but without imposing a fixed bound in order to better represent global phenomena. To facilitate learning of this large and unbounded model, we use a hierarchical Pitman-Yor process prior which provides a recursive form of smoothing. We propose prediction algorithms based on A* and Markov Chain Monte Carlo sampling. Empirical results demonstrate the potential of our model compared to baseline finite-context Markov models on part-of-speech tagging and syntactic parsing.
Optimising PICCANTE - an Open Source Particle-in-Cell Code for Advanced Simulations on Tier-0 Systems
Venue: arXiv cs.DC 2015
Year: 2015

We present a detailed strong and weak scaling analysis of PICCANTE, an open source, massively parallel, fully-relativistic Particle-In-Cell (PIC) code. PIC codes are widely used in plasma physics and astrophysics to study the cases where kinetic effects are relevant. PICCANTE is primarily developed to study laser-plasma interaction. Within a PRACE Preparatory Access Project, various revisions of different routines of the code have been analysed on the HPC systems JUQUEEN at Juelich Supercomputing Centre (JSC), Germany, and FERMI at CINECA, Italy, to improve scalability and I/O performance of the application. The diagnostic tool Scalasca is used to identify suboptimal routines. Different output strategies are discussed. The detailed strong and weak scaling behaviour of the improved code are presented in comparison with the original version of the code.
The Quicksort algorithm and related topics
Venue: arXiv cs.DS 2015
Year: 2015

Sorting algorithms have attracted a great deal of attention and study, as they have numerous applications to Mathematics, Computer Science and related fields. In this thesis, we first deal with the mathematical analysis of the Quicksort algorithm and its variants. Specifically, we study the time complexity of the algorithm and we provide a complete demonstration of the variance of the number of comparisons required, a known result but one whose detailed proof is not easy to read out of the literature. We also examine variants of Quicksort, where multiple pivots are chosen for the partitioning of the array. The rest of this work is dedicated to the analysis of finding the true order by further pairwise comparisons when a partial order compatible with the true order is given in advance. We discuss a number of cases where the partially ordered sets arise at random. To this end, we employ results from Graph and Information Theory. Finally, we obtain an alternative bound on the number of linear extensions when the partially ordered set arises from a random graph, and discuss the possible application of Shellsort in merging chains.
New Algorithms for Computing a Single Component of the Discrete Fourier Transform
Venue: arXiv cs.DM 2015
Year: 2015

This paper introduces the theory and hardware implementation of two new algorithms for computing a single component of the discrete Fourier transform. In terms of multiplicative complexity, both algorithms are more efficient, in general, than the well known Goertzel Algorithm.
An asymptotically optimal policy and state-space collapse for the multi-class shared queue
Venue: arXiv cs.PF 2015
Year: 2015

We consider a multi-class G/G/1 queue with a finite shared buffer. There is task admission and server scheduling control which aims to minimize the cost which consists of holding and rejection components. We construct a policy that is asymptotically optimal in the heavy traffic limit. The policy stems from solution to Harrison-Taksar (HT) free boundary problem and is expressed by a single free boundary point. We show that the HT problem solution translated into the queuelength processes follows a specific {\it triangular} form. This form implies the queuelength control policy which is different from the known $cμ$ priority rule and has a novel structure. We exemplify that the probabilistic methods we exploit can be successfully applied to solving scheduling and admission problems in cloud computing.
On the Intrinsic Limits to Representationally-Adaptive Machine-Learning
Venue: arXiv cs.AI 2015
Year: 2015

Online learning is a familiar problem setting within Machine-Learning in which data is presented serially in time to a learning agent, requiring it to progressively adapt within the constraints of the learning algorithm. More sophisticated variants may involve concepts such as transfer-learning which increase this adaptive capability, enhancing the learner's cognitive capacities in a manner that can begin to imitate the open-ended learning capabilities of human beings. We shall argue in this paper, however, that a full realization of this notion requires that, in addition to the capacity to adapt to novel data, autonomous online learning must ultimately incorporate the capacity to update its own representational capabilities in relation to the data. We therefore enquire about the philosophical limits of this process, and argue that only fully embodied learners exhibiting an a priori perception-action link in order to ground representational adaptations are capable of exhibiting the full range of human cognitive capability.
Algorithms for Replica Placement in High-Availability Storage
Venue: arXiv cs.DS 2015
Year: 2015

A new model of causal failure is presented and used to solve a novel replica placement problem in data centers. The model describes dependencies among system components as a directed graph. A replica placement is defined as a subset of vertices in such a graph. A criterion for optimizing replica placements is formalized and explained. In this work, the optimization goal is to avoid choosing placements in which a single failure event is likely to wipe out multiple replicas. Using this criterion, a fast algorithm is given for the scenario in which the dependency model is a tree. The main contribution of the paper is an $O(n + ρ\log ρ)$ dynamic programming algorithm for placing $ρ$ replicas on a tree with $n$ vertices. This algorithm exhibits the interesting property that only two subproblems need to be recursively considered at each stage. An $O(n^2 ρ)$ greedy algorithm is also briefly reported.
Modeling and Improving the Energy Performance of GPS Receivers for Mobile Applications
Venue: arXiv cs.OH 2015
Year: 2015

Integrated GPS receivers have become a basic module in today's mobile devices. While serving as the cornerstone for location based services, GPS modules have a serious battery drain problem due to high computation load. This paper aims to reveal the impact of key software parameters on hardware energy consumption, by establishing an energy model for a standard GPS receiver architecture as found in both academic and industrial designs. In particular, our measurements show that the receiver's energy consumption is in large part linear with the number of tracked satellites. This leads to a design of selective tracking algorithm that provides similar positioning accuracy (around 12m) with a subset of selected satellites, which translates to an energy saving of 20.9-23.1\% on the Namuru board.
Polynomial-time approximability of the k-Sink Location problem
Venue: arXiv cs.DS 2015
Year: 2015

A dynamic network ${\cal N} = (G,c,τ,S)$ where $G=(V,E)$ is a graph, integers $τ(e)$ and $c(e)$ represent, for each edge $e\in E$, the time required to traverse edge $e$ and its nonnegative capacity, and the set $S\subseteq V$ is a set of sources. In the $k$-{\sc Sink Location} problem, one is given as input a dynamic network ${\cal N}$ where every source $u\in S$ is given a nonnegative supply value $σ(u)$. The task is then to find a set of sinks $X = \{x_1,\ldots,x_k\}$ in $G$ that minimizes the routing time of all supply to $X$. Note that, in the case where $G$ is an undirected graph, the optimal position of the sinks in $X$ needs not be at vertices, and can be located along edges. Hoppe and Tardos showed that, given an instance of $k$-{\sc Sink Location} and a set of $k$ vertices $X\subseteq V$, one can find an optimal routing scheme of all the supply in $G$ to $X$ in polynomial time, in the case where graph $G$ is directed. Note that when $G$ is directed, this suffices to obtain polynomial-time solvability of the $k$-{\sc Sink Location} problem, since any optimal position will be located at vertices of $G$. However, the computational complexity of the $k$-{\sc Sink Location} problem on general undirected graphs is still open. In this paper, we show that the $k$-{\sc Sink Location} problem admits a fully polynomial-time approximation scheme (FPTAS) for every fixed $k$, and that the problem is $W[1]$-hard when parameterized by $k$.
On the Approximability of Independent Set Problem on Power Law Graphs
Venue: arXiv cs.DS 2015
Year: 2015

We give the first nonconstant lower bounds for the approximability of the Independent Set Problem on the Power Law Graphs. These bounds are of the form $n^ε$ in the case when the power law exponent satisfies $β<1$. In the case when $β=1$, the lower bound is of the form $\log (n)^ε$. The embedding technique used in the proof could also be of independent interest.
Fast Multi-class Dictionaries Learning with Geometrical Directions in MRI Reconstruction
Venue: arXiv cs.CV 2015
Year: 2015

Objective: Improve the reconstructed image with fast and multi-class dictionaries learning when magnetic resonance imaging is accelerated by undersampling the k-space data. Methods: A fast orthogonal dictionary learning method is introduced into magnetic resonance image reconstruction to providing adaptive sparse representation of images. To enhance the sparsity, image is divided into classified patches according to the same geometrical direction and dictionary is trained within each class. A new sparse reconstruction model with the multi-class dictionaries is proposed and solved using a fast alternating direction method of multipliers. Results: Experiments on phantom and brain imaging data with acceleration factor up to 10 and various undersampling patterns are conducted. The proposed method is compared with state-of-the-art magnetic resonance image reconstruction methods. Conclusion: Artifacts are better suppressed and image edges are better preserved than the compared methods. Besides, the computation of the proposed approach is much faster than the typical K-SVD dictionary learning method in magnetic resonance image reconstruction. Significance: The proposed method can be exploited in undersapmled magnetic resonance imaging to reduce data acquisition time and reconstruct images with better image quality.
apsis - Framework for Automated Optimization of Machine Learning Hyper Parameters
Venue: arXiv cs.LG 2015
Year: 2015

The apsis toolkit presented in this paper provides a flexible framework for hyperparameter optimization and includes both random search and a bayesian optimizer. It is implemented in Python and its architecture features adaptability to any desired machine learning code. It can easily be used with common Python ML frameworks such as scikit-learn. Published under the MIT License other researchers are heavily encouraged to check out the code, contribute or raise any suggestions. The code can be found at github.com/FrederikDiehl/apsis.
First-Order Logic Theorem Proving and Model Building via Approximation and Instantiation
Venue: arXiv cs.LO 2015
Year: 2015

In this paper we consider first-order logic theorem proving and model building via approximation and instantiation. Given a clause set we propose its approximation into a simplified clause set where satisfiability is decidable. The approximation extends the signature and preserves unsatisfiability: if the simplified clause set is satisfiable in some model, so is the original clause set in the same model interpreted in the original signature. A refutation generated by a decision procedure on the simplified clause set can then either be lifted to a refutation in the original clause set, or it guides a refinement excluding the previously found unliftable refutation. This way the approach is refutationally complete. We do not step-wise lift refutations but conflicting cores, finite unsatisfiable clause sets representing at least one refutation. The approach is dual to many existing approaches in the literature because our approximation preserves unsatisfiability.
A Neurodynamical System for finding a Minimal VC Dimension Classifier
Venue: arXiv cs.LG 2015
Year: 2015

The recently proposed Minimal Complexity Machine (MCM) finds a hyperplane classifier by minimizing an exact bound on the Vapnik-Chervonenkis (VC) dimension. The VC dimension measures the capacity of a learning machine, and a smaller VC dimension leads to improved generalization. On many benchmark datasets, the MCM generalizes better than SVMs and uses far fewer support vectors than the number used by SVMs. In this paper, we describe a neural network based on a linear dynamical system, that converges to the MCM solution. The proposed MCM dynamical system is conducive to an analogue circuit implementation on a chip or simulation using Ordinary Differential Equation (ODE) solvers. Numerical experiments on benchmark datasets from the UCI repository show that the proposed approach is scalable and accurate, as we obtain improved accuracies and fewer number of support vectors (upto 74.3% reduction) with the MCM dynamical system.
Design of High Performance MIPS Cryptography Processor Based on T-DES Algorithm
Venue: arXiv cs.AR 2015
Year: 2015

The paper describes the design of high performance MIPS Cryptography processor based on triple data encryption standard. The organization of pipeline stages in such a way that pipeline can be clocked at high frequency. Encryption and Decryption blocks of triple data encryption standard (T-DES) crypto system and dependency among themselves are explained in detail with the help of block diagram. In order to increase the processor functionality and performance, especially for security applications we include three new 32-bit instructions LKLW, LKUW and CRYPT. The design has been synthesized at 40nm process technology targeting using Xilinx Virtex-6 device. The overall MIPS Crypto processor works at 209MHz.
Experimental Estimation of Number of Clusters Based on Cluster Quality
Venue: arXiv cs.IR 2015
Year: 2015

Text Clustering is a text mining technique which divides the given set of text documents into significant clusters. It is used for organizing a huge number of text documents into a well-organized form. In the majority of the clustering algorithms, the number of clusters must be specified apriori, which is a drawback of these algorithms. The aim of this paper is to show experimentally how to determine the number of clusters based on cluster quality. Since partitional clustering algorithms are well-suited for clustering large document datasets, we have confined our analysis to a partitional clustering algorithm.
A model-based approach to recovering the structure of a plant from images
Venue: arXiv cs.CV 2015
Year: 2015

We present a method for recovering the structure of a plant directly from a small set of widely-spaced images. Structure recovery is more complex than shape estimation, but the resulting structure estimate is more closely related to phenotype than is a 3D geometric model. The method we propose is applicable to a wide variety of plants, but is demonstrated on wheat. Wheat is made up of thin elements with few identifiable features, making it difficult to analyse using standard feature matching techniques. Our method instead analyses the structure of plants using only their silhouettes. We employ a generate-and-test method, using a database of manually modelled leaves and a model for their composition to synthesise plausible plant structures which are evaluated against the images. The method is capable of efficiently recovering accurate estimates of plant structure in a wide variety of imaging scenarios, with no manual intervention.
Proiectarea si implementarea unui portal HL7
Venue: arXiv cs.SE 2015
Year: 2015

This paper introduces some techniques used in developing and implementing an HL7 clinical data portal used in client-server architecture. The HL7 portal is used by nonHL7 applications that need medical data from HL7 servers. Also, the portal can translate a large number of HL7 terms between an indefinite number of languages.
Fraudulent Electronic transaction detection using KDA Model
Venue: arXiv cs.DB 2015
Year: 2015

Clustering analysis and Datamining methodologies were applied to the problem of identifying illegal and fraud transactions. The researchers independently developed model and software using data provided by a bank and using Rapidminer modeling tool. The research objectives are to propose dynamic model and mechanism to cover fraud detection system limitations. KDA model as proposed model can detect 68.75% of fraudulent transactions with online dynamic modeling and 81.25% in offline mode and the Fraud Detection System & Decision Support System. Software propose a good supporting procedure to detect fraudulent transaction dynamically.
On Acyclic Edge-Coloring of Complete Bipartite Graphs
Venue: arXiv cs.DM 2015
Year: 2015

An acyclic edge-coloring of a graph is a proper edge-coloring without bichromatic ($2$-colored) cycles. The acyclic chromatic index of a graph $G$, denoted by $a'(G)$, is the least integer $k$ such that $G$ admits an acyclic edge-coloring using $k$ colors. Let $Δ= Δ(G)$ denote the maximum degree of a vertex in a graph $G$. A complete bipartite graph with $n$ vertices on each side is denoted by $K_{n,n}$. Basavaraju, Chandran and Kummini proved that $a'(K_{n,n}) \ge n+2 = Δ+ 2$ when $n$ is odd. Basavaraju and Chandran provided an acyclic edge-coloring of $K_{p,p}$ using $p+2$ colors and thus establishing $a'(K_{p,p}) = p+2 = Δ+ 2$ when $p$ is an odd prime. The main tool in their approach is perfect $1$-factorization of $K_{p,p}$. Recently, following their approach, Venkateswarlu and Sarkar have shown that $K_{2p-1,2p-1}$ admits an acyclic edge-coloring using $2p+1$ colors which implies that $a'(K_{2p-1,2p-1}) = 2p+1 = Δ+ 2$, where $p$ is an odd prime. In this paper, we generalize this approach and present a general framework to possibly get an acyclic edge-coloring of $K_{n,n}$ which possess a perfect $1$-factorization using $n+2 = Δ+2$ colors. In this general framework, we show that $K_{p^2,p^2}$ admits an acyclic edge-coloring using $p^2+2$ colors and thus establishing $a'(K_{p^2,p^2}) = p^2+2 = Δ+ 2$ when $p\ge 5$ is an odd prime.
Tools and Models for High Level Parallel and Grid Programming
Venue: arXiv cs.DC 2015
Year: 2015

When algorithmic skeletons were first introduced by Cole in late 1980 the idea had an almost immediate success. The skeletal approach has been proved to be effective when application algorithms can be expressed in terms of skeletons composition. However, despite both their effectiveness and the progress made in skeletal systems design and implementation, algorithmic skeletons remain absent from mainstream practice. Cole and other researchers, focused the problem. They recognized the issues affecting skeletal systems and stated a set of principles that have to be tackled in order to make them more effective and to take skeletal programming into the parallel mainstream. In this thesis we propose tools and models for addressing some among the skeletal programming environments issues. We describe three novel approaches aimed at enhancing skeletons based systems from different angles. First, we present a model we conceived that allows algorithmic skeletons customization exploiting the macro data-flow abstraction. Then we present two results about the exploitation of meta-programming techniques for the run-time generation and optimization of macro data-flow graphs. In particular, we show how to generate and how to optimize macro data-flow graphs accordingly both to programmers provided non-functional requirements and to execution platform features. The last result we present are the Behavioural Skeletons, an approach aimed at addressing the limitations of skeletal programming environments when used for the development of component-based Grid applications. We validated all the approaches conducting several test, performed exploiting a set of tools we developed.
Improving GGH Public Key Scheme Using Low Density Lattice Codes
Venue: arXiv cs.CR 2015
Year: 2015

Goldreich-Goldwasser-Halevi (GGH) public key cryptosystem is an instance of lattice-based cryptosystems whose security is based on the hardness of lattice problems. In fact, GGH cryptosystem is the lattice version of the first code-based cryptosystem, proposed by McEliece. However, it has a number of drawbacks such as; large public key length and low security level. On the other hand, Low Density Lattice Codes (LDLCs) are the practical classes of lattice codes which can achieve capacity on the additive white Gaussian noise (AWGN) channel with low complexity decoding algorithm. This paper introduces a public key cryptosystem based on LDLCs to withdraw the drawbacks of GGH cryptosystem. To reduce the key length, we employ the generator matrix of the used LDLC in Hermite normal form (HNF) as the public key. Also, by exploiting the linear decoding complexity of the used LDLC, the decryption complexity is decreased compared with GGH cryptosystem. These increased efficiencies allow us to use the bigger values of security parameters. Moreover, we exploit the special Gaussian vector whose variance is upper bounded by the Poltyrev limit as the perturbation vector. These techniques can resist the proposed scheme against the most efficient attacks to the GGH-like cryptosystems.
Fourier Codes
Venue: arXiv cs.IT 2015
Year: 2015

A new family of error-correcting codes, called Fourier codes, is introduced. The code parity-check matrix, dimension and an upper bound on its minimum distance are obtained from the eigenstructure of the Fourier number theoretic transform. A decoding technique for such codes is proposed.
Joint Link Adaptation and User Scheduling with HARQ in Multi-Cell Environments
Venue: arXiv cs.IT 2015
Year: 2015

Inter-cell interference (ICI) is one of the most critical factors affecting performance of cellular networks. In this paper, we investigate a joint link adaptation and user scheduling problem for multi-cell downlink employing HARQ techniques, where the ICI exists among cells. We first propose an approximation method on aggregated ICI for analyzing an effective signal-to-interference-and-noise ratio (SINR) with the HARQ technique at users, named identical path-loss approximation (IPLA). Based on the proposed IPLA, we propose a transmission rate selection algorithm maximizing an expected throughput at each user. We also propose a simple but effective cross-layer framework jointly combining transmission rate adaptation and user scheduling techniques, considering both HARQ and ICI. It is shown that statistical distribution of the effective SINR at users based on the IPLA agrees well with the empirical distribution, while the conventional Gaussian approximation (GA) does not work well in the case that dominant ICIs exist. Thus, IPLA enables base stations to choose more accurate transmission rates. Furthermore, the proposed IPLA-based cross-layer policy outperforms existing policies in terms of both system throughput and user fairness.