OpenRaiser/Intern-Atlas huggingface dataset:
Large-Scale Spectrum Allocation for Cellular Networks via Sparse Optimization
Venue: arXiv cs.IT 2018
Year: 2018

This paper studies joint spectrum allocation and user association in large heterogeneous cellular networks. The objective is to maximize some network utility function based on given traffic statistics collected over a slow timescale, conceived to be seconds to minutes. A key challenge is scalability: interference across cells creates dependencies across the entire network, making the optimization problem computationally challenging as the size of the network becomes large. A suboptimal solution is presented, which performs well in networks consisting of one hundred access points (APs) serving several hundred user devices. This is achieved by optimizing over local overlapping neighborhoods, defined by interference conditions, and by exploiting the sparsity of a globally optimal solution. Specifically, with a total of $k$ user devices in the entire network, it suffices to divide the spectrum into $k$ segments, where each segment is mapped to a particular set, or pattern, of active APs within each local neighborhood. The problem is then to find a mapping of segments to patterns, and to optimize the widths of the segments. A convex relaxation is proposed for this, which relies on a re-weighted $\ell_1$ approximation of an $\ell_0$ constraint, and is used to enforce the mapping of a unique pattern to each spectrum segment. A distributed implementation based on alternating direction method of multipliers (ADMM) is also proposed. Numerical comparisons with benchmark schemes show that the proposed method achieves a substantial increase in achievable throughput and/or reduction in the average packet delay.
Sample Complexity of Nonparametric Semi-Supervised Learning
Venue: arXiv cs.LG 2018
Year: 2018

We study the sample complexity of semi-supervised learning (SSL) and introduce new assumptions based on the mismatch between a mixture model learned from unlabeled data and the true mixture model induced by the (unknown) class conditional distributions. Under these assumptions, we establish an $Ω(K\log K)$ labeled sample complexity bound without imposing parametric assumptions, where $K$ is the number of classes. Our results suggest that even in nonparametric settings it is possible to learn a near-optimal classifier using only a few labeled samples. Unlike previous theoretical work which focuses on binary classification, we consider general multiclass classification ($K>2$), which requires solving a difficult permutation learning problem. This permutation defines a classifier whose classification error is controlled by the Wasserstein distance between mixing measures, and we provide finite-sample results characterizing the behaviour of the excess risk of this classifier. Finally, we describe three algorithms for computing these estimators based on a connection to bipartite graph matching, and perform experiments to illustrate the superiority of the MLE over the majority vote estimator.
Efficient Counterfactual Learning from Bandit Feedback
Venue: arXiv cs.LG 2018
Year: 2018

What is the most statistically efficient way to do off-policy evaluation and optimization with batch data from bandit feedback? For log data generated by contextual bandit algorithms, we consider offline estimators for the expected reward from a counterfactual policy. Our estimators are shown to have lowest variance in a wide class of estimators, achieving variance reduction relative to standard estimators. We then apply our estimators to improve advertisement design by a major advertisement company. Consistent with the theoretical result, our estimators allow us to improve on the existing bandit algorithm with more statistical confidence compared to a state-of-the-art benchmark.
A Comparison of BDD-Based Parity Game Solvers
Venue: arXiv cs.LO 2018
Year: 2018

Parity games are two player games with omega-winning conditions, played on finite graphs. Such games play an important role in verification, satisfiability and synthesis. It is therefore important to identify algorithms that can efficiently deal with large games that arise from such applications. In this paper, we describe our experiments with BDD-based implementations of four parity game solving algorithms, viz. Zielonka's recursive algorithm, the more recent Priority Promotion algorithm, the Fixpoint-Iteration algorithm and the automata based APT algorithm. We compare their performance on several types of random games and on a number of cases taken from the Keiren benchmark set.
Regular omega-Languages with an Informative Right Congruence
Venue: arXiv cs.FL 2018
Year: 2018

A regular language is almost fully characterized by its right congruence relation. Indeed, a regular language can always be recognized by a DFA isomorphic to the automaton corresponding to its right congruence, henceforth the Rightcon automaton. The same does not hold for regular omega-languages. The right congruence of a regular omega-language is not informative enough; many regular omega-languages have a trivial right congruence, and in general it is not always possible to define an omega-automaton recognizing a given language that is isomorphic to the rightcon automaton. The class of weak regular omega-languages does have an informative right congruence. That is, any weak regular omega-language can always be recognized by a deterministic Büchi automaton that is isomorphic to the rightcon automaton. Weak regular omega-languages reside in the lower levels of the expressiveness hierarchy of regular omega-languages. Are there more expressive sub-classes of regular omega languages that have an informative right congruence? Can we fully characterize the class of languages with a trivial right congruence? In this paper we try to place some additional pieces of this big puzzle.
On Privacy of Quantized Sensor Measurements through Additive Noise
Venue: arXiv cs.SY 2018
Year: 2018

We study the problem of maximizing privacy of quantized sensor measurements by adding random variables. In particular, we consider the setting where information about the state of a process is obtained using noisy sensor measurements. This information is quantized and sent to a remote station through an unsecured communication network. It is desired to keep the state of the process private; however, because the network is not secure, adversaries might have access to sensor information, which could be used to estimate the process state. To avoid an accurate state estimation, we add random numbers to the quantized sensor measurements and send the sum to the remote station instead. The distribution of these random variables is designed to minimize the mutual information between the sum and the quantized sensor measurements for a desired level of distortion -- how different the sum and the quantized sensor measurements are allowed to be. Simulations are presented to illustrate our results.
Texturing and Deforming Meshes with Casual Images
Venue: arXiv cs.GR 2018
Year: 2018

Using (casual) images to texture 3D models is a common way to create realistic 3D models, which is a very important task in computer graphics. However, if the shape of the casual image does not look like the target model or the target mapping area, the textured model will become strange since the image will be distorted very much. In this paper, we present a novel texturing and deforming approach for mapping the pattern and shape of a casual image to a 3D model at the same time based on an alternating least-square approach. Through a photogrammetric method, we project the target model onto the source image according to the estimated camera model. Then, the target model is deformed according to the shape of the source image using a surface-based deformation method while minimizing the image distortion simultaneously. The processes are performed iteratively until convergence. Hence, our method can achieve texture mapping, shape deformation, and detail-preserving at once, and can obtain more reasonable texture mapped results than traditional methods.
OpenMP Loop Scheduling Revisited: Making a Case for More Schedules
Venue: arXiv cs.DC 2018
Year: 2018

In light of continued advances in loop scheduling, this work revisits the OpenMP loop scheduling by outlining the current state of the art in loop scheduling and presenting evidence that the existing OpenMP schedules are insufficient for all combinations of applications, systems, and their characteristics. A review of the state of the art shows that due to the specifics of the parallel applications, the variety of computing platforms, and the numerous performance degradation factors, no single loop scheduling technique can be a 'one-fits-all' solution to effectively optimize the performance of all parallel applications in all situations. The impact of irregularity in computational workloads and hardware systems, including operating system noise, on the performance of parallel applications, results in performance loss and has often been neglected in loop scheduling research, in particular, the context of OpenMP schedules. Existing dynamic loop self-scheduling techniques, such as trapezoid self-scheduling, factoring, and weighted factoring, offer an unexplored potential to alleviate this degradation in OpenMP due to the fact that they explicitly target the minimization of load imbalance and scheduling overhead. Through theoretical and experimental evaluation, this work shows that these loop self-scheduling methods provide a benefit in the context of OpenMP. In conclusion, OpenMP must include more schedules to offer a broader performance coverage of applications executing on an increasing variety of heterogeneous shared memory computing platforms.
Learning to Generate Structured Queries from Natural Language with Indirect Supervision
Venue: arXiv cs.CL 2018
Year: 2018

Generating structured query language (SQL) from natural language is an emerging research topic. This paper presents a new learning paradigm from indirect supervision of the answers to natural language questions, instead of SQL queries. This paradigm facilitates the acquisition of training data due to the abundant resources of question-answer pairs for various domains in the Internet, and expels the difficult SQL annotation job. An end-to-end neural model integrating with reinforcement learning is proposed to learn SQL generation policy within the answer-driven learning paradigm. The model is evaluated on datasets of different domains, including movie and academic publication. Experimental results show that our model outperforms the baseline models.
Studying Confirmation Bias in Hashtag Usage on Twitter
Venue: arXiv cs.IR 2018
Year: 2018

The micro-blogging platform Twitter allows its nearly 320 million monthly active users to build a network of follower connections to other Twitter users (i.e., followees) in order to subscribe to content posted by these users. With this feature, Twitter has become one of the most popular social networks on the Web and was also the first platform that offered the concept of hashtags. Hashtags are freely-chosen keywords, which start with the hash character, to annotate, categorize and contextualize Twitter posts (i.e., tweets). Although hashtags are widely accepted and used by the Twitter community, the heavy reuse of hashtags that are popular in the personal Twitter networks (i.e., own hashtags and hashtags used by followees) can lead to filter bubble effects and thus, to situations, in which only content associated with these hashtags are presented to the user. These filter bubble effects are also highly associated with the concept of confirmation bias, which is the tendency to favor and reuse information that confirms personal preferences. One example would be a Twitter user who is interested in political tweets of US president Donald Trump. Depending on the hashtags used, the user could either be stuck in a pro-Trump (e.g., #MAGA) or contra-Trump (e.g., #fakepresident) filter bubble. Therefore, the goal of this paper is to study confirmation bias and filter bubble effects in hashtag usage on Twitter by treating the reuse of hashtags as a phenomenon that fosters confirmation bias.
Adaptive Behavior Generation for Autonomous Driving using Deep Reinforcement Learning with Compact Semantic States
Venue: arXiv cs.LG 2018
Year: 2018

Making the right decision in traffic is a challenging task that is highly dependent on individual preferences as well as the surrounding environment. Therefore it is hard to model solely based on expert knowledge. In this work we use Deep Reinforcement Learning to learn maneuver decisions based on a compact semantic state representation. This ensures a consistent model of the environment across scenarios as well as a behavior adaptation function, enabling on-line changes of desired behaviors without re-training. The input for the neural network is a simulated object list similar to that of Radar or Lidar sensors, superimposed by a relational semantic scene description. The state as well as the reward are extended by a behavior adaptation function and a parameterization respectively. With little expert knowledge and a set of mid-level actions, it can be seen that the agent is capable to adhere to traffic rules and learns to drive safely in a variety of situations.
Classification by Re-generation: Towards Classification Based on Variational Inference
Venue: arXiv cs.CV 2018
Year: 2018

As Deep Neural Networks (DNNs) are considered the state-of-the-art in many classification tasks, the question of their semantic generalizations has been raised. To address semantic interpretability of learned features, we introduce a novel idea of classification by re-generation based on variational autoencoder (VAE) in which a separate encoder-decoder pair of VAE is trained for each class. Moreover, the proposed architecture overcomes the scalability issue in current DNN networks as there is no need to re-train the whole network with the addition of new classes and it can be done for each class separately. We also introduce a criterion based on Kullback-Leibler divergence to reject doubtful examples. This rejection criterion should improve the trust in the obtained results and can be further exploited to reject adversarial examples.
Feature Learning for Meta-Paths in Knowledge Graphs
Venue: arXiv cs.LG 2018
Year: 2018

In this thesis, we study the problem of feature learning on heterogeneous knowledge graphs. These features can be used to perform tasks such as link prediction, classification and clustering on graphs. Knowledge graphs provide rich semantics encoded in the edge and node types. Meta-paths consist of these types and abstract paths in the graph. Until now, meta-paths can only be used as categorical features with high redundancy and are therefore unsuitable for machine learning models. We propose meta-path embeddings to solve this problem by learning semantical and compact vector representations of them. Current graph embedding methods only embed nodes and edge types and therefore miss semantics encoded in the combination of them. Our method embeds meta-paths using the skipgram model with an extension to deal with the redundancy and high amount of meta-paths in big knowledge graphs. We critically evaluate our embedding approach by predicting links on Wikidata. The experiments indicate that we learn a sensible embedding of the meta-paths but can improve it further.
MANTIS: Model-Augmented Neural neTwork with Incoherent k-space Sampling for efficient MR T2 mapping
Venue: arXiv cs.CV 2018
Year: 2018

Quantitative mapping of magnetic resonance (MR) parameters have been shown as valuable methods for improved assessment of a range of diseases. Due to the need to image an anatomic structure multiple times, parameter mapping usually requires long scan times compared to conventional static imaging. Therefore, accelerated parameter mapping is highly-desirable and remains a topic of great interest in the MR research community. While many recent deep learning methods have focused on highly efficient image reconstruction for conventional static MR imaging, applications of deep learning for dynamic imaging and in particular accelerated parameter mapping have been limited. The purpose of this work was to develop and evaluate a novel deep learning-based reconstruction framework called Model-Augmented Neural neTwork with Incoherent k-space Sampling (MANTIS) for efficient MR parameter mapping. Our approach combines end-to-end CNN mapping with k-space consistency using the concept of cyclic loss to further enforce data and model fidelity. Incoherent k-space sampling is used to improve reconstruction performance. A physical model is incorporated into the proposed framework, so that the parameter maps can be efficiently estimated directly from undersampled images. The performance of MANTIS was demonstrated for the spin-spin relaxation time (T2) mapping of the knee joint. Compared to conventional reconstruction approaches that exploited image sparsity, MANTIS yielded lower errors and higher similarity with respect to the reference in the T2 estimation. Our study demonstrated that the proposed MANTIS framework, with a combination of end-to-end CNN mapping, signal model-augmented data consistency, and incoherent k-space sampling, represents a promising approach for efficient MR parameter mapping. MANTIS can potentially be extended to other types of parameter mapping with appropriate models.
Interactive Binary Image Segmentation with Edge Preservation
Venue: arXiv cs.CV 2018
Year: 2018

Binary image segmentation plays an important role in computer vision and has been widely used in many applications such as image and video editing, object extraction, and photo composition. In this paper, we propose a novel interactive binary image segmentation method based on the Markov Random Field (MRF) framework and the fast bilateral solver (FBS) technique. Specifically, we employ the geodesic distance component to build the unary term. To ensure both computation efficiency and effective responsiveness for interactive segmentation, superpixels are used in computing geodesic distances instead of pixels. Furthermore, we take a bilateral affinity approach for the pairwise term in order to preserve edge information and denoise. Through the alternating direction strategy, the MRF energy minimization problem is divided into two subproblems, which then can be easily solved by steepest gradient descent (SGD) and FBS respectively. Experimental results on the VGG interactive image segmentation dataset show that the proposed algorithm outperforms several state-of-the-art ones, and in particular, it can achieve satisfactory edge-smooth segmentation results even when the foreground and background color appearances are quite indistinctive.
Strongly regular graphs from weakly regular plateaued functions
Venue: arXiv cs.IT 2018
Year: 2018

The paper provides the first constructions of strongly regular graphs and association schemes from weakly regular plateaued functions over finite fields of odd characteristic. We generalize the construction method of strongly regular graphs from weakly regular bent functions given by Chee et al. in [Journal of Algebraic Combinatorics, 34(2), 251-266, 2011] to weakly regular plateaued functions. In this framework, we construct strongly regular graphs with three types of parameters from weakly regular plateaued functions with some homogeneous conditions. We also construct a family of association schemes of class p from weakly regular p-ary plateaued functions.
A collection of database industrial techniques and optimization approaches of database operations
Venue: arXiv cs.DB 2018
Year: 2018

Databases play an essential role in our society today. Databases are embedded in sectors like corporations, institutions, and government organizations, among others. These databases are used for our video and audio streaming platforms, social gaming, finances, cloud storage, e-commerce, healthcare, economy, etc. It is therefore imperative that we learn how to properly execute database operations and efficiently implement methodologies so that we may optimize the performance of databases.
Deep Learning Towards Mobile Applications
Venue: arXiv cs.LG 2018
Year: 2018

Recent years have witnessed an explosive growth of mobile devices. Mobile devices are permeating every aspect of our daily lives. With the increasing usage of mobile devices and intelligent applications, there is a soaring demand for mobile applications with machine learning services. Inspired by the tremendous success achieved by deep learning in many machine learning tasks, it becomes a natural trend to push deep learning towards mobile applications. However, there exist many challenges to realize deep learning in mobile applications, including the contradiction between the miniature nature of mobile devices and the resource requirement of deep neural networks, the privacy and security concerns about individuals' data, and so on. To resolve these challenges, during the past few years, great leaps have been made in this area. In this paper, we provide an overview of the current challenges and representative achievements about pushing deep learning on mobile devices from three aspects: training with mobile data, efficient inference on mobile devices, and applications of mobile deep learning. The former two aspects cover the primary tasks of deep learning. Then, we go through our two recent applications that apply the data collected by mobile devices to inferring mood disturbance and user identification. Finally, we conclude this paper with the discussion of the future of this area.
Network Coded Handover in IEEE 802.11
Venue: arXiv cs.IT 2018
Year: 2018

We propose a network coded handover of a station moving between two IEEE 802.11 access points (AP). To address such novel proposed framework on a small cell WiFi to WiFi AP handoff, we propose a novel model for the Distributed Coordination Function (DCF) of the WiFi IEEE 802.11 with fixed average contention window. We provide a single packet tranmission model which has been extended to N-packets transmission models with and without fragmentation. We also model the N-packet transmission for the uncoded/coded packets broadcast in order to compare the IEEE 802.11 unreliable to reliable coded broadcast with ACK. We analyze the delay over all, unicast and broadcast transmissions, for the scenario considered with a topology with one WiFi AP before the handover. Capitalizing on the set of models and their corresponding mean completion times (delay), we analyze the performance of different mechanisms. Finally, we provide a novel formulation of the Network Coding on the Edge handover when the station is mobile allowing for the derivation of optimal transmission strategies that can define an optimal time, when to switch to the other AP.