bluuebunny/crossref_metadata_2025 huggingface dataset:
Better and Faster: Knowledge Transfer from Multiple Self-supervised Learning Tasks via Graph Distillation for Video Classification
Authors: Zhang Chenrui , Peng Yuxin
Published: July 2018

Video representation learning is a vital problem for

classification task. Recently, a promising unsupervised

paradigm termed self-supervised learning

has emerged, which explores inherent supervisory

signals implied in massive data for feature learning

via solving auxiliary tasks. However, existing

methods in this regard suffer from two limitations

when extended to video classification. First, they

focus only on a single task, whereas ignoring complementarity

among different task-specific features

and thus resulting in suboptimal video representation.

Second, high computational and memory cost

hinders their application in real-world scenarios. In

this paper, we propose a graph-based distillation

framework to address these problems: (1) We propose

logits graph and representation graph to transfer

knowledge from multiple self-supervised tasks,

where the former distills classifier-level knowledge

by solving a multi-distribution joint matching problem,

and the latter distills internal feature knowledge

from pairwise ensembled representations with

tackling the challenge of heterogeneity among different

features; (2) The proposal that adopts a

teacher-student framework can reduce the redundancy

of knowledge learned from teachers dramatically,

leading to a lighter student model that solves

classification task more efficiently. Experimental

results on 3 video datasets validate that our proposal

not only helps learn better video representation

but also compress model for faster inference.
An Analytical and Experimental Comparison of Maximal Lottery Schemes
Authors: Brandl Florian , Brandt Felix , Stricker Christian
Published: July 2018

Randomized voting rules are gaining increasing attention in computational and non-computational social choice. A particularly interesting class of such rules are maximal lottery (ML) schemes, which were proposed by Peter Fishburn in 1984 and have been repeatedly recommended for practical use. However, the subtle differences between different ML schemes are often ignored. Two canonical subsets of ML schemes are C1-ML schemes (which only depend on unweighted majority comparisons) and C2-ML schemes (which only depend on weighted majority comparisons). We prove that C2-ML schemes are the only Pareto efficient---but also among the most manipulable---ML schemes. Furthermore, we evaluate the frequency of manipulable preference profiles and the degree of randomization of ML schemes via extensive computer simulations. In general, ML schemes are rarely manipulable and often do not randomize at all, especially when there are only few alternatives. For up to 21 alternatives, the average support size of ML schemes lies below 4 under reasonable assumptions. The average degree of randomization (in terms of Shannon entropy) of C2-ML schemes is significantly lower than that of C1-ML schemes.
Layered Optical Flow Estimation Using a Deep Neural Network with a Soft Mask
Authors: Zhang Xi , Ma Di , Ouyang Xu , Jiang Shanshan , Gan Lin , Agam Gady
Published: July 2018

Using a layered representation for motion estimation has the advantage of being able to cope with discontinuities and occlusions. In this paper, we learn to estimate optical flow by combining a layered motion representation with deep learning. Instead of pre-segmenting the image to layers, the proposed approach automatically generates a layered representation of optical flow using the proposed soft-mask module. The essential components of the soft-mask module are maxout and fuse operations, which enable a disjoint layered representation of optical flow and more accurate flow estimation. We show that by using masks the motion estimate results in a quadratic function of input features in the output layer. The proposed soft-mask module can be added to any existing optical flow estimation networks by replacing their flow output layer. In this work, we use FlowNet as the base network to which we add the soft-mask module. The resulting network is tested on three well-known benchmarks with both supervised and unsupervised flow estimation tasks. Evaluation results show that the proposed network achieve better results compared with the original FlowNet.
3D-Aided Deep Pose-Invariant Face Recognition
Authors: Zhao Jian , Xiong Lin , Cheng Yu , Cheng Yi , Li Jianshu , Zhou Li , Xu Yan , Karlekar Jayashree , Pranata Sugiri , Shen Shengmei , Xing Junliang , Yan Shuicheng , Feng Jiashi
Published: July 2018

Learning from synthetic faces, though perhaps appealing for high data efficiency, may not bring satisfactory performance due to the distribution discrepancy of the synthetic and real face images. To mitigate this gap, we propose a 3D-Aided Deep Pose-Invariant Face Recognition Model (3D-PIM), which automatically recovers realistic frontal faces from arbitrary poses through a 3D face model in a novel way. Specifically, 3D-PIM incorporates a simulator with the aid of a 3D Morphable Model (3D MM) to obtain shape and appearance prior for accelerating face normalization learning, requiring less training data. It further leverages a global-local Generative Adversarial Network (GAN) with multiple critical improvements as a refiner to enhance the realism of both global structures and local details of the face simulator’s output using unlabelled real data only, while preserving the identity information. Qualitative and quantitative experiments on both controlled and in-the-wild benchmarks clearly demonstrate superiority of the proposed model over state-of-the-arts.
Learning Robust Gaussian Process Regression for Visual Tracking
Authors: Zheng Linyu , Tang Ming , Wang Jinqiao
Published: July 2018

Recent developments of Correlation Filter based trackers (CF trackers) have attracted much attention because of their top performance. However, the boundary effect imposed by the basic periodic assumption in their fast optimization seriously degrades the performance of CF trackers. Although there existed many recent works to relax the boundary effect in CF trackers, the cost was that they can not utilize the kernel trick to improve the accuracy further. In this paper, we propose a novel Gaussian Process Regression based tracker (GPRT) which is a conceptually natural tracking approach. Compared to all the existing CF trackers, the boundary effect is eliminated thoroughly and the kernel trick can be employed in our GPRT. In addition, we present two efficient and effective update methods for our GPRT. Experiments are performed on two public datasets: OTB-2013 and OTB-2015. Without bells and whistles, on these two datasets, our GPRT obtains 84.1% and 79.2% in mean overlap precision, respectively, outperforming all the existing trackers with hand-crafted features.
A Framework for Constraint Based Local Search using Essence
Authors: Akgün Özgür , Attieh Saad , Gent Ian P. , Jefferson Christopher , Miguel Ian , Nightingale Peter , Salamon András Z. , Spracklen Patrick , Wetter James
Published: July 2018

Structured Neighbourhood Search (SNS) is a framework for constraint-based local search for problems expressed in the Essence abstract constraint specification language.  The local search explores a structured neighbourhood, where each state in the neighbourhood preserves a high level structural feature of the problem. SNS derives  highly structured problem-specific neighbourhoods automatically and directly from the features of the Essence specification of the problem. Hence, neighbourhoods can represent important structural features of the problem, such as partitions of sets, even if that structure is obscured in the low-level input format required by a constraint solver.  SNS expresses each neighbourhood as a constrained optimisation problem, which is solved with a constraint solver. We have implemented SNS, together with automatic generation of neighbourhoods for high level structures, and report high quality results for several optimisation problems.
Descriptive Clustering: ILP and CP Formulations with Applications
Authors: Dao Thi-Bich-Hanh , Kuo Chia-Tung , Ravi S. S. , Vrain Christel , Davidson Ian
Published: July 2018

In many settings just finding a good clustering is insufficient and

an explanation of the clustering is required. If the features used

to perform the clustering are interpretable then methods such as

conceptual clustering can be used. However, in many applications

this is not the case particularly for image, graph and other complex

data. Here we explore the setting where a set of interpretable

discrete tags for each instance is available. We formulate the

descriptive clustering problem as a bi-objective optimization

to simultaneously find compact clusters using the features and to

describe them using the tags. We present our formulation in a

declarative platform and show it can be integrated into a standard

iterative algorithm to find all Pareto optimal solutions to the two

objectives. Preliminary results demonstrate the utility of our

approach on real data sets for images and electronic health care

records and that it outperforms single objective and multi-view clustering

baselines.
Combinatorial Auctions via Machine Learning-based Preference Elicitation
Authors: Brero Gianluca , Lubin Benjamin , Seuken Sven
Published: July 2018

Combinatorial auctions (CAs) are used to allocate multiple items among bidders with complex valuations. Since the value space grows exponentially in the number of items, it is impossible for bidders to report their full value function even in medium-sized settings. Prior work has shown that current designs often fail to elicit the most relevant values of the bidders, thus leading to inefficiencies. We address this problem by introducing a machine learning-based elicitation algorithm to identify which values to query from the bidders. Based on this elicitation paradigm we design a new CA mechanism we call PVM, where payments are determined so that bidders’ incentives are aligned with allocative efficiency. We validate PVM experimentally in several spectrum auction domains, and we show that it achieves high allocative efficiency even when only few values are elicited from the bidders.
Compact-MDD: Efficiently Filtering (s)MDD Constraints with Reversible Sparse Bit-sets
Authors: Verhaeghe Hélène , Lecoutre Christophe , Schaus Pierre
Published: July 2018

Multi-Valued Decision Diagrams (MDDs) are instrumental in modeling combinatorial problems with Constraint Programming.In this paper, we propose a related data structure called sMDD (semi-MDD) where the central layer of the diagrams is non-deterministic.We show that it is easy and efficient to transform any table (set of tuples) into an sMDD.We also introduce a new filtering algorithm, called Compact-MDD, which is based on bitwise operations, and can be applied to both MDDs and sMDDs.Our experimental results show the practical interest of our approach, both in terms of compression and filtering speed.
Model-free, Model-based, and General Intelligence
Authors: Geffner Hector
Published: July 2018

During the 60s and 70s, AI researchers explored intuitions about intelligence by writing programs that displayed intelligent behavior. Many good ideas came out from this work but programs written by hand were not robust or general. After the 80s, research increasingly shifted to the development of learners capable of inferring behavior and functions from experience and data, and solvers capable of tackling well-defined but intractable models like SAT, classical planning, Bayesian networks, and POMDPs. The learning approach has achieved considerable success but results in black boxes that do not have the flexibility, transparency, and generality of their model-based counterparts. Model-based approaches, on the other hand, require models and scalable algorithms. Model-free learners and model-based solvers have indeed close parallels with Systems 1 and 2 in current theories of the human mind: the first, a fast, opaque, and inflexible intuitive mind; the second, a slow, transparent, and flexible analytical mind. In this paper, I review developments in AI and draw on these theories to discuss the gap between model-free learners and model-based solvers, a gap that needs to be bridged in order to have intelligent systems that are robust and general.
Neural Networks for Predicting Algorithm Runtime Distributions
Authors: Eggensperger Katharina , Lindauer Marius , Hutter Frank
Published: July 2018

Many state-of-the-art algorithms for solving hard combinatorial problems in artificial intelligence (AI) include elements of stochasticity that lead to high variations in runtime, even for a fixed problem instance. Knowledge about the resulting runtime distributions (RTDs) of algorithms on given problem instances can be exploited in various meta-algorithmic procedures, such as algorithm selection, portfolios, and randomized restarts. Previous work has shown that machine learning can be used to individually predict mean, median and variance of RTDs. To establish a new state-of-the-art in predicting RTDs, we demonstrate that the parameters of an RTD should be learned jointly and that neural networks can do this well by directly optimizing the likelihood of an RTD given runtime observations. In an empirical study involving five algorithms for SAT solving and AI planning, we show that neural networks predict the true RTDs of unseen instances better than

previous methods, and can even do so when only few runtime observations are available per training instance.
A Fast Algorithm for Optimally Finding Partially Disjoint Shortest Paths
Authors: Guo Longkun , Deng Yunyun , Liao Kewen , He Qiang , Sellis Timos , Hu Zheshan
Published: July 2018

The classical disjoint shortest path problem has recently recalled

interests from researchers in the network planning and optimization

community. However, the requirement of the shortest paths being completely

vertex or edge disjoint might be too restrictive and demands much

more resources in a network. Partially disjoint shortest paths, in

which a bounded number of shared vertices or edges is allowed, balance

between degree of disjointness and occupied network resources.

In this paper, we consider the problem of finding k

shortest paths which are edge disjoint but partially vertex disjoint.

For a pair of distinct vertices in a network graph, the problem aims

to optimally find k edge disjoint shortest paths among which

at most a bounded number of vertices are shared by at least two paths. In particular,

we present novel techniques for exactly solving the problem

with a runtime that significantly improves

the current best result. The

proposed algorithm is also validated by computer experiments on both

synthetic and real networks which demonstrate its superior efficiency

of up to three orders of magnitude faster than the state of the art.
Sequence Selection by Pareto Optimization
Authors: Qian Chao , Feng Chao , Tang Ke
Published: July 2018

The problem of selecting a sequence of items from a universe that maximizes some given objective function arises in many real-world applications. In this paper, we propose an anytime randomized iterative approach POSeqSel, which maximizes the given objective function and minimizes the sequence length simultaneously. We prove that for any previously studied objective function, POSeqSel using a reasonable time can always reach or improve the best known approximation guarantee. Empirical results exhibit the superior performance of POSeqSel.
Master-Slave Curriculum Design for Reinforcement Learning
Authors: Wu Yuechen , Zhang Wei , Song Ke
Published: July 2018

Curriculum learning is often introduced as a leverage to improve the agent training for complex tasks, where the goal is to generate a sequence of easier subasks for an agent to train on, such that final performance or learning speed is improved. However, conventional curriculum is mainly designed for one agent with fixed action space and sequential simple-to-hard training manner. Instead, we present a novel curriculum learning strategy by introducing the concept of master-slave agents and enabling flexible action setting for agent training. Multiple agents, referred as master agent for the target task and slave agents for the subtasks, are trained concurrently within different action spaces by sharing a perception network with an asynchronous strategy. Extensive evaluation on the VizDoom platform demonstrates the joint learning of master agent and slave agents mutually benefit each other. Significant improvement is obtained over A3C in terms of learning speed and performance.
A Novel Strategy for Active Task Assignment in Crowd Labeling
Authors: Hu Zehong , Zhang Jie
Published: July 2018

Active learning strategies are often used in crowd labeling to improve task assignment. However, these strategies require prohibitive computation time yet still cannot improve the assignment to the utmost, because they simply evaluate each possible assignment and then greedily select the optimal one. In this paper, we first derive an efficient algorithm for assignment evaluation. Then, to overcome the uncertainty of labels, we develop a novel strategy that modulates the scope of the greedy task assignment with posterior uncertainty and keeps the evaluation optimistic. The experiments on two popular worker models and four MTurk datasets show that our strategy achieves the best performance and highest computation efficiency.
Deep Learning Based Multi-modal Addressee Recognition in Visual Scenes with Utterances
Authors: Le Minh Thao , Shimizu Nobuyuki , Miyazaki Takashi , Shinoda Koichi
Published: July 2018

With the widespread use of intelligent systems, such as smart speakers, addressee recognition has become a concern in human-computer interaction, as more and more people expect such systems to understand complicated social scenes, including those outdoors, in cafeterias, and hospitals. Because previous studies typically focused only on pre-specified tasks with limited conversational situations such as controlling smart homes, we created a mock dataset called Addressee Recognition in Visual Scenes with Utterances (ARVSU) that contains a vast body of image variations in visual scenes with an annotated utterance and a corresponding addressee for each scenario. We also propose a multi-modal deep-learning-based model that takes different human cues, specifically eye gazes and transcripts of an utterance corpus, into account to predict the conversational addressee from a specific speaker's view in various real-life conversational scenarios. To the best of our knowledge, we are the first to introduce an end-to-end deep learning model that combines vision and transcripts of utterance for addressee recognition. As a result, our study suggests that future addressee recognition can reach the ability to understand human intention in many social situations previously unexplored, and our modality dataset is a first step in promoting research in this field.
Enhancing Existential Rules by Closed-World Variables
Authors: Amendola Giovanni , Leone Nicola , Manna Marco , Veltri Pierfrancesco
Published: July 2018

Existential rules generalize Datalog with existential quantification in the head. Natively, Datalog is interpreted under a closed-world semantics, while existential rules typically employ the open-world assumption. The interpretation domain in the latter case is enlarged by infinitely many "anonymous" individuals. Then, in any rule, each variable ranges over all individuals, even if not needed or required. In this paper, we enhance existential rules by closed-world variables to consciously reason on the properties of "known" (non-anonymous) and arbitrary individuals in different ways. Accordingly, we uniformly generalize the basic classes of existential rules that ensure decidability of ontology-based query answering. For them, after observing that decidability is preserved, we prove that a strict increase in expressiveness is gained, and in most cases the computational complexity is not altered.
Inconsistency-Tolerant Ontology-Based Data Access Revisited: Taking Mappings into Account
Authors: Bienvenu Meghyn
Published: July 2018

Inconsistency-tolerant query answering in the presence of ontologies has received considerable attention in recent years. However, existing work assumes that the data is expressed using the vocabulary of the ontology and is therefore not directly applicable to ontology-based data access (OBDA), where relational data is connected to the ontology via mappings. This motivates us to revisit existing results in the wider context of OBDA with mappings. After formalizing the problem, we perform a detailed analysis of the data complexity of inconsistency-tolerant OBDA for ontologies formulated in DL-Lite and other data-tractable description logics, considering three different semantics (AR, IAR, and brave), two notions of repairs (subset and symmetric difference), and two classes of global-as-view (GAV) mappings. We show that adding plain GAV mappings does not affect data complexity, but there is a jump in complexity if mappings with negated atoms are considered.
Actual Causality in a Logical Setting
Authors: Bochman Alexander
Published: July 2018

We provide a definition of actual causation in the logical framework of the causal calculus, which is based on a causal version of the well-known NESS (or INUS) condition. We compare our definition with other, mainly counterfactual, approaches on standard examples. On the way, we explore general capabilities of the logical representation for structural equation models of causation and beyond.
A Study of Argumentative Characterisations of Preferred Subtheories
Authors: D'Agostino Marcello , Modgil Sanjay
Published: July 2018

Classical logic argumentation (Cl-Arg) under the

stable semantics yields argumentative characterisations

of non-monotonic inference in Preferred Subtheories.

This paper studies these characterisations

under both the standard approach to Cl-Arg, and a

recent dialectical approach that is provably rational

under resource bounds. Two key contributions are

made. Firstly, the preferred extensions are shown

to coincide with the stable extensions. This means

that algorithms and proof theories for the admissible

semantics can now be used to decide credulous

inference in Preferred Subtheories. Secondly, we

show that as compared with the standard approach,

the grounded semantics applied to the dialectical

approach more closely approximates sceptical inference

in Preferred Subtheories.
An Empirical Study of Knowledge Tradeoffs in Case-Based Reasoning
Authors: Ganesan Devi , Chakraborti Sutanu
Published: July 2018

Case-Based Reasoning provides a framework for integrating domain knowledge with data in the form of four knowledge containers namely Case base, Vocabulary, Similarity and Adaptation. It is a known fact in Case-Based Reasoning community that knowledge can be interchanged between the containers. However, the explicit interplay between them, and how this interchange is affected by the knowledge richness of the underlying domain is not yet fully understood. We attempt to bridge this gap by proposing footprint size reduction as a measure for quantifying knowledge tradeoffs between containers. The proposed measure is empirically evaluated on synthetic as well as real world datasets. From a practical standpoint, footprint size reduction provides a unified way of estimating the impact of a given piece of knowledge in any knowledge container, and can also suggest ways of characterizing the nature of domains ranging from ill-defined to well-defined ones. Our study also makes evident the need for maintenance approaches that go beyond case base and competence to include other containers and performance objectives.
Possibilistic ASP Base Revision by Certain Input
Authors: Garcia Laurent , Lefèvre Claire , Papini Odile , Stéphan Igor , Würbel Eric
Published: July 2018

Belief base revision has been studied within the answer set programming framework. We go a step further by introducing uncertainty and studying belief base revision when beliefs are represented by possibilistic logic programs under possibilistic answer set semantics and revised by certain input. The paper proposes two approaches of rule-based revision operators and presents their semantic characterization in terms of possibilistic distribution. This semantic characterization allows for equivalently considering the evolution of syntactic logic programs and the evolution of their semantic content. It then studies the logical properties of the proposed operators and gives complexity results.
Finite Model Reasoning in Hybrid Classes of Existential Rules
Authors: Gottlob Georg , Manna Marco , Pieris Andreas
Published: July 2018

Two paradigmatic restrictions that have been studied for ensuring the decidability of query answering under existential rules are guardedness and stickiness. With the aim of consolidating these restrictions, a flexible condition, called tameness, has been proposed a few years ago, which relies on hybrid reasoning, i.e., a combination of forward and backward procedures. The complexity of query answering under this hybrid class of existential rules is by now well-understood. However, the complexity of finite query answering, i.e., query answering under finite models, has remained an open problem. Closing this problem is the main goal of this work.
Computing Approximate Query Answers over Inconsistent Knowledge Bases
Authors: Greco Sergio , Molinaro Cristian , Trubitsyna Irina
Published: July 2018

Consistent query answering is a principled approach for querying inconsistent knowledge bases. It relies on the notion of a "repair", that is, a maximal consistent subset of the facts in the knowledge base. One drawback of this approach is that entire facts are deleted to resolve inconsistency, even if they may still contain useful "reliable" information.

To overcome this limitation, we propose a new notion of repair allowing values within facts to be updated for restoring consistency. This more fine-grained repair primitive allows us to preserve more information in the knowledge base. We also introduce the notion of a "universal repair", which is a compact representation of all repairs. Then, we show that consistent query answering in our framework is intractable (coNP-complete). In light of this result, we develop a polynomial time approximation algorithm for computing a sound (but possibly incomplete) set of consistent query answers.
Horn-Rewritability vs PTime Query Evaluation in Ontology-Mediated Querying
Authors: Hernich Andre , Lutz Carsten , Papacchini Fabio , Wolter Frank
Published: July 2018

In ontology-mediated querying with an expressive description logic L, two desirable properties of a TBox T are (1) being able to replace T with a TBox formulated in the Horn-fragment of L without affecting the answers to conjunctive queries, and (2) that every conjunctive query can be evaluated in PTime w.r.t. T. We investigate in which cases (1) and (2) are equivalent, finding that the answer depends on whether the unique name assumption (UNA) is made, on the description logic under consideration, and on the nesting depth of quantifiers in the TBox. We also clarify the relationship between query evaluation with and without UNA and consider natural variations of property (1).
Facility Reallocation on the Line
Authors: de Keijzer Bart , Wojtczak Dominik
Published: July 2018

We consider a multi-stage facility reallocation problems on the real line, where a facility is being moved between stages based on the locations reported by n agents. The aim of the reallocation mechanism is to minimize the social cost, i.e., the sum over the total distance between the facility and all agents at all stages, plus the cost incurred for moving the facility. We also study this problem both in the offline setting and online setting. In the offline case the mechanism has full knowledge of the agent locations in all future stages, and in the online setting the mechanism does not know these future locations and must decide the location of the facility on a stage-per-stage basis. For both cases, we derive the optimal mechanism, where for the online setting we show that its competitive ratio is (n+2)/(n+1). As neither of these mechanisms turns out to be strategyproof, we propose another strategyproof mechanism which has a competitive ratio of (n+3)/(n+1) for odd n and (n+4)/n for even n, which we conjecture to be the best possible. We also consider a generalization with multiple facilities and weighted agents, for which we show that the optimum can be computed in polynomial time for a fixed number of facilities.
Abducing Relations in Continuous Spaces
Authors: Sato Taisuke , Inoue Katsumi , Sakama Chiaki
Published: July 2018

We propose a new approach to abduction, i.e., non-deductive inference to find a hypothesis H for an observation O such that H,KB |- O where KB is background knowledge. We reformulate it linear algebraically in vector spaces to abduce ``relations'', not logical  formulas, to realize  approximate but  scalable  abduction that can deal with web-scale knowledge bases.  More specifically we consider the problem of abducing relations for Datalog programs with binary predicates.  We treat two cases, the non-recursive case and the recursive case. In the non-recursive case, given r1(X,Y) and r3(X,Z),  we abduce r2(Y,Z) so that r3(X,Z) <= r1(X,Y)&r2(Y,Z) approximately holds, by computing a matrix R2 that approximately satisfies a matrix equation R3  = min1(R1R2) containing a  nonlinear function min1(x).  Here R1, R2 andR3 encode as adjacency matrix r1(X,Y),  r2(Y,Z) and r3(Y,Z) respectively.  We apply this matrix-based abduction to rule discovery and relation discovery in a  knowledge graph.  The recursive  case is mathematically more  involved and computationally more difficult but solvable by deriving  a recursive matrix equation and  solving it.  We illustrate concrete recursive cases including a transitive closure relation.
Consequence-based Reasoning for Description Logics with Disjunction, Inverse Roles, Number Restrictions, and Nominals
Authors: Tena Cucala David , Cuenca Grau Bernardo , Horrocks Ian
Published: July 2018

We present a consequence-based calculus for concept subsumption and classification in the description logic ALCHOIQ, which extends ALC with role hierarchies, inverse roles, number restrictions, and nominals. By using standard transformations, our calculus extends to SROIQ, which covers all of OWL 2 DL except for datatypes. A key feature of our calculus is its pay-as-you-go behaviour: unlike existing algorithms, our calculus is worst-case optimal for all the well-known proper fragments of ALCHOIQ, albeit not for the full logic.
Causal Inference in Time Series via Supervised Learning
Authors: Chikahara Yoichi , Fujino Akinori
Published: July 2018

Causal inference in time series is an important problem in many fields. Traditional methods use regression models for this problem. The inference accuracies of these methods depend greatly on whether or not the model can be well fitted to the data, and therefore we are required to select an appropriate regression model, which is difficult in practice. This paper proposes a supervised learning framework that utilizes a classifier instead of regression models. We present a feature representation that employs the distance between the conditional distributions given past variable values and show experimentally that the feature representation provides sufficiently different feature vectors for time series with different causal relationships. Furthermore, we extend our framework to multivariate time series and present experimental results where our method outperformed the model-based methods and the supervised learning method for i.i.d. data.
Counterexample-Guided Data Augmentation
Authors: Dreossi Tommaso , Ghosh Shromona , Yue Xiangyu , Keutzer Kurt , Sangiovanni-Vincentelli Alberto , Seshia Sanjit A.
Published: July 2018

We present a novel framework for augmenting data sets for

machine learning based on counterexamples. Counterexamples

are misclassified examples that have

important properties for retraining and improving the model.

Key components of our framework include a \textit{counterexample generator},

which produces data items that are misclassified by the model and

error tables, a novel data

structure that stores information pertaining to misclassifications.

Error tables can be used to explain the model's

vulnerabilities and are used to efficiently generate counterexamples for augmentation.

We show the efficacy of the proposed framework by comparing it

to classical augmentation techniques on a case study of object detection in autonomous

driving based on deep neural networks.
Quantum Divide-and-Conquer Anchoring for Separable Non-negative Matrix Factorization
Authors: Du Yuxuan , Liu Tongliang , Li Yinan , Duan Runyao , Tao Dacheng
Published: July 2018

It is NP-complete to find non-negative factors W and H with fixed rank r from a non-negative matrix X by minimizing ||X-WH^Τ ||^2. Although the separability assumption (all data points are in the conical hull of the extreme rows) enables polynomial-time algorithms, the computational cost is not affordable for big data. This paper investigates how the power of quantum computation can be capitalized to solve the non-negative matrix factorization with the separability assumption (SNMF) by devising a quantum algorithm based on the divide-and-conquer anchoring (DCA) scheme [Zhou et al., 2013]. The design of quantum DCA (QDCA) is challenging. In the divide step,  the random projections in  DCA is completed by a quantum algorithm for linear operations, which achieves the exponential speedup. We then  devise a heuristic post-selection procedure which extracts the information of anchors stored in the quantum states efficiently. Under a plausible assumption, QDCA performs efficiently, achieves the quantum speedup, and is beneficial for high dimensional problems.
Complementary Binary Quantization for Joint Multiple Indexing
Authors: Fu Qiang , Han Xu , Liu Xianglong , Song Jingkuan , Deng Cheng
Published: July 2018

Building multiple hash tables has been proven a successful technique for indexing massive databases, which can guarantee a desired level of overall performance. However, existing hash based multi-indexing methods suffer from the heavy redundancy, without strong table complementarity and effective hash code learning. To address the problems, this paper proposes a complementary binary quantization (CBQ) method to jointly learning multiple hash tables. It exploits the power of incomplete binary coding based on prototypes to align the original space and the Hamming space, and further utilizes the nature of multi-indexing search to jointly reduce the quantization loss based on the prototype based hash function. Our alternating optimization adaptively discovers the complementary prototype sets and the corresponding code sets of a varying size in an efficient way, which together robustly approximate the data relations. Our method can be naturally generalized to the product space for long hash codes. Extensive experiments carried out on two popular large-scale tasks including Euclidean and semantic nearest neighbor search demonstrate that the proposed CBQ method enjoys the strong table complementarity and significantly outperforms the state-of-the-art, with up to 57.76\% performance gains relatively.
Joint Generative Moment-Matching Network for Learning Structural Latent Code
Authors: Gao Hongchang , Huang Heng
Published: July 2018

Generative Moment-Matching Network (GMMN) is a deep generative model, which employs maximum mean discrepancy as the objective to learn model parameters. However, this model can only generate samples, failing to infer the latent code from samples for downstream tasks. In this paper, we propose a novel Joint Generative Moment-Matching Network (JGMMN), which learns the structural latent code for unsupervised inference. Specifically, JGMMN has a generation network for the generation task and an inference network for the inference task. We first reformulate this model as the two joint distributions matching problem. To solve this problem, we propose to use the Joint Maximum Mean Discrepancy (JMMD) as the objective to learn these two networks simultaneously. Furthermore, to enforce the consistency between the sample distribution and the inferred latent code distribution, we propose a novel multi-modal regularization to enforce this consistency. At last, extensive experiments on both synthetic and real-world datasets have verified the effectiveness and correctness of our proposed JGMMN.
Stochastic Second-Order Method for Large-Scale Nonconvex Sparse Learning Models
Authors: Gao Hongchang , Huang Heng
Published: July 2018

Sparse learning models have shown promising performance in the high dimensional machine learning applications. The main challenge of sparse learning models is how to optimize it efficiently. Most existing methods solve this problem by relaxing it as a convex problem, incurring large estimation bias. Thus, the sparse learning model with nonconvex constraint has attracted much attention due to its better performance. But it is difficult to optimize due to the non-convexity.

In this paper, we propose a linearly convergent stochastic second-order method to optimize this nonconvex problem for large-scale datasets. The proposed method incorporates second-order information to improve the convergence speed. Theoretical analysis shows that our proposed method enjoys linear convergence rate and guarantees to converge to the underlying true model parameter. Experimental results have verified the efficiency and correctness of our proposed method.
Faster Training Algorithms for Structured Sparsity-Inducing Norm
Authors: Gu Bin , Ju Xingwang , Li Xiang , Zheng Guansheng
Published: July 2018

Structured-sparsity regularization is popular for sparse learning because of its flexibility of encoding the feature structures. This paper considers a generalized version of structured-sparsity regularization (especially for $l_1/l_{\infty}$ norm) with arbitrary group overlap. Due to the group overlap, it is time-consuming to solve the associated proximal operator. Although Mairal~\shortcite{mairal2010network} have proposed a  network-flow  algorithm to solve the proximal operator, it is still time-consuming especially in the high-dimensional setting. To address this challenge, in this paper, we have developed a more efficient solution for $l_1/l_{\infty}$ group lasso with arbitrary group overlap using an Inexact Proximal-Gradient method. In each iteration, our algorithm only requires to calculate an inexact solution to the proximal sub-problem, which can be done efficiently. On the theoretic side, the proposed algorithm enjoys the same global convergence rate as the exact proximal methods. Experiments demonstrate that our algorithm is much more efficient than network-flow algorithm, while retaining the similar generalization performance.
Replicating Active Appearance Model by Generator Network
Authors: Han Tian , Wu Jiawen , Wu Ying Nian
Published: July 2018

A recent Cell paper [Chang and Tsao, 2017] reports an interesting discovery. For the face stimuli generated by a pre-trained active appearance model (AAM), the responses of neurons in the areas of the primate brain that are responsible for face recognition exhibit strong linear relationship with the shape variables and appearance variables of the AAM that generates the face stimuli. In this paper, we show that this behavior can be replicated by a deep generative model called the generator network, which assumes that the observed signals are generated by latent random variables via a top-down convolutional neural network. Specifically, we learn the generator network from the face images generated by a pre-trained AAM model using variational auto-encoder, and we show that the inferred latent variables of the learned generator network have strong linear relationship with the shape and appearance variables of the AAM model that generates the face images. Unlike the AAM model that has an explicit shape model where the shape variables generate the control points or landmarks, the generator network has no such shape model and shape variables. Yet the generator network can learn the shape knowledge in the sense that some of the latent variables of the learned generator network capture the shape variations in the face images generated by AAM.
MIXGAN: Learning Concepts from Different Domains for Mixture Generation
Authors: Hao Guang-Yuan , Yu Hong-Xing , Zheng Wei-Shi
Published: July 2018

In this work, we present an interesting attempt on mixture generation: absorbing different image concepts (e.g., content and style) from different domains and thus generating a new domain with learned concepts. In particular, we propose a mixture generative adversarial network (MIXGAN). MIXGAN learns concepts of content and style from two domains respectively, and thus can join them for mixture generation in a new domain, i.e., generating images with content from one domain and style from another. MIXGAN overcomes the limitation of current GAN-based models which either generate new images in the same domain as they observed in training stage, or require off-the-shelf content templates for transferring or translation. Extensive experimental results demonstrate the effectiveness of MIXGAN as compared to related state-of-the-art GAN-based models.
Preventing Disparate Treatment in Sequential Decision Making
Authors: Heidari Hoda , Krause Andreas
Published: July 2018

We study fairness in sequential decision making environments, where at each time step a learning algorithm receives data corresponding to a new individual (e.g. a new job application) and must make an irrevocable decision about him/her (e.g. whether to hire the applicant) based on observations made so far. In order to prevent cases of disparate treatment, our time-dependent notion of fairness requires algorithmic decisions to be consistent: if two individuals are similar in the feature space and arrive during the same time epoch, the algorithm must assign them to similar outcomes. We propose a general framework for post-processing predictions made by a black-box learning model, that guarantees the resulting sequence of outcomes is consistent. We show theoretically that imposing consistency will not significantly slow down learning. Our experiments on two real-world data sets illustrate and confirm this finding in practice.
Combinatorial Pure Exploration with Continuous and Separable Reward Functions and Its Applications
Authors: Huang Weiran , Ok Jungseul , Li Liang , Chen Wei
Published: July 2018

We study the Combinatorial Pure Exploration problem with Continuous and Separable reward functions (CPE-CS) in the stochastic multi-armed bandit setting. In a CPE-CS instance, we are given several stochastic arms with unknown distributions, as well as a collection of possible decisions. Each decision has a reward according to the distributions of arms. The goal is to identify the decision with the maximum reward, using as few arm samples as possible. The problem generalizes the combinatorial pure exploration problem with linear rewards, which has attracted significant attention in recent years. In this paper, we propose an adaptive learning algorithm for the CPE-CS problem, and analyze its sample complexity. In particular, we introduce a new hardness measure called the consistent optimality hardness, and give both the upper and lower bounds of sample complexity. Moreover, we give examples to demonstrate that our solution has the capacity to deal with non-linear reward functions.
Trembling-Hand Perfection in Extensive-Form Games with Commitment
Authors: Farina Gabriele , Marchesi Alberto , Kroer Christian , Gatti Nicola , Sandholm Tuomas
Published: July 2018

We initiate the study of equilibrium refinements based on trembling-hand perfection in extensive-form games with commitment strategies, that is, where one player commits to a strategy first. We show that the standard strong (and weak) Stackelberg equilibria are not suitable for trembling-hand perfection, because the limit of a sequence of such strong (weak) Stackelberg commitment strategies of a perturbed game may not be a strong (weak) Stackelberg equilibrium itself. However, we show that the universal set of all Stackelberg equilibria (i.e., those that are optimal for at least some follower response function) is natural for trembling- hand perfection: it does not suffer from the problem above. We also prove that determining the existence of a Stackelberg equilibrium--refined or not--that gives the leader expected value at least v is NP-hard. This significantly extends prior complexity results that were specific to strong Stackelberg equilibrium.
Network Approximation using Tensor Sketching
Authors: Kasiviswanathan Shiva Prasad , Narodytska Nina , Jin Hongxia
Published: July 2018

Deep neural networks are powerful learning models that achieve state-of-the-art performance on many computer vision, speech, and language processing tasks. In this paper, we study a fundamental question that arises when designing deep network architectures: Given a target network architecture can we design a `smaller' network architecture that 'approximates' the operation of the target network? The question is, in part, motivated by the challenge of parameter reduction (compression) in modern deep neural networks, as the ever increasing storage and memory requirements of these networks pose a problem in resource constrained environments.In this work, we focus on deep convolutional neural network architectures, and propose a novel randomized tensor sketching technique that we utilize to develop a unified framework for approximating the operation of both the convolutional and fully connected layers. By applying the sketching technique along different tensor dimensions, we design changes to the convolutional and fully connected layers that substantially reduce the number of effective parameters in a network. We show that the resulting smaller network can be trained directly, and has a classification accuracy that is comparable to the original network.
R-SVM+: Robust Learning with Privileged Information
Authors: Li Xue , Du Bo , Xu Chang , Zhang Yipeng , Zhang Lefei , Tao Dacheng
Published: July 2018

In practice, the circumstance that training and test data are clean is

not always satisfied. The performance of existing methods in the learning using

privileged information (LUPI) paradigm may be seriously challenged, due to the

lack of clear strategies to address potential noises in the data. This paper

proposes a novel Robust SVM+ (RSVM+) algorithm based on a rigorous theoretical analysis.

Under the SVM+ framework in the LUPI paradigm, we study the lower bound of

perturbations of both example feature data and privileged feature data, which

will mislead the model to make wrong decisions. By maximizing the lower bound, tolerance

of the learned model over perturbations will be increased. Accordingly, a novel

regularization function is introduced to upgrade a variant form of SVM+. The

objective function of RSVM+ is transformed into a quadratic programming

problem, which can be efficiently optimized using off-the-shelf solvers.

Experiments on real-world datasets demonstrate the necessity of studying robust

SVM+ and the effectiveness of the proposed algorithm.