- We consider the quantum complexity of computing Schatten $p$-norms and related quantities, and find that the problem of estimating these quantities is closely related to the one clean qubit model of computation. We show that the problem of approximating $\text{Tr}\, (|A|^p)$ for a log-local $n$-qubit Hamiltonian $A$ and $p=\text{poly}(n)$, up to a suitable level of accuracy, is contained in DQC1; and that approximating this quantity up to a somewhat higher level of accuracy is DQC1-hard. In some cases the level of accuracy achieved by the quantum algorithm is substantially better than a natural classical algorithm for the problem. The same problem can be solved for arbitrary sparse matrices in BQP. One application of the algorithm is the approximate computation of the energy of a graph.
- Jun 29 2017 quant-ph cond-mat.stat-mech arXiv:1706.09379v1We prove that for one-dimensional many-body states with exponentially decaying correlations, the entanglement between any continuous region and its complement is bounded by a constant depending only on the correlation length. Our proof dramatically reduces the previously known bound on the entanglement, bringing it, for the first time, into a realistic regime. Moreover, its dependence on the correlation length is more favourable than the previous one for systems with a finite spectral gap, which is a stronger condition than a finite correlation length. Our proof is composed of several simple steps based only on elementary quantum information tools. In the course of the proof, we directly inspect how the internal structure of many-body states is restricted by exponentially decaying correlations. Our proof is thus expected to be an important step towards the understanding of the area law in higher dimensions.
- Jun 29 2017 quant-ph arXiv:1706.09131v1We investigate the efficacy of a cavity optomechanical system for gravitational accelerometry when it has a light-matter interaction of the canonical `trilinear' radiation pressure form. Using a full quantum treatment, we find that although the cavity and mechanical components entangle during the time evolution, the phase of the optical output of the cavity encodes the gravitational acceleration $g$ and is the only component which needs to be measured to perform the gravimetry. Strikingly, the mechanical oscillator can remain in a thermal state without affecting the efficacy of the scheme and thereby the cooling requirements are not significant. We analytically show that the quantum and classical Fisher information coincide for a homodyne detection scheme and use the results to estimate the relative accuracy obtainable for $\Delta g /g$. We predict a $\Delta g /g = 10^{-13}$ for both Fabry-Perot and levitated object optomechanical systems which can, in principle, surpass the best atomic interferometers even for low intra-cavity intensities in the resolved side-band and single photon nonlinearity regimes. Key to our enhancement are the cavity confinement leading to repeated interaction with photons and the larger polarizabilities of mesoscopic trapped objects with respect to atoms.
- Jun 29 2017 cs.CC arXiv:1706.09362v1In the problem of high-dimensional convexity testing, there is an unknown set $S \subseteq \mathbb{R}^n$ which is promised to be either convex or $\varepsilon$-far from every convex body with respect to the standard multivariate normal distribution $\mathcal{N}(0, 1)^n$. The job of a testing algorithm is then to distinguish between these two cases while making as few inspections of the set $S$ as possible. In this work we consider sample-based testing algorithms, in which the testing algorithm only has access to labeled samples $(\boldsymbol{x},S(\boldsymbol{x}))$ where each $\boldsymbol{x}$ is independently drawn from $\mathcal{N}(0, 1)^n$. We give nearly matching sample complexity upper and lower bounds for both one-sided and two-sided convexity testing algorithms in this framework. For constant $\varepsilon$, our results show that the sample complexity of one-sided convexity testing is $2^{\tilde{\Theta}(n)}$ samples, while for two-sided convexity testing it is $2^{\tilde{\Theta}(\sqrt{n})}$.
- Jun 29 2017 quant-ph arXiv:1706.09275v1If a measurement is made on one half of a bipartite system then, conditioned on the outcome, the other half has a new reduced state. If these reduced states defy classical explanation --- that is, if shared randomness cannot produce these reduced states for all possible measurements --- the bipartite state is said to be steerable. Determining which states are steerable is a challenging problem even for low dimensions. In the case of two-qubit systems a criterion is known for T-states (that is, those with maximally mixed marginals) under projective measurements. In the current work we introduce the concept of keyring models --- a special class of local hidden state model. When the measurements made correspond to real projectors, these allow us to study steerability beyond T-states. Using keyring models, we completely solve the steering problem for real projective measurements when the state arises from mixing a pure two-qubit state with uniform noise. We also give a partial solution in the case when the uniform noise is replaced by independent depolarizing channels. Our results imply that Werner states, which are a special case of the previous states, are unsteerable under real projective measurements if and only if their efficiency is at most $2/\pi$.
- It has been conjectured by Maldacena, Shenker, and Stanford [J. High Energy Phys. 08 (2016) 106] that the exponential growth rate of the out-of-time-ordered correlator $F(t)$ has a universal upper bound $2\pi k_B T/\hbar$. Here we introduce a one-parameter family of out-of-time-ordered correlators $F_\gamma(t)$ ($0\leq\gamma\leq 1$), which has as good properties as $F(t)$ as a regularization of the out-of-time-ordered part of the squared commutator $\langle [ A(t),B(0)]^2\rangle$ that diagnoses quantum many-body chaos, and coincides with $F(t)$ at $\gamma=1/2$. We rigorously prove that if $F_\gamma(t)$ shows a transient exponential growth for all $\gamma$ in $0\leq\gamma\leq 1$, the growth rate $\lambda$ does not depend on the regularization parameter $\gamma$, and satisfies the inequality $\lambda\leq 2\pi k_B T/\hbar$.
- Jun 29 2017 quant-ph arXiv:1706.09319v1Every statistical operator---that represents a quantum state---must follow three conditions the Hermiticity, normalization, and positivity. These conditions give birth to quantum constraints on the expectation values with the aid of Born's rule, which connects the mean values for any set of operators to a quantum state. The quantum constraints identify a permissible region of the expectation values. For a set of observables, the allowed region is a compact and convex set in a real space, and all its extreme points come from pure quantum states. By defining an appropriate concave function on the permitted region, one can establish a tight uncertainty relation by finding its absolute minimum at the extreme points. The permissible region is the smallest and resides in every other region bounded by a (un)certainty relation. A point outside of the admissible region---even if it satisfies a tight (un)certainty relation---does not correspond to any quantum state. Therefore, in a nutshell, the quantum constraints are optimal.
- A proper semantic representation for encoding side information is key to the success of zero-shot learning. In this paper, we explore two alternative semantic representations especially for zero-shot human action recognition: textual descriptions of human actions and deep features extracted from still images relevant to human actions. Such side information are accessible on Web with little cost, which paves a new way in gaining side information for large-scale zero-shot human action recognition. We investigate different encoding methods to generate semantic representations for human actions from such side information. Based on our zero-shot visual recognition method, we conducted experiments on UCF101 and HMDB51 to evaluate two proposed semantic representations . The results suggest that our proposed text- and image-based semantic representations outperform traditional attributes and word vectors considerably for zero-shot human action recognition. In particular, the image-based semantic representations yield the favourable performance even though the representation is extracted from a small number of images per class.
- Jun 29 2017 cs.CV arXiv:1706.09274v1We took part in the YouTube-8M Video Understanding Challenge hosted on Kaggle, and achieved the 10th place within less than one month's time. In this paper, we present an extensive analysis and solution to the underlying machine-learning problem based on frame-level data, where major challenges are identified and corresponding preliminary methods are proposed. It's noteworthy that, with merely the proposed strategies and uniformly-averaging multi-crop ensemble was it sufficient for us to reach our ranking. We also report the methods we believe to be promising but didn't have enough time to train to convergence. We hope this paper could serve, to some extent, as a review and guideline of the YouTube-8M multi-label video classification benchmark, inspiring future attempts and research.
- Jun 29 2017 cs.DS arXiv:1706.09185v1In the $k$-dispersion problem, we need to select $k$ nodes of a given graph so as to maximize the minimum distance between any two chosen nodes. This can be seen as a generalization of the independent set problem, where the goal is to select nodes so that the minimum distance is larger than 1. We design an optimal $O(n)$ time algorithm for the dispersion problem on trees consisting of $n$ nodes, thus improving the previous $O(n\log n)$ time solution from 1997. We also consider the weighted case, where the goal is to choose a set of nodes of total weight at least $W$. We present an $O(n\log^2n)$ algorithm improving the previous $O(n\log^4 n)$ solution. Our solution builds on the search version (where we know the minimum distance $\lambda$ between the chosen nodes) for which we present tight $\Theta(n\log n)$ upper and lower bounds.
- Jun 29 2017 quant-ph arXiv:1706.09051v1There has been significant interest recently in using complex quantum systems to create effective nonreciprocal dynamics. Theoretical proposals have been put forward for the realization of artificial magnetic fields for photons and even phonons; experimental progress is fast making these proposals a reality. Much work has concentrated on the use of such systems for controlling the flow of signals, e.g., to create isolators or directional amplifiers for optical signals. In this paper, we build on this work but move in a different direction. We develop the theory and discuss a potential realization for the controllable flow of heat in quantum systems. We demonstrate theoretically that the observation of unidirectional flow of heat is possible within quantum cascaded systems. Viewing an optomechanical cavity platform as a cascaded system we show here that one can ultimately control the direction of the heat flow. By appropriately engineering the mechanical resonator, which acts as an artificial reservoir, heat flow can be constrained to a desired direction, yielding a thermal rectifier. The proposed quantum heat rectifier could potentially be used to develop devices such as a thermal modulator, a thermal router, and a thermal amplifier for nanoelectronic devices and superconducting circuits.
- In this paper, we present two main results. First, by only one conjecture (Conjecture 2.9) for recognizing a vertex symmetric graph, which is the hardest task for our problem, we construct an algorithm for finding an isomorphism between two graphs in polynomial time $ O(n^{3}) $. Second, without that conjecture, we prove the algorithm to be of quasi-polynomial time $ O(n^{1.5\log n}) $. The conjectures in this paper are correct for all graphs of size no larger than $ 5 $ and all graphs we have encountered. At least the conjecture for determining if a graph is vertex symmetric is quite true intuitively. We are not able to prove them by hand, so we have planned to find possible counterexamples by a computer. We also introduce new concepts like collapse pattern and collapse tomography, which play important roles in our algorithms.
- Jun 29 2017 cs.CY arXiv:1706.09372v1Improving the health of the nation's population and increasing the capabilities of the US healthcare system to support diagnosis, treatment, and prevention of disease is a critical national and societal priority. In the past decade, tremendous advances in expanding computing capabilities--sensors, data analytics, networks, advanced imaging, and cyber-physical systems--have, and will continue to, enhance healthcare and health research, with resulting improvements in health and wellness. However, the cost and complexity of healthcare continues to rise alongside the impact of poor health on productivity and quality of life. What is lacking are transformative capabilities that address significant health and healthcare trends: the growing demands and costs of chronic disease, the greater responsibility placed on patients and informal caregivers, and the increasing complexity of health challenges in the US, including mental health, that are deeply rooted in a person's social and environmental context.
- A vibrant theoretical research area are efficient exact parameterized algorithms. Very recent solving competitions such as the PACE challenge show that there is also increasing practical interest in the parameterized algorithms community. An important research question is whether dedicated parameterized exact algorithms exhibit certain practical relevance and one can even beat well-established problem solvers. We consider the logic-based declarative modeling language and problem solving framework Answer Set Programming (ASP). State-of-the-art ASP solvers rely considerably on Sat-based algorithms. An ASP solver (DynASP2), which is based on a classical dynamic programming on tree decompositions, has been published very recently. Unfortunately, DynASP2 can outperform modern ASP solvers on programs of small treewidth only if the question of interest is to count the number of solutions. In this paper, we describe underlying concepts of our new implementation (DynASP2.5) that shows competitive behavior to state-of-the-art ASP solvers even for finding just one solution when solving problems as the Steiner tree problem that have been modeled in ASP on graphs with low treewidth. Our implementation is based on a novel approach that we call multi-pass dynamic programming (M-DPSINC).
- Jun 29 2017 cs.CV arXiv:1706.09364v1We tackle the task of semi-supervised video object segmentation, i.e. segmenting the pixels belonging to an object in the video using the ground truth pixel mask for the first frame. We build on the recently introduced one-shot video object segmentation (OSVOS) approach which uses a pretrained network and fine-tunes it on the first frame. While achieving impressive performance, at test time OSVOS uses the fine-tuned network in unchanged form and is not able to adapt to large changes in object appearance. To overcome this limitation, we propose Online Adaptive Video Object Segmentation (OnAVOS) which updates the network online using training examples selected based on the confidence of the network and the spatial configuration. Additionally, we add a pretraining step based on objectness, which is learned on PASCAL. Our experiments show that both extensions are highly effective and improve the state of the art on DAVIS to an intersection-over-union score of 85.7%.
- Jun 29 2017 cs.CL arXiv:1706.09335v1Providing appealing brand names to newly launched products, newly formed companies or for renaming existing companies is highly important as it can play a crucial role in deciding its success or failure. In this work, we propose a computational method to generate appealing brand names based on the description of such entities. We use quantitative scores for readability, pronounceability, memorability and uniqueness of the generated names to rank order them. A set of diverse appealing names is recommended to the user for the brand naming task. Experimental results show that the names generated by our approach are more appealing than names which prior approaches and recruited humans could come up.
- Jun 29 2017 cs.SI physics.soc-ph arXiv:1706.09310v1This doctoral work focuses on three main problems related to social networks: (1) Orchestrating Network Formation: We consider the problem of orchestrating formation of a social network having a certain given topology that may be desirable for the intended usecases. Assuming the social network nodes to be strategic in forming relationships, we derive conditions under which a given topology can be uniquely obtained. We also study the efficiency and robustness of the derived conditions. (2) Multi-phase Influence Maximization: We propose that information diffusion be carried out in multiple phases rather than in a single instalment. With the objective of achieving better diffusion, we discover optimal ways of splitting the available budget among the phases, determining the time delay between consecutive phases, and also finding the individuals to be targeted for initiating the diffusion process. (3) Scalable Preference Aggregation: It is extremely useful to determine a small number of representatives of a social network such that the individual preferences of these nodes, when aggregated, reflect the aggregate preference of the entire network. Using real-world data collected from Facebook with human subjects, we discover a model that faithfully captures the spread of preferences in a social network. We hence propose fast and reliable ways of computing a truly representative aggregate preference of the entire network. In particular, we develop models and methods for solving the above problems, which primarily deal with formation and analysis of social networks.
- Jun 29 2017 cs.CV arXiv:1706.09308v1Urban informatics explore data science methods to address different urban issues using intensively based on data. The large variety and quantity of data available should be explored but this brings important challenges. For instance, although there are powerful computer vision methods that may be explored, they may require large annotated datasets. In this work we propose a novel approach to automatically creating an object recognition system with minimal manual annotation. The basic idea behind the method is to use large input datasets using available online cameras on large cities. A off-the-shelf weak classifier is used to detect an initial set of urban elements of interest (e.g. cars, pedestrians, bikes, etc.). Such initial dataset undergoes a quality control procedure and it is subsequently used to fine tune a strong classifier. Quality control and comparative performance assessment are used as part of the pipeline. We evaluate the method for detecting cars based on monitoring cameras. Experimental results using real data show that despite losing generality, the final detector provides better detection rates tailored to the selected cameras. The programmed robot gathered 770 video hours from 24 online city cameras (\~300GB), which has been fed to the proposed system. Our approach has shown that the method nearly doubled the recall (93\%) with respect to state-of-the-art methods using off-the-shelf algorithms.
- Multithreaded software is typically built with specialized concurrent objects like atomic integers, queues, and maps. These objects' methods are designed to behave according to certain consistency criteria like atomicity, despite being optimized to avoid blocking and exploit parallelism, e.g., by using atomic machine instructions like compare and exchange (cmpxchg). Exposing atomicity violations is important since they generally lead to elusive bugs that are difficult to identify, reproduce, and ultimately repair. In this work we expose atomicity violations in concurrent object implementations from the most widely-used software development kit: The Java Development Kit (JDK). We witness atomicity violations via simple test harnesses containing few concurrent method invocations. While stress testing is effective at exposing violations given catalytic test harnesses and lightweight means of falsifying atomicity, divining effectual catalysts can be difficult, and atomicity checks are generally cumbersome. We overcome these problems by automating test-harness search, and establishing atomicity via membership in precomputed sets of acceptable return-value outcomes. Our approach enables testing millions of executions of each harness each second (per processor core). This scale is important since atomicity violations are observed in very few executions (tens to hundreds out of millions) of very few harnesses (one out of hundreds to thousands). Our implementation is open source and publicly available.
- High-resolution satellite imagery have been increasingly used on remote sensing classification problems. One of the main factors is the availability of this kind of data. Even though, very little effort has been placed on the zebra crossing classification problem. In this letter, crowdsourcing systems are exploited in order to enable the automatic acquisition and annotation of a large-scale satellite imagery database for crosswalks related tasks. Then, this dataset is used to train deep-learning-based models in order to accurately classify satellite images that contains or not zebra crossings. A novel dataset with more than 240,000 images from 3 continents, 9 countries and more than 20 cities was used in the experiments. Experimental results showed that freely available crowdsourcing data can be used to accurately (97.11%) train robust models to perform crosswalk classification on a global scale.
- Jun 29 2017 cs.AI arXiv:1706.09278v1Learning relations based on evidence from knowledge bases relies on processing the available relation instances. Many relations, however, have clear domain and range, which we hypothesize could help learn a better, more generalizing, model. We include such information in the RESCAL model in the form of a regularization factor added to the loss function that takes into account the types (categories) of the entities that appear as arguments to relations in the knowledge base. We note increased performance compared to the baseline model in terms of mean reciprocal rank and hits@N, N = 1, 3, 10. Furthermore, we discover scenarios that significantly impact the effectiveness of the type regularizer.
- Class-agnostic object tracking is particularly difficult in cluttered environments as target specific discriminative models cannot be learned a priori. Inspired by how the human visual cortex employs spatial attention and separate "where" and "what" processing pathways to actively suppress irrelevant visual features, this work develops a hierarchical attentive recurrent model for single object tracking in videos. The first layer of attention discards the majority of background by selecting a region containing the object of interest, while the subsequent layers tune in on visual features particular to the tracked object. This framework is fully differentiable and can be trained in a purely data driven fashion by gradient methods. To improve training convergence, we augment the loss function with terms for a number of auxiliary tasks relevant for tracking. Evaluation of the proposed model is performed on two datasets of increasing difficulty: pedestrian tracking on the KTH activity recognition dataset and the KITTI object tracking dataset.
- Jun 29 2017 cs.DL arXiv:1706.09258v1After giving a brief overview of Eugene Garfield contributions to the issue of identifying and studying the most cited scientific articles, manifested in the creation of his Citation Classics, the main characteristics and features of Google Scholar new service Classic Papers, as well as its main strengths and weaknesses, are addressed. This product currently displays the most cited English-language original research articles by fields and published in 2006
- Jun 29 2017 cs.CL arXiv:1706.09254v1This paper describes the E2E data, a new dataset for training end-to-end, data-driven natural language generation systems in the restaurant domain, which is ten times bigger than existing, frequently used datasets in this area. The E2E dataset poses new challenges: (1) its human reference texts show more lexical richness and syntactic variation, including discourse phenomena; (2) generating from this set requires content selection. As such, learning from this dataset promises more natural, varied and less template-like system utterances. We also establish a baseline on this dataset, which illustrates some of the difficulties associated with this data.
- Jun 29 2017 cs.LO arXiv:1706.09236v1Quantifier-free nonlinear arithmetic (QF_NRA) appears in many applications of satisfiability modulo theories solving (SMT). Accordingly, efficient reasoning for corresponding constraints in SMT theory solvers is highly relevant. We propose a new incomplete but efficient and terminating method to identify satisfiable instances. The method is derived from the subtropical method recently introduced in the context of symbolic computation for computing real zeros of single very large multivariate polynomials. Our method takes as input conjunctions of strict polynomial inequalities, which represent more than 40% of the QF_NRA section of the SMT-LIB library of benchmarks. The method takes an abstraction of polynomials as exponent vectors over the natural numbers tagged with the signs of the corresponding coefficients. It then uses, in turn, SMT to solve linear problems over the reals to heuristically find suitable points that translate back to satisfying points for the original problem. Systematic experiments on the SMT-LIB demonstrate that our method is not a sufficiently strong decision procedure by itself but a valuable heuristic to use within a portfolio of techniques.
- Jun 29 2017 cs.NI arXiv:1706.09219v1Future warehouses will be made of modular embedded entities with communication ability and energy aware operation attached to the traditional materials handling and warehousing objects. This advancement is mainly to fulfill the flexibility and scalability needs of the emerging warehouses. However, it leads to a new layer of complexity during development and evaluation of such systems due to the multidisciplinarity in logistics, embedded systems, and wireless communications. Although each discipline provides theoretical approaches and simulations for these tasks, many issues are often discovered in a real deployment of the full system. In this paper we introduce PhyNetLab as a real scale warehouse testbed made of cyber physical objects (PhyNodes) developed for this type of application. The presented platform provides a possibility to check the industrial requirement of an IoT-based warehouse in addition to the typical wireless sensor networks tests. We describe the hardware and software components of the nodes in addition to the overall structure of the testbed. Finally, we will demonstrate the advantages of the testbed by evaluating the performance of the ETSI compliant radio channel access procedure for an IoT warehouse.
- Recommender systems aim to find an accurate and efficient mapping from historic data of user-preferred items to a new item that is to be liked by a user. Towards this goal, energy-based sequence generative adversarial nets (EB-SeqGANs) are adopted for recommendation by learning a generative model for the time series of user-preferred items. By recasting the energy function as the feature function, the proposed EB-SeqGANs is interpreted as an instance of maximum-entropy imitation learning.
- Jun 29 2017 cs.CV arXiv:1706.09193v1We present a parameterized approach to produce personalized variable length summaries of soccer matches. Our approach is based on temporally segmenting the soccer video into 'plays', associating a user-specifiable 'utility' for each type of play and using 'bin-packing' to select a subset of the plays that add up to the desired length while maximizing the overall utility (volume in bin-packing terms). Our approach systematically allows a user to override the default weights assigned to each type of play with individual preferences and thus see a highly personalized variable length summarization of soccer matches. We demonstrate our approach based on the output of an end-to-end pipeline that we are building to produce such summaries. Though aspects of the overall end-to-end pipeline are human assisted at present, the results clearly show that the proposed approach is capable of producing semantically meaningful and compelling summaries. Besides the obvious use of producing summaries of superior league matches for news broadcasts, we anticipate our work to promote greater awareness of the local matches and junior leagues by producing consumable summaries of them.
- Jun 29 2017 cs.CV arXiv:1706.09180v1This paper introduces a new real-time object detection approach named Yes-Net. It realizes the prediction of bounding boxes and class via single neural network like YOLOv2 and SSD, but owns more efficient and outstanding features. It combines local information with global information by adding the RNN architecture as a packed unit in CNN model to form the basic feature extractor. Independent anchor boxes coming from full-dimension k-means is also applied in Yes-Net, it brings better average IOU than grid anchor box. In addition, instead of NMS, Yes-Net uses RNN as a filter to get the final boxes, which is more efficient. For 416 x 416 input, Yes-Net achieves 74.3% mAP on VOC2007 test at 39 FPS on an Nvidia Titan X Pascal.
- This paper introduces a new methodology for the complexity analysis of higher-order functional programs, which is based on three ingredients: a powerful type system for size analysis and a sound type inference procedure for it, a ticking monadic transformation, and constraint solving. Noticeably, the presented methodology can be fully automated, and is able to analyse a series of examples which cannot be handled by most competitor methodologies. This is possible due to the choice of adopting an abstract index language and index polymorphism at higher ranks. A prototype implementation is available.
- In sequence prediction task, there mainly exist two types of learning algorithms. One genre based on maximum likelihood estimation (MLE) supervises the training in every time step via a surrogate loss function but leads to train-test discrepancy and hard-to-train problem. The other genre based on Reinforcement Learning gives the model freedom to generate samples and guides the training by feeding back task-level reward but suffers from high variance and instability problem. In general, these two frameworks both have their own trade-offs and complement each other. In this paper, we introduce a hybrid-coach framework to combine these two existing algorithms so that the supervision from MLE can stabilize RL training while RL can incorporate task-level loss into MLE training. To augment more easy-to-learn samples for MLE training and denser reward for RL training, the coach is encouraged to be close to both the data and model distribution. During training, the coach acts as a proxy target and pulls the model distribution to the data distribution, as the model makes progress it correspondingly upgrades itself to become harsher and finally anneal to the ultimate target distribution. With the coordination of the coach system, our hybrid-coach framework can efficiently resolve RL's reward sparsity problem and MLE's data sparsity problem. We apply our algorithm on two Machine Translation Task and show significant improvements over the state-of-art systems.
- Jun 29 2017 cs.CL arXiv:1706.09147v1We address the task of Named Entity Disambiguation (NED) for noisy text. We present WikilinksNED, a large-scale NED dataset of text fragments from the web, which is significantly noisier and more challenging than existing news-based datasets. To capture the limited and noisy local context surrounding each mention, we design a neural model and train it with a novel method for sampling informative negative examples. We also describe a new way of initializing word and entity embeddings that significantly improves performance. Our model significantly outperforms existing state-of-the-art methods on WikilinksNED while achieving comparable performance on a smaller newswire dataset.
- In this note we present an explicit realization of the affine vertex algebra $V^{cri}(\frak{gl}(1 \vert 1)) $ inside of the tensor product $F\otimes M$ where $F$ is a fermionic verex algebra and $M$ is a commutative vertex algebra. This immediately gives an alternative description of the center of $V^{cri}(\frak{gl}(1 \vert 1) ) )$ as a subalgebra $M _ 0$ of $M$. We reconstruct the Molev-Mukhin formula for the Hilbert-Poincare series of the center of $V^ {cri}(\frak{gl}(1 \vert 1) )$. Moreover, we construct a family of irreducible $V^{cri}(\frak{gl}(1 \vert 1))$ -modules realized on $F$ and parameterized by $\chi^+, \chi ^- \in {\Bbb C}((z)). $ We propose a generalization of $V^ {cri}(\frak{gl}(1 \vert 1))$ as a critical level version of the super $\mathcal W_{1+\infty}$ vertex algebra.
- Jun 29 2017 stat.ME arXiv:1706.09141v1Graphical models can represent a multivariate distribution in a convenient and accessible form as a graph. Causal models can be viewed as a special class of graphical models that not only represent the distribution of the observed system but also the distributions under external interventions. They hence enable predictions under hypothetical interventions, which is important for decision making. The challenging task of learning causal models from data always relies on some underlying assumptions. We discuss several recently proposed structure learning algorithms and their assumptions, and compare their empirical performance under various scenarios.
- Jun 29 2017 cs.CV arXiv:1706.09138v1In this paper, we propose a principled Perceptual Adversarial Networks (PAN) for image-to-image transformation tasks. Unlike existing application-specific algorithms, PAN provides a generic framework of learning mapping relationship between paired images (Fig. 1), such as mapping a rainy image to its de-rained counterpart, object edges to its photo, semantic labels to a scenes image, etc. The proposed PAN consists of two feed-forward convolutional neural networks (CNNs), the image transformation network T and the discriminative network D. Through combining the generative adversarial loss and the proposed perceptual adversarial loss, these two networks can be trained alternately to solve image-to-image transformation tasks. Among them, the hidden layers and output of the discriminative network D are upgraded to continually and automatically discover the discrepancy between the transformed image and the corresponding ground-truth. Simultaneously, the image transformation network T is trained to minimize the discrepancy explored by the discriminative network D. Through the adversarial training process, the image transformation network T will continually narrow the gap between transformed images and ground-truth images. Experiments evaluated on several image-to-image transformation tasks (e.g., image de-raining, image inpainting, etc.) show that the proposed PAN outperforms many related state-of-the-art methods.
- Jun 29 2017 cs.SE arXiv:1706.09120v1Test-based automatic program repair has attracted a lot of attentions in recent years. Given a program and a test suite containing at least a failed test, test-based automatic program repair approaches change the program to make all test pass. A major challenge faced by automatic program repair approaches is weak test suite. That is, the test suites in practice are often too weak to guarantee correctness, and many patches that pass all the tests are not correct. As a result, existing approaches often generate a large number of incorrect patches. To reduce the number of incorrect patches generated, in this paper we propose a novel approach that heuristically determines the correctness of the generated patches. The core idea of our approach is to exploit the behavior similarity of test case executions. The executions of passed tests on original and patched programs are likely to behave similarly while the executions of failed tests on original and patched programs are likely to behave differently. Also, if two tests exhibit similar runtime behavior, the two tests are likely to have the same test results. Based on these observations, we generate new test inputs to enhance the test suites and use their behavior similarity to determine patch correctness. Our approach is evaluated on a dataset consisting of 130 patches generated from existing program repair systems including jGenProg, Nopol, Kali, and ACS. Our approach successfully prevented 56.3% of the incorrect patches to be generated, without blocking any correct patches.
- We show that the gravitational quasi-normal modes (QNMs) of a Schwarzschild black hole play the role of a multimode squeezer that can generate particles. For a minimally coupled scalar field, the QNMs "squeeze" the initial state of the scalar field (even for the vacuum) and produce scalar particles. The maximal squeezing amplitude is inversely proportional to the cube of the imaginary part of the QNM frequency, implying that the particle generation efficiency is higher for lower decaying QNMs. Our results show that the gravitational perturbations can amplify Hawking radiation.
- Jun 29 2017 cs.CV arXiv:1706.09092v1The Classification of medical images and illustrations in the literature aims to label a medical image according to the modality it was produced or label an illustration according to its production attributes. It is an essential and challenging research hotspot in the area of automated literature review, retrieval and mining. The significant intra-class variation and inter-class similarity caused by the diverse imaging modalities and various illustration types brings a great deal of difficulties to the problem. In this paper, we propose a synergic deep learning (SDL) model to address this issue. Specifically, a dual deep convolutional neural network with a synergic signal system is designed to mutually learn image representation. The synergic signal is used to verify whether the input image pair belongs to the same category and to give the corrective feedback if a synergic error exists. Our SDL model can be trained 'end to end'. In the test phase, the class label of an input can be predicted by averaging the likelihood probabilities obtained by two convolutional neural network components. Experimental results on the ImageCLEF2016 Subfigure Classification Challenge suggest that our proposed SDL model achieves the state-of-the art performance in this medical image classification problem and its accuracy is higher than that of the first place solution on the Challenge leader board so far.
- Increasing technological sophistication and widespread use of smartphones and wearable devices provide opportunities for innovative and highly personalized health interventions. A Just-In-Time Adaptive Intervention (JITAI) uses real-time data collection and communication capabilities of modern mobile devices to deliver interventions in real-time that are adapted to the in-the-moment needs of the user. The lack of methodological guidance in constructing data-based JITAIs remains a hurdle in advancing JITAI research despite the increasing popularity of JITAIs among clinical scientists. In this article, we make a first attempt to bridge this methodological gap by formulating the task of tailoring interventions in real-time as a contextual bandit problem. Interpretability requirements in the domain of mobile health lead us to formulate the problem differently from existing formulations intended for web applications such as ad or news article placement. Under the assumption of linear reward function, we choose the reward function (the "critic") parameterization separately from a lower dimensional parameterization of stochastic policies (the "actor"). We provide an online actor-critic algorithm that guides the construction and refinement of a JITAI. Asymptotic properties of the actor-critic algorithm are developed and backed up by numerical experiments. Additional numerical experiments are conducted to test the robustness of the algorithm when idealized assumptions used in the analysis of contextual bandit algorithm are breached.
- We present a semantic vector space model for capturing complex polyphonic musical context. A word2vec model based on a skip-gram representation with negative sampling was used to model slices of music from a dataset of Beethoven's piano sonatas. A visualization of the reduced vector space using t-distributed stochastic neighbor embedding shows that the resulting embedded vector space captures tonal relationships, even without any explicit information about the musical contents of the slices. Secondly, an excerpt of the Moonlight Sonata from Beethoven was altered by replacing slices based on context similarity. The resulting music shows that the selected slice based on similar word2vec context also has a relatively short tonal distance from the original slice.
- Jun 29 2017 cs.CV arXiv:1706.09077v1The recent phenomenal interest in convolutional neural networks (CNNs) must have made it inevitable for the super-resolution (SR) community to explore its potential. The response has been immense and in the last three years, since the advent of the pioneering work, there appeared too many works not to warrant a comprehensive survey. This paper surveys the SR literature in the context of deep learning. We focus on the three important aspects of multimedia - namely image, video and multi-dimensions, especially depth maps. In each case, first relevant benchmarks are introduced in the form of datasets and state of the art SR methods, excluding deep learning. Next is a detailed analysis of the individual works, each including a short description of the method and a critique of the results with special reference to the benchmarking done. This is followed by minimum overall benchmarking in the form of comparison on some common dataset, while relying on the results reported in various works.
- A descriptive approach for automatic generation of visual blends is presented. The implemented system, the Blender, is composed of two components: the Mapper and the Visual Blender. The approach uses structured visual representations along with sets of visual relations which describe how the elements (in which the visual representation can be decomposed) relate among each other. Our system is a hybrid blender, as the blending process starts at the Mapper (conceptual level) and ends at the Visual Blender (visual representation level). The experimental results show that the Blender is able to create analogies from input mental spaces and produce well-composed blends, which follow the rules imposed by its base-analogy and its relations. The resulting blends are visually interesting and some can be considered as unexpected.
- Measuring influence and determining what drives it are persistent questions in political science and in network analysis more generally. Herein we focus on the domain of international relations. Our major substantive question is: How can we determine what characteristics make an actor influential? To address the topic of influence, we build on a multilinear tensor regression framework (MLTR) that captures influence relationships using a tensor generalization of a vector autoregression model. Influence relationships in that approach are captured in a pair of n x n matrices and provide measurements of how the network actions of one actor may influence the future actions of another. A limitation of the MLTR and earlier latent space approaches is that there are no direct mechanisms through which to explain why a certain actor is more or less influential than others. Our new framework, social influence regression, provides a way to statistically model the influence of one actor on another as a function of characteristics of the actors. Thus we can move beyond just estimating that an actor influences another to understanding why. To highlight the utility of this approach, we apply it to studying monthly-level conflictual events between countries as measured through the Integrated Crisis Early Warning System (ICEWS) event data project.
- Jun 29 2017 cs.RO arXiv:1706.09068v1The ROS navigation stack is powerful for mobile robots to move from place to place reliably. The job of navigation stack is to produce a safe path for the robot to execute, by processing data from odometry, sensors and environment map. Maximizing the performance of this navigation stack requires some fine tuning of parameters, and this is not as simple as it looks. One who is sophomoric about the concepts and reasoning may try things randomly, and wastes a lot of time. This article intends to guide the reader through the process of fine tuning navigation parameters. It is the reference when someone need to know the "how" and "why" when setting the value of key parameters. This guide assumes that the reader has already set up the navigation stack and ready to optimize it. This is also a summary of my work with the ROS navigation stack.
- Jun 29 2017 cs.IR arXiv:1706.09067v1Current recommender systems largely focus on static, unstructured content. In many scenarios, we would like to recommend content that has structure, such as a trajectory of points-of-interests in a city, or a playlist of songs. Dubbed Structured Recommendation, this problem differs from the typical structured prediction problem in that there are multiple correct answers for a given input. Motivated by trajectory recommendation, we focus on sequential structures but in contrast to classical Viterbi decoding we require that valid predictions are sequences with no repeated elements. We propose an approach to sequence recommendation based on the structured support vector machine. For prediction, we modify the inference procedure to avoid predicting loops in the sequence. For training, we modify the objective function to account for the existence of multiple ground truths for a given input. We also modify the loss-augmented inference procedure to exclude the known ground truths. Experiments on real-world trajectory recommendation datasets show the benefits of our approach over existing, non-structured recommendation approaches.
- High-accuracy speech recognition is especially challenging when large datasets are not available. It is possible to bridge this gap with careful and knowledge-driven parsing combined with the biologically inspired CNN and the learning guarantees of the Vapnik Chervonenkis (VC) theory. This work presents a Shallow-CNN-HTSVM (Hierarchical Tree Support Vector Machine classifier) architecture which uses a predefined knowledge-based set of rules with statistical machine learning techniques. Here we show that gross errors present even in state-of-the-art systems can be avoided and that an accurate acoustic model can be built in a hierarchical fashion. The CNN-HTSVM acoustic model outperforms traditional GMM-HMM models and the HTSVM structure outperforms a MLP multi-class classifier. More importantly we isolate the performance of the acoustic model and provide results on both the frame and phoneme level considering the true robustness of the model. We show that even with a small amount of data accurate and robust recognition rates can be obtained.
- In this paper, we introduce a new model for the risk process based on general compound Hawkes process (GCHP) for the arrival of claims. We call it risk model based on general compound Hawkes process (RMGCHP). The Law of Large Numbers (LLN) and the Functional Central Limit Theorem (FCLT) are proved. We also study the main properties of this new risk model, net profit condition, premium principle and ruin time (including ultimate ruin time) applying the LLN and FCLT for the RMGCHP. We show, as applications of our results, similar results for risk model based on compound Hawkes process (RMCHP) and apply them to the classical risk model based on compound Poisson process (RMCPP).
- Jun 29 2017 cs.CL arXiv:1706.09031v1The CoNLL-SIGMORPHON 2017 shared task on supervised morphological generation required systems to be trained and tested in each of 52 typologically diverse languages. In sub-task 1, submitted systems were asked to predict a specific inflected form of a given lemma. In sub-task 2, systems were given a lemma and some of its specific inflected forms, and asked to complete the inflectional paradigm by predicting all of the remaining inflected forms. Both sub-tasks included high, medium, and low-resource conditions. Sub-task 1 received 24 system submissions, while sub-task 2 received 3 system submissions. Following the success of neural sequence-to-sequence models in the SIGMORPHON 2016 shared task, all but one of the submissions included a neural component. The results show that high performance can be achieved with small training datasets, so long as models have appropriate inductive bias or make use of additional unlabeled data or synthetic data. However, different biasing and data augmentation resulted in disjoint sets of inflected forms being predicted correctly, suggesting that there is room for future improvement.
- Jun 29 2017 math.OC arXiv:1706.09019v1There is a growing need to develop optimization methods to enable the reliable and efficient operation of power systems that have a large fraction of their power supplied from intermittent renewable resources. In this paper, we formulate the robust AC optimal power flow (RAC-OPF) problem as a two-stage robust optimization problem with recourse. This problem amounts to an infinite-dimensional nonconvex optimization problem, which is computationally intractable, in general. By restricting the space of recourse policies to those which are affine in the uncertain problem data, we provide a method to approximate RAC-OPF from within by a finite-dimensional semidefinite program. The resulting semidefinite program yields an affine recourse policy that is guaranteed to be feasible for RAC-OPF. We illustrate the effectiveness of the proposed optimization method on a nine-bus power system with different levels of renewable resource penetration and uncertainty.
- Jun 29 2017 math.OC arXiv:1706.08996v1The clustering of a data set into disjoint clusters is one of the core tasks in data analytics. Many clustering algorithms exhibit a strong contrast between a favorable performance in practice and bad theoretical worst-cases. Prime examples are least-squares assignments and the popular k-means algorithm. We are interested in this contrast and approach it using methods of polyhedral theory. Several popular clustering algorithms are readily connected to finding a vertex of the so-called bounded-shape partition polytopes. The vertices correspond to clusterings with extraordinary separation properties, in particular allowing the construction of a separating power diagram such that each cluster has its own cell. The geometric structure of these polytopes reveals useful information: First, we are able to quantitatively measure the space of all sites that allow construction of a separating power diagrams for a clustering by the volume of its normal cone. This gives rise to a new quality criterion for clusterings, and explains why good clusterings are also the most likely to be found by some classical algorithms. Second, we characterize the edges of the bounded-shape partition polytopes. Through this, we obtain an explicit description of the normal cones. This allows us to compute measures with respect to the new quality criterion, and even compute most stable sites for the separation of clusters. The hardness of these computations depends on the number of edges incident to a vertex, which may be exponential. However, this computational effort is rewarded with a wealth of information that can be gained from the results, which we highlight using a toy example.