OpenRaiser/Intern-Atlas huggingface dataset:
Minimax Lower Bounds for Kronecker-Structured Dictionary Learning
Venue: arXiv cs.IT 2016
Year: 2016

Dictionary learning is the problem of estimating the collection of atomic elements that provide a sparse representation of measured/collected signals or data. This paper finds fundamental limits on the sample complexity of estimating dictionaries for tensor data by proving a lower bound on the minimax risk. This lower bound depends on the dimensions of the tensor and parameters of the generative model. The focus of this paper is on second-order tensor data, with the underlying dictionaries constructed by taking the Kronecker product of two smaller dictionaries and the observed data generated by sparse linear combinations of dictionary atoms observed through white Gaussian noise. In this regard, the paper provides a general lower bound on the minimax risk and also adapts the proof techniques for equivalent results using sparse and Gaussian coefficient models. The reported results suggest that the sample complexity of dictionary learning for tensor data can be significantly lower than that for unstructured data.
Hardware Based Projection onto The Parity Polytope and Probability Simplex
Venue: arXiv cs.IT 2016
Year: 2016

This paper is concerned with the adaptation to hardware of methods for Euclidean norm projections onto the parity polytope and probability simplex. We first refine recent efforts to develop efficient methods of projection onto the parity polytope. Our resulting algorithm can be configured to have either average computational complexity $\mathcal{O}\left(d\right)$ or worst case complexity $\mathcal{O}\left(d\log{d}\right)$ on a serial processor where $d$ is the dimension of projection space. We show how to adapt our projection routine to hardware. Our projection method uses a sub-routine that involves another Euclidean projection; onto the probability simplex. We therefore explain how to adapt to hardware a well know simplex projection algorithm. The hardware implementations of both projection algorithms achieve area scalings of $\mathcal{O}(d\left(\log{d}\right)^2)$ at a delay of $\mathcal{O}(\left(\log{d}\right)^2)$. Finally, we present numerical results in which we evaluate the fixed-point accuracy and resource scaling of these algorithms when targeting a modern FPGA.
Bounds on the rate of disjunctive codes (in Russian)
Venue: arXiv cs.IT 2016
Year: 2016

A binary code is called a superimposed cover-free $(s,\ell)$-code if the code is identified by the incidence matrix of a family of finite sets in which no intersection of $\ell$ sets is covered by the union of $s$ others. A binary code is called a superimposed list-decoding $s_L$-code if the code is identified by the incidence matrix of a family of finite sets in which the union of any $s$ sets can cover not more than $L-1$ other sets of the family. For $L=\ell=1$, both of the definitions coincide and the corresponding binary code is called a superimposed $s$-code. Our aim is to obtain new lower and upper bounds on the rate of the given codes. In particular, we derive lower bounds on the rates of a superimposed cover-free $(s,\ell)$-code and list-decoding $s_L$-code based on the ensemble of constant weight binary codes. Also, we establish an upper bound on the rate of superimposed list-decoding $s_L$-code.
Deep Action Sequence Learning for Causal Shape Transformation
Venue: arXiv cs.LG 2016
Year: 2016

Deep learning became the method of choice in recent year for solving a wide variety of predictive analytics tasks. For sequence prediction, recurrent neural networks (RNN) are often the go-to architecture for exploiting sequential information where the output is dependent on previous computation. However, the dependencies of the computation lie in the latent domain which may not be suitable for certain applications involving the prediction of a step-wise transformation sequence that is dependent on the previous computation only in the visible domain. We propose that a hybrid architecture of convolution neural networks (CNN) and stacked autoencoders (SAE) is sufficient to learn a sequence of actions that nonlinearly transforms an input shape or distribution into a target shape or distribution with the same support. While such a framework can be useful in a variety of problems such as robotic path planning, sequential decision-making in games, and identifying material processing pathways to achieve desired microstructures, the application of the framework is exemplified by the control of fluid deformations in a microfluidic channel by deliberately placing a sequence of pillars. Learning of a multistep topological transform has significant implications for rapid advances in material science and biomedical applications.
Dual Local-Global Contextual Pathways for Recognition in Aerial Imagery
Venue: arXiv cs.CV 2016
Year: 2016

Visual context is important in object recognition and it is still an open problem in computer vision. Along with the advent of deep convolutional neural networks (CNN), using contextual information with such systems starts to receive attention in the literature. At the same time, aerial imagery is gaining momentum. While advances in deep learning make good progress in aerial image analysis, this problem still poses many great challenges. Aerial images are often taken under poor lighting conditions and contain low resolution objects, many times occluded by trees or taller buildings. In this domain, in particular, visual context could be of great help, but there are still very few papers that consider context in aerial image understanding. Here we introduce context as a complementary way of recognizing objects. We propose a dual-stream deep neural network model that processes information along two independent pathways, one for local and another for global visual reasoning. The two are later combined in the final layers of processing. Our model learns to combine local object appearance as well as information from the larger scene at the same time and in a complementary way, such that together they form a powerful classifier. We test our dual-stream network on the task of segmentation of buildings and roads in aerial images and obtain state-of-the-art results on the Massachusetts Buildings Dataset. We also introduce two new datasets, for buildings and road segmentation, respectively, and study the relative importance of local appearance vs. the larger scene, as well as their performance in combination. While our local-global model could also be useful in general recognition tasks, we clearly demonstrate the effectiveness of visual context in conjunction with deep nets for aerial image understanding.
Beamwidth Optimization in Millimeter Wave Small Cell Networks with Relay Nodes: A Swarm Intelligence Approach
Venue: arXiv cs.NI 2016
Year: 2016

Millimeter wave (mmWave) communications have been postulated as one of the most disruptive technologies for future 5G systems. Among mmWave bands the 60-GHz radio technology is specially suited for ultradense small cells and mobile data offloading scenarios. Many challenges remain to be addressed in mmWave communications but among them deafness, or misalignment between transmitter and receivers beams, and interference management lie among the most prominent ones. In the recent years, scenarios considering negligible interference on mmWave resource allocation have been rather common in literature. To this end, interestingly, many open issues still need to be addressed such as the applicability of noise-limited regime for mmWave. Furthermore, in mmWave the beam-steering mechanism imposes a forced silence period, in the course of which no data can be conveyed, that should not be neglected in throughput/delay calculations. This paper introduces mmWave enabled Small Cell Networks (SCNs) with relaying capabilities where as a result of a coordinated meta-heuristically optimized beamwidth/alignment-delay approach overall system throughput is optimized. Simulations have been conveyed for three transmitter densities under TDMA and naive 'all-on' scheduling producing average per node throughput increments of up to 248%. The paper further elaborates on the off-balancing impact of alignment delay and time-multiplexing strategies by illustrating how the foreseen transition that increasing the number of transmitters produces in the regime of a fixed-node size SCN in downlink operation fades out by a poor choice in the scheduling strategy.
Information Security Awareness at Oman Educational Institutions : An Academic Prespective
Venue: arXiv cs.CY 2016
Year: 2016

The gap between the knowledge and the practices regarding the computer and Internet use are the major factors which influence security of Information. A survey was performed on the education institutions in Oman to investigate the level of information security awareness among various entities. The survey focused on the following factors of IT Security: Demographics, Internet usage, Awareness about organizations network Security threats experience, Awareness on Password management, Email security awareness and Knowledge on security practices. The survey attracted 173 respondents: the level of information security awareness and knowledge on security practices were correlated and analyzed. The areas of weakness related to the security implementation, awareness and practice were identified.
A Multi-perspective Analysis of Carrier-Grade NAT Deployment
Venue: arXiv cs.NI 2016
Year: 2016

As ISPs face IPv4 address scarcity they increasingly turn to network address translation (NAT) to accommodate the address needs of their customers. Recently, ISPs have moved beyond employing NATs only directly at individual customers and instead begun deploying Carrier-Grade NATs (CGNs) to apply address translation to many independent and disparate endpoints spanning physical locations, a phenomenon that so far has received little in the way of empirical assessment. In this work we present a broad and systematic study of the deployment and behavior of these middleboxes. We develop a methodology to detect the existence of hosts behind CGNs by extracting non-routable IP addresses from peer lists we obtain by crawling the BitTorrent DHT. We complement this approach with improvements to our Netalyzr troubleshooting service, enabling us to determine a range of indicators of CGN presence as well as detailed insights into key properties of CGNs. Combining the two data sources we illustrate the scope of CGN deployment on today's Internet, and report on characteristics of commonly deployed CGNs and their effect on end users.
Detecting Novel Processes with CANDIES -- An Holistic Novelty Detection Technique based on Probabilistic Models
Venue: arXiv cs.LG 2016
Year: 2016

In this article, we propose CANDIES (Combined Approach for Novelty Detection in Intelligent Embedded Systems), a new approach to novelty detection in technical systems. We assume that in a technical system several processes interact. If we observe these processes with sensors, we are able to model the observations (samples) with a probabilistic model, where, in an ideal case, the components of the parametric mixture density model we use, correspond to the processes in the real world. Eventually, at run-time, novel processes emerge in the technical systems such as in the case of an unpredictable failure. As a consequence, new kinds of samples are observed that require an adaptation of the model. CANDIES relies on mixtures of Gaussians which can be used for classification purposes, too. New processes may emerge in regions of the models' input spaces where few samples were observed before (low-density regions) or in regions where already many samples were available (high-density regions). The latter case is more difficult, but most existing solutions focus on the former. Novelty detection in low- and high-density regions requires different detection strategies. With CANDIES, we introduce a new technique to detect novel processes in high-density regions by means of a fast online goodness-of-fit test. For detection in low-density regions we combine this approach with a 2SND (Two-Stage-Novelty-Detector) which we presented in preliminary work. The properties of CANDIES are evaluated using artificial data and benchmark data from the field of intrusion detection in computer networks, where the task is to detect new kinds of attacks.
Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale
Venue: arXiv cs.SI 2016
Year: 2016

Notions of community quality underlie network clustering. While studies surrounding network clustering are increasingly common, a precise understanding of the realtionship between different cluster quality metrics is unknown. In this paper, we examine the relationship between stand-alone cluster quality metrics and information recovery metrics through a rigorous analysis of four widely-used network clustering algorithms -- Louvain, Infomap, label propagation, and smart local moving. We consider the stand-alone quality metrics of modularity, conductance, and coverage, and we consider the information recovery metrics of adjusted Rand score, normalized mutual information, and a variant of normalized mutual information used in previous work. Our study includes both synthetic graphs and empirical data sets of sizes varying from 1,000 to 1,000,000 nodes. We find significant differences among the results of the different cluster quality metrics. For example, clustering algorithms can return a value of 0.4 out of 1 on modularity but score 0 out of 1 on information recovery. We find conductance, though imperfect, to be the stand-alone quality metric that best indicates performance on information recovery metrics. Our study shows that the variant of normalized mutual information used in previous work cannot be assumed to differ only slightly from traditional normalized mutual information. Smart local moving is the best performing algorithm in our study, but discrepancies between cluster evaluation metrics prevent us from declaring it absolutely superior. Louvain performed better than Infomap in nearly all the tests in our study, contradicting the results of previous work in which Infomap was superior to Louvain. We find that although label propagation performs poorly when clusters are less clearly defined, it scales efficiently and accurately to large graphs with well-defined clusters.
Declarative Machine Learning - A Classification of Basic Properties and Types
Venue: arXiv cs.DB 2016
Year: 2016

Declarative machine learning (ML) aims at the high-level specification of ML tasks or algorithms, and automatic generation of optimized execution plans from these specifications. The fundamental goal is to simplify the usage and/or development of ML algorithms, which is especially important in the context of large-scale computations. However, ML systems at different abstraction levels have emerged over time and accordingly there has been a controversy about the meaning of this general definition of declarative ML. Specification alternatives range from ML algorithms expressed in domain-specific languages (DSLs) with optimization for performance, to ML task (learning problem) specifications with optimization for performance and accuracy. We argue that these different types of declarative ML complement each other as they address different users (data scientists and end users). This paper makes an attempt to create a taxonomy for declarative ML, including a definition of essential basic properties and types of declarative ML. Along the way, we provide insights into implications of these properties. We also use this taxonomy to classify existing systems. Finally, we draw conclusions on defining appropriate benchmarks and specification languages for declarative ML.
Benchmarking NFV Software Dataplanes
Venue: arXiv cs.NI 2016
Year: 2016

A key enabling technology of NFV is software dataplane, which has attracted much attention in both academia and industry recently. Yet, till now there is little understanding about its performance in practice. In this paper, we make a benchmark measurement study of NFV software dataplanes in terms of packet processing capability, one of the most fundamental and critical performance metrics. Specifically, we compare two state-of-the-art open-source NFV dataplanes, SoftNIC and ClickOS, using commodity 10GbE NICs under various typical workloads. Our key observations are that (1) both dataplanes have performance issues processing small (<=128B) packets; (2) it is not always best to put all VMs of a service chain on one server due to NUMA effect. We propose resource allocation strategies to remedy the problems, including carefully adding CPU cores and vNICs to VMs, and spreading VMs of a service chain to separate servers. To fundamentally address these problems and scale their performance, SoftNIC and ClickOS could improve the support for NIC queues and multiple cores.
Interests Diffusion on a Semantic Multiplex
Venue: arXiv cs.SI 2016
Year: 2016

Exploiting the information about members of a Social Network (SN) represents one of the most attractive and dwelling subjects for both academic and applied scientists. The community of Complexity Science and especially those researchers working on multiplex social systems are devoting increasing efforts to outline general laws, models, and theories, to the purpose of predicting emergent phenomena in SN's (e.g. success of a product). On the other side the semantic web community aims at engineering a new generation of advanced services tailored to specific people needs. This implies defining constructs, models and methods for handling the semantic layer of SNs. We combined models and techniques from both the former fields to provide a hybrid approach to understand a basic (yet complex) phenomenon: the propagation of individual interests along the social networks. Since information may move along different social networks, one should take into account a multiplex structure. Therefore we introduced the notion of "Semantic Multiplex". In this paper we analyse two different semantic social networks represented by authors publishing in the Computer Science and those in the American Physical Society Journals. The comparison allows to outline common and specific features
Twitter as a Lifeline: Human-annotated Twitter Corpora for NLP of Crisis-related Messages
Venue: arXiv cs.CL 2016
Year: 2016

Microblogging platforms such as Twitter provide active communication channels during mass convergence and emergency events such as earthquakes, typhoons. During the sudden onset of a crisis situation, affected people post useful information on Twitter that can be used for situational awareness and other humanitarian disaster response efforts, if processed timely and effectively. Processing social media information pose multiple challenges such as parsing noisy, brief and informal messages, learning information categories from the incoming stream of messages and classifying them into different classes among others. One of the basic necessities of many of these tasks is the availability of data, in particular human-annotated data. In this paper, we present human-annotated Twitter corpora collected during 19 different crises that took place between 2013 and 2015. To demonstrate the utility of the annotations, we train machine learning classifiers. Moreover, we publish first largest word2vec word embeddings trained on 52 million crisis-related tweets. To deal with tweets language issues, we present human-annotated normalized lexical resources for different lexical variations.
An Algebraic Geometric Approach to Nivat's Conjecture
Venue: arXiv cs.DM 2016
Year: 2016

We study multidimensional configurations (infinite words) and subshifts of low pattern complexity using tools of algebraic geometry. We express the configuration as a multivariate formal power series over integers and investigate the setup when there is a non-trivial annihilating polynomial: a non-zero polynomial whose formal product with the power series is zero. Such annihilator exists, for example, if the number of distinct patterns of some finite shape $D$ in the configuration is at most the size $|D|$ of the shape. This is our low pattern complexity assumption. We prove that the configuration must be a sum of periodic configurations over integers, possibly with unbounded values. As a specific application of the method we obtain an asymptotic version of the well-known Nivat's conjecture: we prove that any two-dimensional, non-periodic configuration can satisfy the low pattern complexity assumption with respect to only finitely many distinct rectangular shapes $D$.
On a convergent off -policy temporal difference learning algorithm in on-line learning environment
Venue: arXiv cs.LG 2016
Year: 2016

In this paper we provide a rigorous convergence analysis of a "off"-policy temporal difference learning algorithm with linear function approximation and per time-step linear computational complexity in "online" learning environment. The algorithm considered here is TDC with importance weighting introduced by Maei et al. We support our theoretical results by providing suitable empirical results for standard off-policy counterexamples.
Square Formation by Asynchronous Oblivious Robots
Venue: arXiv cs.DC 2016
Year: 2016

A fundamental problem in Distributed Computing is the Pattern Formation problem, where some independent mobile entities, called robots, have to rearrange themselves in such a way as to form a given figure from every possible (non-degenerate) initial configuration. In the present paper, we consider robots that operate in the Euclidean plane and are dimensionless, anonymous, oblivious, silent, asynchronous, disoriented, non-chiral, and non-rigid. For this very elementary type of robots, the feasibility of the Pattern Formation problem has been settled, either in the positive or in the negative, for every possible pattern, except for one case: the Square Formation problem by a team of four robots. Here we solve this last case by giving a Square Formation algorithm and proving its correctness. Our contribution represents the concluding chapter in a long thread of research. Our results imply that in the context of the Pattern Formation problem for mobile robots, features such as synchronicity, chirality, and rigidity are computationally irrelevant.
Automatic Selection of the Optimal Local Feature Detector
Venue: arXiv cs.CV 2016
Year: 2016

A large number of different feature detectors has been proposed so far. Any existing approach presents strengths and weaknesses, which make a detector optimal only for a limited range of applications. A tool capable of selecting the optimal feature detector in relation to the operating conditions is presented in this paper. The input images are quickly analyzed to determine what type of image transformation is applied to them and at which amount. Finally, the detector that is expected to obtain the highest repeatability under such conditions, is chosen to extract features from the input images. The efficiency and the good accuracy in determining the optimal feature detector for any operating condition, make the proposed tool suitable to be utilized in real visual applications. %A large number of different feature detectors has been proposed so far. Any existing approach presents strengths and weaknesses, which make a detector optimal only for a limited range of applications. A large number of different local feature detectors have been proposed in the last few years. However, each feature detector has its own strengths ad weaknesses that limit its use to a specific range of applications. In this paper is presented a tool capable of quickly analysing input images to determine which type and amount of transformation is applied to them and then selecting the optimal feature detector, which is expected to perform the best. The results show that the performance and the fast execution time render the proposed tool suitable for real-world vision applications.