OpenRaiser/Intern-Atlas huggingface dataset:
Analytic Network Learning
Venue: arXiv cs.LG 2018
Year: 2018

Based on the property that solving the system of linear matrix equations via the column space and the row space projections boils down to an approximation in the least squares error sense, a formulation for learning the weight matrices of the multilayer network can be derived. By exploiting into the vast number of feasible solutions of these interdependent weight matrices, the learning can be performed analytically layer by layer without needing of gradient computation after an initialization. Possible initialization schemes include utilizing the data matrix as initial weights and random initialization. The study is followed by an investigation into the representation capability and the output variance of the learning scheme. An extensive experimentation on synthetic and real-world data sets validates its numerical feasibility.
A general framework for handling commitment in online throughput maximization
Venue: arXiv cs.DS 2018
Year: 2018

We study a fundamental online job admission problem where jobs with deadlines arrive online over time at their release dates, and the task is to determine a preemptive single-server schedule which maximizes the number of jobs that complete on time. To circumvent known impossibility results, we make a standard slackness assumption by which the feasible time window for scheduling a job is at least $1+\varepsilon$ times its processing time, for some $\varepsilon>0$. We quantify the impact that different provider commitment requirements have on the performance of online algorithms. Our main contribution is one universal algorithmic framework for online job admission both with and without commitments. Without commitment, our algorithm with a competitive ratio of $O(1/\varepsilon)$ is the best possible (deterministic) for this problem. For commitment models, we give the first non-trivial performance bounds. If the commitment decisions must be made before a job's slack becomes less than a $δ$-fraction of its size, we prove a competitive ratio of $O(\varepsilon/((\varepsilon-δ)δ^2))$, for $0<δ<\varepsilon$. When a provider must commit upon starting a job, our bound is $O(1/\varepsilon^2)$. Finally, we observe that for scheduling with commitment the restriction to the `unweighted' throughput model is essential; if jobs have individual weights, we rule out competitive deterministic algorithms.
A Deep Dive into Blockchain Selfish Mining
Venue: arXiv cs.CR 2018
Year: 2018

This paper studies a fundamental problem regarding the security of blockchain on how the existence of multiple misbehaving pools influences the profitability of selfish mining. Each selfish miner maintains a private chain and makes it public opportunistically for the purpose of acquiring more rewards incommensurate to his Hashrate. We establish a novel Markov chain model to characterize all the state transitions of public and private chains. The minimum requirement of Hashrate together with the minimum delay of being profitable is derived in close-form. The former reduces to 21.48% with the symmetric selfish miners, while their competition with asymmetric Hashrates puts forward a higher requirement of the profitable threshold. The profitable delay increases with the decrease of the Hashrate of selfish miners, making the mining pools more cautious on performing selfish mining.
Self-Organizing Maps for Storage and Transfer of Knowledge in Reinforcement Learning
Venue: arXiv cs.AI 2018
Year: 2018

The idea of reusing or transferring information from previously learned tasks (source tasks) for the learning of new tasks (target tasks) has the potential to significantly improve the sample efficiency of a reinforcement learning agent. In this work, we describe a novel approach for reusing previously acquired knowledge by using it to guide the exploration of an agent while it learns new tasks. In order to do so, we employ a variant of the growing self-organizing map algorithm, which is trained using a measure of similarity that is defined directly in the space of the vectorized representations of the value functions. In addition to enabling transfer across tasks, the resulting map is simultaneously used to enable the efficient storage of previously acquired task knowledge in an adaptive and scalable manner. We empirically validate our approach in a simulated navigation environment, and also demonstrate its utility through simple experiments using a mobile micro-robotics platform. In addition, we demonstrate the scalability of this approach, and analytically examine its relation to the proposed network growth mechanism. Further, we briefly discuss some of the possible improvements and extensions to this approach, as well as its relevance to real world scenarios in the context of continual learning.
Design and Analysis of Distributed State Estimation Algorithms Based on Belief Propagation and Applications in Smart Grids
Venue: arXiv cs.IT 2018
Year: 2018

We present a detailed study on application of factor graphs and the belief propagation (BP) algorithm to the power system state estimation (SE) problem. We start from the BP solution for the linear DC model, for which we provide a detailed convergence analysis. Using BP-based DC model we propose a fast real-time state estimator for the power system SE. The proposed estimator is easy to distribute and parallelize, thus alleviating computational limitations and allowing for processing measurements in real time. The presented algorithm may run as a continuous process. Using insights from the DC model, we use two different approaches to derive the BP algorithm for the non-linear model. The first method directly applies BP methodology, however, providing only approximate BP solution for the non-linear model. In the second approach, we make a key further step by providing the solution in which the BP is applied sequentially over the non-linear model, akin to what is done by the Gauss-Newton method. The resulting iterative Gauss-Newton belief propagation (GN-BP) algorithm can be interpreted as a distributed Gauss-Newton method with the same accuracy as the centralized SE.
On a hypergraph probabilistic graphical model
Venue: arXiv cs.DS 2018
Year: 2018

We propose a directed acyclic hypergraph framework for a probabilistic graphical model that we call Bayesian hypergraphs. The space of directed acyclic hypergraphs is much larger than the space of chain graphs. Hence Bayesian hypergraphs can model much finer factorizations than Bayesian networks or LWF chain graphs and provide simpler and more computationally efficient procedures for factorizations and interventions. Bayesian hypergraphs also allow a modeler to represent causal patterns of interaction such as Noisy-OR graphically (without additional annotations). We introduce global, local and pairwise Markov properties of Bayesian hypergraphs and prove under which conditions they are equivalent. We define a projection operator, called shadow, that maps Bayesian hypergraphs to chain graphs, and show that the Markov properties of a Bayesian hypergraph are equivalent to those of its corresponding chain graph. We extend the causal interpretation of LWF chain graphs to Bayesian hypergraphs and provide corresponding formulas and a graphical criterion for intervention.
Shape-only Features for Plant Leaf Identification
Venue: arXiv cs.CV 2018
Year: 2018

This paper presents a novel feature set for shape-only leaf identification motivated by real-world, mobile deployment. The feature set includes basic shape features, as well as signal features extracted from local area integral invariants (LAIIs), similar to curvature maps, at multiple scales. The proposed methodology is evaluated on a number of publicly available leaf datasets with comparable results to existing methods which make use of colour and texture features in addition to shape. Over 90% classification accuracy is achieved on most datasets, with top-four accuracy for these datasets reaching over 98%. Rotation and scale invariance of the proposed features are demonstrated, along with an evaluation of the generalisability of the approach for generic shape matching.
Fading of collective attention shapes the evolution of linguistic variants
Venue: arXiv cs.CL 2018
Year: 2018

Language change involves the competition between alternative linguistic forms (1). The spontaneous evolution of these forms typically results in monotonic growths or decays (2, 3) like in winner-take-all attractor behaviors. In the case of the Spanish past subjunctive, the spontaneous evolution of its two competing forms (ended in -ra and -se) was perturbed by the appearance of the Royal Spanish Academy in 1713, which enforced the spelling of both forms as perfectly interchangeable variants (4), at a moment in which the -ra form was dominant (5). Time series extracted from a massive corpus of books (6) reveal that this regulation in fact produced a transient renewed interest for the old form -se which, once faded, left the -ra again as the dominant form up to the present day. We show that time series are successfully explained by a two-dimensional linear model that integrates an imitative and a novelty component. The model reveals that the temporal scale over which collective attention fades is in inverse proportion to the verb frequency. The integration of the two basic mechanisms of imitation and attention to novelty allows to understand diverse competing objects, with lifetimes that range from hours for memes and news (7, 8) to decades for verbs, suggesting the existence of a general mechanism underlying cultural evolution.
Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark
Venue: arXiv cs.SE 2018
Year: 2018

Repackaging is a serious threat to the Android ecosystem as it deprives app developers of their benefits, contributes to spreading malware on users' devices, and increases the workload of market maintainers. In the space of six years, the research around this specific issue has produced 57 approaches which do not readily scale to millions of apps or are only evaluated on private datasets without, in general, tool support available to the community. Through a systematic literature review of the subject, we argue that the research is slowing down, where many state-of-the-art approaches have reported high-performance rates on closed datasets, which are unfortunately difficult to replicate and to compare against. In this work, we propose to reboot the research in repackaged app detection by providing a literature review that summarises the challenges and current solutions for detecting repackaged apps and by providing a large dataset that supports replications of existing solutions and implications of new research directions. We hope that these contributions will re-activate the direction of detecting repackaged apps and spark innovative approaches going beyond the current state-of-the-art.
A Novel Integrated Framework for Learning both Text Detection and Recognition
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we propose a novel integrated framework for learning both text detection and recognition. For most of the existing methods, detection and recognition are treated as two isolated tasks and trained separately, since parameters of detection and recognition models are different and two models target to optimize their own loss functions during individual training processes. In contrast to those methods, by sharing model parameters, we merge the detection model and recognition model into a single end-to-end trainable model and train the joint model for two tasks simultaneously. The shared parameters not only help effectively reduce the computational load in inference process, but also improve the end-to-end text detection-recognition accuracy. In addition, we design a simpler and faster sequence learning method for the recognition network based on a succession of stacked convolutional layers without any recurrent structure, this is proved feasible and dramatically improves inference speed. Extensive experiments on different datasets demonstrate that the proposed method achieves very promising results.
Benchmarking Inverse Rashba-Edelstein Magnetoelectric Devices for Neuromorphic Computing
Venue: arXiv cs.ET 2018
Year: 2018

We propose a new design for a cellular neural network with spintronic neurons and CMOS-based synapses. Harnessing the magnetoelectric and inverse Rashba-Edelstein effects allows natural emulation of the behavior of an ideal cellular network. This combination of effects offers an increase in speed and efficiency over other spintronic neural networks. A rigorous performance analysis via simulation is provided.
A Deep Tree-Structured Fusion Model for Single Image Deraining
Venue: arXiv cs.CV 2018
Year: 2018

We propose a simple yet effective deep tree-structured fusion model based on feature aggregation for the deraining problem. We argue that by effectively aggregating features, a relatively simple network can still handle tough image deraining problems well. First, to capture the spatial structure of rain we use dilated convolutions as our basic network block. We then design a tree-structured fusion architecture which is deployed within each block (spatial information) and across all blocks (content information). Our method is based on the assumption that adjacent features contain redundant information. This redundancy obstructs generation of new representations and can be reduced by hierarchically fusing adjacent features. Thus, the proposed model is more compact and can effectively use spatial and content information. Experiments on synthetic and real-world datasets show that our network achieves better deraining results with fewer parameters.
Retina U-Net: Embarrassingly Simple Exploitation of Segmentation Supervision for Medical Object Detection
Venue: arXiv cs.CV 2018
Year: 2018

The task of localizing and categorizing objects in medical images often remains formulated as a semantic segmentation problem. This approach, however, only indirectly solves the coarse localization task by predicting pixel-level scores, requiring ad-hoc heuristics when mapping back to object-level scores. State-of-the-art object detectors on the other hand, allow for individual object scoring in an end-to-end fashion, while ironically trading in the ability to exploit the full pixel-wise supervision signal. This can be particularly disadvantageous in the setting of medical image analysis, where data sets are notoriously small. In this paper, we propose Retina U-Net, a simple architecture, which naturally fuses the Retina Net one-stage detector with the U-Net architecture widely used for semantic segmentation in medical images. The proposed architecture recaptures discarded supervision signals by complementing object detection with an auxiliary task in the form of semantic segmentation without introducing the additional complexity of previously proposed two-stage detectors. We evaluate the importance of full segmentation supervision on two medical data sets, provide an in-depth analysis on a series of toy experiments and show how the corresponding performance gain grows in the limit of small data sets. Retina U-Net yields strong detection performance only reached by its more complex two-staged counterparts. Our framework including all methods implemented for operation on 2D and 3D images is available at github.com/pfjaeger/medicaldetectiontoolkit.
On the Proximity of Markets with Integral Equilibria
Venue: arXiv cs.GT 2018
Year: 2018

We study Fisher markets that admit equilibria wherein each good is integrally assigned to some agent. While strong existence and computational guarantees are known for equilibria of Fisher markets with additive valuations, such equilibria, in general, assign goods fractionally to agents. Hence, Fisher markets are not directly applicable in the context of indivisible goods. In this work we show that one can always bypass this hurdle and, up to a bounded change in agents' budgets, obtain markets that admit an integral equilibrium. We refer to such markets as pure markets and show that, for any given Fisher market (with additive valuations), one can efficiently compute a "near-by," pure market with an accompanying integral equilibrium. Our work on pure markets leads to novel algorithmic results for fair division of indivisible goods. Prior work in discrete fair division has shown that, under additive valuations, there always exist allocations that simultaneously achieve the seemingly incompatible properties of fairness and efficiency; here fairness refers to envy-freeness up to one good (EF1) and efficiency corresponds to Pareto efficiency. However, polynomial-time algorithms are not known for finding such allocations. Considering relaxations of proportionality and EF1, respectively, as our notions of fairness, we show that fair and Pareto efficient allocations can be computed in strongly polynomial time.
Equality of Voice: Towards Fair Representation in Crowdsourced Top-K Recommendations
Venue: arXiv cs.SI 2018
Year: 2018

To help their users to discover important items at a particular time, major websites like Twitter, Yelp, TripAdvisor or NYTimes provide Top-K recommendations (e.g., 10 Trending Topics, Top 5 Hotels in Paris or 10 Most Viewed News Stories), which rely on crowdsourced popularity signals to select the items. However, different sections of a crowd may have different preferences, and there is a large silent majority who do not explicitly express their opinion. Also, the crowd often consists of actors like bots, spammers, or people running orchestrated campaigns. Recommendation algorithms today largely do not consider such nuances, hence are vulnerable to strategic manipulation by small but hyper-active user groups. To fairly aggregate the preferences of all users while recommending top-K items, we borrow ideas from prior research on social choice theory, and identify a voting mechanism called Single Transferable Vote (STV) as having many of the fairness properties we desire in top-K item (s)elections. We develop an innovative mechanism to attribute preferences of silent majority which also make STV completely operational. We show the generalizability of our approach by implementing it on two different real-world datasets. Through extensive experimentation and comparison with state-of-the-art techniques, we show that our proposed approach provides maximum user satisfaction, and cuts down drastically on items disliked by most but hyper-actively promoted by a few users.
University-industry collaboration in Italy: a bibliometric examination
Venue: arXiv cs.DL 2018
Year: 2018

This work investigates public-private research collaboration between Italian universities and domestic industry, applying a bibliometric type of approach. The study is based on an exhaustive listing of all co-authored publications in international journals that are jointly realized by Italian university scientists and researchers in the private sector: this listing permits the development of a national mapping system for public-private collaboration, which results unique for its extensive and representative character. It is shown that, in absolute terms, most collaborations occur in medicine and chemistry, while it is industrial and information engineering which shows the highest percentage of co-authored articles out of all articles in the field. In addition, the investigation empirically examines and tests several hypotheses concerning the qualitative-quantitative impact of collaboration on the scientific production of individual university researchers. The analyses demonstrate that university researchers who collaborate with those in the private sector show research performance that is superior to that of colleagues who are not involved in such collaboration. But the impact factor of journals publishing academic articles co-authored by industry is generally lower than that concerning co-authorships with other entities. Finally, a further specific elaboration also reveals that publications with public-private co-authorship do not show a level of multidisciplinarity that is significantly different than that of other publications.
MATMPC - A MATLAB Based Toolbox for Real-time Nonlinear Model Predictive Control
Venue: arXiv cs.SY 2018
Year: 2018

In this paper we introduce MATMPC, an open source software built in MATLAB for nonlinear model predictive control (NMPC). It is designed to facilitate modelling, controller design and simulation for a wide class of NMPC applications. MATMPC has a number of algorithmic modules, including automatic differentiation, direct multiple shooting, condensing, linear quadratic program (QP) solver and globalization. It also supports a unique Curvature-like Measure of Nonlinearity (CMoN) MPC algorithm. MATMPC has been designed to provide state-of-the-art performance while making the prototyping easy, also with limited programming knowledge. This is achieved by writing each module directly in MATLAB API for C. As a result, MATMPC modules can be compiled into MEX functions with performance comparable to plain C/C++ solvers. MATMPC has been successfully used in operating systems including WINDOWS, LINUX AND OS X. Selected examples are shown to highlight the effectiveness of MATMPC.
Tablet-based Information System for Commercial Air-craft: Onboard Context-Sensitive Information System (OCSIS)
Venue: arXiv cs.HC 2018
Year: 2018

Pilots currently use paper-based documentation and electronic systems to help them perform procedures to ensure safety, efficiency and comfort on commercial aircrafts. Management of interconnections among paper-based operational documents can be a challenge for pilots, especially when time pressure is high in normal, abnormal, and emergency situations. This dissertation is a contribution to the design of an Onboard Context-Sensitive Information System (OCSIS), which was developed on a tablet. The claim is that the use of con-textual information facilitates access to appropriate operational content at the right time either automatically or on demand. OCSIS was tested using human-in-the-loop simulations that involved professional pilots in the Airbus 320 cockpit simulator. First results are encouraging that show OCSIS can be usable and useful for operational information access. More specifically, context-sensitivity contributes to simplify this access (i.e., appropriate operational information is provided at the right time in the right format. In addition, OCSIS provides other features that paper-based documents do not have, such as procedure execution status after an interruption. Also, the fact that several calculations are automatically done by OCSIS tends to decrease the pilot's task demand .
CARAVAN: a framework for comprehensive simulations on massive parallel machines
Venue: arXiv cs.DC 2018
Year: 2018

We present a software framework called CARAVAN, which was developed for comprehensive simulations on massive parallel computers. The framework runs user-developed simulators with various input parameters in parallel without requiring the knowledge of parallel programming. The framework is useful for exploring high-dimensional parameter spaces, for which sampling points must be dynamically determined based on the previous results. Possible use cases include optimization, data assimilation, and Markov-chain Monte Carlo sampling in parameter spaces. As a demonstration, we applied CARAVAN to an evacuation planning problem in an urban area. We formulated the problem as a multi-objective optimization problem, and searched for solutions using multi-agent simulations and a multi-objective evolutionary algorithm, which were developed as modules of the framework.