On the Smoothness of Paging Algorithms

We study the smoothness of paging algorithms. How much can the number of page faults increase due to a perturbation of the request sequence? We call a paging algorithm smooth if the maximal increase in page faults is proportional to the number of changes in the request sequence. We also introduce quantitative smoothness notions that measure the smoothness of an algorithm. We derive lower and upper bounds on the smoothness of deterministic and randomized demand-paging and competitive algorithms. Among strongly-competitive deterministic algorithms LRU matches the lower bound, while FIFO matches the upper bound. Well-known randomized algorithms like Partition, Equitable, or Mark are shown not to be smooth. We introduce two new randomized algorithms, called Smoothed-LRU and LRU-Random. Smoothed- LRU allows to sacrifice competitiveness for smoothness, where the trade-off is controlled by a parameter. LRU-Random is at least as competitive as any deterministic algorithm while smoother.

Evaluating Real-time Anomaly Detection Algorithms – the Numenta Anomaly Benchmark

Much of the world’s data is streaming, time-series data, where anomalies give significant information in critical situations; examples abound in domains such as finance, IT, security, medical, and energy. Yet detecting anomalies in streaming data is a difficult task, requiring detectors to process data in real-time, not batches, and learn while simultaneously making predictions. There are no benchmarks to adequately test and score the efficacy of real-time anomaly detectors. Here we propose the Numenta Anomaly Benchmark (NAB), which attempts to provide a controlled and repeatable environment of open-source tools to test and measure anomaly detection algorithms on streaming data. The perfect detector would detect all anomalies as soon as possible, trigger no false alarms, work with real-world time-series data across a variety of domains, and automatically adapt to changing statistics. Rewarding these characteristics is formalized in NAB, using a scoring algorithm designed for streaming data. NAB evaluates detectors on a benchmark dataset with labeled, real-world time-series data. We present these components, and give results and analyses for several open source, commercially-used algorithms. The goal for NAB is to provide a standard, open source framework with which the research community can compare and evaluate different algorithms for detecting anomalies in streaming data.

The Inductive Constraint Programming Loop

Constraint programming is used for a variety of real-world optimisation problems, such as planning, scheduling and resource allocation problems. At the same time, one continuously gathers vast amounts of data about these problems. Current constraint programming software does not exploit such data to update schedules, resources and plans. We propose a new framework, that we call the Inductive Constraint Programming loop. In this approach data is gathered and analyzed systematically, in order to dynamically revise and adapt constraints and optimization criteria. Inductive Constraint Programming aims at bridging the gap between the areas of data mining and machine learning on the one hand, and constraint programming on the other hand.

Further Theoretical Study of Distribution Separation Method for Information Retrieval

Recently, a Distribution Separation Method (DSM) is proposed for relevant feedback in information retrieval, which aims to approximate the true relevance distribution by separating a seed irrelevance distribution from the mixture one. While DSM achieved a promising empirical performance, theoretical analysis of DSM is still need further study and comparison with other relative retrieval model. In this article, we first generalize DSM’s theoretical property, by proving that its minimum correlation assumption is equivalent to the maximum (original and symmetrized) KL-Divergence assumption. Second, we also analytically show that the EM algorithm in a well-known Mixture Model is essentially a distribution separation process and can be simplified using the linear separation algorithm in DSM. Some empirical results are also presented to support our theoretical analysis.

A unified framework for model-based clustering, linear regression and multiple cluster structure detection

A general framework for dealing with both linear regression and clustering problems is described. It includes Gaussian clusterwise linear regression analysis with random covariates and cluster analysis via Gaussian mixture models with variable selection. It also admits a novel approach for detecting multiple clusterings from possibly correlated sub-vectors of variables, based on a model defined as the product of conditionally independent Gaussian mixture models. A necessary condition for the identifiability of such a model is provided. The usefulness and effectiveness of the described methodology are illustrated using simulated and real datasets.

Context-Aware Bandits

In this paper, we present the CAB (Context- Aware Bandits). With CAB we attempt to craft a bandit algorithm that can exploit collaborative effects and that can be deployed in a practical recommendation system setting, where the multi-armed bandits have been shown to perform well in particular with respect to the cold start problem. CAB exploits, a context-aware clustering technique augmenting exploration-exploitation strategies in a contextual multi-armed bandit settings. CAB dynamically clusters the users based on the content universe under consideration. We demonstrate the efficacy of our approach on extensive real-world datasets, showing the scalability, and more importantly, the significant increased prediction performance compared to related state-of-the-art methods.

ParallelPC: an R package for efficient constraint based causal exploration

Discovering causal relationships from data is the ultimate goal of many research areas. Constraint based causal exploration algorithms, such as PC, FCI, RFCI, PC-simple, IDA and Joint-IDA have achieved significant progress and have many applications. A common problem with these methods is the high computational complexity, which hinders their applications in real world high dimensional datasets, e.g gene expression datasets. In this paper, we present an R package, ParallelPC, that includes the parallelised versions of these causal exploration algorithms. The parallelised algorithms help speed up the procedure of experimenting big datasets and reduce the memory used when running the algorithms. The package is not only suitable for super-computers or clusters, but also convenient for researchers using personal computers with multi core CPUs. Our experiment results on real world datasets show that using the parallelised algorithms it is now practical to explore causal relationships in high dimensional datasets with thousands of variables in a single multicore computer. ParallelPC is available in CRAN repository at https://…/index.html.

OmniGraph: Rich Representation and Graph Kernel Learning

OmniGraph, a novel representation to support a range of NLP classification tasks, integrates lexical items, syntactic dependencies and frame semantic parses into graphs. Feature engineering is folded into the learning through convolution graph kernel learning to explore different extents of the graph. A high-dimensional space of features includes individual nodes as well as complex subgraphs. In experiments on a text-forecasting problem that predicts stock price change from news for company mentions, OmniGraph beats several benchmarks based on bag-of-words, syntactic dependencies, and semantic trees. The highly expressive features OmniGraph discovers provide insights into the semantics across distinct market sectors. To demonstrate the method’s generality, we also report its high performance results on a fine-grained sentiment corpus.

Survey on Feature Selection

Feature selection plays an important role in the data mining process. It is needed to deal with the excessive number of features, which can become a computational burden on the learning algorithms. It is also necessary, even when computational resources are not scarce, since it improves the accuracy of the machine learning tasks, as we will see in the upcoming sections. In this review, we discuss the different feature selection approaches, and the relation between them and the various machine learning algorithms.

Artificial Intelligence and Asymmetric Information Theory

When human agents come together to make decisions it is often the case that one human agent has more information than the other and this phenomenon is called information asymmetry and this distorts the market. Often if one human agent intends to manipulate a decision in its favor the human agent can signal wrong or right information. Alternatively, one human agent can screen for information to reduce the impact of asymmetric information on decisions. With the advent of artificial intelligence, signaling and screening have been made easier. This chapter studies the impact of artificial intelligence on the theory of asymmetric information. It is surmised that artificial intelligent agents reduce the degree of information asymmetry and thus the market where these agents are deployed become more efficient. It is also postulated that the more artificial intelligent agents there are deployed in the market the less is the volume of trades in the market. This is because for trade to happen the asymmetry of information on goods and services to be traded should exist.

The Legendre structure of the Parisi formula

Optimal ETF Selection for Passive Investing

I,F-partitions of Sparse Graphs

Asymptotic Logical Uncertainty and The Benford Test

Layered Heaps Beating Standard and Fibonacci Heaps in Practice

A note on spatial monotonicity for one-dimensional spin systems

On flow polytopes, order polytopes, and certain faces of the alternating sign matrix polytope

Parallel Triangles Counting Using Pipelining

Toward a Better Understanding of Leaderboard

On the 2-ranks of a class of unitals

A Still Simpler Way of Introducing the Interior-Point Method for Linear Programming

Vanishing corrections for the position in a linear model of FKPP fronts

Critical Scaling of Bagnold Rheology at the Jamming Transition of Frictionless Two Dimensional Disks

A low-energy decomposition theorem

Duality between star and plus connected components in percolation

Penalized estimation in large-scale generalized linear array models

On the Robustness of Regularized Pairwise Learning Methods Based on Kernels

Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches

Hopf-type neurons increase input-sensitivity by forming forcing-coupled ensembles

Birth and Death process in mean field type interaction

Efficient quantum tomography with incomplete measurement settings

Bias-corrected methods for estimating the receiver operating characteristic surface of continuous diagnostic tests

VB calibration to improve the interface between phone recognizer and i-vector extractor

Explosiveness of Age-Dependent Branching Processes with Contagious and Incubation Periods

Single Jump Processes and Strict Local Martingales

Data structuring for the ontological modelling of wind energy systems

Tasks Scheduling Technique Using League Championship Algorithm for Makespan Minimization in IaaS Cloud

A robust adaptive-to-model enhancement test for parametric single-index models

Analogues of Sury’s Fibonacci-Lucas Identity

Treetopes and their Graphs

Elastic Resource Allocation for Distributed Graph Processing Platforms

Higher order variance reduction for discretised diffusions via regression

On Correcting Inputs: Inverse Optimization for Online Structured Prediction

The Terminal Wiener Index of Trees with Diameter or Maximum Degree

Kernel Adaptive Sequential Monte Carlo

Channel Metrization

Tests for Large Dimensional Covariance Structure Based on Rao’s Score Test

An Explicit Description of the B(\infty) Crystal For Generalized Quantum Groups of a Family of Comet Quivers

Influence of network topology on cooperative problem-solving systems

A Diversity-Promoting Objective Function for Neural Conversation Models

$(r)$-Pancyclic, $(r)$-Bipancyclic and Oddly $(r)$-Bipancyclic Graphs

Inferring disease correlation from healthcare data

A localized quantum walk with a gap in distribution

Minors in graphs of large $θ_r$-girth

Coupled uncertainty provided by a multifractal random walker

The representation theory of finite sets and correspondences

On composition polynomials

Error estimates of finite element method for semi-linear stochastic strongly damped wave equation

Mining Interesting Trivia for Entities from Wikipedia

Textual Analysis for Studying Chinese Historical Documents and Literary Novels

A Shifting Bloom Filter Framework for Set Queries

Neural Networks with Few Multiplications

Assessing the Value of Peer-Produced Information for Exploratory Search

Meyniel’s conjecture holds for random d-regular graphs

Regularity Conditions for Convergence of Linear Statistics of Wigner Random Matrices

Linear Statistics of Non-Hermitian Matrices Matching the Real or Complex Ginibre Ensemble to Four Moments

Optimal Piecewise Linear Function Approximation for GPU-based Applications

On the large-scale structure of the tall peaks for stochastic heat equations with fractional Laplacian

Do Deep Neural Networks Learn Facial Action Units When Doing Expression Recognition?

On the estimation of the order of smoothness of the regression function

Pseudo-Marginal Slice Sampling

Recurrence-time statistics in non-Hamiltonian volume preserving maps and flows

Translation invariant realizability problem on the $d-$dimensional lattice: an explicit construction

On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth

A measure of evidence based on the likelihood-ratio statistics

Construction of fullerenes

Concentration of Measure Inequalities and Their Communication and Information-Theoretic Applications

Evaluation of Joint Multi-Instance Multi-Label Learning For Breast Cancer Diagnosis

On the Eschenauer-Gligor key predistribution scheme under on-off communication channels: The absence of isolated nodes (Extended version)

Tract Orientation and Angular Dispersion Deviation Indicator (TOADDI): A framework for single-subject analysis in diffusion tensor imaging

Asymptotically Optimal Pointwise and Minimax Quickest Change-point Detection for Dependent Data

Set partitions and integrable hierarchies

Localization and limit laws of a three-state alternate quantum walk on a two-dimensional lattice

Lempel Ziv Computation In Compressed Space (LZ-CICS)

ADAAPT: A Deep Architecture for Adaptive Policy Transfer from Multiple Sources

Exploring mod2 n-queens games

TSEB: More Efficient Thompson Sampling for Policy Learning

Mixture models applied to heterogeneous populations

The dissection of expression quantitative trait locus hotspots

Moderate deviations for the mildly stationary autoregressive models with dependent errors

AtomNet: A Deep Convolutional Neural Network for Bioactivity Prediction in Structure-based Drug Discovery

Beyond graph energy: norms of graphs and matrices

On the solvability of the discrete conductivity and Schrödinger inverse problems

Active Learning from Weak and Strong Labelers

A survey of discrete methods in (algebraic) statistics for networks

Earth Mover’s Distance Yields Positive Definite Kernels For Certain Ground Distances

p-Markov Gaussian Processes for Scalable and Expressive Online Bayesian Nonparametric Time Series Forecasting

Gelisp: A Library to Represent Musical CSPs and Search Strategies

On the Complexity of Inner Product Similarity Join

Human languages order information efficiently

The cone percolation model on spherically symmetric trees and its variations

Universal portfolios in stochastic portfolio theory

Avoiding fractional powers over the natural numbers