OpenRaiser/Intern-Atlas huggingface dataset:
Realizing an optimization approach inspired from Piagets theory on cognitive development
Venue: arXiv cs.AI 2017
Year: 2017

The objective of this paper is to introduce an artificial intelligence based optimization approach, which is inspired from Piagets theory on cognitive development. The approach has been designed according to essential processes that an individual may experience while learning something new or improving his / her knowledge. These processes are associated with the Piagets ideas on an individuals cognitive development. The approach expressed in this paper is a simple algorithm employing swarm intelligence oriented tasks in order to overcome single-objective optimization problems. For evaluating effectiveness of this early version of the algorithm, test operations have been done via some benchmark functions. The obtained results show that the approach / algorithm can be an alternative to the literature in terms of single-objective optimization. The authors have suggested the name: Cognitive Development Optimization Algorithm (CoDOA) for the related intelligent optimization approach.
A Coalition Formation Algorithm for Multi-Robot Task Allocation in Large-Scale Natural Disasters
Venue: arXiv cs.MA 2017
Year: 2017

In large-scale natural disasters, humans are likely to fail when they attempt to reach high-risk sites or act in search and rescue operations. Robots, however, outdo their counterparts in surviving the hazards and handling the search and rescue missions due to their multiple and diverse sensing and actuation capabilities. The dynamic formation of optimal coalition of these heterogeneous robots for cost efficiency is very challenging and research in the area is gaining more and more attention. In this paper, we propose a novel heuristic. Since the population of robots in large-scale disaster settings is very large, we rely on Quantum Multi-Objective Particle Swarm Optimization (QMOPSO). The problem is modeled as a multi-objective optimization problem. Simulations with different test cases and metrics, and comparison with other algorithms such as NSGA-II and SPEA-II are carried out. The experimental results show that the proposed algorithm outperforms the existing algorithms not only in terms of convergence but also in terms of diversity and processing time.
Application of Econometric Data Analysis Methods to Physics Software
Venue: arXiv cs.SE 2017
Year: 2017

We report an investigation of data analysis methods derived from other disciplines, which we applied to physics software systems. They concern the analysis of inequality, trend analysis and the analysis of diversity. The analysis of inequality exploits statistical methods originating from econometrics; trend analysis is typical of economics and environmental sciences; the analysis of diversity is based on concepts derived from ecology and treats software as an ecosystem. To the best of our knowledge, this is an innovative exploration, as we could not find track of previous use of these methods in the experimental physics domains within the scope of the IEEE Nuclear Science Symposium. We applied these methods in the context of Geant4 physics validation and Geant4 maintainability assessment.
Memcapacitive Devices in Logic and Crossbar Applications
Venue: arXiv cs.ET 2017
Year: 2017

Over the last decade, memristive devices have been widely adopted in computing for various conventional and unconventional applications. While the integration density, memory property, and nonlinear characteristics have many benefits, reducing the energy consumption is limited by the resistive nature of the devices. Memcapacitors would address that limitation while still having all the benefits of memristors. Recent work has shown that with adjusted parameters during the fabrication process, a metal-oxide device can indeed exhibit a memcapacitive behavior. We introduce novel memcapacitive logic gates and memcapacitive crossbar classifiers as a proof of concept that such applications can outperform memristor-based architectures. The results illustrate that, compared to memristive logic gates, our memcapacitive gates consume about 7x less power. The memcapacitive crossbar classifier achieves similar classification performance but reduces the power consumption by a factor of about 1,500x for the MNIST dataset and a factor of about 1,000x for the CIFAR-10 dataset compared to a memristive crossbar. Our simulation results demonstrate that memcapacitive devices have great potential for both Boolean logic and analog low-power applications.
SemEval-2017 Task 8: RumourEval: Determining rumour veracity and support for rumours
Venue: arXiv cs.CL 2017
Year: 2017

Media is full of false claims. Even Oxford Dictionaries named "post-truth" as the word of 2016. This makes it more important than ever to build systems that can identify the veracity of a story, and the kind of discourse there is around it. RumourEval is a SemEval shared task that aims to identify and handle rumours and reactions to them, in text. We present an annotation scheme, a large dataset covering multiple topics - each having their own families of claims and replies - and use these to pose two concrete challenges as well as the results achieved by participants on these challenges.
A Fuzzy Brute Force Matching Method for Binary Image Features
Venue: arXiv cs.CV 2017
Year: 2017

Matching of binary image features is an important step in many different computer vision applications. Conventionally, an arbitrary threshold is used to identify a correct match from incorrect matches using Hamming distance which may improve or degrade the matching results for different input images. This is mainly due to the image content which is affected by the scene, lighting and imaging conditions. This paper presents a fuzzy logic based approach for brute force matching of image features to overcome this situation. The method was tested using a well-known image database with known ground truth. The approach is shown to produce a higher number of correct matches when compared against constant distance thresholds. The nature of fuzzy logic which allows the vagueness of information and tolerance to errors has been successfully exploited in an image processing context. The uncertainty arising from the imaging conditions has been overcome with the use of compact fuzzy matching membership functions.
Flexible Level-1 Consensus Ensuring Stable Social Choice: Analysis and Algorithms
Venue: arXiv cs.GT 2017
Year: 2017

Level-1 Consensus is a property of a preference-profile. Intuitively, it means that there exists a preference relation which induces an ordering of all other preferences such that frequent preferences are those that are more similar to it. This is a desirable property, since it enhances the stability of social choice by guaranteeing that there exists a Condorcet winner and it is elected by all scoring rules. In this paper, we present an algorithm for checking whether a given preference profile exhibits level-1 consensus. We apply this algorithm to a large number of preference profiles, both real and randomly-generated, and find that level-1 consensus is very improbable. We support these empirical findings theoretically, by showing that, under the impartial culture assumption, the probability of level-1 consensus approaches zero when the number of individuals approaches infinity. Motivated by these observations, we show that the level-1 consensus property can be weakened while retaining its stability implications. We call this weaker property Flexible Consensus. We show, both empirically and theoretically, that it is considerably more probable than the original level-1 consensus. In particular, under the impartial culture assumption, the probability for Flexible Consensus converges to a positive number when the number of individuals approaches infinity.
How Bandwidth Affects the $CONGEST$ Model
Venue: arXiv cs.DC 2017
Year: 2017

The $CONGEST$ model for distributed network computing is well suited for analyzing the impact of limiting the throughput of a network on its capacity to solve tasks efficiently. For many "global" problems there exists a lower bound of $Ω(D + \sqrt{n/B})$, where $B$ is the amount of bits that can be exchanged between two nodes in one round of communication, $n$ is the number of nodes and $D$ is the diameter of the graph. Typically, upper bounds are given only for the case $B=O(\log n)$, or for the case $B = +\infty$. For $B=O(\log n)$, the Minimum Spanning Tree (MST) construction problem can be solved in $O(D + \sqrt{n}\log^* n)$ rounds, and the Single Source Shortest Path (SSSP) problem can be $(1+ε)$-approximated in $\widetilde{O}(ε^{-O(1)} (D+\sqrt{n}) )$ rounds. We extend these results by providing algorithms with a complexity parametric on $B$. We show that, for any $B=Ω(\log n)$, there exists an algorithm that constructs a MST in $\widetilde{O}(D + \sqrt{n/B})$ rounds, and an algorithm that $(1+ε)$-approximate the SSSP problem in $\widetilde{O}(ε^{-O(1)} (D+\sqrt{n/B}) )$ rounds. We also show that there exist problems that are bandwidth insensitive.
Using Mise-En-Scène Visual Features based on MPEG-7 and Deep Learning for Movie Recommendation
Venue: arXiv cs.IR 2017
Year: 2017

Item features play an important role in movie recommender systems, where recommendations can be generated by using explicit or implicit preferences of users on traditional features (attributes) such as tag, genre, and cast. Typically, movie features are human-generated, either editorially (e.g., genre and cast) or by leveraging the wisdom of the crowd (e.g., tag), and as such, they are prone to noise and are expensive to collect. Moreover, these features are often rare or absent for new items, making it difficult or even impossible to provide good quality recommendations. In this paper, we show that user's preferences on movies can be better described in terms of the mise-en-scène features, i.e., the visual aspects of a movie that characterize design, aesthetics and style (e.g., colors, textures). We use both MPEG-7 visual descriptors and Deep Learning hidden layers as example of mise-en-scène features that can visually describe movies. Interestingly, mise-en-scène features can be computed automatically from video files or even from trailers, offering more flexibility in handling new items, avoiding the need for costly and error-prone human-based tagging, and providing good scalability. We have conducted a set of experiments on a large catalogue of 4K movies. Results show that recommendations based on mise-en-scène features consistently provide the best performance with respect to richer sets of more traditional features, such as genre and tag.
An Achievable Rate for an Optical Channel with Finite Memory
Venue: arXiv cs.IT 2017
Year: 2017

A fiber optic channel is modeled in a variety of ways; from the simple additive white complex Gaussian noise model, to models that incorporate memory in the channel. Because of Kerr nonlinearity, a simple model is not a good approximation to an optical fiber. Hence we study a fiber optic channel with finite memory and provide an achievable bound on channel capacity that improves upon a previously known bound.
Optimal Query Time for Encoding Range Majority
Venue: arXiv cs.DS 2017
Year: 2017

We revisit the range $τ$-majority problem, which asks us to preprocess an array $A[1..n]$ for a fixed value of $τ\in (0,1/2]$, such that for any query range $[i,j]$ we can return a position in $A$ of each distinct $τ$-majority element. A $τ$-majority element is one that has relative frequency at least $τ$ in the range $[i,j]$: i.e., frequency at least $τ(j-i+1)$. Belazzougui et al. [WADS 2013] presented a data structure that can answer such queries in $O(1/τ)$ time, which is optimal, but the space can be as much as $Θ(n \lg n)$ bits. Recently, Navarro and Thankachan [Algorithmica 2016] showed that this problem could be solved using an $O(n \lg (1/τ))$ bit encoding, which is optimal in terms of space, but has suboptimal query time. In this paper, we close this gap and present a data structure that occupies $O(n \lg (1/τ))$ bits of space, and has $O(1/τ)$ query time. We also show that this space bound is optimal, even for the much weaker query in which we must decide whether the query range contains at least one $τ$-majority element.
The Design, Implementation, and Deployment of a System to Transparently Compress Hundreds of Petabytes of Image Files for a File-Storage Service
Venue: arXiv cs.MM 2017
Year: 2017

We report the design, implementation, and deployment of Lepton, a fault-tolerant system that losslessly compresses JPEG images to 77% of their original size on average. Lepton replaces the lowest layer of baseline JPEG compression-a Huffman code-with a parallelized arithmetic code, so that the exact bytes of the original JPEG file can be recovered quickly. Lepton matches the compression efficiency of the best prior work, while decoding more than nine times faster and in a streaming manner. Lepton has been released as open-source software and has been deployed for a year on the Dropbox file-storage backend. As of February 2017, it had compressed more than 203 PiB of user JPEG files, saving more than 46 PiB.
A Time Hierarchy Theorem for the LOCAL Model
Venue: arXiv cs.DC 2017
Year: 2017

The celebrated Time Hierarchy Theorem for Turing machines states, informally, that more problems can be solved given more time. The extent to which a time hierarchy-type theorem holds in the distributed LOCAL model has been open for many years. It is consistent with previous results that all natural problems in the LOCAL model can be classified according to a small constant number of complexities, such as $O(1),O(\log^* n), O(\log n), 2^{O(\sqrt{\log n})}$, etc. In this paper we establish the first time hierarchy theorem for the LOCAL model and prove that several gaps exist in the LOCAL time hierarchy. 1. We define an infinite set of simple coloring problems called Hierarchical $2\frac{1}{2}$-Coloring}. A correctly colored graph can be confirmed by simply checking the neighborhood of each vertex, so this problem fits into the class of locally checkable labeling (LCL) problems. However, the complexity of the $k$-level Hierarchical $2\frac{1}{2}$-Coloring problem is $Θ(n^{1/k})$, for $k\in\mathbb{Z}^+$. The upper and lower bounds hold for both general graphs and trees, and for both randomized and deterministic algorithms. 2. Consider any LCL problem on bounded degree trees. We prove an automatic-speedup theorem that states that any randomized $n^{o(1)}$-time algorithm solving the LCL can be transformed into a deterministic $O(\log n)$-time algorithm. Together with a previous result, this establishes that on trees, there are no natural deterministic complexities in the ranges $ω(\log^* n)$---$o(\log n)$ or $ω(\log n)$---$n^{o(1)}$. 3. We expose a gap in the randomized time hierarchy on general graphs. Any randomized algorithm that solves an LCL problem in sublogarithmic time can be sped up to run in $O(T_{LLL})$ time, which is the complexity of the distributed Lovasz local lemma problem, currently known to be $Ω(\log\log n)$ and $O(\log n)$.
Short-Packet Communications in Non-Orthogonal Multiple Access Systems
Venue: arXiv cs.IT 2017
Year: 2017

This work introduces, for the first time, non-orthogonal multiple access (NOMA) into short-packet communications to achieve low latency in wireless networks. Specifically, we address the optimization of transmission rates and power allocation to maximize the effective throughput of the user with a higher channel gain while guaranteeing the other user achieving a certain level of effective throughput. To demonstrate the benefits of NOMA, we analyze the performance of orthogonal multiple access (OMA) as a benchmark. Our examination shows that NOMA can significantly outperform OMA by achieving a higher effective throughput with the same latency or incurring a lower latency to achieve the same effective throughput targets. Surprisingly, we find that the performance gap between NOMA and OMA becomes more prominent when the effective throughput targets at the two users become closer to each other. This demonstrates that NOMA can significantly reduce the latency in the context of short-packet communications with practical constraints.
Exploring the bounds on the positive semidefinite rank
Venue: arXiv cs.CC 2017
Year: 2017

The nonnegative and positive semidefinite (PSD-) ranks are closely connected to the nonnegative and positive semidefinite extension complexities of a polytope, which are the minimal dimensions of linear and SDP programs which represent this polytope. Though some exponential lower bounds on the nonnegative and PSD- ranks has recently been proved for the slack matrices of some particular polytopes, there are still no tight bounds for these quantities. We explore some existing bounds on the PSD-rank and prove that they cannot give exponential lower bounds on the extension complexity. Our approach consists in proving that the existing bounds are upper bounded by the polynomials of the regular rank of the matrix, which is equal to the dimension of the polytope (up to an additive constant). As one of the implications, we also retrieve an upper bound on the mutual information of an arbitrary matrix of a joint distribution, based on its regular rank.
PQTable: Non-exhaustive Fast Search for Product-quantized Codes using Hash Tables
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we propose a product quantization table (PQTable); a fast search method for product-quantized codes via hash-tables. An identifier of each database vector is associated with the slot of a hash table by using its PQ-code as a key. For querying, an input vector is PQ-encoded and hashed, and the items associated with that code are then retrieved. The proposed PQTable produces the same results as a linear PQ scan, and is 10^2 to 10^5 times faster. Although state-of-the-art performance can be achieved by previous inverted-indexing-based approaches, such methods require manually-designed parameter setting and significant training; our PQTable is free of these limitations, and therefore offers a practical and effective solution for real-world problems. Specifically, when the vectors are highly compressed, our PQTable achieves one of the fastest search performances on a single CPU to date with significantly efficient memory usage (0.059 ms per query over 10^9 data points with just 5.5 GB memory consumption). Finally, we show that our proposed PQTable can naturally handle the codes of an optimized product quantization (OPQTable).
Path-contractions, edge deletions and connectivity preservation
Venue: arXiv cs.DS 2017
Year: 2017

We study several problems related to graph modification problems under connectivity constraints from the perspective of parameterized complexity: {\sc (Weighted) Biconnectivity Deletion}, where we are tasked with deleting~$k$ edges while preserving biconnectivity in an undirected graph, {\sc Vertex-deletion Preserving Strong Connectivity}, where we want to maintain strong connectivity of a digraph while deleting exactly~$k$ vertices, and {\sc Path-contraction Preserving Strong Connectivity}, in which the operation of path contraction on arcs is used instead. The parameterized tractability of this last problem was posed by Bang-Jensen and Yeo [DAM 2008] as an open question and we answer it here in the negative: both variants of preserving strong connectivity are $\sf W[1]$-hard. Preserving biconnectivity, on the other hand, turns out to be fixed parameter tractable and we provide a $2^{O(k\log k)} n^{O(1)}$-algorithm that solves {\sc Weighted Biconnectivity Deletion}. Further, we show that the unweighted case even admits a randomized polynomial kernel. All our results provide further interesting data points for the systematic study of connectivity-preservation constraints in the parameterized setting.
Markov Automata with Multiple Objectives
Venue: arXiv cs.LO 2017
Year: 2017

Markov automata combine non-determinism, probabilistic branching, and exponentially distributed delays. This compositional variant of continuous-time Markov decision processes is used in reliability engineering, performance evaluation and stochastic scheduling. Their verification so far focused on single objectives such as (timed) reachability, and expected costs. In practice, often the objectives are mutually dependent and the aim is to reveal trade-offs. We present algorithms to analyze several objectives simultaneously and approximate Pareto curves. This includes, e.g., several (timed) reachability objectives, or various expected cost objectives. We also consider combinations thereof, such as on-time-within-budget objectives - which policies guarantee reaching a goal state within a deadline with at least probability $p$ while keeping the allowed average costs below a threshold? We adopt existing approaches for classical Markov decision processes. The main challenge is to treat policies exploiting state residence times, even for untimed objectives. Experimental results show the feasibility and scalability of our approach.
Governing Governance: A Formal Framework for Analysing Institutional Design and Enactment Governance
Venue: arXiv cs.AI 2017
Year: 2017

This dissertation is motivated by the need, in today's globalist world, for a precise way to enable governments, organisations and other regulatory bodies to evaluate the constraints they place on themselves and others. An organisation's modus operandi is enacting and fulfilling contracts between itself and its participants. Yet, organisational contracts should respect external laws, such as those setting out data privacy rights and liberties. Contracts can only be enacted by following contract law processes, which often require bilateral agreement and consideration. Governments need to legislate whilst understanding today's context of national and international governance hierarchy where law makers shun isolationism and seek to influence one another. Governments should avoid punishment by respecting constraints from international treaties and human rights charters. Governments can only enact legislation by following their own, pre-existing, law making procedures. In other words, institutions, such as laws and contracts are designed and enacted under constraints.
Feature selection algorithm based on Catastrophe model to improve the performance of regression analysis
Venue: arXiv cs.LG 2017
Year: 2017

In this paper we introduce a new feature selection algorithm to remove the irrelevant or redundant features in the data sets. In this algorithm the importance of a feature is based on its fitting to the Catastrophe model. Akaike information crite- rion value is used for ranking the features in the data set. The proposed algorithm is compared with well-known RELIEF feature selection algorithm. Breast Cancer, Parkinson Telemonitoring data and Slice locality data sets are used to evaluate the model.
SREFI: Synthesis of Realistic Example Face Images
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we propose a novel face synthesis approach that can generate an arbitrarily large number of synthetic images of both real and synthetic identities. Thus a face image dataset can be expanded in terms of the number of identities represented and the number of images per identity using this approach, without the identity-labeling and privacy complications that come from downloading images from the web. To measure the visual fidelity and uniqueness of the synthetic face images and identities, we conducted face matching experiments with both human participants and a CNN pre-trained on a dataset of 2.6M real face images. To evaluate the stability of these synthetic faces, we trained a CNN model with an augmented dataset containing close to 200,000 synthetic faces. We used a snapshot of this trained CNN to recognize extremely challenging frontal (real) face images. Experiments showed training with the augmented faces boosted the face recognition performance of the CNN.