OpenRaiser/Intern-Atlas huggingface dataset:
SIFT Meets CNN: A Decade Survey of Instance Retrieval
Venue: arXiv cs.CV 2017
Year: 2017

In the early days, content-based image retrieval (CBIR) was studied with global features. Since 2003, image retrieval based on local descriptors (de facto SIFT) has been extensively studied for over a decade due to the advantage of SIFT in dealing with image transformations. Recently, image representations based on the convolutional neural network (CNN) have attracted increasing interest in the community and demonstrated impressive performance. Given this time of rapid evolution, this article provides a comprehensive survey of instance retrieval over the last decade. Two broad categories, SIFT-based and CNN-based methods, are presented. For the former, according to the codebook size, we organize the literature into using large/medium-sized/small codebooks. For the latter, we discuss three lines of methods, i.e., using pre-trained or fine-tuned CNN models, and hybrid methods. The first two perform a single-pass of an image to the network, while the last category employs a patch-based feature extraction scheme. This survey presents milestones in modern instance retrieval, reviews a broad selection of previous works in different categories, and provides insights on the connection between SIFT and CNN-based methods. After analyzing and comparing retrieval performance of different categories on several datasets, we discuss promising directions towards generic and specialized instance retrieval.
Embedding graphs into embedded graphs
Venue: arXiv cs.CG 2017
Year: 2017

A (possibly denerate) drawing of a graph $G$ in the plane is approximable by an embedding if it can be turned into an embedding by an arbitrarily small perturbation. We show that testing, whether a straight-line drawing of a planar graph $G$ in the plane is approximable by an embedding, can be carried out in polynomial time, if a desired embedding of $G$ belongs to a fixed isotopy class. In other words, we show that c-planarity with embedded pipes is tractable for graphs with fixed embeddings. To the best of our knowledge an analogous result was previously known essentially only when $G$ is a cycle.
Spacetimes with Semantics (III) - The Structure of Functional Knowledge Representation and Artificial Reasoning
Venue: arXiv cs.AI 2017
Year: 2017

Using the previously developed concepts of semantic spacetime, I explore the interpretation of knowledge representations, and their structure, as a semantic system, within the framework of promise theory. By assigning interpretations to phenomena, from observers to observed, we may approach a simple description of knowledge-based functional systems, with direct practical utility. The focus is especially on the interpretation of concepts, associative knowledge, and context awareness. The inference seems to be that most if not all of these concepts emerge from purely semantic spacetime properties, which opens the possibility for a more generalized understanding of what constitutes a learning, or even `intelligent' system. Some key principles emerge for effective knowledge representation: 1) separation of spacetime scales, 2) the recurrence of four irreducible types of association, by which intent propagates: aggregation, causation, cooperation, and similarity, 3) the need for discrimination of identities (discrete), which is assisted by distinguishing timeline simultaneity from sequential events, and 4) the ability to learn (memory). It is at least plausible that emergent knowledge abstraction capabilities have their origin in basic spacetime structures. These notes present a unified view of mostly well-known results; they allow us to see information models, knowledge representations, machine learning, and semantic networking (transport and information base) in a common framework. The notion of `smart spaces' thus encompasses artificial systems as well as living systems, across many different scales, e.g. smart cities and organizations.
Multivariable Adaptive Harmonic Steady-State Control for Rejection of Sinusoidal Disturbances Acting on an Unknown System
Venue: arXiv cs.SY 2017
Year: 2017

This paper presents an adaptive harmonic steady-state (AHSS) controller, which addresses the problem of rejecting sinusoids with known frequencies that act on a completely unknown multi-input multi-output linear time-invariant system. We analyze the stability and closed-loop performance of AHSS for single-input single-output systems. In this case, we show that AHSS asymptotically rejects disturbances.
Facial Expression Recognition Using a Hybrid CNN-SIFT Aggregator
Venue: arXiv cs.CV 2017
Year: 2017

Deriving an effective facial expression recognition component is important for a successful human-computer interaction system. Nonetheless, recognizing facial expression remains a challenging task. This paper describes a novel approach towards facial expression recognition task. The proposed method is motivated by the success of Convolutional Neural Networks (CNN) on the face recognition problem. Unlike other works, we focus on achieving good accuracy while requiring only a small sample data for training. Scale Invariant Feature Transform (SIFT) features are used to increase the performance on small data as SIFT does not require extensive training data to generate useful features. In this paper, both Dense SIFT and regular SIFT are studied and compared when merged with CNN features. Moreover, an aggregator of the models is developed. The proposed approach is tested on the FER-2013 and CK+ datasets. Results demonstrate the superiority of CNN with Dense SIFT over conventional CNN and CNN with SIFT. The accuracy even increased when all the models are aggregated which generates state-of-art results on FER-2013 and CK+ datasets, where it achieved 73.4% on FER-2013 and 99.1% on CK+.
Temporal Correlation of Interference and Outage in Mobile Networks over One-Dimensional Finite Regions
Venue: arXiv cs.NI 2017
Year: 2017

In practice, wireless networks are deployed over finite domains, the level of mobility is different at different locations, and user mobility is correlated over time. All these features have an impact on the temporal properties of interference which is often neglected. In this paper, we show how to incorporate correlated user mobility into the interference and outage correlation models. We use the random waypoint mobility model over a bounded one-dimensional domain as an example model inducing correlation, and we calculate its displacement law at different locations. Based on that, we illustrate that the temporal correlations of interference and outage are location-dependent, being lower close to the centre of the domain, where the level of mobility is higher than near the boundary. Close to the boundary, more time is also needed to see uncorrelated interference. Our findings suggest that an accurate description of the mobility pattern is important, because it leads to more accurate understanding/modeling of interference and receiver performance.
Information-Centric Offloading in Cellular Networks with Coordinated Device-to-Device Communication
Venue: arXiv cs.NI 2017
Year: 2017

In this paper, we develop a comprehensive analytical framework for cache enabled cellular networks overlaid with coordinated device-to-device (D2D) communication. We follow an approach similar to LTE Direct, where the base station (BS) is responsible for establishing D2D links. We consider that an arbitrary requesting user is offloaded to D2D mode to communicate with one of its 'k' closest D2D helpers within the macrocell subject to content availability and helper selection scheme. We consider two different D2D helper selection schemes: 1) uniform selection (US), where the D2D helper is selected uniformly and 2) nearest selection (NS), where the nearest helper possessing the content is selected. Employing tools from stochastic geometry, we model the locations of BSs and D2D helpers using independent homogeneous Poisson point processes (HPPPs). We characterize the D2D mode probability of an arbitrary user for both the NS and US schemes. The distribution of the distance between an arbitrary user and its ith neighboring D2D helper within the macrocell is derived using disk approximation for the Voronoi cell, which is shown to be reasonably accurate. We fully characterize the overall coverage probability and the average ergodic rate of an arbitrary user requesting a particular content. We show that significant performance gains can be achieved compared to conventional cellular communication under both the NS and US schemes when popular contents are requested and NS scheme always outperforms the US scheme. Our analysis reveals an interesting trade off between the performance metrics and the number of candidate D2D helpers 'k'. We conclude that enhancing D2D opportunities for the users does not always result in better performance and the network parameters have to be carefully tuned to harness maximum gains.
A Conflict-Free Replicated JSON Datatype
Venue: arXiv cs.DC 2017
Year: 2017

Many applications model their data in a general-purpose storage format such as JSON. This data structure is modified by the application as a result of user input. Such modifications are well understood if performed sequentially on a single copy of the data, but if the data is replicated and modified concurrently on multiple devices, it is unclear what the semantics should be. In this paper we present an algorithm and formal semantics for a JSON data structure that automatically resolves concurrent modifications such that no updates are lost, and such that all replicas converge towards the same state (a conflict-free replicated datatype or CRDT). It supports arbitrarily nested list and map types, which can be modified by insertion, deletion and assignment. The algorithm performs all merging client-side and does not depend on ordering guarantees from the network, making it suitable for deployment on mobile devices with poor network connectivity, in peer-to-peer networks, and in messaging systems with end-to-end encryption.
Performance prediction of finite-difference solvers for different computer architectures
Venue: arXiv cs.PF 2017
Year: 2017

The life-cycle of a partial differential equation (PDE) solver is often characterized by three development phases: the development of a stable numerical discretization, development of a correct (verified) implementation, and the optimization of the implementation for different computer architectures. Often it is only after significant time and effort has been invested that the performance bottlenecks of a PDE solver are fully understood, and the precise details varies between different computer architectures. One way to mitigate this issue is to establish a reliable performance model that allows a numerical analyst to make reliable predictions of how well a numerical method would perform on a given computer architecture, before embarking upon potentially long and expensive implementation and optimization phases. The availability of a reliable performance model also saves developer effort as it both informs the developer on what kind of optimisations are beneficial, and when the maximum expected performance has been reached and optimisation work should stop. We show how discretization of a wave equation can be theoretically studied to understand the performance limitations of the method on modern computer architectures. We focus on the roofline model, now broadly used in the high-performance computing community, which considers the achievable performance in terms of the peak memory bandwidth and peak floating point performance of a computer with respect to algorithmic choices. A first principles analysis of operational intensity for key time-stepping finite-difference algorithms is presented. With this information available at the time of algorithm design, the expected performance on target computer systems can be used as a driver for algorithm design.
Refining Approximating Betweenness Centrality Based on Samplings
Venue: arXiv cs.SI 2017
Year: 2017

Betweenness Centrality (BC) is an important measure used widely in complex network analysis, such as social network, web page search, etc. Computing the exact BC values is highly time consuming. Currently the fastest exact BC determining algorithm is given by Brandes, taking $O(nm)$ time for unweighted graphs and $O(nm+n^2\log n)$ time for weighted graphs, where $n$ is the number of vertices and $m$ is the number of edges in the graph. Due to the extreme difficulty of reducing the time complexity of exact BC determining problem, many researchers have considered the possibility of any satisfactory BC approximation algorithms, especially those based on samplings. Bader et al. give the currently best BC approximation algorithm, with a high probability to successfully estimate the BC of one vertex within a factor of $1/\varepsilon$ using $\varepsilon t$ samples, where $t$ is the ratio between $n^2$ and the BC value of the vertex. However, some of the algorithmic parameters in Bader's work are not yet tightly bounded, leaving some space to improve their algorithm. In this project, we revisit Bader's algorithm, give more tight bounds on the estimations, and improve the performance of the approximation algorithm, i.e., fewer samples and lower factors. On the other hand, Riondato proposes a non-adaptive BC approximation method with samplings on shortest paths. We investigate the possibility to give an adaptive algorithm with samplings on vertices. With rigorous reasoning, we show that this algorithm can also give bounded approximation factors and number of samplings. To evaluate our results, we also conduct extensive experiments using real-world datasets, and find that both our algorithms can achieve acceptable performance. We verify that our work can improve the current BC approximation algorithm with better parameters, i.e., higher successful probabilities, lower factors and fewer samples.
Layered Synthesis of Latent Gaussian Trees
Venue: arXiv cs.IT 2017
Year: 2017

A new synthesis scheme is proposed to generate a random vector with prescribed joint density that induces a (latent) Gaussian tree structure. The quality of synthesis is shown by vanishing total variation distance between the synthesized and desired statistics. The proposed layered and successive synthesis scheme relies on the learned structure of tree to use sufficient number of common random variables to synthesize the desired density. We characterize the achievable rate region for the rate tuples of multi-layer latent Gaussian tree, through which the number of bits needed to synthesize such Gaussian joint density are determined. The random sources used in our algorithm are the latent variables at the top layer of tree, the additive independent Gaussian noises, and the Bernoulli sign inputs that capture the ambiguity of correlation signs between the variables. We have shown that such ambiguity can further help in reducing the synthesis rates for the underlying Gaussian trees.
Towards Music Captioning: Generating Music Playlist Descriptions
Venue: arXiv cs.MM 2017
Year: 2017

Descriptions are often provided along with recommendations to help users' discovery. Recommending automatically generated music playlists (e.g. personalised playlists) introduces the problem of generating descriptions. In this paper, we propose a method for generating music playlist descriptions, which is called as music captioning. In the proposed method, audio content analysis and natural language processing are adopted to utilise the information of each track.
BBQ-Networks: Efficient Exploration in Deep Reinforcement Learning for Task-Oriented Dialogue Systems
Venue: arXiv cs.LG 2017
Year: 2017

We present a new algorithm that significantly improves the efficiency of exploration for deep Q-learning agents in dialogue systems. Our agents explore via Thompson sampling, drawing Monte Carlo samples from a Bayes-by-Backprop neural network. Our algorithm learns much faster than common exploration strategies such as $ε$-greedy, Boltzmann, bootstrapping, and intrinsic-reward-based ones. Additionally, we show that spiking the replay buffer with experiences from just a few successful episodes can make Q-learning feasible when it might otherwise fail.
Photo Filter Recommendation by Category-Aware Aesthetic Learning
Venue: arXiv cs.CV 2017
Year: 2017

Nowadays, social media has become a popular platform for the public to share photos. To make photos more visually appealing, users usually apply filters on their photos without domain knowledge. However, due to the growing number of filter types, it becomes a major issue for users to choose the best filter type. For this purpose, filter recommendation for photo aesthetics takes an important role in image quality ranking problems. In these years, several works have declared that Convolutional Neural Networks (CNNs) outperform traditional methods in image aesthetic categorization, which classifies images into high or low quality. Most of them do not consider the effect on filtered images; hence, we propose a novel image aesthetic learning for filter recommendation. Instead of binarizing image quality, we adjust the state-of-the-art CNN architectures and design a pairwise loss function to learn the embedded aesthetic responses in hidden layers for filtered images. Based on our pilot study, we observe image categories (e.g., portrait, landscape, food) will affect user preference on filter selection. We further integrate category classification into our proposed aesthetic-oriented models. To the best of our knowledge, there is no public dataset for aesthetic judgment with filtered images. We create a new dataset called Filter Aesthetic Comparison Dataset (FACD). It contains 28,160 filtered images based on the AVA dataset and 42,240 reliable image pairs with aesthetic annotations using Amazon Mechanical Turk. It is the first dataset containing filtered images and user preference labels. We conduct experiments on the collected FACD for filter recommendation, and the results show that our proposed category-aware aesthetic learning outperforms aesthetic classification methods (e.g., 12% relative improvement).
Automatic Selection of Context Configurations for Improved Class-Specific Word Representations
Venue: arXiv cs.CL 2017
Year: 2017

This paper is concerned with identifying contexts useful for training word representation models for different word classes such as adjectives (A), verbs (V), and nouns (N). We introduce a simple yet effective framework for an automatic selection of class-specific context configurations. We construct a context configuration space based on universal dependency relations between words, and efficiently search this space with an adapted beam search algorithm. In word similarity tasks for each word class, we show that our framework is both effective and efficient. Particularly, it improves the Spearman's rho correlation with human scores on SimLex-999 over the best previously proposed class-specific contexts by 6 (A), 6 (V) and 5 (N) rho points. With our selected context configurations, we train on only 14% (A), 26.2% (V), and 33.6% (N) of all dependency-based contexts, resulting in a reduced training time. Our results generalise: we show that the configurations our algorithm learns for one English training setup outperform previously proposed context types in another training setup for English. Moreover, basing the configuration space on universal dependencies, it is possible to transfer the learned configurations to German and Italian. We also demonstrate improved per-class results over other context types in these two languages.
Memory-efficient and Ultra-fast Network Lookup and Forwarding using Othello Hashing
Venue: arXiv cs.NI 2017
Year: 2017

Network algorithms always prefer low memory cost and fast packet processing speed. Forwarding information base (FIB), as a typical network processing component, requires a scalable and memory-efficient algorithm to support fast lookups. In this paper, we present a new network algorithm, Othello Hashing, and its application of a FIB design called Concise, which uses very little memory to support ultra-fast lookups of network names. Othello Hashing and Concise make use of minimal perfect hashing and relies on the programmable network framework to support dynamic updates. Our conceptual contribution of Concise is to optimize the memory efficiency and query speed in the data plane and move the relatively complex construction and update components to the resource-rich control plane. We implemented Concise on three platforms. Experimental results show that Concise uses significantly smaller memory to achieve much faster query speed compared to existing solutions of network name lookups.
A Scalable Framework for Wireless Distributed Computing
Venue: arXiv cs.IT 2017
Year: 2017

We consider a wireless distributed computing system, in which multiple mobile users, connected wirelessly through an access point, collaborate to perform a computation task. In particular, users communicate with each other via the access point to exchange their locally computed intermediate computation results, which is known as data shuffling. We propose a scalable framework for this system, in which the required communication bandwidth for data shuffling does not increase with the number of users in the network. The key idea is to utilize a particular repetitive pattern of placing the dataset (thus a particular repetitive pattern of intermediate computations), in order to provide coding opportunities at both the users and the access point, which reduce the required uplink communication bandwidth from users to access point and the downlink communication bandwidth from access point to users by factors that grow linearly with the number of users. We also demonstrate that the proposed dataset placement and coded shuffling schemes are optimal (i.e., achieve the minimum required shuffling load) for both a centralized setting and a decentralized setting, by developing tight information-theoretic lower bounds.
Efficient non-anonymous composition operator for modeling complex dependable systems
Venue: arXiv cs.DC 2017
Year: 2017

A new model composer is proposed to automatically generate non-anonymous model replicas in the context of performability and dependability evaluation. It is a state-sharing composer that extends the standard anonymous replication composer in order to share the state of a replica among a set of other specific replicas or among the eplica and another external model. This new composition operator aims to improve expressiveness and performance with respect to the standard anonymous replicator, namely the one adopted by the M{ö}bius modeling framework.