OpenRaiser/Intern-Atlas huggingface dataset:
Kernel Cross-Correlator
Venue: arXiv cs.CV 2018
Year: 2018

Cross-correlator plays a significant role in many visual perception tasks, such as object detection and tracking. Beyond the linear cross-correlator, this paper proposes a kernel cross-correlator (KCC) that breaks traditional limitations. First, by introducing the kernel trick, the KCC extends the linear cross-correlation to non-linear space, which is more robust to signal noises and distortions. Second, the connection to the existing works shows that KCC provides a unified solution for correlation filters. Third, KCC is applicable to any kernel function and is not limited to circulant structure on training data, thus it is able to predict affine transformations with customized properties. Last, by leveraging the fast Fourier transform (FFT), KCC eliminates direct calculation of kernel vectors, thus achieves better performance yet still with a reasonable computational cost. Comprehensive experiments on visual tracking and human activity recognition using wearable devices demonstrate its robustness, flexibility, and efficiency. The source codes of both experiments are released at https://github.com/wang-chen/KCC
Sensor Assignment Algorithms to Improve Observability while Tracking Targets
Venue: arXiv cs.RO 2018
Year: 2018

We study two sensor assignment problems for multi-target tracking with the goal of improving the observability of the underlying estimator. We consider various measures of the observability matrix as the assignment value function. We first study the general version where the sensors must form teams to track individual targets. If the value function is monotonically increasing and submodular then a greedy algorithm yields a 1/2-approximation. We then study a restricted version where exactly two sensors must be assigned to each target. We present a 1/3-approximation algorithm for this problem which holds for arbitrary value functions (not necessarily submodular or monotone). In addition to approximation algorithms, we also present various properties of observability measures. We show that the inverse of the condition number of the observability matrix is neither monotone nor submodular, but present other measures which are. Specifically, we show that the trace and rank of the symmetric observability matrix are monotone and submodular and the log determinant of the symmetric observability matrix is monotone and submodular when the matrix is non-singular. If the target's motion model is not known, the inverse cannot be computed exactly. Instead, we present a lower bound for distance sensors. In addition to theoretical results, we evaluate our results empirically through simulations.
Reasoning about proof and knowledge
Venue: arXiv cs.LO 2018
Year: 2018

In previous work [Lewitzka, Log. J. IGPL 2017], we presented a hierarchy of classical modal systems, along with algebraic semantics, for the reasoning about intuitionistic truth, belief and knowledge. Deviating from Gödel's interpretation of IPC in S4, our modal systems contain IPC in the way established in [Lewitzka, J. Log. Comp. 2015]. The modal operator can be viewed as a predicate for intuitionistic truth, i.e. proof. Epistemic principles are partially adopted from Intuitionistic Epistemic Logic IEL [Artemov and Protopopescu, Rev. Symb. Log. 2016]. In the present paper, we show that the S5-style systems of our hierarchy correspond to an extended Brouwer-Heyting-Kolmogorov interpretation and are complete w.r.t. a relational semantics based on intuitionistic general frames. In this sense, our S5-style logics are adequate and complete systems for the reasoning about proof combined with belief or knowledge. The proposed relational semantics is a uniform framework in which also IEL can be modeled. Verification-based intuitionistic knowledge formalized in IEL turns out to be a special case of the kind of knowledge described by our S5-style systems.
Covert Wireless Communication with Artificial Noise Generation
Venue: arXiv cs.IT 2018
Year: 2018

Covert communication conceals the transmission of the message from an attentive adversary. Recent work on the limits of covert communication in additive white Gaussian noise (AWGN) channels has demonstrated that a covert transmitter (Alice) can reliably transmit a maximum of $\mathcal{O}\left(\sqrt{n}\right)$ bits to a covert receiver (Bob) without being detected by an adversary (Warden Willie) in $n$ channel uses. This paper focuses on the scenario where other friendly nodes distributed according to a two-dimensional Poisson point process with density $m$ are present in the environment. We propose a strategy where the friendly node closest to the adversary, without close coordination with Alice, produces artificial noise. We show that this method allows Alice to reliably and covertly send $\mathcal{O}(\min\{{n,m^{γ/2}\sqrt{n}}\})$ bits to Bob in $n$ channel uses, where $γ$ is the path-loss exponent. Moreover, we also consider a setting where there are $N_{\mathrm{w}}$ collaborating adversaries uniformly and randomly located in the environment and show that in $n$ channel uses, Alice can reliably and covertly send $\mathcal{O}\left(\min\left\{n,\frac{m^{γ/2} \sqrt{n}}{N_{\mathrm{w}}^γ}\right\}\right)$ bits to Bob when $γ>2$, and $\mathcal{O}\left(\min\left\{n,\frac{m \sqrt{n}}{N_{\mathrm{w}}^{2}\log^2 {N_{\mathrm{w}}}}\right\}\right)$ when $γ= 2$. Conversely, we demonstrate that no higher covert throughput is possible for $γ>2$.
SpectralLeader: Online Spectral Learning for Single Topic Models
Venue: arXiv cs.LG 2018
Year: 2018

We study the problem of learning a latent variable model from a stream of data. Latent variable models are popular in practice because they can explain observed data in terms of unobserved concepts. These models have been traditionally studied in the offline setting. In the online setting, on the other hand, the online EM is arguably the most popular algorithm for learning latent variable models. Although the online EM is computationally efficient, it typically converges to a local optimum. In this work, we develop a new online learning algorithm for latent variable models, which we call SpectralLeader. SpectralLeader always converges to the global optimum, and we derive a sublinear upper bound on its $n$-step regret in the bag-of-words model. In both synthetic and real-world experiments, we show that SpectralLeader performs similarly to or better than the online EM with tuned hyper-parameters.
Convergence characteristics of the generalized residual cutting method
Venue: arXiv cs.NA 2018
Year: 2018

The residual cutting (RC) method has been proposed for efficiently solving linear equations obtained from elliptic partial differential equations. Based on the RC, we have introduced the generalized residual cutting (GRC) method, which can be applied to general sparse matrix problems. In this paper, we study the mathematics of the GRC algorithm and and prove it is a Krylov subspace method. Moreover, we show that it is deeply related to the conjugate residual (CR) method and that GRC becomes equivalent to CR for symmetric matrices. Also, in numerical experiments, GRC shows more robust convergence and needs less memory compared to GMRES, for significantly larger matrix sizes.
A First Derivative Potts Model for Segmentation and Denoising Using ILP
Venue: arXiv cs.CV 2018
Year: 2018

Unsupervised image segmentation and denoising are two fundamental tasks in image processing. Usually, graph based models such as multicut are used for segmentation and variational models are employed for denoising. Our approach addresses both problems at the same time. We propose a novel ILP formulation of the first derivative Potts model with the $\ell_1$ data term, where binary variables are introduced to deal with the $\ell_0$ norm of the regularization term. The ILP is then solved by a standard off-the-shelf MIP solver. Numerical experiments are compared with the multicut problem.
Hybrid Beamforming Based on Implicit Channel State Information for Millimeter Wave Links
Venue: arXiv cs.IT 2018
Year: 2018

Hybrid beamforming provides a promising solution to achieve high data rate transmission at millimeter waves. Implementing hybrid beamforming at a transceiver based on available channel state information is a common solution. However, many reference methods ignore the complexity of channel estimation for large antenna arrays or subsequent steps, such as the singular value decomposition of a channel matrix. To this end, we present a low-complexity scheme that exploits implicit channel knowledge to facilitate the design of hybrid beamforming for frequency-selective fading channels. The implicit channel knowledge can be interpreted as couplings between all possible pairs of analog beamforming vectors at the transmitter and receiver over the surrounding channel. Instead of calculating mutual information between large antenna arrays, we focus on small-size coupling matrices between beam patterns selected by using appropriate key parameters as performance indicators. This converts the complicated hybrid beamforming problem to a much simpler one: it amounts to collecting different sets of the large-power coupling coefficients to construct multiple alternatives for an effective channel matrix. Then, the set yielding the largest Frobenius norm (or the largest absolute value of the determinant) of the effective channel provides the solution to the hybrid beamforming problem. It turns out that the proposed method does not require information on MIMO channel and can be simply implemented by the received correlated pilot signals that are supposed to be used for channel estimation.
H-DenseUNet: Hybrid Densely Connected UNet for Liver and Tumor Segmentation from CT Volumes
Venue: arXiv cs.CV 2018
Year: 2018

Liver cancer is one of the leading causes of cancer death. To assist doctors in hepatocellular carcinoma diagnosis and treatment planning, an accurate and automatic liver and tumor segmentation method is highly demanded in the clinical practice. Recently, fully convolutional neural networks (FCNs), including 2D and 3D FCNs, serve as the back-bone in many volumetric image segmentation. However, 2D convolutions can not fully leverage the spatial information along the third dimension while 3D convolutions suffer from high computational cost and GPU memory consumption. To address these issues, we propose a novel hybrid densely connected UNet (H-DenseUNet), which consists of a 2D DenseUNet for efficiently extracting intra-slice features and a 3D counterpart for hierarchically aggregating volumetric contexts under the spirit of the auto-context algorithm for liver and tumor segmentation. We formulate the learning process of H-DenseUNet in an end-to-end manner, where the intra-slice representations and inter-slice features can be jointly optimized through a hybrid feature fusion (HFF) layer. We extensively evaluated our method on the dataset of MICCAI 2017 Liver Tumor Segmentation (LiTS) Challenge and 3DIRCADb Dataset. Our method outperformed other state-of-the-arts on the segmentation results of tumors and achieved very competitive performance for liver segmentation even with a single model.
Expanding Motor Skills through Relay Neural Networks
Venue: arXiv cs.RO 2018
Year: 2018

While the recent advances in deep reinforcement learning have achieved impressive results in learning motor skills, many of the trained policies are only capable within a limited set of initial states. We propose a technique to break down a complex robotic task to simpler subtasks and train them sequentially such that the robot can expand its existing skill set gradually. Our key idea is to build a tree of local control policies represented by neural networks, which we refer as Relay Neural Networks. Starting from the root policy that attempts to achieve the task from a small set of initial states, each subsequent policy expands the set of successful initial states by driving the new states to existing "good" states. Our algorithm utilizes the value function of the policy to determine whether a state is "good" under each policy. We take advantage of many existing policy search algorithms that learn the value function simultaneously with the policy, such as those that use actor-critic representations or those that use the advantage function to reduce variance. We demonstrate that the relay networks can solve complex continuous control problems for underactuated dynamic systems.
Tensor-Based Classifiers for Hyperspectral Data Analysis
Venue: arXiv cs.CV 2018
Year: 2018

In this work, we present tensor-based linear and nonlinear models for hyperspectral data classification and analysis. By exploiting principles of tensor algebra, we introduce new classification architectures, the weight parameters of which satisfies the {\it rank}-1 canonical decomposition property. Then, we introduce learning algorithms to train both the linear and the non-linear classifier in a way to i) to minimize the error over the training samples and ii) the weight coefficients satisfies the {\it rank}-1 canonical decomposition property. The advantages of the proposed classification model is that i) it reduces the number of parameters required and thus reduces the respective number of training samples required to properly train the model, ii) it provides a physical interpretation regarding the model coefficients on the classification output and iii) it retains the spatial and spectral coherency of the input samples. To address issues related with linear classification, characterizing by low capacity, since it can produce rules that are linear in the input space, we introduce non-linear classification models based on a modification of a feedforward neural network. We call the proposed architecture {\it rank}-1 Feedfoward Neural Network (FNN), since their weights satisfy the {\it rank}-1 caconical decomposition property. Appropriate learning algorithms are also proposed to train the network. Experimental results and comparisons with state of the art classification methods, either linear (e.g., SVM) and non-linear (e.g., deep learning) indicates the outperformance of the proposed scheme, especially in cases where a small number of training samples are available. Furthermore, the proposed tensor-based classfiers are evaluated against their capabilities in dimensionality reduction.
Hodge decomposition and the Shapley value of a cooperative game
Venue: arXiv cs.GT 2018
Year: 2018

We show that a cooperative game may be decomposed into a sum of component games, one for each player, using the combinatorial Hodge decomposition on a graph. This decomposition is shown to satisfy certain efficiency, null-player, symmetry, and linearity properties. Consequently, we obtain a new characterization of the classical Shapley value as the value of the grand coalition in each player's component game. We also relate this decomposition to a least-squares problem involving inessential games (in a similar spirit to previous work on least-squares and minimum-norm solution concepts) and to the graph Laplacian. Finally, we generalize this approach to games with weights and/or constraints on coalition formation.
TuringMobile: A Turing Machine of Oblivious Mobile Robots with Limited Visibility and its Applications
Venue: arXiv cs.DC 2018
Year: 2018

In this paper we investigate the computational power of a set of mobile robots with limited visibility. At each iteration, a robot takes a snapshot of its surroundings, uses the snapshot to compute a destination point, and it moves toward its destination. Each robot is punctiform and memoryless, it operates in $\mathbb{R}^m$, it has a local reference system independent of the other robots' ones, and is activated asynchronously by an adversarial scheduler. Moreover, robots are non-rigid, in that they may be stopped by the scheduler at each move before reaching their destination (but are guaranteed to travel at least a fixed unknown distance before being stopped). We show that despite these strong limitations, it is possible to arrange $3m+3k$ of these weak entities in $\mathbb{R}^m$ to simulate the behavior of a stronger robot that is rigid (i.e., it always reaches its destination) and is endowed with $k$ registers of persistent memory, each of which can store a real number. We call this arrangement a TuringMobile. In its simplest form, a TuringMobile consisting of only three robots can travel in the plane and store and update a single real number. We also prove that this task is impossible with fewer than three robots. Among the applications of the TuringMobile, we focused on Near-Gathering (all robots have to gather in a small-enough disk) and Pattern Formation (of which Gathering is a special case) with limited visibility. Interestingly, our investigation implies that both problems are solvable in Euclidean spaces of any dimension, even if the visibility graph of the robots is initially disconnected, provided that a small amount of these robots are arranged to form a TuringMobile. In the special case of the plane, a basic TuringMobile of only three robots is sufficient.
Generating Sentences by Editing Prototypes
Venue: arXiv cs.CL 2018
Year: 2018

We propose a new generative model of sentences that first samples a prototype sentence from the training corpus and then edits it into a new sentence. Compared to traditional models that generate from scratch either left-to-right or by first sampling a latent sentence vector, our prototype-then-edit model improves perplexity on language modeling and generates higher quality outputs according to human evaluation. Furthermore, the model gives rise to a latent edit vector that captures interpretable semantics such as sentence similarity and sentence-level analogies.
Performance Analysis of QoS-Differentiated Pricing in Cloud Computing: An Analytical Approach
Venue: arXiv cs.DC 2018
Year: 2018

A fundamental goal in the design of IaaS service is to enable both user-friendly and cost-effective service access, while attaining high resource efficiency for revenue maximization. QoS differentiation is an important lens to achieve this design goal. In this paper, we propose the first analytical QoS-differentiated resource management and pricing architecture in the cloud computing context; here, a cloud service provider (CSP) offers a portfolio of SLAs. In order to maximize the CSP's revenue, we address two technical questions: (1) how to set the SLA prices so as to direct users to the SLAs best fitting their needs, and, (2) determining how many servers should be assigned to each SLA, and which users and how many of their jobs are admitted to be served. We propose optimal schemes to jointly determine SLA-based prices and perform capacity planning in polynomial time. Our pricing model retains high usability at the customer's end. Compared with standard usage-based pricing schemes, numerical results show that the proposed scheme can improve the revenue by up to a five-fold increase.
Embodied Evolution in Collective Robotics: A Review
Venue: arXiv cs.NE 2018
Year: 2018

This paper provides an overview of evolutionary robotics techniques applied to on-line distributed evolution for robot collectives -- namely, embodied evolution. It provides a definition of embodied evolution as well as a thorough description of the underlying concepts and mechanisms. The paper also presents a comprehensive summary of research published in the field since its inception (1999-2017), providing various perspectives to identify the major trends. In particular, we identify a shift from considering embodied evolution as a parallel search method within small robot collectives (fewer than 10 robots) to embodied evolution as an on-line distributed learning method for designing collective behaviours in swarm-like collectives. The paper concludes with a discussion of applications and open questions, providing a milestone for past and an inspiration for future research.
Cluster Editing for Multi-Layer and Temporal Graphs
Venue: arXiv cs.DM 2018
Year: 2018

Motivated by the recent rapid growth of research for algorithms to cluster multi-layer and temporal graphs, we study extensions of the classical Cluster Editing problem. In Multi-Layer Cluster Editing we receive a set of graphs on the same vertex set, called layers and aim to transform all layers into cluster graphs (disjoint unions of cliques) that differ only slightly. More specifically, we want to mark at most $d$ vertices and to transform each layer into a cluster graph using at most $k$ edge additions or deletions per layer so that, if we remove the marked vertices, we obtain the same cluster graph in all layers. In Temporal Cluster Editing we receive a sequence of layers and we want to transform each layer into a cluster graph so that consecutive layers differ only slightly. That is, we want to transform each layer into a cluster graph with at most $k$ edge additions or deletions and to mark a distinct set of $d$ vertices in each layer so that each two consecutive layers are the same after removing the vertices marked in the first of the two layers. We study the combinatorial structure of the two problems via their parameterized complexity with respect to the parameters $d$ and $k$, among others. Despite the similar definition, the two problems behave quite differently: In particular, Multi-Layer Cluster Editing is fixed-parameter tractable with running time $k^{O(k+d)}\cdot s^{O(1)}$ for inputs of size $s$, whereas Temporal Cluster Editing is W[1]-hard with respect to $k$ even if $d = 3$.
Contract Theory Approach to Incentivizing Market and Control Design
Venue: arXiv cs.SY 2018
Year: 2018

We discuss an incentivizing market and model-based approach to design the energy management and control systems which realize high-quality ancillary services in dynamic power grids. Under the electricity liberalization, such incentivizing market should secure a high speed market-clearing by using the market players' private information well. Inspired by contract theory in microeconomics field, we propose a novel design method of such incentivizing market based on the integration of the economic models and the dynamic grid model. The conventional contract problems are analyzed for static systems or dynamical systems with control inputs directly operated by the principal. The analysis is, however, in discord with the incentivizing market. The main challenge of our approach is to reformulate the contract problems adapted to the market from the system and control perspective. We first establish the fundamental formulas for optimal design and clarify the basic properties of the designed market. We also discuss possibilities, limitation and some challenges in the direction of our approach and general market-based approaches.
A Read-Write Memory Network for Movie Story Understanding
Venue: arXiv cs.CV 2018
Year: 2018

We propose a novel memory network model named Read-Write Memory Network (RWMN) to perform question and answering tasks for large-scale, multimodal movie story understanding. The key focus of our RWMN model is to design the read network and the write network that consist of multiple convolutional layers, which enable memory read and write operations to have high capacity and flexibility. While existing memory-augmented network models treat each memory slot as an independent block, our use of multi-layered CNNs allows the model to read and write sequential memory cells as chunks, which is more reasonable to represent a sequential story because adjacent memory blocks often have strong correlations. For evaluation, we apply our model to all the six tasks of the MovieQA benchmark, and achieve the best accuracies on several tasks, especially on the visual QA task. Our model shows a potential to better understand not only the content in the story, but also more abstract information, such as relationships between characters and the reasons for their actions.