OpenRaiser/Intern-Atlas huggingface dataset:
On the Genericity of Maximum Rank Distance and Gabidulin Codes
Venue: arXiv cs.IT 2016
Year: 2016

We consider linear rank-metric codes in $\mathbb F_{q^m}^n$. We show that the properties of being MRD (maximum rank distance) and non-Gabidulin are generic over the algebraic closure of the underlying field, which implies that over a large extension field a randomly chosen generator matrix generates an MRD and a non-Gabidulin code with high probability. Moreover, we give upper bounds on the respective probabilities in dependence on the extension degree $m$.
Spectrum Resource Management and Interference Mitigation for D2D Communications with Awareness of BER Constraint in mmWave 5G Underlay Network
Venue: arXiv cs.NI 2016
Year: 2016

The work presented in this paper deals with the issue of massive demands for higher capacity. For that matter, we investigate the spectrum resource management in outdoor mmWave cell for the uplink of cellular and D2D communications. Indeed, we provide a first insight how to optimize the system performance in terms of achievable throughput while realizing a compromise between the large number of admitted devices and the generated interference constraint. We propose a mathematical formulation of the optimization objective which falls in the mixed integer-real optimization scheme. To overcome its complexity, we apply a heuristic algorithm and test its efficiency through simulation results with a particular regard to the BER impact in the QoS.
Health Figures: An Open Source JavaScript Library for Health Data Visualization
Venue: arXiv cs.HC 2016
Year: 2016

The way we look at data has a great impact on how we can understand it, particularly when the data is related to health and wellness. Due to the increased use of self-tracking devices and the ongoing shift towards preventive medicine, better understanding of our health data is an important part of improving the general welfare of the citizens. Electronic Health Records, self-tracking devices and mobile applications provide a rich variety of data but it often becomes difficult to understand. We implemented the hFigures library inspired on the hGraph visualization with additional improvements. The purpose of the library is to provide a visual representation of the evolution of health measurements in a complete and useful manner. We researched the usefulness and usability of the library by building an application for health data visualization in a health coaching program. We performed a user evaluation with Heuristic Evaluation, Controlled User Testing and Usability Questionnaires. In the Heuristics Evaluation the average response was 6.3 out of 7 points and the Cognitive Walkthrough done by usability experts indicated no design or mismatch errors. In the CSUQ usability test the system obtained an average score of 6.13 out of 7, and in the ASQ usability test the overall satisfaction score was 6.64 out of 7. We developed hFigures, an open source library for visualizing a complete, accurate and normalized graphical representation of health data. The idea is based on the concept of the hGraph but it provides additional key features, including a comparison of multiple health measurements over time. We conducted a usability evaluation of the library as a key component of an application for health and wellness monitoring. The results indicate that the data visualization library was helpful in assisting users in understanding health data and its evolution over time.
On the Equivalence of Maximum SNR and MMSE Estimation: Applications to Additive Non-Gaussian Channels and Quantized Observations
Venue: arXiv cs.IT 2016
Year: 2016

The minimum mean-squared error (MMSE) is one of the most popular criteria for Bayesian estimation. Conversely, the signal-to-noise ratio (SNR) is a typical performance criterion in communications, radar, and generally detection theory. In this paper we first formalize an SNR criterion to design an estimator, and then we prove that there exists an equivalence between MMSE and maximum-SNR estimators, for any statistics. We also extend this equivalence to specific classes of suboptimal estimators, which are expressed by a basis expansion model (BEM). Then, by exploiting an orthogonal BEM for the estimator, we derive the MMSE estimator constrained to a given quantization resolution of the noisy observations, and we prove that this suboptimal MMSE estimator tends to the optimal MMSE estimator that uses an infinite resolution of the observation. Besides, we derive closed-form expressions for the mean-squared error (MSE) and for the SNR of the proposed suboptimal estimators, and we show that these expressions constitute tight, asymptotically exact, bounds for the optimal MMSE and maximum SNR.
AMSOM: Adaptive Moving Self-organizing Map for Clustering and Visualization
Venue: arXiv cs.AI 2016
Year: 2016

Self-Organizing Map (SOM) is a neural network model which is used to obtain a topology-preserving mapping from the (usually high dimensional) input/feature space to an output/map space of fewer dimensions (usually two or three in order to facilitate visualization). Neurons in the output space are connected with each other but this structure remains fixed throughout training and learning is achieved through the updating of neuron reference vectors in feature space. Despite the fact that growing variants of SOM overcome the fixed structure limitation they increase computational cost and also do not allow the removal of a neuron after its introduction. In this paper, a variant of SOM is proposed called AMSOM (Adaptive Moving Self-Organizing Map) that on the one hand creates a more flexible structure where neuron positions are dynamically altered during training and on the other hand tackles the drawback of having a predefined grid by allowing neuron addition and/or removal during training. Experiments using multiple literature datasets show that the proposed method improves training performance of SOM, leads to a better visualization of the input dataset and provides a framework for determining the optimal number and structure of neurons.
As Cool as a Cucumber: Towards a Corpus of Contemporary Similes in Serbian
Venue: arXiv cs.CL 2016
Year: 2016

Similes are natural language expressions used to compare unlikely things, where the comparison is not taken literally. They are often used in everyday communication and are an important part of cultural heritage. Having an up-to-date corpus of similes is challenging, as they are constantly coined and/or adapted to the contemporary times. In this paper we present a methodology for semi-automated collection of similes from the world wide web using text mining techniques. We expanded an existing corpus of traditional similes (containing 333 similes) by collecting 446 additional expressions. We, also, explore how crowdsourcing can be used to extract and curate new similes.
Asymptotic analysis of threshold models for social networks
Venue: arXiv cs.SI 2016
Year: 2016

A class of dynamic threshold models is proposed, for describing the upset of collective actions in social networks. The agents of the network have to decide whether to undertake a certain action or not. They make their decision by comparing the activity level of their neighbors with a time-varying threshold, evolving according to a time-invariant opinion dynamic model. Key features of the model are a parameter representing the degree of self-confidence of the agents, and the mechanism adopted by the agents to evaluate the activity level of their neighbors. The case in which a radical agent, initially eager to undertake the action, interacts with a group of ordinary agents, is considered. The main contribution of the paper is the complete analytic characterization of the asymptotic behaviors of the network, for three different graph topologies. The asymptotic activity patterns are determined as a function of the self-confidence parameter and of the initial threshold of the ordinary agents.
Superpixel Hierarchy
Venue: arXiv cs.CV 2016
Year: 2016

Superpixel segmentation is becoming ubiquitous in computer vision. In practice, an object can either be represented by a number of segments in finer levels of detail or included in a surrounding region at coarser levels of detail, and thus a superpixel segmentation hierarchy is useful for applications that require different levels of image segmentation detail depending on the particular image objects segmented. Unfortunately, there is no method that can generate all scales of superpixels accurately in real-time. As a result, a simple yet effective algorithm named Super Hierarchy (SH) is proposed in this paper. It is as accurate as the state-of-the-art but 1-2 orders of magnitude faster. The proposed method can be directly integrated with recent efficient edge detectors like the structured forest edges to significantly outperforms the state-of-the-art in terms of segmentation accuracy. Quantitative and qualitative evaluation on a number of computer vision applications was conducted, demonstrating that the proposed method is the top performer.
Games from Basic Data Structures
Venue: arXiv cs.DS 2016
Year: 2016

In this paper, we consider combinatorial game rulesets based on data structures normally covered in an undergraduate Computer Science Data Structures course: arrays, stacks, queues, priority queues, sets, linked lists, and binary trees. We describe many rulesets as well as computational and mathematical properties about them. Two of the rulesets, Tower Nim and Myopic Col, are new. We show polynomial-time solutions to Tower Nim and to Myopic Col on paths.
Dealing with Big Data
Venue: arXiv cs.CY 2016
Year: 2016

This book chapter attempts to counter anxieties in the humanities and social science about the role of big data in research by focusing on approaches which, by being firmly grounded in the traditional values of disciplines, enhance existing methods to produce fruitful research. Big data poses many methodological challenges, but these pressures should prompt scholars to pay much closer attention to methodological issues than they have in the past.
Bayesian Hyperparameter Optimization for Ensemble Learning
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we bridge the gap between hyperparameter optimization and ensemble learning by performing Bayesian optimization of an ensemble with regards to its hyperparameters. Our method consists in building a fixed-size ensemble, optimizing the configuration of one classifier of the ensemble at each iteration of the hyperparameter optimization algorithm, taking into consideration the interaction with the other models when evaluating potential performances. We also consider the case where the ensemble is to be reconstructed at the end of the hyperparameter optimization phase, through a greedy selection over the pool of models generated during the optimization. We study the performance of our proposed method on three different hyperparameter spaces, showing that our approach is better than both the best single model and a greedy ensemble construction over the models produced by a standard Bayesian optimization.
Simple DRAM and Virtual Memory Abstractions to Enable Highly Efficient Memory Systems
Venue: arXiv cs.AR 2016
Year: 2016

In most modern systems, the memory subsystem is managed and accessed at multiple different granularities at various resources. We observe that such multi-granularity management results in significant inefficiency in the memory subsystem. Specifically, we observe that 1) page-granularity virtual memory unnecessarily triggers large memory operations, and 2) existing cache-line granularity memory interface is inefficient for performing bulk data operations and operations that exhibit poor spatial locality. To address these problems, we present a series of techniques in this thesis. First, we propose page overlays, a framework augments the existing virtual memory framework with the ability to track a new version of a subset of cache lines within each virtual page. We show that this extension is powerful by demonstrating its benefits on a number of applications. Second, we show that DRAM can be used to perform more complex operations than just store data. We propose RowClone, a mechanism to perform bulk data copy and initialization completely inside DRAM, and Buddy RAM, a mechanism to perform bulk bitwise operations using DRAM. Both these techniques achieve an order-of-magnitude improvement in the efficiency of the respective operations. Third, we propose Gather-Scatter DRAM, a technique that exploits DRAM organization to effectively gather/scatter values with a power-of-2 strided access patterns. For these access patterns, GS-DRAM achieves near-ideal bandwidth and cache utilization, without increasing the latency of fetching data from memory. Finally, we propose the Dirty-Block Index, a new way of tracking dirty blocks. In addition to improving the efficiency of bulk data coherence, DBI has several applications including high-performance memory scheduling, efficient cache lookup bypassing, and enabling heterogeneous ECC.
Bot or Not? Deciphering Time Maps for Tweet Interarrivals
Venue: arXiv cs.SI 2016
Year: 2016

This exploratory study used the R Statistical Software to perform Monte Carlo simulation of time maps, which characterize events based on the elapsed time since the last event and the time that will transpire until the next event, and compare them to time maps from real Twitter users. Time maps are used to explore differences in the interarrival patterns of Tweets between human users, humans who use scheduling services like TweetDeck and HootSuite, and non-human (bot) users. The results indicate that there are differences between the tweet interarrival patterns across these categories of users, and that time maps could potentially be used to automate the detection of bot accounts on Twitter. This could enhance social media intelligence capabilities, help bot developers build more human-like Twitter bots to avoid detection, or both.
Double-Sided Energy Auction Equilibrium Under Price Anticipation
Venue: arXiv cs.GT 2016
Year: 2016

This paper investigates the problem of proportionally fair double sided energy auction involving buying and selling agents. The grid is assumed to be operating under islanded mode. A distributed auction algorithm that can be implemented by an aggregator, as well as a possible approach by which the agents may approximate price anticipation is considered. Equilibrium conditions arising due to price anticipation is analyzed. A modified auction to mitigate the resulting loss in efficiency due to such behavior is suggested. This modified auction allows the aggregate social welfare of the agents to be arbitrarily close to that attainable with price taking agents. Next, equilibrium conditions when the aggregator collects a surcharge price per unit of energy traded is examined. A biobjective optimization problem is identified that takes into account both the agents social welfare as well as the aggregator revenue from the surcharge. Results of extensive simulations, which corroborate the theoretical analysis, are reported.
Complexity of Prefix-Convex Regular Languages
Venue: arXiv cs.FL 2016
Year: 2016

A language $L$ over an alphabet $Σ$ is prefix-convex if, for any words $x,y,z\inΣ^*$, whenever $x$ and $xyz$ are in $L$, then so is $xy$. Prefix-convex languages include right-ideal, prefix-closed, and prefix-free languages. We study complexity properties of prefix-convex regular languages. In particular, we find the quotient/state complexity of boolean operations, product (concatenation), star, and reversal, the size of the syntactic semigroup, and the quotient complexity of atoms. For binary operations we use arguments with different alphabets when appropriate; this leads to higher tight upper bounds than those obtained with equal alphabets. We exhibit most complex prefix-convex languages that meet the complexity bounds for all the measures listed above.
Learning From Hidden Traits: Joint Factor Analysis and Latent Clustering
Venue: arXiv cs.LG 2016
Year: 2016

Dimensionality reduction techniques play an essential role in data analytics, signal processing and machine learning. Dimensionality reduction is usually performed in a preprocessing stage that is separate from subsequent data analysis, such as clustering or classification. Finding reduced-dimension representations that are well-suited for the intended task is more appealing. This paper proposes a joint factor analysis and latent clustering framework, which aims at learning cluster-aware low-dimensional representations of matrix and tensor data. The proposed approach leverages matrix and tensor factorization models that produce essentially unique latent representations of the data to unravel latent cluster structure -- which is otherwise obscured because of the freedom to apply an oblique transformation in latent space. At the same time, latent cluster structure is used as prior information to enhance the performance of factorization. Specific contributions include several custom-built problem formulations, corresponding algorithms, and discussion of associated convergence properties. Besides extensive simulations, real-world datasets such as Reuters document data and MNIST image data are also employed to showcase the effectiveness of the proposed approaches.
Complementary Dual Subfield Linear Codes Over Finite Fields
Venue: arXiv cs.IT 2016
Year: 2016

Two families of complementary codes over finite fields $\mathbb{F}_q$ are studied, where $q=r^2$ is square: i) Hermitian complementary dual linear codes, and ii) trace Hermitian complementary dual subfield linear codes. Necessary and sufficient conditions for a linear code (resp., a subfield linear code) to be Hermitian complementary dual (resp., trace Hermitian complementary dual) are determined. Constructions of such codes are given together their parameters. Some illustrative examples are provided as well.
Orion: Enabling Suggestions in a Visual Query Builder for Ultra-Heterogeneous Graphs
Venue: arXiv cs.DB 2016
Year: 2016

The database community has long recognized the importance of graphical query interface to the usability of data management systems. Yet, relatively less has been done. We present Orion, a visual interface for querying ultra-heterogeneous graphs. It iteratively assists users in query graph construction by making suggestions via machine learning methods. In its active mode, Orion automatically suggests top-k edges to be added to a query graph. In its passive mode, the user adds a new edge manually, and Orion suggests a ranked list of labels for the edge. Orion's edge ranking algorithm, Random Decision Paths (RDP), makes use of a query log to rank candidate edges by how likely they will match the user's query intent. Extensive user studies using Freebase demonstrated that Orion users have a 70% success rate in constructing complex query graphs, a significant improvement over the 58% success rate by the users of a baseline system that resembles existing visual query builders. Furthermore, using active mode only, the RDP algorithm was compared with several methods adapting other machine learning algorithms such as random forests and naive Bayes classifier, as well as class association rules and recommendation systems based on singular value decomposition. On average, RDP required 40 suggestions to correctly reach a target query graph (using only its active mode of suggestion) while other methods required 1.5--4 times as many suggestions.
Mask-CNN: Localizing Parts and Selecting Descriptors for Fine-Grained Image Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Fine-grained image recognition is a challenging computer vision problem, due to the small inter-class variations caused by highly similar subordinate categories, and the large intra-class variations in poses, scales and rotations. In this paper, we propose a novel end-to-end Mask-CNN model without the fully connected layers for fine-grained recognition. Based on the part annotations of fine-grained images, the proposed model consists of a fully convolutional network to both locate the discriminative parts (e.g., head and torso), and more importantly generate object/part masks for selecting useful and meaningful convolutional descriptors. After that, a four-stream Mask-CNN model is built for aggregating the selected object- and part-level descriptors simultaneously. The proposed Mask-CNN model has the smallest number of parameters, lowest feature dimensionality and highest recognition accuracy when compared with state-of-the-arts fine-grained approaches.
Distributed Local Multi-Aggregation and Centrality Approximation
Venue: arXiv cs.DC 2016
Year: 2016

We study local aggregation and graph analysis in distributed environments using the message passing model. We provide a flexible framework, where each of the nodes in a set $S$--which is a subset of all nodes in the network--can perform a large range of common aggregation functions in its $k$-neighborhood. We study this problem in the CONGEST model, where in each synchronous round, every node can transmit a different (but short) message to each of its neighbors. While the $k$-neighborhoods of nodes in $S$ might overlap and aggregation could cause congestion in this model, we present an algorithm that needs time $O(|S|+k)$ even when each of the nodes in $S$ performs a different aggregation on its $k$-neighborhood. The framework is not restricted to aggregation-trees such that it can be used for more advanced graph analysis. We demonstrate this by providing efficient approximations of centrality measures and approximation of minimum routing cost trees.
Bridging Category-level and Instance-level Semantic Image Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

We propose an approach to instance-level image segmentation that is built on top of category-level segmentation. Specifically, for each pixel in a semantic category mask, its corresponding instance bounding box is predicted using a deep fully convolutional regression network. Thus it follows a different pipeline to the popular detect-then-segment approaches that first predict instances' bounding boxes, which are the current state-of-the-art in instance segmentation. We show that, by leveraging the strength of our state-of-the-art semantic segmentation models, the proposed method can achieve comparable or even better results to detect-then-segment approaches. We make the following contributions. (i) First, we propose a simple yet effective approach to semantic instance segmentation. (ii) Second, we propose an online bootstrapping method during training, which is critically important for achieving good performance for both semantic category segmentation and instance-level segmentation. (iii) As the performance of semantic category segmentation has a significant impact on the instance-level segmentation, which is the second step of our approach, we train fully convolutional residual networks to achieve the best semantic category segmentation accuracy. On the PASCAL VOC 2012 dataset, we obtain the currently best mean intersection-over-union score of 79.1%. (iv) We also achieve state-of-the-art results for instance-level segmentation.