OpenRaiser/Intern-Atlas huggingface dataset:
n-Level Hypergraph Partitioning
Venue: arXiv cs.DS 2015
Year: 2015

We develop a multilevel algorithm for hypergraph partitioning that contracts the vertices one at a time and thus allows very high quality. This includes a rating function that avoids nonuniform vertex weights, an efficient "semi-dynamic" hypergraph data structure, a very fast coarsening algorithm, and two new local search algorithms. One is a $k$-way hypergraph adaptation of Fiduccia-Mattheyses local search and gives high quality at reasonable cost. The other is an adaptation of size-constrained label propagation to hypergraphs. Comparisons with hMetis and PaToH indicate that the new algorithm yields better quality over several benchmark sets and has a running time that is comparable to hMetis. Using label propagation local search is several times faster than hMetis and gives better quality than PaToH for a VLSI benchmark set.
Towards the Ontology Web Search Engine
Venue: arXiv cs.IR 2015
Year: 2015

The project of the Ontology Web Search Engine is presented in this paper. The main purpose of this paper is to develop such a project that can be easily implemented. Ontology Web Search Engine is software to look for and index ontologies in the Web. OWL (Web Ontology Languages) ontologies are meant, and they are necessary for the functioning of the SWES (Semantic Web Expert System). SWES is an expert system that will use found ontologies from the Web, generating rules from them, and will supplement its knowledge base with these generated rules. It is expected that the SWES will serve as a universal expert system for the average user.
Space-Time Galerkin Projection of Electro-Magnetic Fields
Venue: arXiv cs.CE 2015
Year: 2015

Spatial Galerkin projection transfers fields between different meshes. In the area of finite element analysis of electromagnetic fields, it provides great convenience for remeshing, multi-physics, domain decomposition methods, etc. In this paper, a space-time Galerkin projection is developed in order to transfer fields between different spatial and temporal discretization bases.
Empirical Evaluation of Rectified Activations in Convolutional Network
Venue: arXiv cs.LG 2015
Year: 2015

In this paper we investigate the performance of different types of rectified activation functions in convolutional neural network: standard rectified linear unit (ReLU), leaky rectified linear unit (Leaky ReLU), parametric rectified linear unit (PReLU) and a new randomized leaky rectified linear units (RReLU). We evaluate these activation function on standard image classification task. Our experiments suggest that incorporating a non-zero slope for negative part in rectified activation units could consistently improve the results. Thus our findings are negative on the common belief that sparsity is the key of good performance in ReLU. Moreover, on small scale dataset, using deterministic negative slope or learning it are both prone to overfitting. They are not as effective as using their randomized counterpart. By using RReLU, we achieved 75.68\% accuracy on CIFAR-100 test set without multiple test or ensemble.
Informational parasites in code evolution
Venue: arXiv cs.MA 2015
Year: 2015

In a previous study, we considered an information-theoretic model of code evolution. In it, agents obtain information about their (common) environment by the perception of messages of other agents, which is determined by an interaction probability (the structure of the population). For an agent to understand another agent's messages, the former must either know the identity of the latter, or the code producing the messages must be universally interpretable. A universal code, however, introduces a vulnerability: a parasitic entity can take advantage of it. Here, we investigate this problem. In our specific setting, we consider a parasite to be an agent that tries to inflict as much damage as possible in the mutual understanding of the population (i.e. the parasite acts as a disinformation agent). We show that, after introducing a parasite in the population, the former adopts a code such that it captures the information about the environment that is missing in the population. Such agent would be of great value, but only if the rest of the population could understand its messages. However, it is of little use here, since the parasite utilises the most common messages in the population to express different concepts. Now we let the population respond by updating their codes such that, in this arms race, they again maximise their mutual understanding. As a result, there is a code drift in the population where the utilisation of the messages of the parasite is avoided. A consequence of this is that the information that the parasite possesses but the agents lack becomes understandable and readily available.
Scraping and Clustering Techniques for the Characterization of Linkedin Profiles
Venue: arXiv cs.SI 2015
Year: 2015

The socialization of the web has undertaken a new dimension after the emergence of the Online Social Networks (OSN) concept. The fact that each Internet user becomes a potential content creator entails managing a big amount of data. This paper explores the most popular professional OSN: LinkedIn. A scraping technique was implemented to get around 5 Million public profiles. The application of natural language processing techniques (NLP) to classify the educational background and to cluster the professional background of the collected profiles led us to provide some insights about this OSN's users and to evaluate the relationships between educational degrees and professional careers.
Counterexample Guided Synthesis of Switched Controllers for Reach-While-Stay Properties
Venue: arXiv cs.SY 2015
Year: 2015

We introduce a counter-example guided inductive synthesis (CEGIS) framework for synthesizing continuous-time switching controllers that guarantee reach while stay (RWS) properties of the closed loop system. The solution is based on synthesizing specially defined class of control Lyapunov functions (CLFs) for switched systems, that yield switching controllers with a guaranteed minimum dwell time in each mode. Next, we use a CEGIS-based approach to iteratively solve the resulting quantified exists-forall constraints, and find a CLF. We introduce relaxations to guarantee termination, as well as heuristics to increase convergence speed. Finally, we evaluate our approach on a set of benchmarks ranging from two to six state variables. Our evaluation includes a preliminary comparison with related tools. The proposed approach shows the promise of nonlinear SMT solvers for the synthesis of provably correct switching control laws.
Joint Interference Alignment and Bi-Directional Scheduling for MIMO Two-Way Multi-Link Networks
Venue: arXiv cs.IT 2015
Year: 2015

By means of the emerging technique of dynamic Time Division Duplex (TDD), the switching point between uplink and downlink transmissions can be optimized across a multi-cell system in order to reduce the impact of inter-cell interference. It has been recently recognized that optimizing also the order in which uplink and downlink transmissions, or more generally the two directions of a two-way link, are scheduled can lead to significant benefits in terms of interference reduction. In this work, the optimization of bi-directional scheduling is investigated in conjunction with the design of linear precoding and equalization for a general multi-link MIMO two-way system. A simple algorithm is proposed that performs the joint optimization of the ordering of the transmissions in the two directions of the two-way links and of the linear transceivers, with the aim of minimizing the interference leakage power. Numerical results demonstrate the effectiveness of the proposed strategy.
Cats & Co: Categorical Time Series Coclustering
Venue: arXiv cs.DB 2015
Year: 2015

We suggest a novel method of clustering and exploratory analysis of temporal event sequences data (also known as categorical time series) based on three-dimensional data grid models. A data set of temporal event sequences can be represented as a data set of three-dimensional points, each point is defined by three variables: a sequence identifier, a time value and an event value. Instantiating data grid models to the 3D-points turns the problem into 3D-coclustering. The sequences are partitioned into clusters, the time variable is discretized into intervals and the events are partitioned into clusters. The cross-product of the univariate partitions forms a multivariate partition of the representation space, i.e., a grid of cells and it also represents a nonparametric estimator of the joint distribution of the sequences, time and events dimensions. Thus, the sequences are grouped together because they have similar joint distribution of time and events, i.e., similar distribution of events along the time dimension. The best data grid is computed using a parameter-free Bayesian model selection approach. We also suggest several criteria for exploiting the resulting grid through agglomerative hierarchies, for interpreting the clusters of sequences and characterizing their components through insightful visualizations. Extensive experiments on both synthetic and real-world data sets demonstrate that data grid models are efficient, effective and discover meaningful underlying patterns of categorical time series data.
Exploiting Known Interference as Green Signal Power for Downlink Beamforming Optimization
Venue: arXiv cs.IT 2015
Year: 2015

We propose a data-aided transmit beamforming scheme for the multi-user multiple-input-single-output (MISO) downlink channel. While conventional beamforming schemes aim at the minimization of the transmit power subject to suppressing interference to guarantee quality of service (QoS) constraints, here we use the knowledge of both data and channel state information (CSI) at the transmitter to exploit, rather than suppress, constructive interference. More specifically, we design a new precoding scheme for the MISO downlink that minimizes the transmit power for generic phase shift keying (PSK) modulated signals. The proposed precoder reduces the transmit power compared to conventional schemes, by adapting the QoS constraints to accommodate constructive interference as a source of useful signal power. By exploiting the power of constructively interfering symbols, the proposed scheme achieves the required QoS at lower transmit power. We extend this concept to the signal to interference plus noise ratio (SINR) balancing problem, where higher SINR values compared to the conventional SINR balancing optimization are achieved for given transmit power budgets. In addition, we derive equivalent virtual multicast formulations for both optimizations, both of which provide insights of the optimal solution and facilitate the design of a more efficient solver. Finally, we propose a robust beamforming technique to deal with imperfect CSI, that also reduces the transmit power over conventional techniques, while guaranteeing the required QoS. Our simulation and analysis show significant power savings for small scale MISO downlink channels with the proposed data-aided optimization compared to conventional beamforming optimization.
Applying FCA toolbox to Software Testing
Venue: arXiv cs.SE 2015
Year: 2015

Software testing uses wide range of different tools to enhance the complicated process of defining quality of the system under test. Formal Concept Analysis (FCA) provides us with algorithms of deriving formal ontology from a set of objects and their attributes. With the use of FCA we can considerably improve the efficiency of test case derivation. Moreover, an FCA-based machine learning system supports the analysis of regression testing results.
The second Feng-Rao number for codes coming from inductive semigroups
Venue: arXiv cs.IT 2015
Year: 2015

The second Feng-Rao number of every inductive numerical semigroup is explicitly computed. This number determines the asymptotical behaviour of the order bound for the second Hamming weight of one-point AG codes. In particular, this result is applied for the codes defined by asymptotically good towers of function fields whose Weierstrass semigroups are inductive. In addition, some properties of inductive numerical semigroups are studied, the involved Apéry sets are computed in a recursive way, and some tests to check whether a given numerical semigroups is inductive or not are provided.
Secrecy Energy Efficiency Optimization for MISO and SISO Communication Networks
Venue: arXiv cs.IT 2015
Year: 2015

Energy-efficiency, high data rates and secure communications are essential requirements of the future wireless networks. In this paper, optimizing the secrecy energy efficiency is considered. The optimal beamformer is designed for a MISO system with and without considering the minimum required secrecy rate. Further, the optimal power control in a SISO system is carried out using an efficient iterative method, and this is followed by analyzing the trade-off between the secrecy energy efficiency and the secrecy rate for both MISO and SISO systems.
Maximum Matching in Turnstile Streams
Venue: arXiv cs.DS 2015
Year: 2015

We consider the unweighted bipartite maximum matching problem in the one-pass turnstile streaming model where the input stream consists of edge insertions and deletions. In the insertion-only model, a one-pass $2$-approximation streaming algorithm can be easily obtained with space $O(n \log n)$, where $n$ denotes the number of vertices of the input graph. We show that no such result is possible if edge deletions are allowed, even if space $O(n^{3/2-δ})$ is granted, for every $δ> 0$. Specifically, for every $0 \le ε\le 1$, we show that in the one-pass turnstile streaming model, in order to compute a $O(n^ε)$-approximation, space $Ω(n^{3/2 - 4ε})$ is required for constant error randomized algorithms, and, up to logarithmic factors, space $O( n^{2-2ε} )$ is sufficient. Our lower bound result is proved in the simultaneous message model of communication and may be of independent interest.
Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence
Venue: arXiv cs.LG 2015
Year: 2015

Data in the form of pairwise comparisons arises in many domains, including preference elicitation, sporting competitions, and peer grading among others. We consider parametric ordinal models for such pairwise comparison data involving a latent vector $w^* \in \mathbb{R}^d$ that represents the "qualities" of the $d$ items being compared; this class of models includes the two most widely used parametric models--the Bradley-Terry-Luce (BTL) and the Thurstone models. Working within a standard minimax framework, we provide tight upper and lower bounds on the optimal error in estimating the quality score vector $w^*$ under this class of models. The bounds depend on the topology of the comparison graph induced by the subset of pairs being compared via its Laplacian spectrum. Thus, in settings where the subset of pairs may be chosen, our results provide principled guidelines for making this choice. Finally, we compare these error rates to those under cardinal measurement models and show that the error rates in the ordinal and cardinal settings have identical scalings apart from constant pre-factors.
Fast List Decoders for Polar Codes
Venue: arXiv cs.IT 2015
Year: 2015

Polar codes asymptotically achieve the symmetric capacity of memoryless channels, yet their error-correcting performance under successive-cancellation (SC) decoding for short and moderate length codes is worse than that of other modern codes such as low-density parity-check (LDPC) codes. Of the many methods to improve the error-correction performance of polar codes, list decoding yields the best results, especially when the polar code is concatenated with a cyclic redundancy check (CRC). List decoding involves exploring several decoding paths with SC decoding, and therefore tends to be slower than SC decoding itself, by an order of magnitude in practical implementations. In this paper, we present a new algorithm based on unrolling the decoding tree of the code that improves the speed of list decoding by an order of magnitude when implemented in software. Furthermore, we show that for software-defined radio applications, our proposed algorithm is faster than the fastest software implementations of LDPC decoders in the literature while offering comparable error-correction performance at similar or shorter code lengths.
Data Fusion of Objects Using Techniques Such as Laser Scanning, Structured Light and Photogrammetry for Cultural Heritage Applications
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we present a semi-automatic 2D-3D local registration pipeline capable of coloring 3D models obtained from 3D scanners by using uncalibrated images. The proposed pipeline exploits the Structure from Motion (SfM) technique in order to reconstruct a sparse representation of the 3D object and obtain the camera parameters from image feature matches. We then coarsely register the reconstructed 3D model to the scanned one through the Scale Iterative Closest Point (SICP) algorithm. SICP provides the global scale, rotation and translation parameters, using minimal manual user intervention. In the final processing stage, a local registration refinement algorithm optimizes the color projection of the aligned photos on the 3D object removing the blurring/ghosting artefacts introduced due to small inaccuracies during the registration. The proposed pipeline is capable of handling real world cases with a range of characteristics from objects with low level geometric features to complex ones.
Integrating K-means with Quadratic Programming Feature Selection
Venue: arXiv cs.CV 2015
Year: 2015

Several data mining problems are characterized by data in high dimensions. One of the popular ways to reduce the dimensionality of the data is to perform feature selection, i.e, select a subset of relevant and non-redundant features. Recently, Quadratic Programming Feature Selection (QPFS) has been proposed which formulates the feature selection problem as a quadratic program. It has been shown to outperform many of the existing feature selection methods for a variety of applications. Though, better than many existing approaches, the running time complexity of QPFS is cubic in the number of features, which can be quite computationally expensive even for moderately sized datasets. In this paper we propose a novel method for feature selection by integrating k-means clustering with QPFS. The basic variant of our approach runs k-means to bring down the number of features which need to be passed on to QPFS. We then enhance this idea, wherein we gradually refine the feature space from a very coarse clustering to a fine-grained one, by interleaving steps of QPFS with k-means clustering. Every step of QPFS helps in identifying the clusters of irrelevant features (which can then be thrown away), whereas every step of k-means further refines the clusters which are potentially relevant. We show that our iterative refinement of clusters is guaranteed to converge. We provide bounds on the number of distance computations involved in the k-means algorithm. Further, each QPFS run is now cubic in number of clusters, which can be much smaller than actual number of features. Experiments on eight publicly available datasets show that our approach gives significant computational gains (both in time and memory), over standard QPFS as well as other state of the art feature selection methods, even while improving the overall accuracy.
Kernelization via Sampling with Applications to Dynamic Graph Streams
Venue: arXiv cs.DS 2015
Year: 2015

In this paper we present a simple but powerful subgraph sampling primitive that is applicable in a variety of computational models including dynamic graph streams (where the input graph is defined by a sequence of edge/hyperedge insertions and deletions) and distributed systems such as MapReduce. In the case of dynamic graph streams, we use this primitive to prove the following results: -- Matching: First, there exists an $\tilde{O}(k^2)$ space algorithm that returns an exact maximum matching on the assumption the cardinality is at most $k$. The best previous algorithm used $\tilde{O}(kn)$ space where $n$ is the number of vertices in the graph and we prove our result is optimal up to logarithmic factors. Our algorithm has $\tilde{O}(1)$ update time. Second, there exists an $\tilde{O}(n^2/α^3)$ space algorithm that returns an $α$-approximation for matchings of arbitrary size. (Assadi et al. (2015) showed that this was optimal and independently and concurrently established the same upper bound.) We generalize both results for weighted matching. Third, there exists an $\tilde{O}(n^{4/5})$ space algorithm that returns a constant approximation in graphs with bounded arboricity. -- Vertex Cover and Hitting Set: There exists an $\tilde{O}(k^d)$ space algorithm that solves the minimum hitting set problem where $d$ is the cardinality of the input sets and $k$ is an upper bound on the size of the minimum hitting set. We prove this is optimal up to logarithmic factors. Our algorithm has $\tilde{O}(1)$ update time. The case $d=2$ corresponds to minimum vertex cover. Finally, we consider a larger family of parameterized problems (including $b$-matching, disjoint paths, vertex coloring among others) for which our subgraph sampling primitive yields fast, small-space dynamic graph stream algorithms. We then show lower bounds for natural problems outside this family.
On the Minimum Labelling Spanning bi-Connected Subgraph problem
Venue: arXiv cs.DS 2015
Year: 2015

We introduce the minimum labelling spanning bi-connected subgraph problem (MLSBP) replacing connectivity by bi-connectivity in the well known minimum labelling spanning tree problem (MLSTP). A graph is bi-connected if, for every two vertices, there are, at least, two vertex-disjoint paths joining them. The problem consists in finding the spanning bi-connected subgraph or block with minimum set of labels. We adapt the exact method of the MLSTP to solve the MLSTB and the basic greedy constructive heuristic, the maximum vertex covering algorithm (MVCA). This proce- dure is a basic component in the application of metaheuristics to solve the problem.
Indoor Positioning in High Speed OFDM Visible Light Communications
Venue: arXiv cs.IT 2015
Year: 2015

Visible Light Communication (VLC) technology using light emitting diodes (LEDs) has been gaining increasing attention in recent years as it is appealing for a wide range of applications such as indoor positioning. Orthogonal frequency division multiplexing (OFDM) has been applied to indoor wireless optical communications in order to mitigate the effect of multipath distortion of the optical channel as well as increasing data rate. In this paper, we investigate the indoor positioning accuracy of optical based OFDM techniques used in VLC systems. A positioning algorithm based on power attenuation is used to estimate the receiver coordinates. We further calculate the positioning errors in all the locations of a room and compare them with those of single carrier modulation scheme, i.e., on-off keying (OOK) modulation. We demonstrate that OFDM positioning system outperforms its conventional counterpart.