OpenRaiser/Intern-Atlas huggingface dataset:
Generating Approximate Solutions to the TTP using a Linear Distance Relaxation
Venue: arXiv cs.AI 2014
Year: 2014

In some domestic professional sports leagues, the home stadiums are located in cities connected by a common train line running in one direction. For these instances, we can incorporate this geographical information to determine optimal or nearly-optimal solutions to the n-team Traveling Tournament Problem (TTP), an NP-hard sports scheduling problem whose solution is a double round-robin tournament schedule that minimizes the sum total of distances traveled by all n teams. We introduce the Linear Distance Traveling Tournament Problem (LD-TTP), and solve it for n=4 and n=6, generating the complete set of possible solutions through elementary combinatorial techniques. For larger n, we propose a novel "expander construction" that generates an approximate solution to the LD-TTP. For n congruent to 4 modulo 6, we show that our expander construction produces a feasible double round-robin tournament schedule whose total distance is guaranteed to be no worse than 4/3 times the optimal solution, regardless of where the n teams are located. This 4/3-approximation for the LD-TTP is stronger than the currently best-known ratio of 5/3 + epsilon for the general TTP. We conclude the paper by applying this linear distance relaxation to general (non-linear) n-team TTP instances, where we develop fast approximate solutions by simply "assuming" the n teams lie on a straight line and solving the modified problem. We show that this technique surprisingly generates the distance-optimal tournament on all benchmark sets on 6 teams, as well as close-to-optimal schedules for larger n, even when the teams are located around a circle or positioned in three-dimensional space.
Achieving Marton's Region for Broadcast Channels Using Polar Codes
Venue: arXiv cs.IT 2014
Year: 2014

This paper presents polar coding schemes for the 2-user discrete memoryless broadcast channel (DM-BC) which achieve Marton's region with both common and private messages. This is the best achievable rate region known to date, and it is tight for all classes of 2-user DM-BCs whose capacity regions are known. To accomplish this task, we first construct polar codes for both the superposition as well as the binning strategy. By combining these two schemes, we obtain Marton's region with private messages only. Finally, we show how to handle the case of common information. The proposed coding schemes possess the usual advantages of polar codes, i.e., they have low encoding and decoding complexity and a super-polynomial decay rate of the error probability. We follow the lead of Goela, Abbe, and Gastpar, who recently introduced polar codes emulating the superposition and binning schemes. In order to align the polar indices, for both schemes, their solution involves some degradedness constraints that are assumed to hold between the auxiliary random variables and the channel outputs. To remove these constraints, we consider the transmission of $k$ blocks and employ a chaining construction that guarantees the proper alignment of the polarized indices. The techniques described in this work are quite general, and they can be adopted to many other multi-terminal scenarios whenever there polar indices need to be aligned.
Polarization as a novel architecture to boost the classical mismatched capacity of B-DMCs
Venue: arXiv cs.IT 2014
Year: 2014

We show that the mismatched capacity of binary discrete memoryless channels can be improved by channel combining and splitting via Arıkan's polar transformations. We also show that the improvement is possible even if the transformed channels are decoded with a mismatched polar decoder.
Identifying Bengali Multiword Expressions using Semantic Clustering
Venue: arXiv cs.CL 2014
Year: 2014

One of the key issues in both natural language understanding and generation is the appropriate processing of Multiword Expressions (MWEs). MWEs pose a huge problem to the precise language processing due to their idiosyncratic nature and diversity in lexical, syntactical and semantic properties. The semantics of a MWE cannot be expressed after combining the semantics of its constituents. Therefore, the formalism of semantic clustering is often viewed as an instrument for extracting MWEs especially for resource constraint languages like Bengali. The present semantic clustering approach contributes to locate clusters of the synonymous noun tokens present in the document. These clusters in turn help measure the similarity between the constituent words of a potentially candidate phrase using a vector space model and judge the suitability of this phrase to be a MWE. In this experiment, we apply the semantic clustering approach for noun-noun bigram MWEs, though it can be extended to any types of MWEs. In parallel, the well known statistical models, namely Point-wise Mutual Information (PMI), Log Likelihood Ratio (LLR), Significance function are also employed to extract MWEs from the Bengali corpus. The comparative evaluation shows that the semantic clustering approach outperforms all other competing statistical models. As a by-product of this experiment, we have started developing a standard lexicon in Bengali that serves as a productive Bengali linguistic thesaurus.
Iterative Universal Hash Function Generator for Minhashing
Venue: arXiv cs.LG 2014
Year: 2014

Minhashing is a technique used to estimate the Jaccard Index between two sets by exploiting the probability of collision in a random permutation. In order to speed up the computation, a random permutation can be approximated by using an universal hash function such as the $h_{a,b}$ function proposed by Carter and Wegman. A better estimate of the Jaccard Index can be achieved by using many of these hash functions, created at random. In this paper a new iterative procedure to generate a set of $h_{a,b}$ functions is devised that eliminates the need for a list of random values and avoid the multiplication operation during the calculation. The properties of the generated hash functions remains that of an universal hash function family. This is possible due to the random nature of features occurrence on sparse datasets. Results show that the uniformity of hashing the features is maintaned while obtaining a speed up of up to $1.38$ compared to the traditional approach.
Spatially regularized reconstruction of fibre orientation distributions in the presence of isotropic diffusion
Venue: arXiv cs.CV 2014
Year: 2014

The connectivity and structural integrity of the white matter of the brain is nowadays known to be implicated into a wide range of brain-related disorders. However, it was not before the advent of diffusion Magnetic Resonance Imaging (dMRI) that researches have been able to examine the properties of white matter in vivo. Presently, among a range of various methods of dMRI, high angular resolution diffusion imaging (HARDI) is known to excel in its ability to provide reliable information about the local orientations of neural fasciculi (aka fibre tracts). Moreover, as opposed to the more traditional diffusion tensor imaging (DTI), HARDI is capable of distinguishing the orientations of multiple fibres passing through a given spatial voxel. Unfortunately, the ability of HARDI to discriminate between neural fibres that cross each other at acute angles is always limited, which is the main reason behind the development of numerous post-processing tools, aiming at the improvement of the directional resolution of HARDI. Among such tools is spherical deconvolution (SD). Due to its ill-posed nature, however, SD standardly relies on a number of a priori assumptions which are to render its results unique and stable. In this paper, we propose a different approach to the problem of SD in HARDI, which accounts for the spatial continuity of neural fibres as well as the presence of isotropic diffusion. Subsequently, we demonstrate how the proposed solution can be used to successfully overcome the effect of partial voluming, while preserving the spatial coherency of cerebral diffusion at moderate-to-severe noise levels. In a series of both in silico and in vivo experiments, the performance of the proposed method is compared with that of several available alternatives, with the comparative results clearly supporting the viability and usefulness of our approach.
Word-length entropies and correlations of natural language written texts
Venue: arXiv cs.CL 2014
Year: 2014

We study the frequency distributions and correlations of the word lengths of ten European languages. Our findings indicate that a) the word-length distribution of short words quantified by the mean value and the entropy distinguishes the Uralic (Finnish) corpus from the others, b) the tails at long words, manifested in the high-order moments of the distributions, differentiate the Germanic languages (except for English) from the Romanic languages and Greek and c) the correlations between nearby word lengths measured by the comparison of the real entropies with those of the shuffled texts are found to be smaller in the case of Germanic and Finnish languages.
Rate Region of the Vector Gaussian CEO Problem with the Trace Distortion Constraint
Venue: arXiv cs.IT 2014
Year: 2014

We establish a new extremal inequality, which is further leveraged to give a complete characterization of the rate region of the vector Gaussian CEO problem with the trace distortion constraint. The proof of this extremal inequality hinges on a careful analysis of the Karush-Kuhn-Tucker necessary conditions for the non-convex optimization problem associated with the Berger-Tung scheme, which enables us to integrate the perturbation argument by Wang and Chen with the distortion projection method by Rahman and Wagner.
An Extended Result on the Optimal Estimation under Minimum Error Entropy Criterion
Venue: arXiv cs.IT 2014
Year: 2014

The minimum error entropy (MEE) criterion has been successfully used in fields such as parameter estimation, system identification and the supervised machine learning. There is in general no explicit expression for the optimal MEE estimate unless some constraints on the conditional distribution are imposed. A recent paper has proved that if the conditional density is conditionally symmetric and unimodal (CSUM), then the optimal MEE estimate (with Shannon entropy) equals the conditional median. In this study, we extend this result to the generalized MEE estimation where the optimality criterion is the Renyi entropy or equivalently, the α-order information potential (IP).
Hypergraph Acyclicity and Propositional Model Counting
Venue: arXiv cs.CC 2014
Year: 2014

We show that the propositional model counting problem #SAT for CNF- formulas with hypergraphs that allow a disjoint branches decomposition can be solved in polynomial time. We show that this class of hypergraphs is incomparable to hypergraphs of bounded incidence cliquewidth which were the biggest class of hypergraphs for which #SAT was known to be solvable in polynomial time so far. Furthermore, we present a polynomial time algorithm that computes a disjoint branches decomposition of a given hypergraph if it exists and rejects otherwise. Finally, we show that some slight extensions of the class of hypergraphs with disjoint branches decompositions lead to intractable #SAT, leaving open how to generalize the counting result of this paper.
Truth Table Invariant Cylindrical Algebraic Decomposition by Regular Chains
Venue: arXiv cs.SC 2014
Year: 2014

A new algorithm to compute cylindrical algebraic decompositions (CADs) is presented, building on two recent advances. Firstly, the output is truth table invariant (a TTICAD) meaning given formulae have constant truth value on each cell of the decomposition. Secondly, the computation uses regular chains theory to first build a cylindrical decomposition of complex space (CCD) incrementally by polynomial. Significant modification of the regular chains technology was used to achieve the more sophisticated invariance criteria. Experimental results on an implementation in the RegularChains Library for Maple verify that combining these advances gives an algorithm superior to its individual components and competitive with the state of the art.
Fuzzy Logic Based Multi User Adaptive Test System
Venue: arXiv cs.CY 2014
Year: 2014

The present proliferation of e-learning has been actively underway for the last 10 years. Current research in Adaptive Testing System focuses on the development of psychometric models with items selection strategies applicable to adaptive testing processes. The key aspect of proposed Adaptive Testing System is to develop an increasingly sophisticated latent trait model which can assist users in developing and enhancing their skills. Computerized Adaptive Test (CAT) System requires a lot of investment in time and effort to develop analyze and administrate an adaptive test. In this paper a fuzzy logic based Multi User Adaptive Test System (MUATS) is developed. Which is a Short Messaging Service (SMS) based System, currently integrated with GSM network based on the new psychometric model in education assessment. MUATS is not only a platform independent Adaptive Test System but also it eases the evaluation effort for adaptive test process. It further uses fuzzy logic to pick the most appropriate question from the pool of database for a specific user to be asked which makes the overall system an intelligent one.
Subsumption Checking in Conjunctive Coalgebraic Fixpoint Logics
Venue: arXiv cs.LO 2014
Year: 2014

While reasoning in a logic extending a complete Boolean basis is coNP-hard, restricting to conjunctive fragments of modal languages sometimes allows for tractable reasoning even in the presence of greatest fixpoints. One such example is the EL family of description logics; here, efficient reasoning is based on satisfaction checking in suitable small models that characterize formulas in terms of simulations. It is well-known, though, that not every conjunctive modal language has a tractable reasoning problem. Natural questions are then how common such tractable fragments are and how to identify them. In this work we provide sufficient conditions for tractability in a general way by considering unlabeled tableau rules for a given modal logic. We work in the framework of coalgebraic logic as a unifying semantic setting. Apart from recovering known results for description logics such as EL and FL0, we obtain new ones for conjunctive fragments of relational and non-relational modal logics with greatest fixpoints. Most notably we find tractable fragments of game logic and the alternating-time mu-calculus.
User Interface Design for E-Learning Software
Venue: arXiv cs.CY 2014
Year: 2014

User interface (UI) is point of interaction between user and computer software. The success and failure of a software application depends on User Interface Design (UID). Possibility of using a software, easily using and learning are issues influenced by UID. The UI is significant in designing of educational software (e-Learning). Principles and concepts of learning should be considered in addition to UID principles in UID for e-learning. In this regard, to specify the logical relationship between education, learning, UID and multimedia at first we readdress the issues raised in previous studies. It is followed by examining the principle concepts of e-learning and UID. Then, we will see how UID contributes to e-learning through the educational software built by authors. Also we show the way of using UI to improve learning and motivating the learners and to improve the time efficiency of using e-learning software.
Predicting Multi-actor collaborations using Hypergraphs
Venue: arXiv cs.SI 2014
Year: 2014

Social networks are now ubiquitous and most of them contain interactions involving multiple actors (groups) like author collaborations, teams or emails in an organizations, etc. Hypergraphs are natural structures to effectively capture multi-actor interactions which conventional dyadic graphs fail to capture. In this work the problem of predicting collaborations is addressed while modeling the collaboration network as a hypergraph network. The problem of predicting future multi-actor collaboration is mapped to hyperedge prediction problem. Given that the higher order edge prediction is an inherently hard problem, in this work we restrict to the task of predicting edges (collaborations) that have already been observed in past. In this work, we propose a novel use of hyperincidence temporal tensors to capture time varying hypergraphs and provides a tensor decomposition based prediction algorithm. We quantitatively compare the performance of the hypergraphs based approach with the conventional dyadic graph based approach. Our hypothesis that hypergraphs preserve the information that simple graphs destroy is corroborated by experiments using author collaboration network from the DBLP dataset. Our results demonstrate the strength of hypergraph based approach to predict higher order collaborations (size>4) which is very difficult using dyadic graph based approach. Moreover, while predicting collaborations of size>2 hypergraphs in most cases provide better results with an average increase of approx. 45% in F-Score for different sizes = {3,4,5,6,7}.
Predicting Nearly As Well As the Optimal Twice Differentiable Regressor
Venue: arXiv cs.LG 2014
Year: 2014

We study nonlinear regression of real valued data in an individual sequence manner, where we provide results that are guaranteed to hold without any statistical assumptions. We address the convergence and undertraining issues of conventional nonlinear regression methods and introduce an algorithm that elegantly mitigates these issues via an incremental hierarchical structure, (i.e., via an incremental decision tree). Particularly, we present a piecewise linear (or nonlinear) regression algorithm that partitions the regressor space in a data driven manner and learns a linear model at each region. Unlike the conventional approaches, our algorithm gradually increases the number of disjoint partitions on the regressor space in a sequential manner according to the observed data. Through this data driven approach, our algorithm sequentially and asymptotically achieves the performance of the optimal twice differentiable regression function for any data sequence with an unknown and arbitrary length. The computational complexity of the introduced algorithm is only logarithmic in the data length under certain regularity conditions. We provide the explicit description of the algorithm and demonstrate the significant gains for the well-known benchmark real data sets and chaotic signals.
Zombie Politics: Evolutionary Algorithms to Counteract the Spread of Negative Opinions
Venue: arXiv cs.SI 2014
Year: 2014

This paper is about simulating the spread of opinions in a society and about finding ways to counteract that spread. To abstract away from potentially emotionally laden opinions, we instead simulate the spread of a zombie outbreak in a society. The virus causing this outbreak is different from traditional approaches: it not only causes a binary outcome (healthy vs infected) but rather a continuous outcome. To counteract the outbreak, a discrete number of infection-level specific treatments is available. This corresponds to acts of mild persuasion or the threats of legal action in the opinion spreading use case. This paper offers a genetic and a cultural algorithm that find the optimal mixture of treatments during the run of the simulation. They are assessed in a number of different scenarios. It is shown, that albeit far from being perfect, the cultural algorithm delivers superior performance at lower computational expense.
Toward Supervised Anomaly Detection
Venue: arXiv cs.LG 2014
Year: 2014

Anomaly detection is being regarded as an unsupervised learning task as anomalies stem from adversarial or unlikely events with unknown distributions. However, the predictive performance of purely unsupervised anomaly detection often fails to match the required detection rates in many tasks and there exists a need for labeled data to guide the model generation. Our first contribution shows that classical semi-supervised approaches, originating from a supervised classifier, are inappropriate and hardly detect new and unknown anomalies. We argue that semi-supervised anomaly detection needs to ground on the unsupervised learning paradigm and devise a novel algorithm that meets this requirement. Although being intrinsically non-convex, we further show that the optimization problem has a convex equivalent under relatively mild assumptions. Additionally, we propose an active learning strategy to automatically filter candidates for labeling. In an empirical study on network intrusion detection data, we observe that the proposed learning methodology requires much less labeled data than the state-of-the-art, while achieving higher detection accuracies.
A Robust Compressive Quantum State Tomography Algorithm Using ADMM
Venue: arXiv cs.IT 2014
Year: 2014

The possible state space dimension increases exponentially with respect to the number of qubits. This feature makes the quantum state tomography expensive and impractical for identifying the state of merely several qubits. The recent developed approach, compressed sensing, gives us an alternative to estimate the quantum state with fewer measurements. It is proved that the estimation then can be converted to a convex optimization problem with quantum mechanics constraints. In this paper we present an alternating augmented Lagrangian method for quantum convex optimization problem aiming for recovering pure or near pure quantum states corrupted by sparse noise given observables and the expectation values of the measurements. The proposed algorithm is much faster, robust to outlier noises (even very large for some entries) and can solve the reconstruction problem distributively. The simulations verify the superiority of the proposed algorithm and compare it to the conventional least square and compressive quantum tomography using Dantzig method.
Constructing Boolean Functions With Potential Optimal Algebraic Immunity Based on Additive Decompositions of Finite Fields
Venue: arXiv cs.CR 2014
Year: 2014

We propose a general approach to construct cryptographic significant Boolean functions of $(r+1)m$ variables based on the additive decomposition $\mathbb{F}_{2^{rm}}\times\mathbb{F}_{2^m}$ of the finite field $\mathbb{F}_{2^{(r+1)m}}$, where $r$ is odd and $m\geq3$. A class of unbalanced functions are constructed first via this approach, which coincides with a variant of the unbalanced class of generalized Tu-Deng functions in the case $r=1$. This class of functions have high algebraic degree, but their algebraic immunity does not exceeds $m$, which is impossible to be optimal when $r>1$. By modifying these unbalanced functions, we obtain a class of balanced functions which have optimal algebraic degree and high nonlinearity (shown by a lower bound we prove). These functions have optimal algebraic immunity provided a combinatorial conjecture on binary strings which generalizes the Tu-Deng conjecture is true. Computer investigations show that, at least for small values of number of variables, functions from this class also behave well against fast algebraic attacks.
Painting Analysis Using Wavelets and Probabilistic Topic Models
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, computer-based techniques for stylistic analysis of paintings are applied to the five panels of the 14th century Peruzzi Altarpiece by Giotto di Bondone. Features are extracted by combining a dual-tree complex wavelet transform with a hidden Markov tree (HMT) model. Hierarchical clustering is used to identify stylistic keywords in image patches, and keyword frequencies are calculated for sub-images that each contains many patches. A generative hierarchical Bayesian model learns stylistic patterns of keywords; these patterns are then used to characterize the styles of the sub-images; this in turn, permits to discriminate between paintings. Results suggest that such unsupervised probabilistic topic models can be useful to distill characteristic elements of style.