OpenRaiser/Intern-Atlas huggingface dataset:
Delay-Optimal Probabilistic Scheduling with Arbitrary Arrival and Adaptive Transmission
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we aim to obtain the optimal delay-power tradeoff and the corresponding optimal scheduling policy for an arbitrary i.i.d. arrival process and adaptive transmissions. The number of backlogged packets at the transmitter is known to a scheduler, who has to determine how many backlogged packets to transmit during each time slot. The power consumption is assumed to be convex in transmission rates. Hence, if the scheduler transmits faster, the delay will be reduced but with higher power consumption. To obtain the optimal delay-power tradeoff and the corresponding optimal policy, we model the problem as a Constrained Markov Decision Process (CMDP), where we minimize the average delay given an average power constraint. By steady-state analysis and Lagrangian relaxation, we can show that the optimal tradeoff curve is decreasing, convex, and piecewise linear, and the optimal policy is threshold-based. Based on the revealed properties of the optimal policy, we develop an algorithm to efficiently obtain the optimal tradeoff curve and the optimal policy with full information of the system. The complexity of our proposed algorithm is much lower than a general algorithm based on Linear Programming. However, usually the distribution of the arrival process is unknown to the scheduler, therefore we proposed a reinforcement learning algorithm to efficiently obtain the optimal policy under this circumstance. We also analyse in details about how the system parameters affect the optimal policy and the system performance. In the final, we use simulations to validate the derived results and the proposed algorithms.
A Selfie is Worth a Thousand Words: Mining Personal Patterns behind User Selfie-posting Behaviours
Venue: arXiv cs.SI 2017
Year: 2017

Selfies have become increasingly fashionable in the social media era. People are willing to share their selfies in various social media platforms such as Facebook, Instagram and Flicker. The popularity of selfie have caught researchers' attention, especially psychologists. In computer vision and machine learning areas, little attention has been paid to this phenomenon as a valuable data source. In this paper, we focus on exploring the deeper personal patterns behind people's different kinds of selfie-posting behaviours. We develop this work based on a dataset of WeChat, one of the most extensively used instant messaging platform in China. In particular, we first propose an unsupervised approach to classify the images posted by users. Based on the classification result, we construct three types of user-level features that reflect user preference, activity and posting habit. Based on these features, for a series of selfie related tasks, we build classifiers that can accurately predict two sets of users with opposite selfie-posting behaviours. We have found that people's interest, activity and posting habit have a great influence on their selfie-posting behaviours. For example, the classification accuracy between selfie-posting addict and nonaddict reaches 89.36%. We also prove that using user's image information to predict these behaviours achieve better performance than using text information. More importantly, for each set of users with a specific selfie-posting behaviour, we extract and visualize significant personal patterns about them. In addition, we cluster users and extract their high-level attributes, revealing the correlation between these attributes and users' selfie-posting behaviours. In the end, we demonstrate that users' selfie-posting behaviour, as a good predictor, could predict their different preferences toward these high-level attributes accurately.
A Mission Planning System for the AUV "SLOCUM Glider" for the Newfoundland and Labrador Shelf
Venue: arXiv cs.RO 2017
Year: 2017

This paper presents a system for mission planning for an autonomous underwater vehicle in time-varying ocean currents. The mission planning system is designed for the AUV "SLOCUM Glider" to collect oceanographic data along the Newfoundland and Labrador Shelf. The data will be used in conjunction with a numerical ocean model currently under development by the Department of Fisheries and Oceans Canada. This allows for the validation and the modification of existing ocean current and climate models as well as the design of new models with the aim of improving the accuracy of forecasts. The use of the ocean current forecast data in netCDF format in an ocean current model, the algorithms which consider glider-specific behaviour, details of the program's technical implementation in C++, and, preliminary results will be described.
A General Framework for Low-Resolution Receivers for MIMO Channels
Venue: arXiv cs.IT 2017
Year: 2017

The capacity of a discrete-time multi-input multi-output (MIMO) Gaussian channel with output quantization is investigated for different receiver architectures. A general formulation of this problem is proposed in which the antenna outputs are processed by analog combiners while sign quantizers are used for analog-to-digital conversion. To exemplify this approach, four analog receiver architectures of varying generality and complexity are considered: (a) multiple antenna selection and sign quantization of the antenna outputs, (b) single antenna selection and multilevel quantization, (c) multiple antenna selection and multilevel quantization, and (d) linear combining of the antenna outputs and multilevel quantization. Achievable rates are studied as a function of the number of available sign quantizers and compared among different architectures. In particular, it is shown that architecture (a) is sufficient to attain the optimal high signal-to-noise ratio performance for a MIMO receiver in which the number of antennas is larger than the number of sign quantizers. Numerical evaluations of the average performance are presented for the case in which the channel gains are i.i.d. Gaussian.
DeepNAT: Deep Convolutional Neural Network for Segmenting Neuroanatomy
Venue: arXiv cs.CV 2017
Year: 2017

We introduce DeepNAT, a 3D Deep convolutional neural network for the automatic segmentation of NeuroAnaTomy in T1-weighted magnetic resonance images. DeepNAT is an end-to-end learning-based approach to brain segmentation that jointly learns an abstract feature representation and a multi-class classification. We propose a 3D patch-based approach, where we do not only predict the center voxel of the patch but also neighbors, which is formulated as multi-task learning. To address a class imbalance problem, we arrange two networks hierarchically, where the first one separates foreground from background, and the second one identifies 25 brain structures on the foreground. Since patches lack spatial context, we augment them with coordinates. To this end, we introduce a novel intrinsic parameterization of the brain volume, formed by eigenfunctions of the Laplace-Beltrami operator. As network architecture, we use three convolutional layers with pooling, batch normalization, and non-linearities, followed by fully connected layers with dropout. The final segmentation is inferred from the probabilistic output of the network with a 3D fully connected conditional random field, which ensures label agreement between close voxels. The roughly 2.7 million parameters in the network are learned with stochastic gradient descent. Our results show that DeepNAT compares favorably to state-of-the-art methods. Finally, the purely learning-based method may have a high potential for the adaptation to young, old, or diseased brains by fine-tuning the pre-trained network with a small training sample on the target application, where the availability of larger datasets with manual annotations may boost the overall segmentation accuracy in the future.
Mutual Information based labelling and comparing clusters
Venue: arXiv cs.IR 2017
Year: 2017

After a clustering solution is generated automatically, labelling these clusters becomes important to help understanding the results. In this paper, we propose to use a Mutual Information based method to label clusters of journal articles. Topical terms which have the highest Normalised Mutual Information (NMI) with a certain cluster are selected to be the labels of the cluster. Discussion of the labelling technique with a domain expert was used as a check that the labels are discriminating not only lexical-wise but also semantically. Based on a common set of topical terms, we also propose to generate lexical fingerprints as a representation of individual clusters. Eventually, we visualise and compare these fingerprints of different clusters from either one clustering solution or different ones.
Approximation Strategies for Generalized Binary Search in Weighted Trees
Venue: arXiv cs.DS 2017
Year: 2017

We consider the following generalization of the binary search problem. A search strategy is required to locate an unknown target node $t$ in a given tree $T$. Upon querying a node $v$ of the tree, the strategy receives as a reply an indication of the connected component of $T\setminus\{v\}$ containing the target $t$. The cost of querying each node is given by a known non-negative weight function, and the considered objective is to minimize the total query cost for a worst-case choice of the target. Designing an optimal strategy for a weighted tree search instance is known to be strongly NP-hard, in contrast to the unweighted variant of the problem which can be solved optimally in linear time. Here, we show that weighted tree search admits a quasi-polynomial time approximation scheme: for any $0 \textless{} \varepsilon \textless{} 1$, there exists a $(1+\varepsilon)$-approximation strategy with a computation time of $n^{O(\log n / \varepsilon^2)}$. Thus, the problem is not APX-hard, unless $NP \subseteq DTIME(n^{O(\log n)})$. By applying a generic reduction, we obtain as a corollary that the studied problem admits a polynomial-time $O(\sqrt{\log n})$-approximation. This improves previous $\hat O(\log n)$-approximation approaches, where the $\hat O$-notation disregards $O(\mathrm{poly}\log\log n)$-factors.
Anticipating many futures: Online human motion prediction and synthesis for human-robot collaboration
Venue: arXiv cs.RO 2017
Year: 2017

Fluent and safe interactions of humans and robots require both partners to anticipate the others' actions. A common approach to human intention inference is to model specific trajectories towards known goals with supervised classifiers. However, these approaches do not take possible future movements into account nor do they make use of kinematic cues, such as legible and predictable motion. The bottleneck of these methods is the lack of an accurate model of general human motion. In this work, we present a conditional variational autoencoder that is trained to predict a window of future human motion given a window of past frames. Using skeletal data obtained from RGB depth images, we show how this unsupervised approach can be used for online motion prediction for up to 1660 ms. Additionally, we demonstrate online target prediction within the first 300-500 ms after motion onset without the use of target specific training data. The advantage of our probabilistic approach is the possibility to draw samples of possible future motions. Finally, we investigate how movements and kinematic cues are represented on the learned low dimensional manifold.
Synergistic Team Composition
Venue: arXiv cs.AI 2017
Year: 2017

Effective teams are crucial for organisations, especially in environments that require teams to be constantly created and dismantled, such as software development, scientific experiments, crowd-sourcing, or the classroom. Key factors influencing team performance are competences and personality of team members. Hence, we present a computational model to compose proficient and congenial teams based on individuals' personalities and their competences to perform tasks of different nature. With this purpose, we extend Wilde's post-Jungian method for team composition, which solely employs individuals' personalities. The aim of this study is to create a model to partition agents into teams that are balanced in competences, personality and gender. Finally, we present some preliminary empirical results that we obtained when analysing student performance. Results show the benefits of a more informed team composition that exploits individuals' competences besides information about their personalities.
On the second Feng-Rao distance of Algebraic Geometry codes related to Arf semigroups
Venue: arXiv cs.IT 2017
Year: 2017

We describe the second (generalized) Feng-Rao distance for elements in an Arf numerical semigroup that are greater than or equal to the conductor of the semigroup. This provides a lower bound for the second Hamming weight for one point AG codes. In particular, we can obtain the second Feng-Rao distance for the codes defined by asymptotically good towers of function fields whose Weierstrass semigroups are inductive. In addition, we compute the second Feng-Rao number, and provide some examples and comparisons with previous results on this topic. These calculations rely on Apéry sets, and thus several results concerning Apéry sets of Arf semigroups are presented.
How Functional Complexity affects the Scalability-Energy Efficiency Trade-Off of HCC WSN Clustering
Venue: arXiv cs.NI 2017
Year: 2017

Even though clustering algorithms in Wireless Sensor Networks (WSN) are a well investigate subject, the increasing interest in the Internet of Things (IoT) and 5G technologies has precipitated the need of new ways to comprehend and overcome a new set of challenges. While studies mainly propose new algorithms and compare these algorithms based on a set of properties (e.g. energy efficiency, scalability), none of them focuses on the underlying mechanisms and organizational patterns that lead to these properties. We address this lack of understanding by applying a complex systems science approach to investigate the properties of WSNs arising from the communication patterns of the network nodes. We represent different implementations of clustering in WSNs with a functional topology graph. Moreover, we employ a complexity metric - functional complexity (CF) - to explain how local interactions give rise to the global behavior of the network. Our analysis shows that higher values of CF indicate higher scalability and lower energy efficiency.
On-the-Fly Computation of Bisimilarity Distances
Venue: arXiv cs.LO 2017
Year: 2017

We propose a distance between continuous-time Markov chains (CTMCs) and study the problem of computing it by comparing three different algorithmic methodologies: iterative, linear program, and on-the-fly. In a work presented at FoSSaCS'12, Chen et al. characterized the bisimilarity distance of Desharnais et al. between discrete-time Markov chains as an optimal solution of a linear program that can be solved by using the ellipsoid method. Inspired by their result, we propose a novel linear program characterization to compute the distance in the continuous-time setting. Differently from previous proposals, ours has a number of constraints that is bounded by a polynomial in the size of the CTMC. This, in particular, proves that the distance we propose can be computed in polynomial time. Despite its theoretical importance, the proposed linear program characterization turns out to be inefficient in practice. Nevertheless, driven by the encouraging results of our previous work presented at TACAS'13, we propose an efficient on-the-fly algorithm, which, unlike the other mentioned solutions, computes the distances between two given states avoiding an exhaustive exploration of the state space. This technique works by successively refining over-approximations of the target distances using a greedy strategy, which ensures that the state space is further explored only when the current approximations are improved. Tests performed on a consistent set of (pseudo)randomly generated CTMCs show that our algorithm improves, on average, the efficiency of the corresponding iterative and linear program methods with orders of magnitude.
A Message Passing Approach for Decision Fusion in Adversarial Multi-Sensor Networks
Venue: arXiv cs.SY 2017
Year: 2017

We consider a simple, yet widely studied, set-up in which a Fusion Center (FC) is asked to make a binary decision about a sequence of system states by relying on the possibly corrupted decisions provided by byzantine nodes, i.e. nodes which deliberately alter the result of the local decision to induce an error at the fusion center. When independent states are considered, the optimum fusion rule over a batch of observations has already been derived, however its complexity prevents its use in conjunction with large observation windows. In this paper, we propose a near-optimal algorithm based on message passing that greatly reduces the computational burden of the optimum fusion rule. In addition, the proposed algorithm retains very good performance also in the case of dependent system states. By first focusing on the case of small observation windows, we use numerical simulations to show that the proposed scheme introduces a negligible increase of the decision error probability compared to the optimum fusion rule. We then analyse the performance of the new scheme when the FC make its decision by relying on long observation windows. We do so by considering both the case of independent and Markovian system states and show that the obtained performance are superior to those obtained with prior suboptimal schemes. As an additional result, we confirm the previous finding that, in some cases, it is preferable for the byzantine nodes to minimise the mutual information between the sequence system states and the reports submitted to the FC, rather than always flipping the local decision.
Backhaul-aware Robust 3D Drone Placement in 5G+ Wireless Networks
Venue: arXiv cs.NI 2017
Year: 2017

Using drones as flying base stations is a promising approach to enhance the network coverage and area capacity by moving supply towards demand when required. However deployment of such base stations can face some restrictions that need to be considered. One of the limitations in drone base stations (drone-BSs) deployment is the availability of reliable wireless backhaul link. This paper investigates how different types of wireless backhaul offering various data rates would affect the number of served users. Two approaches, namely, network-centric and user-centric, are introduced and the optimal 3D backhaul-aware placement of a drone-BS is found for each approach. To this end, the total number of served users and sum-rates are maximized in the network-centric and user-centric frameworks, respectively. Moreover, as it is preferred to decrease drone-BS movements to save more on battery and increase flight time and to reduce the channel variations, the robustness of the network is examined as how sensitive it is with respect to the users displacements.
Learning Hierarchical Features from Generative Models
Venue: arXiv cs.LG 2017
Year: 2017

Deep neural networks have been shown to be very successful at learning feature hierarchies in supervised learning tasks. Generative models, on the other hand, have benefited less from hierarchical models with multiple layers of latent variables. In this paper, we prove that hierarchical latent variable models do not take advantage of the hierarchical structure when trained with existing variational methods, and provide some limitations on the kind of features existing models can learn. Finally we propose an alternative architecture that do not suffer from these limitations. Our model is able to learn highly interpretable and disentangled hierarchical features on several natural image datasets with no task specific regularization or prior knowledge.
Strong Chain Rules for Min-Entropy under Few Bits Spoiled
Venue: arXiv cs.IT 2017
Year: 2017

It is well established that the notion of min-entropy fails to satisfy the \emph{chain rule} of the form $H(X,Y) = H(X|Y)+H(Y)$, known for Shannon Entropy. Such a property would help to analyze how min-entropy is split among smaller blocks. Problems of this kind arise for example when constructing extractors and dispersers. We show that any sequence of variables exhibits a very strong strong block-source structure (conditional distributions of blocks are nearly flat) when we \emph{spoil few correlated bits}. This implies, conditioned on the spoiled bits, that \emph{splitting-recombination properties} hold. In particular, we have many nice properties that min-entropy doesn't obey in general, for example strong chain rules, "information can't hurt" inequalities, equivalences of average and worst-case conditional entropy definitions and others. Quantitatively, for any sequence $X_1,\ldots,X_t$ of random variables over an alphabet $\mathcal{X}$ we prove that, when conditioned on $m = t\cdot O( \log\log|\mathcal{X}| + \log\log(1/ε) + \log t)$ bits of auxiliary information, all conditional distributions of the form $X_i|X_{<i}$ are $ε$-close to be nearly flat (only a constant factor away). The argument is combinatorial (based on simplex coverings). This result may be used as a generic tool for \emph{exhibiting block-source structures}. We demonstrate this by reproving the fundamental converter due to Nisan and Zuckermann (\emph{J. Computer and System Sciences, 1996}), which shows that sampling blocks from a min-entropy source roughly preserves the entropy rate. Our bound implies, only by straightforward chain rules, an additive loss of $o(1)$ (for sufficiently many samples), which qualitatively meets the first tighter analysis of this problem due to Vadhan (\emph{CRYPTO'03}), obtained by large deviation techniques.
Synergistic Computation of Planar Maxima and Convex Hull
Venue: arXiv cs.DS 2017
Year: 2017

Refinements of the worst case complexity over instances of fixed input size consider the input order or the input structure, but rarely both at the same time. Barbay et al. [2016] described ``synergistic'' solutions on multisets, which take advantage of the input order and the input structure, such as to asymptotically outperform any comparable solution which takes advantage only of one of those features. We consider the extension of their results to the computation of the \textsc{Maxima Set} and the \textsc{Convex Hull} of a set of planar points. After revisiting and improving previous approaches taking advantage only of the input order or of the input structure, we describe synergistic solutions taking optimally advantage of various notions of the input order and input structure in the plane. As intermediate results, we describe and analyze the first adaptive algorithms for \textsc{Merging Maxima} and \textsc{Merging Convex Hulls}.