OpenRaiser/Intern-Atlas huggingface dataset:
A Two-Stage Auction Mechanism for Cloud Resource Allocation
Venue: arXiv cs.DC 2018
Year: 2018

With the recent growth in the size of cloud computing business, handling the interactions between customers and cloud providers has become more challenging. Auction theory has been proposed to model these interactions due to its simplicity and a good match with real-world scenarios. In this paper, we consider cloud of clouds networks (CCNs) with different types of servers along with customers with heterogeneous demands. For each CCN, a CCN manager is designated to handle the cloud resources. A comprehensive framework is introduced in which the process of resource gathering and allocation is addressed via two stages, where the first stage models the interactions between customers and CCN managers, and the second stage examines the interactions between CCN managers and private cloud providers (CPs). For the first stage, an options-based sequential auction (OBSA) is adapted to the examined market, which is capable of providing truthfulness as the dominant strategy and resolving the entrance time problem. An analytical foundation for OBSAs is presented and multiple performance metrics are derived. For the second stage, two parallel markets are assumed: flat-price and auction-based market. A theoretical framework for market analysis is provided and the bidding behavior of CCN managers is described.
Manifold regularization with GANs for semi-supervised learning
Venue: arXiv cs.LG 2018
Year: 2018

Generative Adversarial Networks are powerful generative models that are able to model the manifold of natural images. We leverage this property to perform manifold regularization by approximating a variant of the Laplacian norm using a Monte Carlo approximation that is easily computed with the GAN. When incorporated into the semi-supervised feature-matching GAN we achieve state-of-the-art results for GAN-based semi-supervised learning on CIFAR-10 and SVHN benchmarks, with a method that is significantly easier to implement than competing methods. We also find that manifold regularization improves the quality of generated images, and is affected by the quality of the GAN used to approximate the regularizer.
A Generic Approach to Lung Field Segmentation from Chest Radiographs using Deep Space and Shape Learning
Venue: arXiv cs.CV 2018
Year: 2018

Computer-aided diagnosis (CAD) techniques for lung field segmentation from chest radiographs (CXR) have been proposed for adult cohorts, but rarely for pediatric subjects. Statistical shape models (SSMs), the workhorse of most state-of-the-art CXR-based lung field segmentation methods, do not efficiently accommodate shape variation of the lung field during the pediatric developmental stages. The main contributions of our work are: (1) a generic lung field segmentation framework from CXR accommodating large shape variation for adult and pediatric cohorts; (2) a deep representation learning detection mechanism, \emph{ensemble space learning}, for robust object localization; and (3) \emph{marginal shape deep learning} for the shape deformation parameter estimation. Unlike the iterative approach of conventional SSMs, the proposed shape learning mechanism transforms the parameter space into marginal subspaces that are solvable efficiently using the recursive representation learning mechanism. Furthermore, our method is the first to include the challenging retro-cardiac region in the CXR-based lung segmentation for accurate lung capacity estimation. The framework is evaluated on 668 CXRs of patients between 3 month to 89 year of age. We obtain a mean Dice similarity coefficient of $0.96\pm0.03$ (including the retro-cardiac region). For a given accuracy, the proposed approach is also found to be faster than conventional SSM-based iterative segmentation methods. The computational simplicity of the proposed generic framework could be similarly applied to the fast segmentation of other deformable objects.
AtDelfi: Automatically Designing Legible, Full Instructions For Games
Venue: arXiv cs.AI 2018
Year: 2018

This paper introduces a fully automatic method for generating video game tutorials. The AtDELFI system (AuTomatically DEsigning Legible, Full Instructions for games) was created to investigate procedural generation of instructions that teach players how to play video games. We present a representation of game rules and mechanics using a graph system as well as a tutorial generation method that uses said graph representation. We demonstrate the concept by testing it on games within the General Video Game Artificial Intelligence (GVG-AI) framework; the paper discusses tutorials generated for eight different games. Our findings suggest that a graph representation scheme works well for simple arcade style games such as Space Invaders and Pacman, but it appears that tutorials for more complex games might require higher-level understanding of the game than just single mechanics.
Sliding window order statistics in sublinear space
Venue: arXiv cs.DS 2018
Year: 2018

We extend the multi-pass streaming model to sliding window problems, and address the problem of computing order statistics on fixed-size sliding windows, in the multi-pass streaming model as well as the closely related communication complexity model. In the $2$-pass streaming model, we show that on input of length $N$ with values in range $[0,R]$ and a window of length $K$, sliding window minimums can be computed in $\widetilde{O}(\sqrt{N})$. We show that this is nearly optimal (for any constant number of passes) when $R \geq K$, but can be improved when $R = o(K)$ to $\widetilde{O}(\sqrt{NR/K})$. Furthermore, we show that there is an $(l+1)$-pass streaming algorithm which computes $l^\text{th}$-smallest elements in $\widetilde{O}(l^{3/2} \sqrt{N})$ space. In the communication complexity model, we describe a simple $\widetilde{O}(pN^{1/p})$ algorithm to compute minimums in $p$ rounds of communication for odd $p$, and a more involved algorithm which computes the $l^\text{th}$-smallest elements in $\widetilde{O}(pl^2 N^{1/(p-2l-1)})$ space. Finally, we prove that the majority statistic on boolean streams cannot be computed in sublinear space, implying that $l^\text{th}$-smallest elements cannot be computed in space both sublinear in $N$ and independent of $l$.
Interactive Discovery System for Direct Democracy
Venue: arXiv cs.CY 2018
Year: 2018

Decide Madrid is the civic technology of Madrid City Council which allows users to create and support online petitions. Despite the initial success, the platform is encountering problems with the growth of petition signing because petitions are far from the minimum number of supporting votes they must gather. Previous analyses have suggested that this problem is produced by the interface: a paginated list of petitions which applies a non-optimal ranking algorithm. For this reason, we present an interactive system for the discovery of topics and petitions. This approach leads us to reflect on the usefulness of data visualization techniques to address relevant societal challenges.
Query-Efficient Hard-label Black-box Attack:An Optimization-based Approach
Venue: arXiv cs.LG 2018
Year: 2018

We study the problem of attacking a machine learning model in the hard-label black-box setting, where no model information is revealed except that the attacker can make queries to probe the corresponding hard-label decisions. This is a very challenging problem since the direct extension of state-of-the-art white-box attacks (e.g., CW or PGD) to the hard-label black-box setting will require minimizing a non-continuous step function, which is combinatorial and cannot be solved by a gradient-based optimizer. The only current approach is based on random walk on the boundary, which requires lots of queries and lacks convergence guarantees. We propose a novel way to formulate the hard-label black-box attack as a real-valued optimization problem which is usually continuous and can be solved by any zeroth order optimization algorithm. For example, using the Randomized Gradient-Free method, we are able to bound the number of iterations needed for our algorithm to achieve stationary points. We demonstrate that our proposed method outperforms the previous random walk approach to attacking convolutional neural networks on MNIST, CIFAR, and ImageNet datasets. More interestingly, we show that the proposed algorithm can also be used to attack other discrete and non-continuous machine learning models, such as Gradient Boosting Decision Trees (GBDT).
Competitive Analysis System for Theatrical Movie Releases Based on Movie Trailer Deep Video Representation
Venue: arXiv cs.IR 2018
Year: 2018

Audience discovery is an important activity at major movie studios. Deep models that use convolutional networks to extract frame-by-frame features of a movie trailer and represent it in a form that is suitable for prediction are now possible thanks to the availability of pre-built feature extractors trained on large image datasets. Using these pre-built feature extractors, we are able to process hundreds of publicly available movie trailers, extract frame-by-frame low level features (e.g., a face, an object, etc) and create video-level representations. We use the video-level representations to train a hybrid Collaborative Filtering model that combines video features with historical movie attendance records. The trained model not only makes accurate attendance and audience prediction for existing movies, but also successfully profiles new movies six to eight months prior to their release.
Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering
Venue: arXiv cs.DS 2018
Year: 2018

We develop and analyze a method to reduce the size of a very large set of data points in a high dimensional Euclidean space R d to a small set of weighted points such that the result of a predetermined data analysis task on the reduced set is approximately the same as that for the original point set. For example, computing the first k principal components of the reduced set will return approximately the first k principal components of the original set or computing the centers of a k-means clustering on the reduced set will return an approximation for the original set. Such a reduced set is also known as a coreset. The main new feature of our construction is that the cardinality of the reduced set is independent of the dimension d of the input space and that the sets are mergable. The latter property means that the union of two reduced sets is a reduced set for the union of the two original sets (this property has recently also been called composability, see Indyk et. al., PODS 2014). It allows us to turn our methods into streaming or distributed algorithms using standard approaches. For problems such as k-means and subspace approximation the coreset sizes are also independent of the number of input points. Our method is based on projecting the points on a low dimensional subspace and reducing the cardinality of the points inside this subspace using known methods. The proposed approach works for a wide range of data analysis techniques including k-means clustering, principal component analysis and subspace clustering. The main conceptual contribution is a new coreset definition that allows to charge costs that appear for every solution to an additive constant.
A Generic Framework for Implicate Generation Modulo Theories
Venue: arXiv cs.LO 2018
Year: 2018

The clausal logical consequences of a formula are called its implicates. The generation of these implicates has several applications, such as the identification of missing hypotheses in a logical specification. We present a procedure that generates the implicates of a quantifier-free formula modulo a theory. No assumption is made on the considered theory, other than the existence of a decision procedure. The algorithm has been implemented (using the solvers MiniSat, CVC4 and Z3) and experimental results show evidence of the practical relevance of the proposed approach.
Situation Calculus for Synthesis of Manufacturing Controllers
Venue: arXiv cs.AI 2018
Year: 2018

Manufacturing is transitioning from a mass production model to a manufacturing as a service model in which manufacturing facilities 'bid' to produce products. To decide whether to bid for a complex, previously unseen product, a manufacturing facility must be able to synthesize, 'on the fly', a process plan controller that delegates abstract manufacturing tasks in the supplied process recipe to the appropriate manufacturing resources, e.g., CNC machines, robots etc. Previous work in applying AI behaviour composition to synthesize process plan controllers has considered only finite state ad-hoc representations. Here, we study the problem in the relational setting of the Situation Calculus. By taking advantage of recent work on abstraction in the Situation Calculus, process recipes and available resources are represented by ConGolog programs over, respectively, an abstract and a concrete action theory. This allows us to capture the problem in a formal, general framework, and show decidability for the case of bounded action theories. We also provide techniques for actually synthesizing the controller.
PDE-constrained LDDMM via geodesic shooting and inexact Gauss-Newton-Krylov optimization using the incremental adjoint Jacobi equations
Venue: arXiv cs.NA 2018
Year: 2018

The class of non-rigid registration methods proposed in the framework of PDE-constrained Large Deformation Diffeomorphic Metric Mapping is a particularly interesting family of physically meaningful diffeomorphic registration methods. Inexact Newton-Krylov optimization has shown an excellent numerical accuracy and an extraordinarily fast convergence rate in this framework. However, the Galerkin representation of the non-stationary velocity fields does not provide proper geodesic paths. In this work, we propose a method for PDE-constrained LDDMM parameterized in the space of initial velocity fields under the EPDiff equation. The derivation of the gradient and the Hessian-vector products are performed on the final velocity field and transported backward using the adjoint and the incremental adjoint Jacobi equations. This way, we avoid the complex dependence on the initial velocity field in the derivations and the computation of the adjoint equation and its incremental counterpart. The proposed method provides geodesics in the framework of PDE-constrained LDDMM, and it shows performance competitive to benchmark PDE-constrained LDDMM and EPDiff-LDDMM methods.
Deep semi-supervised segmentation with weight-averaged consistency targets
Venue: arXiv cs.CV 2018
Year: 2018

Recently proposed techniques for semi-supervised learning such as Temporal Ensembling and Mean Teacher have achieved state-of-the-art results in many important classification benchmarks. In this work, we expand the Mean Teacher approach to segmentation tasks and show that it can bring important improvements in a realistic small data regime using a publicly available multi-center dataset from the Magnetic Resonance Imaging (MRI) domain. We also devise a method to solve the problems that arise when using traditional data augmentation strategies for segmentation tasks on our new training scheme.
The Importance of Song Context and Song Order in Automated Music Playlist Generation
Venue: arXiv cs.IR 2018
Year: 2018

The automated generation of music playlists can be naturally regarded as a sequential task, where a recommender system suggests a stream of songs that constitute a listening session. In order to predict the next song in a playlist, some of the playlist models proposed so far consider the current and previous songs in the playlist (i.e., the song context) and possibly the order of the songs in the playlist. We investigate the impact of the song context and the song order on next-song recommendations by conducting dedicated off-line experiments on two datasets of hand-curated music playlists. Firstly, we compare three playlist models, each able to consider a different song context length: a popularity-based model, a song-based Collaborative Filtering (CF) model and a Recurrent-Neural-Network-based model (RNN). We also consider a model that predicts next songs at random as a reference. Secondly, we challenge the RNN model (the only model from the first experiment able to consider the song order) by manipulating the order of songs within playlists. Our results indicate that the song context has a positive impact on the quality of next-song recommendations, even though this effect can be masked by the bias towards very popular songs. Furthermore, in our experiments the song order does not appear as a crucial variable to predict better next-song recommendations.
Scalable Convolutional Dictionary Learning with Constrained Recurrent Sparse Auto-encoders
Venue: arXiv cs.LG 2018
Year: 2018

Given a convolutional dictionary underlying a set of observed signals, can a carefully designed auto-encoder recover the dictionary in the presence of noise? We introduce an auto-encoder architecture, termed constrained recurrent sparse auto-encoder (CRsAE), that answers this question in the affirmative. Given an input signal and an approximate dictionary, the encoder finds a sparse approximation using FISTA. The decoder reconstructs the signal by applying the dictionary to the output of the encoder. The encoder and decoder in CRsAE parallel the sparse-coding and dictionary update steps in optimization-based alternating-minimization schemes for dictionary learning. As such, the parameters of the encoder and decoder are not independent, a constraint which we enforce for the first time. We derive the back-propagation algorithm for CRsAE. CRsAE is a framework for blind source separation that, only knowing the number of sources (dictionary elements), and assuming sparsely-many can overlap, is able to separate them. We demonstrate its utility in the context of spike sorting, a source separation problem in computational neuroscience. We demonstrate the ability of CRsAE to recover the underlying dictionary and characterize its sensitivity as a function of SNR.
Improving on Q & A Recurrent Neural Networks Using Noun-Tagging
Venue: arXiv cs.LG 2018
Year: 2018

Often, more time is spent on finding a model that works well, rather than tuning the model and working directly with the dataset. Our research began as an attempt to improve upon a simple Recurrent Neural Network for answering "simple" first-order questions (QA-RNN), developed by Ferhan Ture and Oliver Jojic, from Comcast Labs, using the SimpleQuestions dataset. Their baseline model, a bidirectional, 2-layer LSTM RNN and a GRU RNN, have accuracies of 0.94 and 0.90, for entity detection and relation prediction, respectively. We fine tuned these models by doing substantial hyper-parameter tuning, getting resulting accuracies of 0.70 and 0.80, for entity detection and relation prediction, respectively. An accuracy of 0.984 was obtained on entity detection using a 1-layer LSTM, where preprocessing was done by removing all words not part of a noun chunk from the question. 100% of the dataset was available for relation prediction, but only 20% of the dataset, was available for entity detection, which we believe to be much of the reason for our initial difficulties in replicating their result, despite the fact we were able to improve on their entity detection results.
A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs
Venue: arXiv cs.DS 2018
Year: 2018

We give an $\tilde{O}(n^{7/5} \log (nC))$-time algorithm to compute a minimum-cost maximum cardinality matching (optimal matching) in $K_h$-minor free graphs with $h=O(1)$ and integer edge weights having magnitude at most $C$. This improves upon the $\tilde{O}(n^{10/7}\log{C})$ algorithm of Cohen et al. [SODA 2017] and the $O(n^{3/2}\log (nC))$ algorithm of Gabow and Tarjan [SIAM J. Comput. 1989]. For a graph with $m$ edges and $n$ vertices, the well-known Hungarian Algorithm computes a shortest augmenting path in each phase in $O(m)$ time, yielding an optimal matching in $O(mn)$ time. The Hopcroft-Karp [SIAM J. Comput. 1973], and Gabow-Tarjan [SIAM J. Comput. 1989] algorithms compute, in each phase, a maximal set of vertex-disjoint shortest augmenting paths (for appropriately defined costs) in $O(m)$ time. This reduces the number of phases from $n$ to $O(\sqrt{n})$ and the total execution time to $O(m\sqrt{n})$. In order to obtain our speed-up, we relax the conditions on the augmenting paths and iteratively compute, in each phase, a set of carefully selected augmenting paths that are not restricted to be shortest or vertex-disjoint. As a result, our algorithm computes substantially more augmenting paths in each phase, reducing the number of phases from $O(\sqrt{n})$ to $O(n^{2/5})$. By using small vertex separators, the execution of each phase takes $\tilde{O}(m)$ time on average. For planar graphs, we combine our algorithm with efficient shortest path data structures to obtain a minimum-cost perfect matching in $\tilde{O}(n^{6/5} \log{(nC)})$ time. This improves upon the recent $\tilde{O}(n^{4/3}\log{(nC)})$ time algorithm by Asathulla et al. [SODA 2018].
Latent Transformations for Object View Points Synthesis
Venue: arXiv cs.CV 2018
Year: 2018

We propose a fully-convolutional conditional generative model, the latent transformation neural network (LTNN), capable of view synthesis using a light-weight neural network suited for real-time applications. In contrast to existing conditional generative models which incorporate conditioning information via concatenation, we introduce a dedicated network component, the conditional transformation unit (CTU), designed to learn the latent space transformations corresponding to specified target views. In addition, a consistency loss term is defined to guide the network toward learning the desired latent space mappings, a task-divided decoder is constructed to refine the quality of generated views, and an adaptive discriminator is introduced to improve the adversarial training process. The generality of the proposed methodology is demonstrated on a collection of three diverse tasks: multi-view reconstruction on real hand depth images, view synthesis of real and synthetic faces, and the rotation of rigid objects. The proposed model is shown to exceed state-of-the-art results in each category while simultaneously achieving a reduction in the computational demand required for inference by 30% on average.
Hybrid Temporal Situation Calculus
Venue: arXiv cs.AI 2018
Year: 2018

The ability to model continuous change in Reiter's temporal situation calculus action theories has attracted a lot of interest. In this paper, we propose a new development of his approach, which is directly inspired by hybrid systems in control theory. Specifically, while keeping the foundations of Reiter's axiomatization, we propose an elegant extension of his approach by adding a time argument to all fluents that represent continuous change. Thereby, we insure that change can happen not only because of actions, but also due to the passage of time. We present a systematic methodology to derive, from simple premises, a new group of axioms which specify how continuous fluents change over time within a situation. We study regression for our new temporal basic action theories and demonstrate what reasoning problems can be solved. Finally, we formally show that our temporal basic action theories indeed capture hybrid automata.