OpenRaiser/Intern-Atlas huggingface dataset:
Hierarchical Subtask Discovery With Non-Negative Matrix Factorization
Venue: arXiv cs.AI 2017
Year: 2017

Hierarchical reinforcement learning methods offer a powerful means of planning flexible behavior in complicated domains. However, learning an appropriate hierarchical decomposition of a domain into subtasks remains a substantial challenge. We present a novel algorithm for subtask discovery, based on the recently introduced multitask linearly-solvable Markov decision process (MLMDP) framework. The MLMDP can perform never-before-seen tasks by representing them as a linear combination of a previously learned basis set of tasks. In this setting, the subtask discovery problem can naturally be posed as finding an optimal low-rank approximation of the set of tasks the agent will face in a domain. We use non-negative matrix factorization to discover this minimal basis set of tasks, and show that the technique learns intuitive decompositions in a variety of domains. Our method has several qualitatively desirable features: it is not limited to learning subtasks with single goal states, instead learning distributed patterns of preferred states; it learns qualitatively different hierarchical decompositions in the same domain depending on the ensemble of tasks the agent will face; and it may be straightforwardly iterated to obtain deeper hierarchical decompositions.
Minimal Sum Labeling of Graphs
Venue: arXiv cs.DM 2017
Year: 2017

A graph $G$ is called a sum graph if there is a so-called sum labeling of $G$, i.e. an injective function $\ell: V(G) \rightarrow \mathbb{N}$ such that for every $u,v\in V(G)$ it holds that $uv\in E(G)$ if and only if there exists a vertex $w\in V(G)$ such that $\ell(u)+\ell(v) = \ell(w)$. We say that sum labeling $\ell$ is minimal if there is a vertex $u\in V(G)$ such that $\ell(u)=1$. In this paper, we show that if we relax the conditions (either allow non-injective labelings or consider graphs with loops) then there are sum graphs without a minimal labeling, which partially answers the question posed by Miller, Ryan and Smyth in 1998.
Low-Rank Hidden State Embeddings for Viterbi Sequence Labeling
Venue: arXiv cs.CL 2017
Year: 2017

In textual information extraction and other sequence labeling tasks it is now common to use recurrent neural networks (such as LSTM) to form rich embedded representations of long-term input co-occurrence patterns. Representation of output co-occurrence patterns is typically limited to a hand-designed graphical model, such as a linear-chain CRF representing short-term Markov dependencies among successive labels. This paper presents a method that learns embedded representations of latent output structure in sequence data. Our model takes the form of a finite-state machine with a large number of latent states per label (a latent variable CRF), where the state-transition matrix is factorized---effectively forming an embedded representation of state-transitions capable of enforcing long-term label dependencies, while supporting exact Viterbi inference over output labels. We demonstrate accuracy improvements and interpretable latent structure in a synthetic but complex task based on CoNLL named entity recognition.
Exact Tensor Completion from Sparsely Corrupted Observations via Convex Optimization
Venue: arXiv cs.LG 2017
Year: 2017

This paper conducts a rigorous analysis for provable estimation of multidimensional arrays, in particular third-order tensors, from a random subset of its corrupted entries. Our study rests heavily on a recently proposed tensor algebraic framework in which we can obtain tensor singular value decomposition (t-SVD) that is similar to the SVD for matrices, and define a new notion of tensor rank referred to as the tubal rank. We prove that by simply solving a convex program, which minimizes a weighted combination of tubal nuclear norm, a convex surrogate for the tubal rank, and the $\ell_1$-norm, one can recover an incoherent tensor exactly with overwhelming probability, provided that its tubal rank is not too large and that the corruptions are reasonably sparse. Interestingly, our result includes the recovery guarantees for the problems of tensor completion (TC) and tensor principal component analysis (TRPCA) under the same algebraic setup as special cases. An alternating direction method of multipliers (ADMM) algorithm is presented to solve this optimization problem. Numerical experiments verify our theory and real-world applications demonstrate the effectiveness of our algorithm.
Accurate Lung Segmentation via Network-Wise Training of Convolutional Networks
Venue: arXiv cs.CV 2017
Year: 2017

We introduce an accurate lung segmentation model for chest radiographs based on deep convolutional neural networks. Our model is based on atrous convolutional layers to increase the field-of-view of filters efficiently. To improve segmentation performances further, we also propose a multi-stage training strategy, network-wise training, which the current stage network is fed with both input images and the outputs from pre-stage network. It is shown that this strategy has an ability to reduce falsely predicted labels and produce smooth boundaries of lung fields. We evaluate the proposed model on a common benchmark dataset, JSRT, and achieve the state-of-the-art segmentation performances with much fewer model parameters.
Relatório Técnico: Controle Distribuído de Tráfego Baseado em Veículos Conectados e Comunicações Veiculares Centradas em Interesses
Venue: arXiv cs.OH 2017
Year: 2017

Although advanced traffic management systems can deal with the heterogeneous traffic flows approaching of intersections, their performances are compromised, when the traffic volume is not distributed uniformly. To evenly distribute the traffic flow, an advanced driver information system should be aware of the traffic control operations. However, such requirement can not ultimately be satisfied due to the gaps in state of the art in advanced traffic management systems. Therefore, this study proposes a distributed traffic control system, in which agents embedded in connected vehicles, traffic signals, urban elements and a traffic control center interact with each other to provide a greater traffic fluidity. Therefore, the agents depend strongly on a heterogeneous vehicular network. In this sense, this study also proposes a heterogeneous vehicular network whose communication protocol can satisfy the communication requirements of intelligent transportation systems service applications. According to the results obtained from simulations, the distributed traffic control system was able to maximize the flow of vehicles and the mean speed of the vehicles, and minimize the wait time, travel time, fuel consume and emissions (CO, CO$_2$, HC, NOx and PMx).
Efficient Inversion of Multiple-Scattering Model for Optical Diffraction Tomography
Venue: arXiv cs.CE 2017
Year: 2017

Optical diffraction tomography relies on solving an inverse scattering problem governed by the wave equation. Classical reconstruction algorithms are based on linear approximations of the forward model (Born or Rytov), which limits their applicability to thin samples with low refractive-index contrasts. More recent works have shown the benefit of adopting nonlinear models. They account for multiple scattering and reflections, improving the quality of reconstruction. To reduce the complexity and memory requirements of these methods, we derive an explicit formula for the Jacobian matrix of the nonlinear Lippmann-Schwinger model which lends itself to an efficient evaluation of the gradient of the data- fidelity term. This allows us to deploy efficient methods to solve the corresponding inverse problem subject to sparsity constraints.
Intercell Interference-Aware Scheduling for Delay Sensitive Applications in C-RAN
Venue: arXiv cs.IT 2017
Year: 2017

Cloud radio access network (C-RAN) architecture is a new mobile network architecture that enables cooperative baseband processing and information sharing among multiple cells and achieves high adaptability to nonuniform traffic by centralizing the baseband processing resources in a virtualized baseband unit (BBU) pool. In this work, we formulate the utility of each user using a convex delay cost function, and design a two-step scheduling algorithm with good delay performance for the C-RAN architecture. In the first step, all users in multiple cells are grouped into small user groups, according to their interference levels and estimated utilities. In the second step, channels are matched to the user groups to maximize the system utility. The performance of our algorithm is further studied via simulations, and the advantages of C-RAN architecture is verified.
Average-case reconstruction for the deletion channel: subpolynomially many traces suffice
Venue: arXiv cs.DS 2017
Year: 2017

The deletion channel takes as input a bit string $\mathbf{x} \in \{0,1\}^n$, and deletes each bit independently with probability $q$, yielding a shorter string. The trace reconstruction problem is to recover an unknown string $\mathbf{x}$ from many independent outputs (called "traces") of the deletion channel applied to $\mathbf{x}$. We show that if $\mathbf{x}$ is drawn uniformly at random and $q < 1/2$, then $e^{O(\log^{1/2} n)}$ traces suffice to reconstruct $\mathbf{x}$ with high probability. The previous best bound, established in 2008 by Holenstein-Mitzenmacher-Panigrahy-Wieder, uses $n^{O(1)}$ traces and only applies for $q$ less than a smaller threshold (it seems that $q < 0.07$ is needed). Our algorithm combines several ideas: 1) an alignment scheme for "greedily" fitting the output of the deletion channel as a subsequence of the input; 2) a version of the idea of "anchoring" used by Holenstein-Mitzenmacher-Panigrahy-Wieder; and 3) complex analysis techniques from recent work of Nazarov-Peres and De-O'Donnell-Servedio.
Fingerprint Extraction Using Smartphone Camera
Venue: arXiv cs.CV 2017
Year: 2017

In the previous decade, there has been a considerable rise in the usage of smartphones.Due to exorbitant advancement in technology, computational speed and quality of image capturing has increased considerably. With an increase in the need for remote fingerprint verification, smartphones can be used as a powerful alternative for fingerprint authentication instead of conventional optical sensors. In this research, wepropose a technique to capture finger-images from the smartphones and pre-process them in such a way that it can be easily matched with the optical sensor images.Effective finger-image capturing, image enhancement, fingerprint pattern extraction, core point detection and image alignment techniques have been discussed. The proposed approach has been validated on FVC 2004 DB1 & DB2 dataset and the results show the efficacy of the methodology proposed. The method can be deployed for real-time commercial usage.
Efficient hybrid search algorithm on ordered datasets
Venue: arXiv cs.DS 2017
Year: 2017

The increase in the rate of data is much higher than the increase in the speed of computers, which results in a heavy emphasis on search algorithms in research literature. Searching an item in ordered list is an efficient operation in data processing. Binary and interpolation search algorithms commonly are used for searching ordered dataset in many applications. In this paper, we present a hybrid algorithm to search ordered datasets based on the idea of interpolation and binary search. The proposed algorithm called Hybrid Search (HS), which is designed to work efficiently on unknown distributed ordered datasets, experimental results showed that our proposed algorithm has better performance when compared with other algorithms that use a similar approach.
Attention Transfer from Web Images for Video Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Training deep learning based video classifiers for action recognition requires a large amount of labeled videos. The labeling process is labor-intensive and time-consuming. On the other hand, large amount of weakly-labeled images are uploaded to the Internet by users everyday. To harness the rich and highly diverse set of Web images, a scalable approach is to crawl these images to train deep learning based classifier, such as Convolutional Neural Networks (CNN). However, due to the domain shift problem, the performance of Web images trained deep classifiers tend to degrade when directly deployed to videos. One way to address this problem is to fine-tune the trained models on videos, but sufficient amount of annotated videos are still required. In this work, we propose a novel approach to transfer knowledge from image domain to video domain. The proposed method can adapt to the target domain (i.e. video data) with limited amount of training data. Our method maps the video frames into a low-dimensional feature space using the class-discriminative spatial attention map for CNNs. We design a novel Siamese EnergyNet structure to learn energy functions on the attention maps by jointly optimizing two loss functions, such that the attention map corresponding to a ground truth concept would have higher energy. We conduct extensive experiments on two challenging video recognition datasets (i.e. TVHI and UCF101), and demonstrate the efficacy of our proposed method.
New Results on the DMC Capacity and Renyi's Divergence
Venue: arXiv cs.CR 2017
Year: 2017

This work is part of a project "Walsh Spectrum Analysis and the Cryptographic Applications". The project initiates the study of finding the largest (and/or significantly large) Walsh coefficients as well as the index positions of an unknown distribution by random sampling. This proposed problem has great significance in cryptography and communications. In early 2015, Yi JANET Lu first constructed novel imaginary channel transition matrices and introduced Shannon's channel coding problem to statistical cryptanalysis. For the first time, the channel capacity results of well-chosen transition matrices, which might be impossible to calculate traditionally, become of hottest research focus. For a few Discrete Memoryless Channels (DMCs), it is known that the capacity can be computed analytically; in general, there is no closed-form solution. This work is concerned with analytical results of channel capacity in the new setting. We study both the Blahut-Arimoto algorithm (which gave the first numerical solution historically) and the most recent results [Sutter et al'2014] for the transition matrix of $N\times M$. For an $ε$-approximation (i.e., the desired absolute accuracy of the approximate solution) of the capacity, the former has the computational complexity $ O(MN^2 \log N/ε) $, while the latter has the complexity $ O(M^2N\sqrt{\log N}/ε) $. We also study the relation of Renyi's divergence of degree $1/2$ and the generalized channel capacity of degree $1/2$.
Rank-metric LCD codes
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we investigate the rank-metric codes which are proposed by Delsarte and Gabidulin to be complementary dual codes. We point out the relationship between Delsarte complementary dual codes and Gabidulin complementary dual codes. In finite field $\mathbb{F}_{q}^{m}$, we construct two classes of Gabidulin LCD MRD codes by self-dual basis (or almost self-dual basis) of $\mathbb{F}_{q}^{m}$ over $\mathbb{F}_{q}$. Under a suitable condition, we determine a sufficient condition for Delsarte optimal anticodes to be LCD codes over $\mathbb{F}_{q}$.
What Will I Do Next? The Intention from Motion Experiment
Venue: arXiv cs.CV 2017
Year: 2017

In computer vision, video-based approaches have been widely explored for the early classification and the prediction of actions or activities. However, it remains unclear whether this modality (as compared to 3D kinematics) can still be reliable for the prediction of human intentions, defined as the overarching goal embedded in an action sequence. Since the same action can be performed with different intentions, this problem is more challenging but yet affordable as proved by quantitative cognitive studies which exploit the 3D kinematics acquired through motion capture systems. In this paper, we bridge cognitive and computer vision studies, by demonstrating the effectiveness of video-based approaches for the prediction of human intentions. Precisely, we propose Intention from Motion, a new paradigm where, without using any contextual information, we consider instantaneous grasping motor acts involving a bottle in order to forecast why the bottle itself has been reached (to pass it or to place in a box, or to pour or to drink the liquid inside). We process only the grasping onsets casting intention prediction as a classification framework. Leveraging on our multimodal acquisition (3D motion capture data and 2D optical videos), we compare the most commonly used 3D descriptors from cognitive studies with state-of-the-art video-based techniques. Since the two analyses achieve an equivalent performance, we demonstrate that computer vision tools are effective in capturing the kinematics and facing the cognitive problem of human intention prediction.
Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems
Venue: arXiv cs.DM 2017
Year: 2017

We investigate parameterizing hard combinatorial problems by the size of the solution set compared to all solution candidates. Our main result is a uniform sampling algorithm for satisfying assignments of 2-CNF formulas that runs in expected time $O^*(\varepsilon^{-0.617})$ where $\varepsilon$ is the fraction of assignments that are satisfying. This improves significantly over the trivial sampling bound of expected $Θ^*(\varepsilon^{-1})$, and on all previous algorithms whenever $\varepsilon = Ω(0.708^n)$. We also consider algorithms for 3-SAT with an $\varepsilon$ fraction of satisfying assignments, and prove that it can be solved in $O^*(\varepsilon^{-2.27})$ deterministic time, and in $O^*(\varepsilon^{-0.936})$ randomized time. Finally, to further demonstrate the applicability of this framework, we also explore how similar techniques can be used for vertex cover problems.
Independently Controllable Factors
Venue: arXiv cs.LG 2017
Year: 2017

It has been postulated that a good representation is one that disentangles the underlying explanatory factors of variation. However, it remains an open question what kind of training framework could potentially achieve that. Whereas most previous work focuses on the static setting (e.g., with images), we postulate that some of the causal factors could be discovered if the learner is allowed to interact with its environment. The agent can experiment with different actions and observe their effects. More specifically, we hypothesize that some of these factors correspond to aspects of the environment which are independently controllable, i.e., that there exists a policy and a learnable feature for each such aspect of the environment, such that this policy can yield changes in that feature with minimal changes to other features that explain the statistical variations in the observed data. We propose a specific objective function to find such factors and verify experimentally that it can indeed disentangle independently controllable aspects of the environment without any extrinsic reward signal.
A solution for ARP spoofing: Layer-2 MAC and protocol filtering and arpserver
Venue: arXiv cs.CR 2017
Year: 2017

Most attacks are launched inside the companies by the employees of the same company. These kinds of attacks are generally against layer-2, not against layer-3 or IP. These attacks abuse the switch operation at layer-2. One of the attacks of this kind is Address Resolution Protocol (ARP) Spoofing (sometimes it is called ARP poisoning). This attack is classified as the 'man in the middle' (MITM) attack. The usual security systems such as (personal) firewalls or virus protection software can not recognize this type of attack. Taping into the communication between two hosts one can access the confidential data. Malicious software to run internal attacks on a network is freely available on the Internet, such as Ettercap. In this paper a solution is proposed and implemented to prevent ARP Spoofing. In this proposal access control lists (ACL) for layer-2 Media Access Control (MAC) address and protocol filtering and an application called ARPserver which will reply all ARP requests are used.
A Low-rank Spline Approximation of Planar Domains
Venue: arXiv cs.CG 2017
Year: 2017

Construction of spline surfaces from given boundary curves is one of the classical problems in computer aided geometric design, which regains much attention in isogeometric analysis in recent years and is called domain parameterization. However, for most of the state-of-the-art parameterization methods, the rank of the spline parameterization is usually large, which results in higher computational cost in solving numerical PDEs. In this paper, we propose a low-rank representation for the spline parameterization of planar domains using low-rank tensor approximation technique, and apply quasi-conformal map as the framework of the spline parameterization. Under given correspondence of boundary curves, a quasi-conformal map with low rank and low distortion between a unit square and the computational domain can be modeled as a non-linear optimization problem. We propose an efficient algorithm to compute the quasi-conformal map by solving two convex optimization problems alternatively. Experimental results show that our approach can produce a bijective and low-rank parametric spline representation of planar domains, which results in better performance than previous approaches in solving numerical PDEs.
Using a Predator-Prey Model to Explain Variations of Cloud Spot Price
Venue: arXiv cs.DC 2017
Year: 2017

The spot pricing scheme has been considered to be resource-efficient for providers and cost-effective for consumers in the Cloud market. Nevertheless, unlike the static and straightforward strategies of trading on-demand and reserved Cloud services, the market-driven mechanism for trading spot service would be complicated for both implementation and understanding. The largely invisible market activities and their complex interactions could especially make Cloud consumers hesitate to enter the spot market. To reduce the complexity in understanding the Cloud spot market, we decided to reveal the backend information behind spot price variations. Inspired by the methodology of reverse engineering, we developed a Predator-Prey model that can simulate the interactions between demand and resource based on the visible spot price traces. The simulation results have shown some basic regular patterns of market activities with respect to Amazon's spot instance type m3.large. Although the findings of this study need further validation by using practical data, our work essentially suggests a promising approach (i.e.~using a Predator-Prey model) to investigate spot market activities.