OpenRaiser/Intern-Atlas huggingface dataset:
Neutrosophic information in the framework of multi-valued representation
Venue: arXiv cs.AI 2014
Year: 2014

The paper presents some steps for multi-valued representation of neutrosophic information. These steps are provided in the framework of multi-valued logics using the following logical value: true, false, neutral, unknown and saturated. Also, this approach provides some calculus formulae for the following neutrosophic features: truth, falsity, neutrality, ignorance, under-definedness, over-definedness, saturation and entropy. In addition, it was defined net truth, definedness and neutrosophic score.
Efficient GPU Implementation for Single Block Orthogonal Dictionary Learning
Venue: arXiv cs.CV 2014
Year: 2014

Dictionary training for sparse representations involves dealing with large chunks of data and complex algorithms that determine time consuming implementations. SBO is an iterative dictionary learning algorithm based on constructing unions of orthonormal bases via singular value decomposition, that represents each data item through a single best fit orthobase. In this paper we present a GPGPU approach of implementing SBO in OpenCL. We provide a lock-free solution that ensures full-occupancy of the GPU by following the map-reduce model for the sparse-coding stage and by making use of the Partitioned Global Address Space (PGAS) model for developing parallel dictionary updates. The resulting implementation achieves a favourable trade-off between algorithm complexity and data representation quality compared to PAK-SVD which is the standard overcomplete dictionary learning approach. We present and discuss numerical results showing a significant acceleration of the execution time for the dictionary learning process.
A Scalable Asynchronous Distributed Algorithm for Topic Modeling
Venue: arXiv cs.DC 2014
Year: 2014

Learning meaningful topic models with massive document collections which contain millions of documents and billions of tokens is challenging because of two reasons: First, one needs to deal with a large number of topics (typically in the order of thousands). Second, one needs a scalable and efficient way of distributing the computation across multiple machines. In this paper we present a novel algorithm F+Nomad LDA which simultaneously tackles both these problems. In order to handle large number of topics we use an appropriately modified Fenwick tree. This data structure allows us to sample from a multinomial distribution over $T$ items in $O(\log T)$ time. Moreover, when topic counts change the data structure can be updated in $O(\log T)$ time. In order to distribute the computation across multiple processor we present a novel asynchronous framework inspired by the Nomad algorithm of \cite{YunYuHsietal13}. We show that F+Nomad LDA significantly outperform state-of-the-art on massive problems which involve millions of documents, billions of words, and thousands of topics.
A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers
Venue: arXiv cs.CR 2014
Year: 2014

Since the concept of locally decodable codes was introduced by Katz and Trevisan in 2000, it is well-known that information the-oretically secure private information retrieval schemes can be built using locally decodable codes. In this paper, we construct a Byzantine ro-bust PIR scheme using the multiplicity codes introduced by Kopparty et al. Our main contributions are on the one hand to avoid full replica-tion of the database on each server; this significantly reduces the global redundancy. On the other hand, to have a much lower locality in the PIR context than in the LDC context. This shows that there exists two different notions: LDC-locality and PIR-locality. This is made possible by exploiting geometric properties of multiplicity codes.
$k$-best enumeration
Venue: arXiv cs.DS 2014
Year: 2014

We survey $k$-best enumeration problems and the algorithms for solving them, including in particular the problems of finding the $k$ shortest paths, $k$ smallest spanning trees, and $k$ best matchings in weighted graphs.
Consistency Analysis of an Empirical Minimum Error Entropy Algorithm
Venue: arXiv cs.LG 2014
Year: 2014

In this paper we study the consistency of an empirical minimum error entropy (MEE) algorithm in a regression setting. We introduce two types of consistency. The error entropy consistency, which requires the error entropy of the learned function to approximate the minimum error entropy, is shown to be always true if the bandwidth parameter tends to 0 at an appropriate rate. The regression consistency, which requires the learned function to approximate the regression function, however, is a complicated issue. We prove that the error entropy consistency implies the regression consistency for homoskedastic models where the noise is independent of the input variable. But for heteroskedastic models, a counterexample is used to show that the two types of consistency do not coincide. A surprising result is that the regression consistency is always true, provided that the bandwidth parameter tends to infinity at an appropriate rate. Regression consistency of two classes of special models is shown to hold with fixed bandwidth parameter, which further illustrates the complexity of regression consistency of MEE. Fourier transform plays crucial roles in our analysis.
Optimal-Depth Sorting Networks
Venue: arXiv cs.DS 2014
Year: 2014

We solve a 40-year-old open problem on the depth optimality of sorting networks. In 1973, Donald E. Knuth detailed, in Volume 3 of "The Art of Computer Programming", sorting networks of the smallest depth known at the time for n =< 16 inputs, quoting optimality for n =< 8. In 1989, Parberry proved the optimality of the networks with 9 =< n =< 10 inputs. In this article, we present a general technique for obtaining such optimality results, and use it to prove the optimality of the remaining open cases of 11 =< n =< 16 inputs. We show how to exploit symmetry to construct a small set of two-layer networks on n inputs such that if there is a sorting network on n inputs of a given depth, then there is one whose first layers are in this set. For each network in the resulting set, we construct a propositional formula whose satisfiability is necessary for the existence of a sorting network of a given depth. Using an off-the-shelf SAT solver we show that the sorting networks listed by Knuth are optimal. For n =< 10 inputs, our algorithm is orders of magnitude faster than the prior ones.
Color Image Enhancement In the Framework of Logarithmic Models
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we propose a mathematical model for color image processing. It is a logarithmical one. We consider the cube (-1,1)x(-1,1)x(-1,1) as the set of values for the color space. We define two operations: addition <+> and real scalar multiplication <x>. With these operations the space of colors becomes a real vector space. Then, defining the scalar product (.|.) and the norm || . ||, we obtain a (logarithmic) Euclidean space. We show how we can use this model for color image enhancement and we present some experimental results.
Representation of Evolutionary Algorithms in FPGA Cluster for Project of Large-Scale Networks
Venue: arXiv cs.DC 2014
Year: 2014

Many problems are related to network projects, such as electric distribution, telecommunication and others. Most of them can be represented by graphs, which manipulate thousands or millions of nodes, becoming almost an impossible task to obtain real-time solutions. Many efficient solutions use Evolutionary Algorithms (EA), where researches show that performance of EAs can be substantially raised by using an appropriate representation, such as the Node-Depth Encoding (NDE). The objective of this work was to partition an implementation on single-FPGA (Field-Programmable Gate Array) based on NDE from 512 nodes to a multi-FPGAs approach, expanding the system to 4096 nodes.
A Low-Complexity Improved Successive Cancellation Decoder for Polar Codes
Venue: arXiv cs.IT 2014
Year: 2014

Under successive cancellation (SC) decoding, polar codes are inferior to other codes of similar blocklength in terms of frame error rate. While more sophisticated decoding algorithms such as list- or stack-decoding partially mitigate this performance loss, they suffer from an increase in complexity. In this paper, we describe a new flavor of the SC decoder, called the SC flip decoder. Our algorithm preserves the low memory requirements of the basic SC decoder and adjusts the required decoding effort to the signal quality. In the waterfall region, its average computational complexity is almost as low as that of the SC decoder.
Visualising Emotional Landmarks in Cities
Venue: arXiv cs.HC 2014
Year: 2014

Different people and cultures associate different emotional states to different parts and spaces of cities. These vary according to individuals, their cultures and also to the time of day, day of week, season, special occasions and more. Recurring patterns may occur in correspondence of the places in which people work, study, entertain themselves, consume, relate, wait or just take a break. What can we learn from these patterns? Trying to find possible answers to this question passes through the possibility to visualize and represent the configurations of emotional expressions in urban spaces, across time, geography, theme, cultures and other dimensions. We have developed ways in which it is possible to harvest people's geo-located (or geo-locatable) emotional expressions from major social networks and to visualize them according to a variety of different modalities. In this paper we will present a series of these types of visualizations, and the ways in which they can be used to gain better understandings of these emotional patterns as they arise, from points of view which derive from anthropology, urbanism, sociology, politics and also arts and poetics. The paper will focus on the ways in which the data is harvested from different social networks, then categorized and annotated with meta-data describing the emotional states, the languages in which people express themselves, the geographic locations, the themes expressed. A methodology for representing this information across a variety of domains (time, space, emotion, theme) will then be presented in detail. A reflection on possible usage cases for anthropology, urbanism, policy-making, arts and design will end the contribution, as well as the description of series of open issues and the indication of possible next-steps for research.
New algorithms and lower bounds for monotonicity testing
Venue: arXiv cs.CC 2014
Year: 2014

We consider the problem of testing whether an unknown Boolean function $f$ is monotone versus $ε$-far from every monotone function. The two main results of this paper are a new lower bound and a new algorithm for this well-studied problem. Lower bound: We prove an $\tildeΩ(n^{1/5})$ lower bound on the query complexity of any non-adaptive two-sided error algorithm for testing whether an unknown Boolean function $f$ is monotone versus constant-far from monotone. This gives an exponential improvement on the previous lower bound of $Ω(\log n)$ due to Fischer et al. [FLN+02]. We show that the same lower bound holds for monotonicity testing of Boolean-valued functions over hypergrid domains $\{1,\ldots,m\}^n$ for all $m\ge 2$. Upper bound: We give an $\tilde{O}(n^{5/6})\text{poly}(1/ε)$-query algorithm that tests whether an unknown Boolean function $f$ is monotone versus $ε$-far from monotone. Our algorithm, which is non-adaptive and makes one-sided error, is a modified version of the algorithm of Chakrabarty and Seshadhri [CS13a], which makes $\tilde{O}(n^{7/8})\text{poly}(1/ε)$ queries.
Optimizing User Association and Spectrum Allocation in HetNets: A Utility Perspective
Venue: arXiv cs.NI 2014
Year: 2014

The joint user association and spectrum allocation problem is studied for multi-tier heterogeneous networks (HetNets) in both downlink and uplink in the interference-limited regime. Users are associated with base-stations (BSs) based on the biased downlink received power. Spectrum is either shared or orthogonally partitioned among the tiers. This paper models the placement of BSs in different tiers as spatial point processes and adopts stochastic geometry to derive the theoretical mean proportionally fair utility of the network based on the coverage rate. By formulating and solving the network utility maximization problem, the optimal user association bias factors and spectrum partition ratios are analytically obtained for the multi-tier network. The resulting analysis reveals that the downlink and uplink user associations do not have to be symmetric. For uplink under spectrum sharing, if all tiers have the same target signal-to-interference ratio (SIR), distance-based user association is shown to be optimal under a variety of path loss and power control settings. For both downlink and uplink, under orthogonal spectrum partition, it is shown that the optimal proportion of spectrum allocated to each tier should match the proportion of users associated with that tier. Simulations validate the analytical results. Under typical system parameters, simulation results suggest that spectrum partition performs better for downlink in terms of utility, while spectrum sharing performs better for uplink with power control.
The Next 700 Impossibility Results in Time-Varying Graphs
Venue: arXiv cs.DC 2014
Year: 2014

We address highly dynamic distributed systems modeled by time-varying graphs (TVGs). We interest in proof of impossibility results that often use informal arguments about convergence. First, we provide a distance among TVGs to define correctly the convergence of TVG sequences. Next, we provide a general framework that formally proves the convergence of the sequence of executions of any deterministic algorithm over TVGs of any convergent sequence of TVGs. Finally, we illustrate the relevance of the above result by proving that no deterministic algorithm exists to compute the underlying graph of any connected-over-time TVG, i.e., any TVG of the weakest class of long-lived TVGs.
Montgomery's method of polynomial selection for the number field sieve
Venue: arXiv cs.CR 2014
Year: 2014

The number field sieve is the most efficient known algorithm for factoring large integers that are free of small prime factors. For the polynomial selection stage of the algorithm, Montgomery proposed a method of generating polynomials which relies on the construction of small modular geometric progressions. Montgomery's method is analysed in this paper and the existence of suitable geometric progressions is considered.
Pareto efficiency in synthesizing shared autonomy policies with temporal logic constraints
Venue: arXiv cs.RO 2014
Year: 2014

In systems in which control authority is shared by an autonomous controller and a human operator, it is important to find solutions that achieve a desirable system performance with a reasonable workload for the human operator. We formulate a shared autonomy system capable of capturing the interaction and switching control between an autonomous controller and a human operator, as well as the evolution of the operator's cognitive state during control execution. To trade-off human's effort and the performance level, e.g., measured by the probability of satisfying the underlying temporal logic specification, a two-stage policy synthesis algorithm is proposed for generating Pareto efficient coordination and control policies with respect to user specified weights. We integrate the Tchebychev scalarization method for multi-objective optimization methods to obtain a better coverage of the set of Pareto efficient solutions than linear scalarization methods.
Numerical pricing of American options under two stochastic factor models with jumps using a meshless local Petrov-Galerkin method
Venue: arXiv cs.CE 2014
Year: 2014

The most recent update of financial option models is American options under stochastic volatility models with jumps in returns (SVJ) and stochastic volatility models with jumps in returns and volatility (SVCJ). To evaluate these options, mesh-based methods are applied in a number of papers but it is well-known that these methods depend strongly on the mesh properties which is the major disadvantage of them. Therefore, we propose the use of the meshless methods to solve the aforementioned options models, especially in this work we select and analyze one scheme of them, named local radial point interpolation (LRPI) based on Wendland's compactly supported radial basis functions (WCS-RBFs) with C6, C4 and C2 smoothness degrees. The LRPI method which is a special type of meshless local Petrov-Galerkin method (MLPG), offers several advantages over the mesh-based methods, nevertheless it has never been applied to option pricing, at least to the very best of our knowledge. These schemes are the truly meshless methods, because, a traditional non-overlapping continuous mesh is not required, neither for the construction of the shape functions, nor for the integration of the local sub-domains. In this work, the American option which is a free boundary problem, is reduced to a problem with fixed boundary using a Richardson extrapolation technique. Then the implicit-explicit (IMEX) time stepping scheme is employed for the time derivative which allows us to smooth the discontinuities of the options' payoffs. Stability analysis of the method is analyzed and performed. In fact, according to an analysis carried out in the present paper, the proposed method is unconditionally stable. Numerical experiments are presented showing that the proposed approaches are extremely accurate and fast.
Study of the Influence of the Number Normalization Scheme Used in Two Chaotic Pseudo Random Number Generators Used as the Source of Randomness in Differential Evolution
Venue: arXiv cs.NE 2014
Year: 2014

In many publications, authors showed that chaotic pseudo random number generators (PRNGs) may improve performance of the evolutionary algorithms. In this paper, we use two chaotic maps Gingerbread man and Tinkerbell as the chaotic PRNGs instead of the classical PRNG in the differential evolution. Numbers generated by this maps are normalized to the unit interval by three different methods -- operation modulo, straightforward number normalization where we know minimal and maximal generated number and arctangent of the two variables $x$ and $y$, where numbers $x$ and $y$ are generated by the Gingerbread man map and Tinkerbell map. The first goal of this paper is to show whether the differential evolution convergence speed might be affected by the way how we normalize number generated by the chaotic map. The second goal is to find out the influence of the probability distribution function of the selected chaotic PRNGs. The results mentioned below showed that the selected normalization method may improve differential evolution convergence speed, especially in the case of arctangent and straightforward number normalization, where we know the minimal and maximal generated numbers.
Crypto-Nets: Neural Networks over Encrypted Data
Venue: arXiv cs.LG 2014
Year: 2014

The problem we address is the following: how can a user employ a predictive model that is held by a third party, without compromising private information. For example, a hospital may wish to use a cloud service to predict the readmission risk of a patient. However, due to regulations, the patient's medical files cannot be revealed. The goal is to make an inference using the model, without jeopardizing the accuracy of the prediction or the privacy of the data. To achieve high accuracy, we use neural networks, which have been shown to outperform other learning models for many tasks. To achieve the privacy requirements, we use homomorphic encryption in the following protocol: the data owner encrypts the data and sends the ciphertexts to the third party to obtain a prediction from a trained model. The model operates on these ciphertexts and sends back the encrypted prediction. In this protocol, not only the data remains private, even the values predicted are available only to the data owner. Using homomorphic encryption and modifications to the activation functions and training algorithms of neural networks, we show that it is protocol is possible and may be feasible. This method paves the way to build a secure cloud-based neural network prediction services without invading users' privacy.
Multiple Authors Detection: A Quantitative Analysis of Dream of the Red Chamber
Venue: arXiv cs.LG 2014
Year: 2014

Inspired by the authorship controversy of Dream of the Red Chamber and the application of machine learning in the study of literary stylometry, we develop a rigorous new method for the mathematical analysis of authorship by testing for a so-called chrono-divide in writing styles. Our method incorporates some of the latest advances in the study of authorship attribution, particularly techniques from support vector machines. By introducing the notion of relative frequency as a feature ranking metric our method proves to be highly effective and robust. Applying our method to the Cheng-Gao version of Dream of the Red Chamber has led to convincing if not irrefutable evidence that the first $80$ chapters and the last $40$ chapters of the book were written by two different authors. Furthermore, our analysis has unexpectedly provided strong support to the hypothesis that Chapter 67 was not the work of Cao Xueqin either. We have also tested our method to the other three Great Classical Novels in Chinese. As expected no chrono-divides have been found. This provides further evidence of the robustness of our method.
Supertagging: Introduction, learning, and application
Venue: arXiv cs.CL 2014
Year: 2014

Supertagging is an approach originally developed by Bangalore and Joshi (1999) to improve the parsing efficiency. In the beginning, the scholars used small training datasets and somewhat naïve smoothing techniques to learn the probability distributions of supertags. Since its inception, the applicability of Supertags has been explored for TAG (tree-adjoining grammar) formalism as well as other related yet, different formalisms such as CCG. This article will try to summarize the various chapters, relevant to statistical parsing, from the most recent edited book volume (Bangalore and Joshi, 2010). The chapters were selected so as to blend the learning of supertags, its integration into full-scale parsing, and in semantic parsing.
Wyrm, A Pythonic Toolbox for Brain-Computer Interfacing
Venue: arXiv cs.HC 2014
Year: 2014

A Brain-Computer Interface (BCI) is a system that measures central nervous system activity and translates the recorded data into an output suitable for a computer to use as an input signal. Such a BCI system consists of three parts, the signal acquisition, the signal processing and the feedback/stimulus presentation. In this paper we present Wyrm, a signal processing toolbox for BCI in Python. Wyrm is applicable to a broad range of neuroscientific problems and capable for running online experiments in real time and off-line data analysis and visualisation.