OpenRaiser/Intern-Atlas huggingface dataset:
Unsupervised Joint Mining of Deep Features and Image Labels for Large-scale Radiology Image Categorization and Scene Recognition
Venue: arXiv cs.CV 2017
Year: 2017

The recent rapid and tremendous success of deep convolutional neural networks (CNN) on many challenging computer vision tasks largely derives from the accessibility of the well-annotated ImageNet and PASCAL VOC datasets. Nevertheless, unsupervised image categorization (i.e., without the ground-truth labeling) is much less investigated, yet critically important and difficult when annotations are extremely hard to obtain in the conventional way of "Google Search" and crowd sourcing. We address this problem by presenting a looped deep pseudo-task optimization (LDPO) framework for joint mining of deep CNN features and image labels. Our method is conceptually simple and rests upon the hypothesized "convergence" of better labels leading to better trained CNN models which in turn feed more discriminative image representations to facilitate more meaningful clusters/labels. Our proposed method is validated in tackling two important applications: 1) Large-scale medical image annotation has always been a prohibitively expensive and easily-biased task even for well-trained radiologists. Significantly better image categorization results are achieved via our proposed approach compared to the previous state-of-the-art method. 2) Unsupervised scene recognition on representative and publicly available datasets with our proposed technique is examined. The LDPO achieves excellent quantitative scene classification results. On the MIT indoor scene dataset, it attains a clustering accuracy of 75.3%, compared to the state-of-the-art supervised classification accuracy of 81.0% (when both are based on the VGG-VD model).
Additive cyclic codes over finite commutative chain rings
Venue: arXiv cs.IT 2017
Year: 2017

Additive cyclic codes over Galois rings were investigated in previous works. In this paper, we investigate the same problem but over a more general ring family, finite commutative chain rings. When we focus on non-Galois finite commutative chain rings, we observe two different kinds of additivity. One of them is a natural generalization of the previous studies, whereas the other one has some unusual properties especially while constructing dual codes. We interpret the reasons of such properties and illustrate our results giving concrete examples.
On the Average Locality of Locally Repairable Codes
Venue: arXiv cs.IT 2017
Year: 2017

A linear block code with dimension $k$, length $n$, and minimum distance $d$ is called a locally repairable code (LRC) with locality $r$ if it can retrieve any coded symbol by at most $r$ other coded symbols. LRCs have been recently proposed and used in practice in distributed storage systems (DSSs) such as Windows Azure storage and Facebook HDFS-RAID. Theoretical bounds on the maximum locality of LRCs ($r$) have been established. The \textit{average} locality of an LRC ($\overline{r}$) directly affects the costly repair bandwidth, disk I/O, and number of nodes involved in the repair process of a missing data block. There is a gap in the literature studying $\overline{r}$. In this paper, we establish a lower bound on $\overline{r}$ of arbitrary $(n,k,d)$ LRCs. Furthermore, we obtain a tight lower bound on $\overline{r}$ for a practical case where the code rate $(R=\frac{k}{n})$ is greater than $(1-\frac{1}{\sqrt{n}})^2$. Finally, we design three classes of LRCs that achieve the obtained bounds on $\overline{r}$. Comparing with the existing LRCs, our proposed codes improve the average locality without sacrificing such crucial parameters as the code rate or minimum distance.
Quantum Information on Spectral Sets
Venue: arXiv cs.IT 2017
Year: 2017

For convex optimization problems Bregman divergences appear as regret functions. Such regret functions can be defined on any convex set but if a sufficiency condition is added the regret function must be proportional to information divergence and the convex set must be spectral. Spectral set are sets where different orthogonal decompositions of a state into pure states have unique mixing coefficients. Only on such spectral sets it is possible to define well behaved information theoretic quantities like entropy and divergence. It is only possible to perform measurements in a reversible way if the state space is spectral. The most important spectral sets can be represented as positive elements of Jordan algebras with trace 1. This means that Jordan algebras provide a natural framework for studying quantum information. We compare information theory on Hilbert spaces with information theory in more general Jordan algebras, and conclude that much of the formalism is unchanged but also identify some important differences.
Two-Dimensional Source Coding by Means of Subblock Enumeration
Venue: arXiv cs.IT 2017
Year: 2017

A technique of lossless compression via substring enumeration (CSE) attains compression ratios as well as popular lossless compressors for one-dimensional (1D) sources. The CSE utilizes a probabilistic model built from the circular string of an input source for encoding the source.The CSE is applicable to two-dimensional (2D) sources such as images by dealing with a line of pixels of 2D source as a symbol of an extended alphabet. At the initial step of the CSE encoding process, we need to output the number of occurrences of all symbols of the extended alphabet, so that the time complexity increase exponentially when the size of source becomes large. To reduce the time complexity, we propose a new CSE which can encode a 2D source in block-by-block instead of line-by-line. The proposed CSE utilizes the flat torus of an input 2D source as a probabilistic model for encoding the source instead of the circular string of the source. Moreover, we analyze the limit of the average codeword length of the proposed CSE for general sources.
Discriminative Neural Topic Models
Venue: arXiv cs.LG 2017
Year: 2017

We propose a neural network based approach for learning topics from text and image datasets. The model makes no assumptions about the conditional distribution of the observed features given the latent topics. This allows us to perform topic modelling efficiently using sentences of documents and patches of images as observed features, rather than limiting ourselves to words. Moreover, the proposed approach is online, and hence can be used for streaming data. Furthermore, since the approach utilizes neural networks, it can be implemented on GPU with ease, and hence it is very scalable.
Linear Representation of Symmetric Games
Venue: arXiv cs.GT 2017
Year: 2017

Using semi-tensor product of matrices, the structures of several kinds of symmetric games are investigated via the linear representation of symmetric group in the structure vector of games as its representation space. First of all, the symmetry, described as the action of symmetric group on payoff functions, is converted into the product of permutation matrices with structure vectors of payoff functions. Using the linear representation of the symmetric group in structure vectors, the algebraic conditions for the ordinary, weighted, renaming and name-irrelevant symmetries are obtained respectively as the invariance under the corresponding linear representations. Secondly, using the linear representations the relationship between symmetric games and potential games is investigated. This part is mainly focused on Boolean games. An alternative proof is given to show that ordinary, renaming and weighted symmetric Boolean games are also potential ones under our framework. The corresponding potential functions are also obtained. Finally, an example is given to show that some other Boolean games could also be potential games.
WhatsApp security and role of metadata in preserving privacy
Venue: arXiv cs.CR 2017
Year: 2017

WhatsApp messenger is arguably the most popular mobile app available on all smart-phones. Over one billion people worldwide for free messaging, calling, and media sharing use it. In April 2016, WhatsApp switched to a default end-to-end encrypted service. This means that all messages (SMS), phone calls, videos, audios, and any other form of information exchanged cannot be read by any unauthorized entity since WhatsApp. In this paper we analyze the WhatsApp messaging platform and critique its security architecture along with a focus on its privacy preservation mechanisms. We report that the Signal Protocol, which forms the basis of WhatsApp end-to-end encryption, does offer protection against forward secrecy, and MITM to a large extent. Finally, we argue that simply encrypting the end-to-end channel cannot preserve privacy. The metadata can reveal just enough information to show connections between people, their patterns, and personal information. This paper elaborates on the security architecture of WhatsApp and performs an analysis on the various protocols used. This enlightens us on the status quo of the app security and what further measures can be used to fill existing gaps without compromising the usability. We start by describing the following (i) important concepts that need to be understood to properly understand security, (ii) the security architecture, (iii) security evaluation, (iv) followed by a summary of our work. Some of the important concepts that we cover in this paper before evaluating the architecture are - end-to-end encryption (E2EE), signal protocol, and curve25519. The description of the security architecture covers key management, end-to-end encryption in WhatsApp, Authentication Mechanism, Message Exchange, and finally the security evaluation. We then cover importance of metadata and role it plays in conserving privacy with respect to whatsapp.
Practical Power-Balanced Non-Orthogonal Multiple Access
Venue: arXiv cs.IT 2017
Year: 2017

This paper investigates practical 5G strategies for power-balanced non-orthogonal multiple access (NOMA). By allowing multiple users to share the same time and frequency, NOMA can scale up the number of served users and increase spectral efficiency compared with existing orthogonal multiple access (OMA). Conventional NOMA schemes with successive interference cancellation (SIC) do not work well when users with comparable received powers transmit together. To allow power-balanced NOMA (more exactly, near power-balanced NOMA), this paper investigates a new NOMA architecture, named Network-Coded Multiple Access (NCMA). A distinguishing feature of NCMA is the joint use of physical-layer network coding (PNC) and multiuser decoding (MUD) to boost NOMA throughputs. We first show that a simple NCMA architecture in which all users use the same modulation, referred to as rate-homogeneous NCMA, can achieve substantial throughput improvement over SIC-based NOMA under near power-balanced scenarios. Then, we put forth a new NCMA architecture, referred to as rate-diverse NCMA, in which different users may adopt different modulations commensurate with their relative SNRs. A challenge for rate-diverse NCMA is the design of a channel-coded PNC system. This paper is the first attempt to design channel-coded rate-diverse PNC. Experimental results on our software-defined radio prototype show that the throughput of rate-diverse NCMA can outperform the state-of-the-art rate-homogeneous NCMA by 80%. Overall, rate-diverse NCMA is a practical solution for near power-balanced NOMA.
An hp-adaptive strategy for elliptic problems
Venue: arXiv cs.NA 2017
Year: 2017

In this paper a new hp-adaptive strategy for elliptic problems based on refinement history is proposed, which chooses h-, p- or hp-refinement on individual elements according to a posteriori error estimate, as well as smoothness estimate of the solution obtained by comparing the actual and expected error reduction rate. Numerical experiments show that exponential convergence can be achieved with this strategy.
Ordering information on distributions
Venue: arXiv cs.LO 2017
Year: 2017

This thesis details a class of partial orders on the space of probability distributions and the space of density operators which capture the idea of information content. Some links to domain theory and computational linguistics are also discussed. Chapter 1 details some useful theorems from order theory. In Chapter 2 we define a notion of an information ordering on the space of probability distributions and see that this gives rise to a large class of orderings. In Chapter 3 we extend the idea of an information ordering to the space of density operators and in particular look at the maximum eigenvalue order. We will discuss whether this order might be unique given certain restrictions. In Chapter 4 we discuss a possible application in distributional language models, namely in the study of entailment and disambiguation.
Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
Venue: arXiv cs.DS 2017
Year: 2017

The $q$-Coloring problem asks whether the vertices of a graph can be properly colored with $q$ colors. Lokshtanov et al. [SODA 2011] showed that $q$-Coloring on graphs with a feedback vertex set of size $k$ cannot be solved in time $\mathcal{O}^*((q-\varepsilon)^k)$, for any $\varepsilon > 0$, unless the Strong Exponential-Time Hypothesis (SETH) fails. In this paper we perform a fine-grained analysis of the complexity of $q$-Coloring with respect to a hierarchy of parameters. We show that even when parameterized by the vertex cover number, $q$ must appear in the base of the exponent: Unless ETH fails, there is no universal constant $θ$ such that $q$-Coloring parameterized by vertex cover can be solved in time $\mathcal{O}^*(θ^k)$ for all fixed $q$. We apply a method due to Jansen and Kratsch [Inform. & Comput. 2013] to prove that there are $\mathcal{O}^*((q - \varepsilon)^k)$ time algorithms where $k$ is the vertex deletion distance to several graph classes $\mathcal{F}$ for which $q$-Coloring is known to be solvable in polynomial time. We generalize earlier ad-hoc results by showing that if $\mathcal{F}$ is a class of graphs whose $(q+1)$-colorable members have bounded treedepth, then there exists some $\varepsilon > 0$ such that $q$-Coloring can be solved in time $\mathcal{O}^*((q-\varepsilon)^k)$ when parameterized by the size of a given modulator to $\mathcal{F}$. In contrast, we prove that if $\mathcal{F}$ is the class of paths - some of the simplest graphs of unbounded treedepth - then no such algorithm can exist unless SETH fails.
A de Bruijn identity for discrete random variables
Venue: arXiv cs.IT 2017
Year: 2017

We discuss properties of the "beamsplitter addition" operation, which provides a non-standard scaled convolution of random variables supported on the non-negative integers. We give a simple expression for the action of beamsplitter addition using generating functions. We use this to give a self-contained and purely classical proof of a heat equation and de Bruijn identity, satisfied when one of the variables is geometric.
Artificial Intelligence Approaches To UCAV Autonomy
Venue: arXiv cs.AI 2017
Year: 2017

This paper covers a number of approaches that leverage Artificial Intelligence algorithms and techniques to aid Unmanned Combat Aerial Vehicle (UCAV) autonomy. An analysis of current approaches to autonomous control is provided followed by an exploration of how these techniques can be extended and enriched with AI techniques including Artificial Neural Networks (ANN), Ensembling and Reinforcement Learning (RL) to evolve control strategies for UCAVs.
Attaining Capacity with Algebraic Geometry Codes through the $(U|U+V)$ Construction and Koetter-Vardy Soft Decoding
Venue: arXiv cs.IT 2017
Year: 2017

In this paper we show how to attain the capacity of discrete symmetric channels with polynomial time decoding complexity by considering iterated $(U|U+V)$ constructions with Reed-Solomon code or algebraic geometry code components. These codes are decoded with a recursive computation of the {\em a posteriori} probabilities of the code symbols together with the Koetter-Vardy soft decoder used for decoding the code components in polynomial time. We show that when the number of levels of the iterated $(U|U+V)$ construction tends to infinity, we attain the capacity of any discrete symmetric channel in this way. This result follows from the polarization theorem together with a simple lemma explaining how the Koetter-Vardy decoder behaves for Reed-Solomon codes of rate close to $1$. However, even if this way of attaining the capacity of a symmetric channel is essentially the Arıkan polarization theorem, there are some differences with standard polar codes. Indeed, with this strategy we can operate succesfully close to channel capacity even with a small number of levels of the iterated $(U|U+V)$ construction and the probability of error decays quasi-exponentially with the codelength in such a case (i.e. exponentially if we forget about the logarithmic terms in the exponent). We can even improve on this result by considering the algebraic geometry codes constructed in \cite{TVZ82}. In such a case, the probability of error decays exponentially in the codelength for any rate below the capacity of the channel. Moreover, when comparing this strategy to Reed-Solomon codes (or more generally algebraic geometry codes) decoded with the Koetter-Vardy decoding algorithm, it does not only improve the noise level that the code can tolerate, it also results in a significant complexity gain.
AltGr-Ergo, a Graphical User Interface for the SMT Solver Alt-Ergo
Venue: arXiv cs.HC 2017
Year: 2017

Due to undecidability and complexity of first-order logic, SMT solvers may not terminate on some problems or require a very long time. When this happens, one would like to find the reasons why the solver fails. To this end, we have designed AltGr-Ergo, an interactive graphical interface for the SMT solver Alt-Ergo which allows users and tool developers to help the solver finish some proofs. AltGr-Ergo gives real time feedback in order to evaluate and quantify progress made by the solver, and also offers various syntactic manipulation options to allow a finer grained interaction with Alt-Ergo. This paper describes these features and their implementation, and gives usage scenarios for most of them.
jsCoq: Towards Hybrid Theorem Proving Interfaces
Venue: arXiv cs.PL 2017
Year: 2017

We describe jsCcoq, a new platform and user environment for the Coq interactive proof assistant. The jsCoq system targets the HTML5-ECMAScript 2015 specification, and it is typically run inside a standards-compliant browser, without the need of external servers or services. Targeting educational use, jsCoq allows the user to start interaction with proof scripts right away, thanks to its self-contained nature. Indeed, a full Coq environment is packed along the proof scripts, easing distribution and installation. Starting to use jsCoq is as easy as clicking on a link. The current release ships more than 10 popular Coq libraries, and supports popular books such as Software Foundations or Certified Programming with Dependent Types. The new target platform has opened up new interaction and display possibilities. It has also fostered the development of some new Coq-related technology. In particular, we have implemented a new serialization-based protocol for interaction with the proof assistant, as well as a new package format for library distribution.
CP-decomposition with Tensor Power Method for Convolutional Neural Networks Compression
Venue: arXiv cs.LG 2017
Year: 2017

Convolutional Neural Networks (CNNs) has shown a great success in many areas including complex image classification tasks. However, they need a lot of memory and computational cost, which hinders them from running in relatively low-end smart devices such as smart phones. We propose a CNN compression method based on CP-decomposition and Tensor Power Method. We also propose an iterative fine tuning, with which we fine-tune the whole network after decomposing each layer, but before decomposing the next layer. Significant reduction in memory and computation cost is achieved compared to state-of-the-art previous work with no more accuracy loss.
X-duplex Relaying: Adaptive Antenna Configuration
Venue: arXiv cs.IT 2017
Year: 2017

In this letter, we propose a joint transmission mode and transmit/receive (Tx/Rx) antenna configuration scheme referred to as X-duplex in the relay network with one source, one amplify-and-forward (AF) relay and one destination. The relay is equipped with two antennas, each of which is capable of reception and transmission. In the proposed scheme, the relay adaptively selects its Tx and Rx antenna, operating in either full-duplex (FD) or half-duplex (HD) mode. The proposed scheme is based on minimizing the symbol error rate (SER) of the relay system. The asymptotic expressions of the cumulative distribution function (CDF) for the end-to-end signal to interference plus noise ratio (SINR), average SER and diversity order are derived and validated by simulations. Results show that the X-duplex scheme achieves additional spatial diversity, significantly reduces the performance floor at high SNR and improves the system performance.
A Framework of Dynamic Data Structures for String Processing
Venue: arXiv cs.DS 2017
Year: 2017

In this paper we present DYNAMIC, an open-source C++ library implementing dynamic compressed data structures for string manipulation. Our framework includes useful tools such as searchable partial sums, succinct/gap-encoded bitvectors, and entropy/run-length compressed strings and FM-indexes. We prove close-to-optimal theoretical bounds for the resources used by our structures, and show that our theoretical predictions are empirically tightly verified in practice. To conclude, we turn our attention to applications. We compare the performance of four recently-published compression algorithms implemented using DYNAMIC with those of state-of-the-art tools performing the same task. Our experiments show that algorithms making use of dynamic compressed data structures can be up to three orders of magnitude more space-efficient (albeit slower) than classical ones performing the same tasks.
On the Error Probability of Short Concatenated Polar and Cyclic Codes with Interleaving
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, the analysis of the performance of the concatenation of a short polar code with an outer binary linear block code is addressed from a distance spectrum viewpoint. The analysis targets the case where an outer cyclic code is employed together with an inner systematic polar code. A concatenated code ensemble is introduced placing an interleaver at the input of the polar encoder. The introduced ensemble allows deriving bounds on the achievable error rates under maximum likelihood decoding, by applying the union bound to the (expurgated) average weight enumerators. The analysis suggests the need of careful optimization of the outer code, to attain low error floors.