OpenRaiser/Intern-Atlas huggingface dataset:
Practical Batch Bayesian Optimization for Less Expensive Functions
Venue: arXiv cs.LG 2018
Year: 2018

Bayesian optimization (BO) and its batch extensions are successful for optimizing expensive black-box functions. However, these traditional BO approaches are not yet ideal for optimizing less expensive functions when the computational cost of BO can dominate the cost of evaluating the blackbox function. Examples of these less expensive functions are cheap machine learning models, inexpensive physical experiment through simulators, and acquisition function optimization in Bayesian optimization. In this paper, we consider a batch BO setting for situations where function evaluations are less expensive. Our model is based on a new exploration strategy using geometric distance that provides an alternative way for exploration, selecting a point far from the observed locations. Using that intuition, we propose to use Sobol sequence to guide exploration that will get rid of running multiple global optimization steps as used in previous works. Based on the proposed distance exploration, we present an efficient batch BO approach. We demonstrate that our approach outperforms other baselines and global optimization methods when the function evaluations are less expensive.
Stochastic Modified Equations and Dynamics of Stochastic Gradient Algorithms I: Mathematical Foundations
Venue: arXiv cs.LG 2018
Year: 2018

We develop the mathematical foundations of the stochastic modified equations (SME) framework for analyzing the dynamics of stochastic gradient algorithms, where the latter is approximated by a class of stochastic differential equations with small noise parameters. We prove that this approximation can be understood mathematically as an weak approximation, which leads to a number of precise and useful results on the approximations of stochastic gradient descent (SGD), momentum SGD and stochastic Nesterov's accelerated gradient method in the general setting of stochastic objectives. We also demonstrate through explicit calculations that this continuous-time approach can uncover important analytical insights into the stochastic gradient algorithms under consideration that may not be easy to obtain in a purely discrete-time setting.
Parallel training of linear models without compromising convergence
Venue: arXiv cs.LG 2018
Year: 2018

In this paper we analyze, evaluate, and improve the performance of training generalized linear models on modern CPUs. We start with a state-of-the-art asynchronous parallel training algorithm, identify system-level performance bottlenecks, and apply optimizations that improve data parallelism, cache line locality, and cache line prefetching of the algorithm. These modifications reduce the per-epoch run-time significantly, but take a toll on algorithm convergence in terms of the required number of epochs. To alleviate these shortcomings of our systems-optimized version, we propose a novel, dynamic data partitioning scheme across threads which allows us to approach the convergence of the sequential version. The combined set of optimizations result in a consistent bottom line speedup in convergence of up to 12x compared to the initial asynchronous parallel training algorithm and up to 42x, compared to state of the art implementations (scikit-learn and h2o) on a range of multi-core CPU architectures.
Task Embedded Coordinate Update: A Realizable Framework for Multivariate Non-convex Optimization
Venue: arXiv cs.LG 2018
Year: 2018

We in this paper propose a realizable framework TECU, which embeds task-specific strategies into update schemes of coordinate descent, for optimizing multivariate non-convex problems with coupled objective functions. On one hand, TECU is capable of improving algorithm efficiencies through embedding productive numerical algorithms, for optimizing univariate sub-problems with nice properties. From the other side, it also augments probabilities to receive desired results, by embedding advanced techniques in optimizations of realistic tasks. Integrating both numerical algorithms and advanced techniques together, TECU is proposed in a unified framework for solving a class of non-convex problems. Although the task embedded strategies bring inaccuracies in sub-problem optimizations, we provide a realizable criterion to control the errors, meanwhile, to ensure robust performances with rigid theoretical analyses. By respectively embedding ADMM and a residual-type CNN in our algorithm framework, the experimental results verify both efficiency and effectiveness of embedding task-oriented strategies in coordinate descent for solving practical problems.
Putting the Agents back in the Domain: A Two-Sorted Term-Modal Logic
Venue: arXiv cs.LO 2018
Year: 2018

In the present paper syntax and semantics will be presented for an expansion of ordinary n-agent QML with constant domain, non-rigid constants, rigid variables and including both functions, relations, and equality. Further, the number of agents will be specified axiomatically thus ensuring maximal flexibility wrt. the cardinality of the set of agents. Domain, variables, and constants will be partitioned in an agent-part and an object-part and the syntax will be expanded to include strings in which indexes of modal operators are quantified over as wff's of the language. This will enhance expressiveness regarding the epistemic status of agents. Such a term-modal version of the logic K is shown to be sound and complete wrt. the class of (appropriate) frames, and a term-version of S4 is shown to be sound and complete wrt. the class of (appropriate) frames in which the relations are transitive. It should be noted that completeness is shown via the framework of canonical models and thus allows for non-complicated generalizations to other logics than the term-versions of K and S4.
Semi-Semantic Line-Cluster Assisted Monocular SLAM for Indoor Environments
Venue: arXiv cs.CV 2018
Year: 2018

This paper presents a novel method to reduce the scale drift for indoor monocular simultaneous localization and mapping (SLAM). We leverage the prior knowledge that in the indoor environment, the line segments form tight clusters, e.g. many door frames in a straight corridor are of the same shape, size and orientation, so the same edges of these door frames form a tight line segment cluster. We implement our method in the popular ORB-SLAM2, which also serves as our baseline. In the front end we detect the line segments in each frame and incrementally cluster them in the 3D space. In the back end, we optimize the map imposing the constraint that the line segments of the same cluster should be the same. Experimental results show that our proposed method successfully reduces the scale drift for indoor monocular SLAM.
Matrix Completion With Variational Graph Autoencoders: Application in Hyperlocal Air Quality Inference
Venue: arXiv cs.LG 2018
Year: 2018

Inferring air quality from a limited number of observations is an essential task for monitoring and controlling air pollution. Existing inference methods typically use low spatial resolution data collected by fixed monitoring stations and infer the concentration of air pollutants using additional types of data, e.g., meteorological and traffic information. In this work, we focus on street-level air quality inference by utilizing data collected by mobile stations. We formulate air quality inference in this setting as a graph-based matrix completion problem and propose a novel variational model based on graph convolutional autoencoders. Our model captures effectively the spatio-temporal correlation of the measurements and does not depend on the availability of additional information apart from the street-network topology. Experiments on a real air quality dataset, collected with mobile stations, shows that the proposed model outperforms state-of-the-art approaches.
Fast and exact analysis for LRU caches
Venue: arXiv cs.PL 2018
Year: 2018

For applications in worst-case execution time analysis and in security, it is desirable to statically classify memory accesses into those that result in cache hits, and those that result in cache misses. Among cache replacement policies, the least recently used (LRU) policy has been studied the most and is considered to be the most predictable. The state-of-the-art in LRU cache analysis presents a tradeoff between precision and analysis efficiency: The classical approach to analyzing programs running on LRU caches, an abstract interpretation based on a range abstraction, is very fast but can be imprecise. An exact analysis was recently presented, but, as a last resort, it calls a model checker, which is expensive. In this paper, we develop an analysis based on abstract interpretation that comes close to the efficiency of the classical approach, while achieving exact classification of all memory accesses as the model-checking approach. Compared with the model-checking approach we observe speedups of several orders of magnitude. As a secondary contribution we show that LRU cache analysis problems are in general NP-complete.
The External Interface for Extending WASP
Venue: arXiv cs.LO 2018
Year: 2018

Answer set programming (ASP) is a successful declarative formalism for knowledge representation and reasoning. The evaluation of ASP programs is nowadays based on the Conflict-Driven Clause Learning (CDCL) backtracking search algorithm. Recent work suggested that the performance of CDCL-based implementations can be considerably improved on specific benchmarks by extending their solving capabilities with custom heuristics and propagators. However, embedding such algorithms into existing systems requires expert knowledge of the internals of ASP implementations. The development of effective solver extensions can be made easier by providing suitable programming interfaces. In this paper, we present the interface for extending the CDCL-based ASP solver WASP. The interface is both general, i.e. it can be used for providing either new branching heuristics and propagators, and external, i.e. the implementation of new algorithms requires no internal modifications of WASP. Moreover, we review the applications of the interface witnessing it can be successfully used to extend WASP for solving effectively hard instances of both real-world and synthetic problems. Under consideration in Theory and Practice of Logic Programming (TPLP).
A sensitivity analysis of research institutions' productivity rankings to the time of citation observation
Venue: arXiv cs.DL 2018
Year: 2018

One of the critical issues in bibliometric research assessments is the time required to achieve maturity in citations. Citation counts can be considered a reliable proxy of the real impact of a work only if they are observed after sufficient time has passed from publication date. In the present work the authors investigate the effect of varying the time of citation observation on accuracy of productivity rankings for research institutions. Research productivity measures are calculated for all Italian universities active in the hard sciences in the 2001-2003 period, by individual field and discipline, with the time of the citation observation varying from 2004 to 2008. The objective is to support policy-makers in choosing a citation window that optimizes the tradeoff between accuracy of rankings and timeliness of the exercise.
Combining Subgoal Graphs with Reinforcement Learning to Build a Rational Pathfinder
Venue: arXiv cs.AI 2018
Year: 2018

In this paper, we present a hierarchical path planning framework called SG-RL (subgoal graphs-reinforcement learning), to plan rational paths for agents maneuvering in continuous and uncertain environments. By "rational", we mean (1) efficient path planning to eliminate first-move lags; (2) collision-free and smooth for agents with kinematic constraints satisfied. SG-RL works in a two-level manner. At the first level, SG-RL uses a geometric path-planning method, i.e., Simple Subgoal Graphs (SSG), to efficiently find optimal abstract paths, also called subgoal sequences. At the second level, SG-RL uses an RL method, i.e., Least-Squares Policy Iteration (LSPI), to learn near-optimal motion-planning policies which can generate kinematically feasible and collision-free trajectories between adjacent subgoals. The first advantage of the proposed method is that SSG can solve the limitations of sparse reward and local minima trap for RL agents; thus, LSPI can be used to generate paths in complex environments. The second advantage is that, when the environment changes slightly (i.e., unexpected obstacles appearing), SG-RL does not need to reconstruct subgoal graphs and replan subgoal sequences using SSG, since LSPI can deal with uncertainties by exploiting its generalization ability to handle changes in environments. Simulation experiments in representative scenarios demonstrate that, compared with existing methods, SG-RL can work well on large-scale maps with relatively low action-switching frequencies and shorter path lengths, and SG-RL can deal with small changes in environments. We further demonstrate that the design of reward functions and the types of training environments are important factors for learning feasible policies.
Word Mover's Embedding: From Word2Vec to Document Embedding
Venue: arXiv cs.CL 2018
Year: 2018

While the celebrated Word2Vec technique yields semantically rich representations for individual words, there has been relatively less success in extending to generate unsupervised sentences or documents embeddings. Recent work has demonstrated that a distance measure between documents called \emph{Word Mover's Distance} (WMD) that aligns semantically similar words, yields unprecedented KNN classification accuracy. However, WMD is expensive to compute, and it is hard to extend its use beyond a KNN classifier. In this paper, we propose the \emph{Word Mover's Embedding } (WME), a novel approach to building an unsupervised document (sentence) embedding from pre-trained word embeddings. In our experiments on 9 benchmark text classification datasets and 22 textual similarity tasks, the proposed technique consistently matches or outperforms state-of-the-art techniques, with significantly higher accuracy on problems of short length.
Transductive Learning with String Kernels for Cross-Domain Text Classification
Venue: arXiv cs.CL 2018
Year: 2018

For many text classification tasks, there is a major problem posed by the lack of labeled data in a target domain. Although classifiers for a target domain can be trained on labeled text data from a related source domain, the accuracy of such classifiers is usually lower in the cross-domain setting. Recently, string kernels have obtained state-of-the-art results in various text classification tasks such as native language identification or automatic essay scoring. Moreover, classifiers based on string kernels have been found to be robust to the distribution gap between different domains. In this paper, we formally describe an algorithm composed of two simple yet effective transductive learning approaches to further improve the results of string kernels in cross-domain settings. By adapting string kernels to the test set without using the ground-truth test labels, we report significantly better accuracy rates in cross-domain English polarity classification.
Network Slicing with Mobile Edge Computing for Micro-Operator Networks in Beyond 5G
Venue: arXiv cs.IT 2018
Year: 2018

We model the scenarios of network slicing allocation for the micro-operator (MO) network. The MO creates the slices "as a service" of wireless resource and then allocates these slices to multiple mobile network operators (MNOs). We propose the slice allocation problem of multiple MNOs with the goal of maximizing the social welfare of the network defined as sum rate of all MNOs. The many-to-one matching game framework is adopted to solve this problem. Then, the generic Markov Chain Monte Carlo (MCMC) method is introduced for the computation of game theoretical solution. After the MNOs obtain the slices, for each small cell base station (SBS), we investigate the role of power allocation using Q-learning and uniform power. We numerically show that the solution of the matching game leads to two-sided stable matching. Furthermore, for each MNO, we explore the problem of infrastructure cost minimization constrained on the latency at the user equipment (UE). The optimal solution is given by a greedy fractional knapsack algorithm. We illustrate that it is sufficient for the MNO to use a small fraction of the SBS to serve the UE while satisfying the latency constraint. For the problem of overall data rate maximization, we numerically show that the power allocation has significant effect on the social welfare of the system.
Unique Information and Secret Key Agreement
Venue: arXiv cs.IT 2018
Year: 2018

The partial information decomposition (PID) is a promising framework for decomposing a joint random variable into the amount of influence each source variable Xi has on a target variable Y, relative to the other sources. For two sources, influence breaks down into the information that both X0 and X1 redundantly share with Y, what X0 uniquely shares with Y, what X1 uniquely shares with Y, and finally what X0 and X1 synergistically share with Y. Unfortunately, considerable disagreement has arisen as to how these four components should be quantified. Drawing from cryptography, we consider the secret key agreement rate as an operational method of quantifying unique informations. Secret key agreement rate comes in several forms, depending upon which parties are permitted to communicate. We demonstrate that three of these four forms are inconsistent with the PID. The remaining form implies certain interpretations as to the PID's meaning---interpretations not present in PID's definition but that, we argue, need to be explicit. These reveal an inconsistency between third-order connected information, two-way secret key agreement rate, and synergy. Similar difficulties arise with a popular PID measure in light the results here as well as from a maximum entropy viewpoint. We close by reviewing the challenges facing the PID.
Evaluating research: from informed peer review to bibliometrics
Venue: arXiv cs.DL 2018
Year: 2018

National research assessment exercises are becoming regular events in ever more countries. The present work contrasts the peer-review and bibliometrics approaches in the conduct of these exercises. The comparison is conducted in terms of the essential parameters of any measurement system: accuracy, robustness, validity, functionality, time and costs. Empirical evidence shows that for the natural and formal sciences, the bibliometric methodology is by far preferable to peer-review. Setting up national databases of publications by individual authors, derived from Web of Science or Scopus databases, would allow much better, cheaper and more frequent national research assessments.
Top-Down Transaction-Level Design with TL-Verilog
Venue: arXiv cs.AR 2018
Year: 2018

Transaction-Level Verilog (TL-Verilog) is an emerging extension to SystemVerilog that supports a new design methodology, called transaction-level design. A transaction, in this methodology, is an entity that moves through structures like pipelines, arbiters, and queues, A transaction might be a machine instruction, a flit of a packet, or a memory read/write. Transaction logic, like packet header decode or instruction execution, that operates on the transaction can be placed anywhere along the transaction's flow. Tools produce the logic to carry signals through their flows to stitch the transaction logic. We implemented a small library of TL-Verilog flow components, and we illustrate the use of these components in a top-down design methodology. We construct a hypothetical microarchitecture simply by instantiating components. Within the flows created by these components, we add combinational transaction logic, enabling verification activities and performance evaluation to begin. We then refine the model by positioning the transaction logic within its flow to produce a high-quality register-transfer-level (RTL) implementation.
National-scale research performance assessment at the individual level
Venue: arXiv cs.DL 2018
Year: 2018

There is an evident and rapid trend towards the adoption of evaluation exercises for national research systems for purposes, among others, of improving allocative efficiency in public funding of individual institutions. However the desired macroeconomic aims could be compromised if internal redistribution of government resources within each research institution does not follow a consistent logic: the intended effects of national evaluation systems can result only if a "funds for quality" rule is followed at all levels of decision-making. The objective of this study is to propose a bibliometric methodology for: i) large-scale comparative evaluation of research performance by individual scientists, research groups and departments within research institution, to inform selective funding allocations, and ii) assessment of strengths and weaknesses by field of research, to inform strategic planning and control. The proposed methodology has been applied to the hard science disciplines of the Italian university research system for the period 2004-2006.
Deriving item features relevance from collaborative domain knowledge
Venue: arXiv cs.IR 2018
Year: 2018

An Item based recommender system works by computing a similarity between items, which can exploit past user interactions (collaborative filtering) or item features (content based filtering). Collaborative algorithms have been proven to achieve better recommendation quality then content based algorithms in a variety of scenarios, being more effective in modeling user behaviour. However, they can not be applied when items have no interactions at all, i.e. cold start items. Content based algorithms, which are applicable to cold start items, often require a lot of feature engineering in order to generate useful recommendations. This issue is specifically relevant as the content descriptors become large and heterogeneous. The focus of this paper is on how to use a collaborative models domain-specific knowledge to build a wrapper feature weighting method which embeds collaborative knowledge in a content based algorithm. We present a comparative study for different state of the art algorithms and present a more general model. This machine learning approach to feature weighting shows promising results and high flexibility.