Analysis of the Impact of Negative Sampling on Link Prediction in Knowledge Graphs

Knowledge graphs are large, useful, but incomplete knowledge repositories. They encode knowledge through entities and relations which define each other through the connective structure of the graph. This has inspired methods for the joint embedding of entities and relations in continuous low-dimensional vector spaces, that can be used to induce new edges in the graph, i.e., link prediction in knowledge graphs. Learning these representations relies on contrasting positive instances with negative ones. Knowledge graphs include only positive relation instances, leaving the door open for a variety of methods for selecting negative examples. In this paper we present an empirical study on the impact of negative sampling on the learned embeddings, assessed through the task of link prediction. We use state-of-the-art knowledge graph embeddings — \rescal , TransE, DistMult and ComplEX — and evaluate on benchmark datasets — FB15k and WN18. We compare well known methods for negative sampling and additionally propose embedding based sampling methods. We note a marked difference in the impact of these sampling methods on the two datasets, with the ‘traditional’ corrupting positives method leading to best results on WN18, while embedding based methods benefiting the task on FB15k.

Dynamic Input Structure and Network Assembly for Few-Shot Learning

The ability to learn from a small number of examples has been a difficult problem in machine learning since its inception. While methods have succeeded with large amounts of training data, research has been underway in how to accomplish similar performance with fewer examples, known as one-shot or more generally few-shot learning. This technique has been shown to have promising performance, but in practice requires fixed-size inputs making it impractical for production systems where class sizes can vary. This impedes training and the final utility of few-shot learning systems. This paper describes an approach to constructing and training a network that can handle arbitrary example sizes dynamically as the system is used.

Anytime Neural Networks via Joint Optimization of Auxiliary Losses

We address the problem of anytime prediction in neural networks. An anytime predictor automatically adjusts to and utilizes available test-time budget: it produces a crude initial result quickly and continuously refines the result afterwards. Traditional feed-forward networks achieve state-of-the-art performance on many machine learning tasks, but cannot produce anytime predictions during their typically expensive computation. In this work, we propose to add auxiliary predictions in a residual network to generate anytime predictions, and optimize these predictions simultaneously. We solve this multi-objective optimization by minimizing a carefully constructed weighted sum of losses. We also oscillate weightings of the losses in each iteration to avoid spurious solutions that are optimal for the sum but not for each individual loss. The proposed approach produces competitive results if computation is interrupted early, and the same level of performance as the original network once computation is finished. Observing that the relative performance gap between the optimal and our proposed anytime network shrinks as the network is near completion, we propose a method to combine anytime networks to achieve more accurate anytime predictions with a constant fraction of additional cost. We evaluate the proposed methods on real-world visual recognition data-sets to demonstrate their anytime performance.

Multi-Chart Detection Procedure for Bayesian Quickest Change-Point Detection with Unknown Post-Change Parameters

In this paper, the problem of quickly detecting an abrupt change on a stochastic process under Bayesian framework is considered. Different from the classic Bayesian quickest change-point detection problem, this paper considers the case where there is uncertainty about the post-change distribution. Specifically, the observer only knows that the post-change distribution belongs to a parametric distribution family but he does not know the true value of the post-change parameter. In this scenario, we propose two multi-chart detection procedures, termed as M-SR procedure and modified M-SR procedure respectively, and show that these two procedures are asymptotically optimal when the post-change parameter belongs to a finite set and are asymptotically \epsilon-optimal when the post-change parameter belongs to a compact set with finite measure. Both algorithms can be calculated efficiently as their detection statistics can be updated recursively. We then extend the study to consider the multi-source monitoring problem with unknown post-change parameters. When those monitored sources are mutually independent, we propose a window-based modified M-SR detection procedure and show that the proposed detection method is first-order asymptotically optimal when post-change parameters belong to finite sets. We show that both computation and space complexities of the proposed algorithm increase only linearly with respect to the number of sources.

Mean-Variance Optimization of Discrete Time Discounted Markov Decision Processes

In this paper, we study a mean-variance optimization problem in an infinite horizon discrete time discounted Markov decision process (MDP). The objective is to minimize the variance of system rewards with the constraint of mean performance. Different from most of works in the literature which require the mean performance already achieve optimum, we can let the mean discounted performance equal any constant. The difficulty of this problem is caused by the quadratic form of the variance function which makes the variance minimization problem not a standard MDP. By proving the decomposable structure of the feasible policy space, we transform this constrained variance minimization problem to an equivalent unconstrained MDP under a new discounted criterion and a new reward function. The difference of the variances of Markov chains under any two feasible policies is quantified by a difference formula. Based on the variance difference formula, a policy iteration algorithm is developed to find the optimal policy. We also prove the optimality of deterministic policy over the randomized policy generated in the mean-constrained policy space. Numerical experiments demonstrate the effectiveness of our approach.

Automatic Detection of Fake News

The proliferation of misleading information in everyday access media outlets such as social media feeds, news blogs, and online newspapers have made it challenging to identify trustworthy news sources, thus increasing the need for computational tools able to provide insights into the reliability of online content. In this paper, we focus on the automatic identification of fake content in online news. Our contribution is twofold. First, we introduce two novel datasets for the task of fake news detection, covering seven different news domains. We describe the collection, annotation, and validation process in detail and present several exploratory analysis on the identification of linguistic differences in fake and legitimate news content. Second, we conduct a set of learning experiments to build accurate fake news detectors. In addition, we provide comparative analyses of the automatic and manual identification of fake news.

Elements of nonlinear analysis of information streams

This review considers methods of nonlinear dynamics to apply for analysis of time series corresponding to information streams on the Internet. In the main, these methods are based on correlation, fractal, multifractal, wavelet, and Fourier analysis. The article is dedicated to a detailed description of these approaches and interconnections among them. The methods and corresponding algorithms presented can be used for detecting key points in the dynamic of information processes; identifying periodicity, anomaly, self-similarity, and correlations; forecasting various information processes. The methods discussed can form the basis for detecting information attacks, campaigns, operations, and wars.

Seeing Through Noise: Speaker Separation and Enhancement using Visually-derived Speech
Reflection Separation and Deblurring of Plenoptic Images
Recovering Nonuniform Planted Partitions via Iterated Projection
Matroids with no $U_{2,n}$-minor and many hyperplanes
Volatility and Economic Growth in the Twentieth Century
Human Action Recognition System using Good Features and Multilayer Perceptron Network
A Novel Consensus-based Distributed Algorithm for Economic Dispatch Based on Local Estimation of Power Mismatch
On $Q$-deformations of Postnikov-Shapiro algebras
Deep EndoVO: A Recurrent Convolutional Neural Network (RCNN) based Visual Odometry Approach for Endoscopic Capsule Robots
Classification of Radiology Reports Using Neural Attention Models
Multiple-Kernel Based Vehicle Tracking Using 3D Deformable Model and Camera Self-Calibration
Skip RNN: Learning to Skip State Updates in Recurrent Neural Networks
An improved upper bound on the maximum degree of terminal-pairable complete graphs
Semiparametric Sieve Maximum Likelihood Estimation Under Cure Model with Partly Interval Censored and Left Truncated Data for Application to Spontaneous Abortion Data
Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm
A Conditional Model of Wind Power Forecast Errors and Its Application in Scenario Generation
Inner approximations of power flow feasibility sets
On Relaxing Determinism in Arithmetic Circuits
Learning Deep Neural Network Representations for Koopman Operators of Nonlinear Dynamical Systems
Stochastic Approximation Affine Dynamics and Group Consensus over Random Signed Networks
Min-Max Theorems for Packing and Covering Odd $(u,v)$-trails
ElasticPlay: Interactive Video Summarization with Dynamic Time Budgets
A stochastic power management strategy with skid avoidance for improving energy efficiency of in-wheel motor electric vehicles
Static Graph Challenge: Subgraph Isomorphism
Discovering Political Topics in Facebook Discussion threads with Spectral Contextualization
A Resistance Distance-Based Approach for Optimal Leader Selection in Noisy Consensus Networks
Elastic Local Breakout Strategy and Implementation for Delay-Sensitive Packets with Local Significance
The Reachability of Computer Programs
On Relationship between Primal-Dual Method of Multipliers and Kalman Filter
Big Data Meets HPC Log Analytics: Scalable Approach to Understanding Systems at Extreme Scale
Crowding of interacting fluids in porous media: Soft and hard interactions are different
Fault-Tolerant Dot-Product Engines
Projected support points, with application to optimal MCMC reduction
Traveling Speed of Clusters in the Kuramoto-Sakaguchi Model
Human experts vs. machines in taxa recognition
Random Walks on solvable matrix groups
Proximal-Proximal-Gradient Method
On Words with the Zero Palindromic Defect
Tomographic Reconstruction Methods for Decomposing Directional Components
$\prod\limits_{i=1}^{n} \mathbb{Z}_{2^i}$-Additive Cyclic Codes
Reflection on the coloring and chromatic numbers
Bringing Fault-Tolerant GigaHertz-Computing to Space: A Multi-Stage Software-Side Fault-Tolerance Approach for Miniaturized Spacecraft
Feynman path integrals for magnetic Schrödinger operators on infinite weighted graphs
Hierarchical Multinomial-Dirichlet model for the estimation of conditional probability tables
Is Deep Learning Safe for Robot Vision? Adversarial Examples against the iCub Humanoid
Trajectory stability in the traveling salesman problem
Proof-Labeling Schemes: Broadcast, Unicast and In Between
Markov-Modulated Information Flows
On Local laws for non-Hermitian random matrices and their products
Further results on complete permutation monomials over finite fields
Adaptive Linear Programming Decoding of Nonbinary Linear Codes Over Prime Fields
Towards Cooperative Motion Planning for Automated Vehicles in Mixed Traffic
Pose Estimation using Local Structure-Specific Shape and Appearance Context
Invariant Measures, Hausdorff Dimension and Dimension Drop of some Harmonic Measures on Galton-Watson Trees
In search of inliers: 3d correspondence by local and global voting
Exploiting Convolution Filter Patterns for Transfer Learning
Generating Visual Representations for Zero-Shot Classification
Incremental Learning of Object Detectors without Catastrophic Forgetting
Level set Cox processes
Edgeworth expansions for slow-fast systems and their application to model reduction for finite time scale separation
A Neural Network Approach for Mixing Language Models
On the interpretability and computational reliability of frequency-domain Granger causality
The Unconstrained Ear Recognition Challenge
Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems
Variational autoencoders for tissue heterogeneity exploration from (almost) no preprocessed mass spectrometry imaging data
Random waves on $\mathbb{T}^3$: nodal area variance and lattice point correlations
Hypothesis testing for tail dependence parameters on the boundary of the parameter space with application to generalized max-linear models
Statistical Selection of CNN-Based Audiovisual Features for Instantaneous Estimation of Human Emotional States
Machine Learning Inspired Energy-Efficient Hybrid Precoding for MmWave Massive MIMO Systems
CNN-Based Prediction of Frame-Level Shot Importance for Video Summarization
Bayesian Learning of Clique Tree Structure
Fast single image super-resolution based on sigmoid transformation
Application of a Convolutional Neural Network for image classification to the analysis of collisions in High Energy Physics
Non-linear Convolution Filters for CNN-based Learning
Scale-invariant unconstrained online learning
Capturing Long-term Temporal Dependencies with Convolutional Networks for Continuous Emotion Recognition
Exceedingly Large Deviations of the Totally Asymmetric Exclusion Process
A natural generalization in graph Ramsey theory
Non-asymptotic error bounds for The Multilevel Monte Carlo Euler method applied to SDEs with constant diffusion coefficient
Single Reference Image based Scene Relighting via Material Guided Filtering
Pareto suboptimal solutions to large-scale multiobjective multidimensional knapsack problems with assessments of Pareto suboptimality gaps
Local asymptotic properties for Cox-Ingersoll-Ross process with discrete observations
Measure-valued martingales and optimality of Bass-type solutions to the Skorokhod Embedding Problem
A Grammar for Reproducible and Painless Extract-Transform-Load Operations on Medium Data
More declarative tabling in Prolog using multi-prompt delimited control
Correlated continuous time random walks and fractional Pearson diffusions
Delay Analysis for Wireless D2D Caching with Inter-cluster Cooperation
Predicting Aesthetic Score Distribution through Cumulative Jensen-Shannon Divergence
Construction of the Symbol Invariant of Partition
Positive Solutions of $p$-th Yamabe Type Equations on Graphs
Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
$β$-Nonintersecting Poisson Random Walks: Law of Large Numbers and Central Limit Theorems
Some Criteria for a Signed Graph to Have Full Rank
Super-Convergence: Very Fast Training of Residual Networks Using Large Learning Rates