Learning Bayesian Networks from Big Data with Greedy Search: Computational Complexity and Efficient Implementation

Learning the structure of Bayesian networks from data is known to be a computationally challenging, NP-hard problem. The literature has long investigated how to perform structure learning from data containing large numbers of variables, following a general interest in high-dimensional applications (‘small n, large p’) in systems biology and genetics. More recently, data sets with large numbers of observations (the so-called ‘big data’) have become increasingly common; and many of these data sets are not high-dimensional, having only a few tens of variables. We revisit the computational complexity of Bayesian network structure learning in this setting, showing that the common choice of measuring it with the number of estimated local distributions leads to unrealistic time complexity estimates for the most common class of score-based algorithms, greedy search. We then derive more accurate expressions under common distributional assumptions. These expressions suggest that the speed of Bayesian network learning can be improved by taking advantage of the availability of closed form estimators for local distributions with few parents. Furthermore, we find that using predictive instead of in-sample goodness-of-fit scores improves both speed and accuracy at the same time. We demonstrate these results on large real-world environmental data and on reference data sets available from public repositories.


Causal network discovery by iterative conditioning: comparison of algorithms

Estimating causal interactions in complex networks is an important problem encountered in many fields of current science. While a theoretical solution for detecting the graph of causal interactions has been previously formulated in the framework of prediction improvement, it generally requires the computation of high-dimensional information functionals — a situation invoking the curse of dimensionality with increasing network size. Recently, several methods have been proposed to alleviate this problem, based on iterative procedures for assessment of conditional (in)dependences. In the current work, we bring a comparison of several such prominent approaches. This is done both by theoretical comparison of the algorithms using a formulation in a common framework, and by numerical simulations including realistic complex coupling patterns. The theoretical analysis shows that the algorithms are strongly related; including one algorithm being in particular situations equivalent to the first phase of another. Moreover, numerical simulations suggest that the accuracy of most of the algorithms is under suitable parameter choice almost indistinguishable. However, particularly for large networks there are substantial differences in their computational demands, suggesting some of the algorithms are relatively more efficient in the case of sparse networks, while other perform better in the case of dense networks. The most recent variant of the algorithm by Runge et al. then provides a promising speedup particularly for large sparse networks, albeit appears to lead to a substantial decrease in accuracy in some scenarios. Based on the analysis of the reviewed algorithms, we propose a hybrid approach that provides competitive results both concerning computational efficiency and accuracy.


Automatic Language Identification in Texts: A Survey

Language identification (LI) is the problem of determining the natural language that a document or part thereof is written in. Automatic LI has been extensively researched for over fifty years. Today, LI is a key part of many text processing pipelines, as text processing techniques generally assume that the language of the input text is known. Research in this area has recently been especially active. This article provides a brief history of LI research, and an extensive survey of the features and methods used so far in the LI literature. For describing the features and methods we introduce a unified notation. We discuss evaluation methods, applications of LI, as well as off-the-shelf LI systems that do not require training by the end user. Finally, we identify open issues, survey the work to date on each issue, and propose future directions for research in LI.


Knowledge-based end-to-end memory networks

End-to-end dialog systems have become very popular because they hold the promise of learning directly from human to human dialog interaction. Retrieval and Generative methods have been explored in this area with mixed results. A key element that is missing so far, is the incorporation of a-priori knowledge about the task at hand. This knowledge may exist in the form of structured or unstructured information. As a first step towards this direction, we present a novel approach, Knowledge based end-to-end memory networks (KB-memN2N), which allows special handling of named entities for goal-oriented dialog tasks. We present results on two datasets, DSTC6 challenge dataset and dialog bAbI tasks.


Statistical and Economic Evaluation of Time Series Models for Forecasting Arrivals at Call Centers

Call centers’ managers are interested in obtaining accurate point and distributional forecasts of call arrivals in order to achieve an optimal balance between service quality and operating costs. We present a strategy for selecting forecast models of call arrivals which is based on three pillars: (i) flexibility of the loss function; (ii) statistical evaluation of forecast accuracy; (iii) economic evaluation of forecast performance using money metrics. We implement fourteen time series models and seven forecast combination schemes on three series of daily call arrivals. Although we focus mainly on point forecasts, we also analyze density forecast evaluation. We show that second moments modeling is important both for point and density forecasting and that the simple Seasonal Random Walk model is always outperformed by more general specifications. Our results suggest that call center managers should invest in the use of forecast models which describe both first and second moments of call arrivals.


Dropping Networks for Transfer Learning

In natural language understanding, many challenges require learning relationships between two sequences for various tasks such as similarity, relatedness, paraphrasing and question matching. Some of these challenges are inherently closer in nature, hence the knowledge acquired from one task to another is easier acquired and adapted. However, transferring all knowledge might be undesired and can lead to sub-optimal results due to \textit{negative} transfer. Hence, this paper focuses on the transferability of both instances and parameters across natural language understanding tasks using an ensemble-based transfer learning method to circumvent such issues. The primary contribution of this paper is the combination of both \textit{Dropout} and \textit{Bagging} for improved transferability in neural networks, referred to as \textit{Dropping} herein. Secondly, we present a straightforward yet novel approach to incorporating source \textit{Dropping} Networks to a target task for few-shot learning that mitigates \textit{negative} transfer. This is achieved by using a decaying parameter chosen according to the slope changes of a smoothed spline error curve at sub-intervals during training. We compare the approach over the hard parameter sharing, soft parameter sharing and single-task learning to compare its effectiveness. The aforementioned adjustment leads to improved transfer learning performance and comparable results to the current state of the art only using few instances from the target task.


Measurement Errors in R

This paper presents an R package to handle and represent measurements with errors in a very simple way. We briefly introduce the main concepts of metrology and propagation of uncertainty, and discuss related R packages. Building upon this, we introduce the ‘errors’ package, which provides a class for associating uncertainty metadata, automated propagation and reporting. Working with ‘errors’ enables transparent, lightweight, less error-prone handling and convenient representation of measurements with errors. Finally, we discuss the advantages, limitations and future work of computing with errors.


Approximate Abstractions of Markov Chains with Interval Decision Processes (Extended Version)

This work introduces a new abstraction technique for reducing the state space of large, discrete-time labelled Markov chains. The abstraction leverages the semantics of interval Markov decision processes and the existing notion of approximate probabilistic bisimulation. Whilst standard abstractions make use of abstract points that are taken from the state space of the concrete model and which serve as representatives for sets of concrete states, in this work the abstract structure is constructed considering abstract points that are not necessarily selected from the states of the concrete model, rather they are a function of these states. The resulting model presents a smaller one-step bisimulation error, when compared to a like-sized, standard Markov chain abstraction. We outline a method to perform probabilistic model checking, and show that the computational complexity of the new method is comparable to that of standard abstractions based on approximate probabilistic bisimulations.


Towards Symbolic Reinforcement Learning with Common Sense

Deep Reinforcement Learning (deep RL) has made several breakthroughs in recent years in applications ranging from complex control tasks in unmanned vehicles to game playing. Despite their success, deep RL still lacks several important capacities of human intelligence, such as transfer learning, abstraction and interpretability. Deep Symbolic Reinforcement Learning (DSRL) seeks to incorporate such capacities to deep Q-networks (DQN) by learning a relevant symbolic representation prior to using Q-learning. In this paper, we propose a novel extension of DSRL, which we call Symbolic Reinforcement Learning with Common Sense (SRL+CS), offering a better balance between generalization and specialization, inspired by principles of common sense when assigning rewards and aggregating Q-values. Experiments reported in this paper show that SRL+CS learns consistently faster than Q-learning and DSRL, achieving also a higher accuracy. In the hardest case, where agents were trained in a deterministic environment and tested in a random environment, SRL+CS achieves nearly 100% average accuracy compared to DSRL’s 70% and DQN’s 50% accuracy. To the best of our knowledge, this is the first case of near perfect zero-shot transfer learning using Reinforcement Learning.


Black-box Adversarial Attacks with Limited Queries and Information

Current neural network-based classifiers are susceptible to adversarial examples even in the black-box setting, where the attacker only has query access to the model. In practice, the threat model for real-world systems is often more restrictive than the typical black-box model of full query access. We define three realistic threat models that more accurately characterize many real-world classifiers: the query-limited setting, the partial-information setting, and the label-only setting. We develop new attacks that fool classifiers under these more restrictive threat models, where previous methods would be impractical or ineffective. We demonstrate that our methods are effective against an ImageNet classifier under our proposed threat models. We also demonstrate a targeted black-box attack against a commercial classifier, overcoming the challenges of limited query access, partial information, and other practical issues to attack the Google Cloud Vision API.


Exploiting Partially Annotated Data for Temporal Relation Extraction
Mixed Quality of Service in Cell-Free Massive MIMO
LightRel SemEval-2018 Task 7: Lightweight and Fast Relation Classification
Learn and Pick Right Nodes to Offload
Exploiting Prior Information in Block Sparse Signals
Robust User Scheduling with COST 2100 Channel Model for Massive MIMO Networks
On the Impact of Fixed Point Hardware for Optical Fiber Nonlinearity Compensation Algorithms
A Robust Process to Identify Pivots inside Sub-communities In Social Networks
Understanding UAV Cellular Communications: From Existing Networks to Massive MIMO
Question Answering Resources Applied to Slot-Filling
Optimum Sidelobe Level Reduction in ACF of NLFM Waveform
Sparse Travel Time Estimation from Streaming Data
SolidWorx: A Resilient and Trustworthy Transactive Platform for Smart and Connected Communities
Complex Network Analysis of Men Single ATP Tennis Matches
Same Representation, Different Attentions: Shareable Sentence Representation Learning from Multiple Tasks
Maximum entropy priors with derived parameters in a specified distribution
Union bound for quantum information processing
Micro-Net: A unified model for segmentation of various objects in microscopy images
The connected metric dimension at a vertex of a graph
Deep Learning in Spiking Neural Networks
Price Competition with Geometric Brownian motion in Exchange Rate Uncertainty
Local White Matter Architecture Defines Functional Brain Dynamics
Boolean functions on high-dimensional expanders
Word Embedding Perturbation for Sentence Classification
A Deep Convolutional Neural Network for Lung Cancer Diagnostic
Maximizing Profit with Convex Costs in the Random-order Model
Stochastic Dynamics II: Finite Random Dynamical Systems, Linear Representation, and Entropy Production
Torus polynomials: an algebraic approach to ACC lower bounds
Towards Practical Constrained Monotone Submodular Maximization
Large Receptive Field Networks for High-Scale Image Super-Resolution
Exchange of Renewable Energy among Prosumers using Blockchain with Dynamic Pricing
Advancing Tabu and Restart in Local Search for Maximum Weight Cliques
Embedding Hypertrees into Steiner Triple Systems
Parabolically induced functions and equidistributed pairs
syGlass: Interactive Exploration of Multidimensional Images Using Virtual Reality Head-mounted Displays
A neural interlingua for multilingual machine translation
Linguistically-Informed Self-Attention for Semantic Role Labeling
Spell Once, Summon Anywhere: A Two-Level Open-Vocabulary Language Model
Towards a Unified Natural Language Inference Framework to Evaluate Sentence Representations
Efficient Object Tracking based on Circular and Structural Multi-level Learners
Synthesizing Distributed Energy Resources in Microgrids with Temporal Logic Specifications
q-Gauss summation formula and q-Analogues of Ramanujan-type series for 1/pi
The amazing world of simplicial complexes
Some New Constructions of Quantum MDS Codes
Poisson statistics at the edge of Gaussian $β$-ensemble at high temperature
Mem2Seq: Effectively Incorporating Knowledge Bases into End-to-End Task-Oriented Dialog Systems
Econometric Modeling of Regional Electricity Spot Prices in the Australian Market
Adapted Performance Assessment For Drivers Through Behavioral Advantage
Multi-scale prediction for robust hand detection and classification
A direct approach to false discovery rates by decoy permutations
Parsing Tweets into Universal Dependencies
An Empirical Comparison of PDDL-based and ASP-based Task Planners
Adapting Blockchain Technology for Scientific Computing
N-fold Superposition: Improving Neural Networks by Reducing the Noise in Feature Maps
PeRView: A Framework for Personalized Review Selection Using Micro-Reviews
How Bad is the Freedom to Flood-It?
Constructing Locally Dense Point Clouds Using OpenSfM and ORB-SLAM2
Constructing Permutation Arrays using Partition and Extension
Memory Attention Networks for Skeleton-based Action Recognition
Progressive refinement: a method of coarse-to-fine image parsing using stacked network
On the Relationship Between Ehrhart Unimodality and Ehrhart Positivity
Clinical Assistant Diagnosis for Electronic Medical Record Based on Convolutional Neural Network
On the Diachronic Stability of Irregularity in Inflectional Morphology
Spectral characterization of the complete graph removing a path of small length
To Create What You Tell: Generating Videos from Captions
Deterministic and Randomized Diffusion based Iterative Generalized Hard Thresholding (DiFIGHT) for Distributed Sparse Signal Recovery
NLITrans at SemEval-2018 Task 12: Transfer of Semantic Knowledge for Argument Comprehension
Jointly Localizing and Describing Events for Dense Video Captioning
Deep Semantic Hashing with Generative Adversarial Networks
PlusEmo2Vec at SemEval-2018 Task 1: Exploiting emotion knowledge from emoji and #hashtags
Memory Matching Networks for One-Shot Image Recognition
On the Design of an Intelligent Speed Advisory System for Cyclists
Succinct Oblivious RAM
Fully Convolutional Adaptation Networks for Semantic Segmentation
Guaranteeing Consistency in a Motion Planning and Control Architecture Using a Kinematic Bicycle Model
MVTec D2S: Densely Segmented Supermarket Dataset
Layered Based Augmented Complex Kalman Filter for Fast Forecasting-Aided State Estimation of Distribution Networks
Representational Issues in the Debate on the Standard Model of the Mind
Deep cross-domain building extraction for selective depth estimation from oblique aerial imagery
A Multi-Beam NOMA Framework for Hybrid mmWave Systems
Minimum Symbol Error Rate-Based Constant Envelope Precoding for Multiuser Massive MISO Downlink
Exploiting Semantics in Neural Machine Translation with Graph Convolutional Networks
Making an Appraiser Work for You
Bilingual Embeddings with Random Walks over Multilingual Wordnets
Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines
Asymptotics of even-even correlations in the Ising model
Varieties of Signature Tensors
Understanding Cross-sectional Dependence in Panel Data
Taskonomy: Disentangling Task Transfer Learning
Energy Efficiency of Rate-Splitting Multiple Access, and Performance Benefits over SDMA and NOMA
Client Selection for Federated Learning with Heterogeneous Resources in Mobile Edge
Semantic Parsing with Syntax- and Table-Aware SQL Generation
Randomized Mixture Models for Probability Density Approximation and Estimation
Optimal B-Robust Estimation for the Parameters of Marshall-Olkin Extended Burr XII Distribution and Application for Modeling Data from Pharmacokinetics Study
Deep Facial Expression Recognition: A Survey
Multi-focus Image Fusion using dictionary learning and Low-Rank Representation
DenseFuse: A Fusion Approach to Infrared and Visible Images
Log-transformed kernel density estimation for positive data
VLocNet++: Deep Multitask Learning for Semantic Visual Localization and Odometry
Gaussian Material Synthesis
Convolutional capsule network for classification of breast cancer histology images
BrainSlug: Transparent Acceleration of Deep Learning Through Depth-First Parallelism
STAN: Spatio-Temporal Adversarial Networks for Abnormal Event Detection
Nonlinear state-space modelling of the kinematics of an oscillating circular cylinder in a fluid flow
Stable Lévy processes in a cone
Path Planning in Support of Smart Mobility Applications using Generative Adversarial Networks
Some properties of Bowlin and Brin’s color graphs
Abdominal multi-organ segmentation with organ-attention networks and statistical fusion
An algorithm to compute the Hoffman constant of a system of linear constraints
Efficient Pose Tracking from Natural Features in Standard Web Browsers
Nesting Monte Carlo for high-dimensional Non Linear PDEs
A Spoofing Benchmark for the 2018 Voice Conversion Challenge: Leveraging from Spoofing Countermeasures for Speech Artifact Assessment
Viability approach to finite-time stability
Explicit solutions to utility maximization problems in a regime-switching market model via Laplace transforms
Decorrelated Batch Normalization
Attention Based Natural Language Grounding by Navigating Virtual Environment
Mixing Context Granularities for Improved Entity Linking on Question Answering Data across Entity Categories
Error Bounds for FDD Massive MIMO Channel Covariance Conversion with Set-Theoretic Methods
One-dimensional scaling limits in a planar Laplacian random growth model
Robust Beamforming with Pilot Reuse Scheduling in a Heterogeneous Cloud Radio Access Network
Joint Enhancement and Denoising Method via Sequential Decomposition
The Neumann Boundary Problem for Elliptic Partial Differential Equations with Nonlinear Divergence Terms
High Dimensional Estimation and Multi-Factor Models
Beyond Narrative Description: Generating Poetry from Images by Multi-Adversarial Training
Cosmic Microwave Background Constraints in Light of Priors Over Reionization Histories
ASR Performance Prediction on Unseen Broadcast Programs using Convolutional Neural Networks
Systems of Reflected Stochastic PDEs in a Convex Domain: Analytical Approach
Parallel and I/O-efficient Randomisation of Massive Networks using Global Curveball Trades
On the Asymptotic Normality of Adaptive Multilevel Splitting
Correlations for symplectic and orthogonal Schur measures
ALIGNet: Partial-Shape Agnostic Alignment via Unsupervised Learning
Person Identification from Partial Gait Cycle Using Fully Convolutional Neural Network
On the Capacity of the Peak Power Constrained Vector Gaussian Channel: An Estimation Theoretic Perspective
A New Channel Boosted Convolution Neural Network using Transfer Learning
VectorDefense: Vectorization as a Defense to Adversarial Examples
From the master equation to mean field game limit theory: A central limit theorem
A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming
Entropy bounds for grammar compression
Eigenvector Computation and Community Detection in Asynchronous Gossip Models
From the master equation to mean field game limit theory: Large deviations and concentration of measure
On the circular correlation coefficients for bivariate von Mises distributions on a torus
False Information on Web and Social Media: A Survey
Spatio-Temporal Neural Networks for Space-Time Series Forecasting and Relations Discovery
Measuring Within and Between Group Inequality in Early-Life Mortality Over Time: A Bayesian Approach with Application to India
Light-weight Head Pose Invariant Gaze Tracking
Perron-Frobenius Theorem for Rectangular Tensors and Directed Hypergraphs
Leveraging Friendship Networks for Dynamic Link Prediction in Social Interaction Networks
The random normal matrix model: insertion of a point charge
Guided Attention for Large Scale Scene Text Verification
Single-User mmWave Massive MIMO: SVD-based ADC Bit Allocation and Combiner Design
On capacities of the two-user union channel with complete feedback
Towards Learning Sparsely Used Dictionaries with Arbitrary Supports
Zero-Shot Visual Imitation
Constrained optimal design of automotive radar arrays using the Weiss-Weinstein Bound
Benchmarking projective simulation in navigation problems

Advertisements