OpenRaiser/Intern-Atlas huggingface dataset:
Going Deeper into Action Recognition: A Survey
Venue: arXiv cs.CV 2017
Year: 2017

Understanding human actions in visual data is tied to advances in complementary research areas including object recognition, human dynamics, domain adaptation and semantic segmentation. Over the last decade, human action analysis evolved from earlier schemes that are often limited to controlled environments to nowadays advanced solutions that can learn from millions of videos and apply to almost all daily activities. Given the broad range of applications from video surveillance to human-computer interaction, scientific milestones in action recognition are achieved more rapidly, eventually leading to the demise of what used to be good in a short time. This motivated us to provide a comprehensive review of the notable steps taken towards recognizing human actions. To this end, we start our discussion with the pioneering methods that use handcrafted representations, and then, navigate into the realm of deep learning based approaches. We aim to remain objective throughout this survey, touching upon encouraging improvements as well as inevitable fallbacks, in the hope of raising fresh questions and motivating new research directions for the reader.
Architecture-aware Coding for Distributed Storage: Repairable Block Failure Resilient Codes
Venue: arXiv cs.IT 2017
Year: 2017

In large scale distributed storage systems (DSS) deployed in cloud computing, correlated failures resulting in simultaneous failure (or, unavailability) of blocks of nodes are common. In such scenarios, the stored data or a content of a failed node can only be reconstructed from the available live nodes belonging to the available blocks. To analyze the resilience of the system against such block failures, this work introduces the framework of Block Failure Resilient (BFR) codes, wherein the data (e.g., a file in DSS) can be decoded by reading out from a same number of codeword symbols (nodes) from a subset of available blocks of the underlying codeword. Further, repairable BFR codes are introduced, wherein any codeword symbol in a failed block can be repaired by contacting a subset of remaining blocks in the system. File size bounds for repairable BFR codes are derived, and the trade-off between per node storage and repair bandwidth is analyzed, and the corresponding minimum storage regenerating (BFR-MSR) and minimum bandwidth regenerating (BFR-MBR) points are derived. Explicit codes achieving the two operating points for a special case of parameters are constructed, wherein the underlying regenerating codewords are distributed to BFR codeword symbols according to combinatorial designs. Finally, BFR locally repairable codes (BFR-LRC) are introduced, an upper bound on the resilience is derived and optimal code construction are provided by a concatenation of Gabidulin and MDS codes. Repair efficiency of BFR-LRC is further studied via the use of BFR-MSR/MBR codes as local codes. Code constructions achieving optimal resilience for BFR-MSR/MBR-LRCs are provided for certain parameter regimes. Overall, this work introduces the framework of block failures along with optimal code constructions, and the study of architecture-aware coding for distributed storage systems.
The Quality of the Covariance Selection Through Detection Problem and AUC Bounds
Venue: arXiv cs.IT 2017
Year: 2017

We consider the problem of quantifying the quality of a model selection problem for a graphical model. We discuss this by formulating the problem as a detection problem. Model selection problems usually minimize a distance between the original distribution and the model distribution. For the special case of Gaussian distributions, the model selection problem simplifies to the covariance selection problem which is widely discussed in literature by Dempster [2] where the likelihood criterion is maximized or equivalently the Kullback-Leibler (KL) divergence is minimized to compute the model covariance matrix. While this solution is optimal for Gaussian distributions in the sense of the KL divergence, it is not optimal when compared with other information divergences and criteria such as Area Under the Curve (AUC). In this paper, we analytically compute upper and lower bounds for the AUC and discuss the quality of model selection problem using the AUC and its bounds as an accuracy measure in detection problem. We define the correlation approximation matrix (CAM) and show that analytical computation of the KL divergence, the AUC and its bounds only depend on the eigenvalues of CAM. We also show the relationship between the AUC, the KL divergence and the ROC curve by optimizing with respect to the ROC curve. In the examples provided, we pick tree structures as the simplest graphical models. We perform simulations on fully-connected graphs and compute the tree structured models by applying the widely used Chow-Liu algorithm [3]. Examples show that the quality of tree approximation models are not good in general based on information divergences, the AUC and its bounds when the number of nodes in the graphical model is large. We show both analytically and by simulations that the 1-AUC for the tree approximation model decays exponentially as the dimension of graphical model increases.
Programming with a Differentiable Forth Interpreter
Venue: arXiv cs.NE 2017
Year: 2017

Given that in practice training data is scarce for all but a small set of problems, a core question is how to incorporate prior knowledge into a model. In this paper, we consider the case of prior procedural knowledge for neural networks, such as knowing how a program should traverse a sequence, but not what local actions should be performed at each step. To this end, we present an end-to-end differentiable interpreter for the programming language Forth which enables programmers to write program sketches with slots that can be filled with behaviour trained from program input-output data. We can optimise this behaviour directly through gradient descent techniques on user-specified objectives, and also integrate the program into any larger neural computation graph. We show empirically that our interpreter is able to effectively leverage different levels of prior program structure and learn complex behaviours such as sequence sorting and addition. When connected to outputs of an LSTM and trained jointly, our interpreter achieves state-of-the-art accuracy for end-to-end reasoning about quantities expressed in natural language stories.
Detection of Spatially-Modulated Signals in Doubly Selective Fading Channels With Imperfect CSI
Venue: arXiv cs.IT 2017
Year: 2017

To detect spatially-modulated signals, a receiver needs the channel state information (CSI) of each transmit- receive antenna pair. Although the CSI is never perfect and varies in time, most studies on spatial modulation (SM) systems assume perfectly known CSI and time-invariant channel. The spatial correlations among multiple spatial subchannels, which have to be considered when CSI is imperfect, are also often neglected. In this paper, we release the above assumptions and take the CSI uncertainty along with the spatial-temporal selectivities into account. We derive the channel estimation error aware maximum likelihood (CEEA-ML) detectors as well as several low- complexity alternatives for PSK and QAM signals. As the CSI uncertainty depends on the channel estimator used, we consider both decision feedback and model based estimators in our study. The error rate performance of the ML and some suboptimal detectors is analyzed. Numerical results obtained by simulations and analysis show that the CEEA-ML detectors offer clear performance gain against conventional mismatched SM detectors and, in many cases, the proposed suboptimal detectors incur only minor performance loss.
Limitations of Time Resources in Human Relationships Determine Social Structures
Venue: arXiv cs.SI 2017
Year: 2017

A single human can be involved in a limited number of social relationships, and the distribution of strengths of such relationships shows significant skew. This skewness suggests that the costs and benefits of the social interactions required to bond with others (social grooming) depend on the social relationship strength: if they involved uniform costs and benefits, the distribution would not be skew. Here, we show that the cost of social grooming increases with the social relationship strength, and its gradient determines the structures of these relationships in society as evident from an analysis of data from six communication systems. This may be due to an increase in communication volumes, such as number of characters and duration of calls, along with an increase in the social relationship strength. We tested this hypothesis using an individual-based simulation where social grooming costs were assumed to increase linearly with the social relationship strength; this is the simplest assumption. The results indicated that this model fitted all data sets, i.e., it showed an explanation capacity for the phenomenon. Additionally, an analysis of this simulation suggested that the gradient of social grooming costs increases the width and shallowness of social relationships in its communication system.
Max-Min SINR in Large-Scale Single-Cell MU-MIMO: Asymptotic Analysis and Low Complexity Transceivers
Venue: arXiv cs.IT 2017
Year: 2017

This work focuses on the downlink and uplink of large-scale single-cell MU-MIMO systems in which the base station (BS) endowed with $M$ antennas communicates with $K$ single-antenna user equipments (UEs). Particularly, we aim at reducing the complexity of the linear precoder and receiver that maximize the minimum signal-to-interference-plus-noise ratio subject to a given power constraint. To this end, we consider the asymptotic regime in which $M$ and $K$ grow large with a given ratio. Tools from random matrix theory (RMT) are then used to compute, in closed form, accurate approximations for the parameters of the optimal precoder and receiver, when imperfect channel state information (modeled by the generic Gauss-Markov formulation form) is available at the BS. The asymptotic analysis allows us to derive the asymptotically optimal linear precoder and receiver that are characterized by a lower complexity (due to the dependence on the large scale components of the channel) and, possibly, by a better resilience to imperfect channel state information. However, the implementation of both is still challenging as it requires fast inversions of large matrices in every coherence period. To overcome this issue, we apply the truncated polynomial expansion (TPE) technique to the precoding and receiving vector of each UE and make use of RMT to determine the optimal weighting coefficients on a per-UE basis that asymptotically solve the max-min SINR problem. Numerical results are used to validate the asymptotic analysis in the finite system regime and to show that the proposed TPE transceivers efficiently mimic the optimal ones, while requiring much lower computational complexity.
Alternating Optimisation and Quadrature for Robust Control
Venue: arXiv cs.LG 2017
Year: 2017

Bayesian optimisation has been successfully applied to a variety of reinforcement learning problems. However, the traditional approach for learning optimal policies in simulators does not utilise the opportunity to improve learning by adjusting certain environment variables: state features that are unobservable and randomly determined by the environment in a physical setting but are controllable in a simulator. This paper considers the problem of finding a robust policy while taking into account the impact of environment variables. We present Alternating Optimisation and Quadrature (ALOQ), which uses Bayesian optimisation and Bayesian quadrature to address such settings. ALOQ is robust to the presence of significant rare events, which may not be observable under random sampling, but play a substantial role in determining the optimal policy. Experimental results across different domains show that ALOQ can learn more efficiently and robustly than existing methods.
Parameterized complexity of fair deletion problems
Venue: arXiv cs.DS 2017
Year: 2017

Deletion problems are those where given a graph $G$ and a graph property $π$, the goal is to find a subset of edges such that after its removal the graph $G$ will satisfy the property $π$. Typically, we want to minimize the number of elements removed. In fair deletion problems we change the objective: we minimize the maximum number of deletions in a neighborhood of a single vertex. We study the parameterized complexity of fair deletion problems with respect to the structural parameters of the tree-width, the path-width, the size of a minimum feedback vertex set, the neighborhood diversity, and the size of minimum vertex cover of graph $G$. We prove the W[1]-hardness of the fair FO vertex-deletion problem with respect to the first three parameters combined. Moreover, we show that there is no algorithm for fair FO vertex-deletion problem running in time $n^{o(k^{1/3})}$, where $n$ is the size of the graph and $k$ is the sum of the first three mentioned parameters, provided that the Exponential Time Hypothesis holds. On the other hand, we provide an FPT algorithm for the fair MSO edge-deletion problem parameterized by the size of minimum vertex cover and an FPT algorithm for the fair MSO vertex-deletion problem parameterized by the neighborhood diversity
Using almetrics for contextualised mapping of societal impact: From hits to networks
Venue: arXiv cs.DL 2017
Year: 2017

In this article, we develop a method that uses altmetric data to analyse researchers' interactions, as a way of mapping the contexts of potential societal impact. In the face of an increasing policy demand for quantitative methodologies to assess societal impact, social media data (altmetrics) has been presented as a potential method to capture broader forms of impact. However, current altmetric indicators were extrapolated from traditional citation approaches and are seen as problematic for assessing societal impact. In contrast, established qualitative methodologies for societal impact assessment are based on interaction approaches. These argue that assessment should focus on mapping the contexts in which engagement among researchers and stakeholders take place, as a means to understand the pathways to societal impact. Following these approaches, we propose to shift the use of altmetric data towards network analysis of researchers and stakeholders. We carry out two case studies, analysing researchers' networks with Twitter data. The comparison illustrates the potential of Twitter networks to capture disparate degrees of policy engagement. We propose that this mapping method can be used as an input within broader methodologies in case studies of societal impact assessment.
Recursive Autoconvolution for Unsupervised Learning of Convolutional Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

In visual recognition tasks, such as image classification, unsupervised learning exploits cheap unlabeled data and can help to solve these tasks more efficiently. We show that the recursive autoconvolution operator, adopted from physics, boosts existing unsupervised methods by learning more discriminative filters. We take well established convolutional neural networks and train their filters layer-wise. In addition, based on previous works we design a network which extracts more than 600k features per sample, but with the total number of trainable parameters greatly reduced by introducing shared filters in higher layers. We evaluate our networks on the MNIST, CIFAR-10, CIFAR-100 and STL-10 image classification benchmarks and report several state of the art results among other unsupervised methods.
RCFD: A Novel Channel Access Scheme for Full-Duplex Wireless Networks Based on Contention in Time and Frequency Domains
Venue: arXiv cs.NI 2017
Year: 2017

In the last years, the advancements in signal processing and integrated circuits technology allowed several research groups to develop working prototypes of in-band full-duplex wireless systems. The introduction of such a revolutionary concept is promising in terms of increasing network performance, but at the same time poses several new challenges, especially at the MAC layer. Consequently, innovative channel access strategies are needed to exploit the opportunities provided by full-duplex while dealing with the increased complexity derived from its adoption. In this direction, this paper proposes RTS/CTS in the Frequency Domain (RCFD), a MAC layer scheme for full-duplex ad hoc wireless networks, based on the idea of time-frequency channel contention. According to this approach, different OFDM subcarriers are used to coordinate how nodes access the shared medium. The proposed scheme leads to efficient transmission scheduling with the result of avoiding collisions and exploiting full-duplex opportunities. The considerable performance improvements with respect to standard and state-of-the-art MAC protocols for wireless networks are highlighted through both theoretical analysis and network simulations.
Leveraging Evolution Dynamics to Generate Benchmark Complex Networks with Community Structures
Venue: arXiv cs.SI 2017
Year: 2017

The past decade has seen tremendous growth in the field of Complex Social Networks. Several network generation models have been extensively studied to develop an understanding of how real world networks evolve over time. Two important applications of these models are to study the evolution dynamics and processes that shape a network, and to generate benchmark networks with known community structures. Research has been conducted in both these directions, relatively independent of the other. This creates a disjunct between real world networks and the networks generated as benchmarks to study community detection algorithms. In this paper, we propose to study both these application areas together. We introduce a network generation model which is based on evolution dynamics of real world networks and, it can generate networks with community structures that can be used as benchmark graphs. We study the behaviour of different community detection algorithms based on the proposed model and compare it with other models to generate benchmark graphs. Results suggest that the proposed model can generate networks which are not only structurally similar to real world networks but can be used to generate networks with varying community sizes and topologies.
Online Power Control Optimization for Wireless Transmission with Energy Harvesting and Storage
Venue: arXiv cs.IT 2017
Year: 2017

We consider wireless transmission over fading channel powered by energy harvesting and storage devices. Assuming a finite battery storage capacity, we design an online power control strategy aiming at maximizing the long-term time-averaged transmission rate under battery operational constraints for energy harvesting. We first formulate the stochastic optimization problem, and then develop techniques to transform this problem and employ techniques from Lyapunov optimization to design the online power control solution. In particular, we propose an approach to handle unbounded channel fade which cannot by directly dealt with by Lyapunov framework. Our proposed algorithm determines the transmission power based only on the current energy state of the battery and channel fade conditions,without requiring any knowledge of the statistics of energy arrivals and fading channels. Our online power control solution is a three-stage closed-form solution depending on the battery energy level. It not only provides strategic energy conservation through the battery energy control, but also reveals an opportunistic transmission style based on fading condition, both of which improve the long-term time-averaged transmission rate. We further characterize the performance bound of our proposed algorithm to the optimal solution with a general fading distribution. Simulation results demonstrate a significant performance gain of our proposed online algorithm over alternative online approaches.
Convolutional Neural Fabrics
Venue: arXiv cs.CV 2017
Year: 2017

Despite the success of CNNs, selecting the optimal architecture for a given task remains an open problem. Instead of aiming to select a single optimal architecture, we propose a "fabric" that embeds an exponentially large number of architectures. The fabric consists of a 3D trellis that connects response maps at different layers, scales, and channels with a sparse homogeneous local connectivity pattern. The only hyper-parameters of a fabric are the number of channels and layers. While individual architectures can be recovered as paths, the fabric can in addition ensemble all embedded architectures together, sharing their weights where their paths overlap. Parameters can be learned using standard methods based on back-propagation, at a cost that scales linearly in the fabric size. We present benchmark results competitive with the state of the art for image classification on MNIST and CIFAR10, and for semantic segmentation on the Part Labels dataset.
Low-Complexity MIMO Precoding for Finite-Alphabet Signals
Venue: arXiv cs.IT 2017
Year: 2017

This paper investigates the design of precoders for single-user multiple-input multiple-output (MIMO) channels, and in particular for finite-alphabet signals. Based on an asymptotic expression for the mutual information of channels exhibiting line-of-sight components and rather general antenna correlations, precoding structures that decompose the general channel into a set of parallel subchannel pairs are proposed. Then, a low-complexity iterative algorithm is devised to maximize the sum mutual information of all pairs. The proposed algorithm significantly reduces the computational load of existing approaches with only minimal loss in performance. The complexity savings increase with the number of transmit antennas and with the cardinality of the signal alphabet, making it possible to support values thereof that were unmanageable with existing solutions. Most importantly, the proposed solution does not require instantaneous channel state information (CSI) at the transmitter, but only statistical CSI.
On the Runtime of Universal Coating for Programmable Matter
Venue: arXiv cs.ET 2017
Year: 2017

Imagine coating buildings and bridges with smart particles (also coined smart paint) that monitor structural integrity and sense and report on traffic and wind loads, leading to technology that could do such inspection jobs faster and cheaper and increase safety at the same time. In this paper, we study the problem of uniformly coating objects of arbitrary shape in the context of self-organizing programmable matter, i.e., programmable matter which consists of simple computational elements called particles that can establish and release bonds and can actively move in a self-organized way. Particles are anonymous, have constant-size memory, and utilize only local interactions in order to coat an object. We continue the study of our Universal Coating algorithm by focusing on its runtime analysis, showing that our algorithm terminates within a linear number of rounds with high probability. We also present a matching linear lower bound that holds with high probability. We use this lower bound to show a linear lower bound on the competitive gap between fully local coating algorithms and coating algorithms that rely on global information, which implies that our algorithm is also optimal in a competitive sense. Simulation results show that the competitive ratio of our algorithm may be better than linear in practice.