- We consider the problem of quantum state certification, where one is given $n$ copies of an unknown $d$-dimensional quantum mixed state $\rho$, and one wants to test whether $\rho$ is equal to some known mixed state $\sigma$ or else is $\epsilon$-far from $\sigma$. The goal is to use notably fewer copies than the $\Omega(d^2)$ needed for full tomography on $\rho$ (i.e., density estimation). We give two robust state certification algorithms: one with respect to fidelity using $n = O(d/\epsilon)$ copies, and one with respect to trace distance using $n = O(d/\epsilon^2)$ copies. The latter algorithm also applies when $\sigma$ is unknown as well. These copy complexities are optimal up to constant factors.
- A pure multipartite quantum state is called absolutely maximally entangled (AME), if all reductions obtained by tracing out at least half of its parties are maximally mixed. However, the existence of such states is in many cases unclear. With the help of the weight enumerator machinery known from quantum error correcting codes and the generalized shadow inequalities, we obtain new bounds on the existence of AME states in higher dimensions. To complete the treatment on the weight enumerator machinery, the quantum MacWilliams identity is derived in the Bloch representation.
- Aug 22 2017 cs.CC arXiv:1708.05786v1We give an adaptive algorithm which tests whether an unknown Boolean function $f\colon \{0, 1\}^n \to\{0, 1\}$ is unate, i.e. every variable of $f$ is either non-decreasing or non-increasing, or $\epsilon$-far from unate with one-sided error using $\widetilde{O}(n^{3/4}/\epsilon^2)$ queries. This improves on the best adaptive $O(n/\epsilon)$-query algorithm from Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova and Seshadhri when $1/\epsilon \ll n^{1/4}$. Combined with the $\widetilde{\Omega}(n)$-query lower bound for non-adaptive algorithms with one-sided error of [CWX17, BCPRS17], we conclude that adaptivity helps for the testing of unateness with one-sided error. A crucial component of our algorithm is a new subroutine for finding bi-chromatic edges in the Boolean hypercube called adaptive edge search.
- Aug 22 2017 cs.CV arXiv:1708.06297v1To efficiently establish training databases for machine learning methods, collaborative and crowdsourcing platforms have been investigated to collectively tackle the annotation effort. However, when this concept is ported to the medical imaging domain, reading expertise will have a direct impact on the annotation accuracy. In this study, we examine the impact of expertise and the amount of available annotations on the accuracy outcome of a liver segmentation problem in an abdominal computed tomography (CT) image database. In controlled experiments, we study this impact for different types of weak annotations. To address the decrease in accuracy associated with lower expertise, we propose a method for outlier correction making use of a weakly labelled atlas. Using this approach, we demonstrate that weak annotations subject to high error rates can achieve a similarly high accuracy as state-of-the-art multi-atlas segmentation approaches relying on a large amount of expert manual segmentations. Annotations of this nature can realistically be obtained from a non-expert crowd and can potentially enable crowdsourcing of weak annotation tasks for medical image analysis.
- We model the spread of news as a social learning game on a network. Agents can either endorse or oppose a claim made in a piece of news, which itself may be either true or false. Agents base their decision on a private signal and their neighbors' past actions. Given these inputs, agents follow strategies derived via multi-agent deep reinforcement learning and receive utility from acting in accordance with the veracity of claims. Our framework yields strategies with agent utility close to a theoretical, Bayes optimal benchmark, while remaining flexible to model re-specification. Optimized strategies allow agents to correctly identify most false claims, when all agents receive unbiased private signals. However, an adversary's attempt to spread fake news by targeting a subset of agents with a biased private signal can be successful. Even more so when the adversary has information about agents' network position or private signal. When agents are aware of the presence of an adversary they re-optimize their strategies in the training stage and the adversary's attack is less effective. Hence, exposing agents to the possibility of fake news can be an effective way to curtail the spread of fake news in social networks. Our results also highlight that information about the users' private beliefs and their social network structure can be extremely valuable to adversaries and should be well protected.
- Aug 22 2017 cs.NE arXiv:1708.06008v1We review Boltzmann machines and energy-based models. A Boltzmann machine defines a probability distribution over binary-valued patterns. One can learn parameters of a Boltzmann machine via gradient based approaches in a way that log likelihood of data is increased. The gradient and Laplacian of a Boltzmann machine admit beautiful mathematical representations, although computing them is in general intractable. This intractability motivates approximate methods, including Gibbs sampler and contrastive divergence, and tractable alternatives, namely energy-based models.
- Training large vocabulary Neural Network Language Models (NNLMs) is a difficult task due to the explicit requirement of the output layer normalization, which typically involves the evaluation of the full softmax function over the complete vocabulary. This paper proposes a Batch Noise Contrastive Estimation (B-NCE) approach to alleviate this problem. This is achieved by reducing the vocabulary, at each time step, to the target words in the batch and then replacing the softmax by the noise contrastive estimation approach, where these words play the role of targets and noise samples at the same time. In doing so, the proposed approach can be fully formulated and implemented using optimal dense matrix operations. Applying B-NCE to train different NNLMs on the Large Text Compression Benchmark (LTCB) and the One Billion Word Benchmark (OBWB) shows a significant reduction of the training time with no noticeable degradation of the models performance. This paper also presents a new baseline comparative study of different standard NNLMs on the large OBWB on a single Titan-X GPU.
- Aug 22 2017 cs.CL arXiv:1708.05956v1We present a novel end-to-end trainable neural network model for task-oriented dialog systems. The model is able to track dialog state, issue API calls to knowledge base (KB), and incorporate structured KB query results into system responses to successfully complete task-oriented dialogs. The proposed model produces well-structured system responses by jointly learning belief tracking and KB result processing conditioning on the dialog history. We evaluate the model in a restaurant search domain using a dataset that is converted from the second Dialog State Tracking Challenge (DSTC2) corpus. Experiment results show that the proposed model can robustly track dialog state given the dialog history. Moreover, our model demonstrates promising results in producing appropriate system responses, outperforming prior end-to-end trainable neural network models using per-response accuracy evaluation metrics.
- Aug 22 2017 cs.RO arXiv:1708.06343v1
- Aug 22 2017 cs.CV arXiv:1708.06320v1
- Aug 22 2017 cs.NI arXiv:1708.06313v1
- Aug 22 2017 cs.LO arXiv:1708.06312v1
- Aug 22 2017 cs.SI arXiv:1708.06309v1
- Aug 22 2017 cs.CR arXiv:1708.06308v1
- Aug 22 2017 cs.RO arXiv:1708.06301v1
- Aug 22 2017 cs.MS arXiv:1708.06290v1
- Aug 22 2017 cs.DS arXiv:1708.06275v1
- Aug 22 2017 cs.RO arXiv:1708.06274v1
- Aug 22 2017 cs.DL arXiv:1708.06242v1
- Aug 22 2017 cs.FL arXiv:1708.06228v1
- Aug 22 2017 cs.CV arXiv:1708.06227v1
- Aug 22 2017 cs.FL arXiv:1708.06226v1
- Aug 22 2017 cs.CR arXiv:1708.06199v1
- Aug 22 2017 cs.CV arXiv:1708.06197v1
- Aug 22 2017 cs.CG arXiv:1708.06196v1
- Aug 22 2017 cs.CL arXiv:1708.06185v1
- Aug 22 2017 cs.CR arXiv:1708.06145v1
- Aug 22 2017 cs.CV arXiv:1708.06128v1
- Aug 22 2017 cs.CV arXiv:1708.06126v1
- Aug 22 2017 cs.LO arXiv:1708.06121v1
- Aug 22 2017 cs.CV arXiv:1708.06118v1
- Aug 22 2017 cs.CL arXiv:1708.06075v1
- Aug 22 2017 cs.CL arXiv:1708.06073v1