OpenRaiser/Intern-Atlas huggingface dataset:
Exploiting Equitable Partitions for Efficient Block Triangularization
Venue: arXiv cs.DM 2016
Year: 2016

In graph theory a partition of the vertex set of a graph is called equitable if for all pairs of cells all vertices in one cell have an equal number of neighbours in the other cell. Considering the implications for the adjacency matrix one may generalize that concept as a block partition of a complex square matrix s.t. each block has constant row sum. It is well known that replacing each block by its row sum yields a smaller matrix whose multiset of eigenvalues is contained in the initial spectrum. We generalize this approach to weighted row sums and rectangular matrices and derive an efficient unitary transformation which approximately block triangularizes a matrix w.r.t. an arbitrary partition. Singular values and Hermiticity (if present) are preserved. The approximation is exact in the equitable case and the error can be bounded in terms of unitarily invariant matrix norms.
Interactive Debugging of Knowledge Bases
Venue: arXiv cs.AI 2016
Year: 2016

Many AI applications rely on knowledge about a relevant real-world domain that is encoded by means of some logical knowledge base (KB). The most essential benefit of logical KBs is the opportunity to perform automatic reasoning to derive implicit knowledge or to answer complex queries about the modeled domain. The feasibility of meaningful reasoning requires KBs to meet some minimal quality criteria such as logical consistency. Without adequate tool assistance, the task of resolving violated quality criteria in KBs can be extremely tough even for domain experts, especially when the problematic KB includes a large number of logical formulas or comprises complicated logical formalisms. Published non-interactive debugging systems often cannot localize all possible faults (incompleteness), suggest the deletion or modification of unnecessarily large parts of the KB (non-minimality), return incorrect solutions which lead to a repaired KB not satisfying the imposed quality requirements (unsoundness) or suffer from poor scalability due to the inherent complexity of the KB debugging problem. Even if a system is complete and sound and considers only minimal solutions, there are generally exponentially many solution candidates to select one from. However, any two repaired KBs obtained from these candidates differ in their semantics in terms of entailments and non-entailments. Selection of just any of these repaired KBs might result in unexpected entailments, the loss of desired entailments or unwanted changes to the KB. This work proposes complete, sound and optimal methods for the interactive debugging of KBs that suggest the one (minimally invasive) error correction of the faulty KB that yields a repaired KB with exactly the intended semantics. Users, e.g. domain experts, are involved in the debugging process by answering automatically generated queries about the intended domain.
Performance Analysis of Joint Time Delay and Doppler-Stretch Estimation with Random Stepped-Frequency Signals
Venue: arXiv cs.IT 2016
Year: 2016

This paper investigates the performance of joint time delay and Doppler-stretch estimation with the random stepp ed-frequency (RSF) signal. Applying the ambiguity function (AF) to implement the estimation, we derive the compact expressions of the theoretical mean square errors (MSEs) under high signal-to-noise ratios (SNRs). The obtained MSEs are shown consistent with the corresponding Cramer-Rao lower bounds (CRLBs), implying that the AF-based estimation is approximately efficient. Waveform parameters including higher carrier frequencies, wider bandwidth covered by the carrier frequencies, and frequency shifting codewords with larger variance are expected for a better estimation performance. As a synthetic wideband signal, the RSF signal achieves the same estimation performance as the OFDM signal within an identical bandwidth. Due to its instantaneous narrowband character, requirement for the bandwidth of the receiver is much reduced.
Philosophy in the Face of Artificial Intelligence
Venue: arXiv cs.AI 2016
Year: 2016

In this article, I discuss how the AI community views concerns about the emergence of superintelligent AI and related philosophical issues.
One-shot Learning with Memory-Augmented Neural Networks
Venue: arXiv cs.LG 2016
Year: 2016

Despite recent breakthroughs in the applications of deep neural networks, one setting that presents a persistent challenge is that of "one-shot learning." Traditional gradient-based networks require a lot of data to learn, often through extensive iterative training. When new data is encountered, the models must inefficiently relearn their parameters to adequately incorporate the new information without catastrophic interference. Architectures with augmented memory capacities, such as Neural Turing Machines (NTMs), offer the ability to quickly encode and retrieve new information, and hence can potentially obviate the downsides of conventional models. Here, we demonstrate the ability of a memory-augmented neural network to rapidly assimilate new data, and leverage this data to make accurate predictions after only a few samples. We also introduce a new method for accessing an external memory that focuses on memory content, unlike previous methods that additionally use memory location-based focusing mechanisms.
Striations in PageRank-Ordered Matrices
Venue: arXiv cs.SI 2016
Year: 2016

Patterns often appear in a variety of large, real-world networks, and interesting physical phenomena are often explained by network topology as in the case of the bow-tie structure of the World Wide Web, or the small world phenomenon in social networks. The discovery and modelling of such regular patterns has a wide application from disease propagation to financial markets. In this work we describe a newly discovered regularly occurring striation pattern found in the PageRank ordering of adjacency matrices that encode real-world networks. We demonstrate that these striations are the result of well-known graph generation processes resulting in regularities that are manifest in the typical neighborhood distribution. The spectral view explored in this paper encodes a tremendous amount about the explicit and implicit topology of a given network, so we also discuss the interesting network properties, outliers and anomalies that a viewer can determine from a brief look at the re-ordered matrix.
Shaping Pulses to Control Bistable Monotone Systems Using Koopman Operator
Venue: arXiv cs.SY 2016
Year: 2016

In this paper, we further develop a recently proposed control method to switch a bistable system between its steady states using temporal pulses. The motivation for using pulses comes from biomedical and biological applications (e.g. synthetic biology), where it is generally difficult to build feedback control systems due to technical limitations in sensing and actuation. The original framework was derived for monotone systems and all the extensions relied on monotone systems theory. In contrast, we introduce the concept of switching function which is related to eigenfunctions of the so-called Koopman operator subject to a fixed control pulse. Using the level sets of the switching function we can (i) compute the set of all pulses that drive the system toward the steady state in a synchronous way and (ii) estimate the time needed by the flow to reach an epsilon neighborhood of the target steady state. Additionally, we show that for monotone systems the switching function is also monotone in some sense, a property that can yield efficient algorithms to compute it. This observation recovers and further extends the results of the original framework, which we illustrate on numerical examples inspired by biological applications.
Evolution Patterns: Designing and Reusing Architectural Evolution Knowledge to Introduce Architectural Styles
Venue: arXiv cs.SE 2016
Year: 2016

Software architectures are critical in the successful development and evolution of software-intensive systems. While formal and automated support for architectural descriptions has been widely addressed, their evolution is equally crucial, but significantly less well-understood and supported. In order to face a recurring evolution need, we introduce the concept of evolution pattern. It formalises an architectural evolution through both a set of concepts and a reusable evolution process. We propose it through the recurring need of introducing an architectural style on existing software architectures. We formally describe and analyse the feasibility of architectural evolution patterns, and provide a practical validation by implementing them in COSABuilder, an Eclipse plugin for the COSA architectural description language.
Modeling Evolutionary Dynamics of Lurking in Social Networks
Venue: arXiv cs.SI 2016
Year: 2016

Lurking is a complex user-behavioral phenomenon that occurs in all large-scale online communities and social networks. It generally refers to the behavior characterizing users that benefit from the information produced by others in the community without actively contributing back to the production of social content. The amount and evolution of lurkers may strongly affect an online social environment, therefore understanding the lurking dynamics and identifying strategies to curb this trend are relevant problems. In this regard, we introduce the Lurker Game, i.e., a model for analyzing the transitions from a lurking to a non-lurking (i.e., active) user role, and vice versa, in terms of evolutionary game theory. We evaluate the proposed Lurker Game by arranging agents on complex networks and analyzing the system evolution, seeking relations between the network topology and the final equilibrium of the game. Results suggest that the Lurker Game is suitable to model the lurking dynamics, showing how the adoption of rewarding mechanisms combined with the modeling of hypothetical heterogeneity of users' interests may lead users in an online community towards a cooperative behavior.
Browser Feature Usage on the Modern Web
Venue: arXiv cs.NI 2016
Year: 2016

Modern web browsers are incredibly complex, with millions of lines of code and over one thousand JavaScript functions and properties available to website authors. This work investigates how these browser features are used on the modern, open web. We find that JavaScript features differ wildly in popularity, with over 50% of provided features never used in the Alexa 10k. We also look at how popular ad and tracking blockers change the distribution of features used by sites, and identify a set of approximately 10% of features that are disproportionately blocked (prevented from executing by these extensions at least 90% of the time they are used). We additionally find that in the presence of these blockers, over 83% of available features are executed on less than 1% of the most popular 10,000 websites. We additionally measure a variety of aspects of browser feature usage on the web, including how complex sites have become in terms of feature usage, how the length of time a browser feature has been in the browser relates to its usage on the web, and how many security vulnerabilities have been associated with related browser features.
Potential mass surveillance and privacy violations in proximity-based social applications
Venue: arXiv cs.CR 2016
Year: 2016

Proximity-based social applications let users interact with people that are currently close to them, by revealing some information about their preferences and whereabouts. This information is acquired through passive geo-localisation and used to build a sense of serendipitous discovery of people, places and interests. Unfortunately, while this class of applications opens different interactions possibilities for people in urban settings, obtaining access to certain identity information could lead a possible privacy attacker to identify and follow a user in their movements in a specific period of time. The same information shared through the platform could also help an attacker to link the victim's online profiles to physical identities. We analyse a set of popular dating application that shares users relative distances within a certain radius and show how, by using the information shared on these platforms, it is possible to formalise a multilateration attack, able to identify the user actual position. The same attack can also be used to follow a user in all their movements within a certain period of time, therefore identifying their habits and Points of Interest across the city. Furthermore we introduce a social attack which uses common Facebook likes to profile a person and finally identify their real identity.
You never surf alone. Ubiquitous tracking of users' browsing habits
Venue: arXiv cs.CY 2016
Year: 2016

In the early age of the internet users enjoyed a large level of anonymity. At the time web pages were just hypertext documents; almost no personalisation of the user experience was o ered. The Web today has evolved as a world wide distributed system following specific architectural paradigms. On the web now, an enormous quantity of user generated data is shared and consumed by a network of applications and services, reasoning upon users expressed preferences and their social and physical connections. Advertising networks follow users' browsing habits while they surf the web, continuously collecting their traces and surfing patterns. We analyse how users tracking happens on the web by measuring their online footprint and estimating how quickly advertising networks are able to pro le users by their browsing habits.
Evaluating Power System Vulnerability to False Data Injection Attacks via Scalable Optimization
Venue: arXiv cs.SY 2016
Year: 2016

Physical consequences to power systems of false data injection cyber-attacks are considered. Prior work has shown that the worst-case consequences of such an attack can be determined using a bi-level optimization problem, wherein an attack is chosen to maximize the physical power flow on a target line subsequent to re-dispatch. This problem can be solved as a mixed-integer linear program, but it is difficult to scale to large systems due to numerical challenges. Three new computationally efficient algorithms to solve this problem are presented. These algorithms provide lower and upper bounds on the system vulnerability measured as the maximum power flow subsequent to an attack. Using these techniques, vulnerability assessments are conducted for IEEE 118-bus system and Polish system with 2383 buses.
Adaptive Algorithm and Platform Selection for Visual Detection and Tracking
Venue: arXiv cs.CV 2016
Year: 2016

Computer vision algorithms are known to be extremely sensitive to the environmental conditions in which the data is captured, e.g., lighting conditions and target density. Tuning of parameters or choosing a completely new algorithm is often needed to achieve a certain performance level, especially when there is a limitation of the computation source. In this paper, we focus on this problem and propose a framework to adaptively select the "best" algorithm-parameter combination and the computation platform under performance and cost constraints at design time, and adapt the algorithms at runtime based on real-time inputs. This necessitates developing a mechanism to switch between different algorithms as the nature of the input video changes. Our proposed algorithm calculates a similarity function between a test video scenario and each training scenario, where the similarity calculation is based on learning a manifold of image features that is shared by both the training and test datasets. Similarity between training and test dataset indicates the same algorithm can be applied to both of them and achieve similar performance. We design a cost function with this similarity measure to find the most similar training scenario to the test data. The "best" algorithm under a given platform is obtained by selecting the algorithm with a specific parameter combination that performs the best on the corresponding training data. The proposed framework can be used first offline to choose the platform based on performance and cost constraints, and then online whereby the "best" algorithm is selected for each new incoming video segment for a given platform. In the experiments, we apply our algorithm to the problems of pedestrian detection and tracking. We show how to adaptively select platforms and algorithm-parameter combinations. Our results provide optimal performance on 3 publicly available datasets.
Mitigating Redundant Data Transfers for Mobile Web Applications via App-Specific Cache Space
Venue: arXiv cs.SE 2016
Year: 2016

Redundant transfer of resources is a critical issue for compromising the performance of mobile Web applications (a.k.a., apps) in terms of data traffic, load time, and even energy consumption. Evidence shows that the current cache mechanisms are far from satisfactory. With lessons learned from how native apps manage their resources, in this paper, we propose the ReWAP approach to fundamentally reducing redundant transfers by restructuring the resource loading of mobile Web apps. ReWAP is based on an efficient mechanism of resource packaging where stable resources are encapsulated and maintained into a package, and such a package shall be loaded always from the local storage and updated by explicitly refreshing. By retrieving and analyzing the update of resources, ReWAP maintains resource packages that can accurately identify which resources can be loaded from the local storage for a considerably long period. ReWAP also provides a wrapper for mobile Web apps to enable loading and updating resource packages in the local storage as well as loading resources from resource packages. ReWAP can be easily and seamlessly deployed into existing mobile Web architectures with minimal modifications, and is transparent to end-users. We evaluate ReWAP based on continuous 15-day access traces of 50 mobile Web apps that suffer heavily from the problem of redundant transfers. Compared to the original mobile Web apps with cache enabled, ReWAP can significantly reduce the data traffic, with the median saving up to 51%. In addition, ReWAP can incur only very minor runtime overhead of the client-side browsers.
Fine-to-coarse Knowledge Transfer For Low-Res Image Classification
Venue: arXiv cs.CV 2016
Year: 2016

We address the difficult problem of distinguishing fine-grained object categories in low resolution images. Wepropose a simple an effective deep learning approach that transfers fine-grained knowledge gained from high resolution training data to the coarse low-resolution test scenario. Such fine-to-coarse knowledge transfer has many real world applications, such as identifying objects in surveillance photos or satellite images where the image resolution at the test time is very low but plenty of high resolution photos of similar objects are available. Our extensive experiments on two standard benchmark datasets containing fine-grained car models and bird species demonstrate that our approach can effectively transfer fine-detail knowledge to coarse-detail imagery.
Automatic Detection of Epileptiform Discharges in the EEG
Venue: arXiv cs.CV 2016
Year: 2016

The diagnosis of epilepsy generally includes a visual inspection of EEG recorded data by the Neurologist, with the purpose of checking the occurrence of transient waveforms called interictal epileptiform discharges. These waveforms have short duration (less than 100 ms), so the inspection process is usually time-consuming, particularly for ambulatory long term EEG records. Therefore, an automatic detection system of epileptiform discharges can be a valuable tool for a Neurology service. The proposed approach is the development of a multi stage detection algorithm, which processes the complete EEG signals and applies decision criteria to selected waveforms. It employs EEG analysis techniques such as Wavelet Transform and Mimetic Analysis, complemented with a classification based on Fuzzy Logic. In order to evaluate the algorithm's performance, data were collected from several epileptic patients, with epileptiform activity marked by a Neurologist. The average values obtained for both Sensitivity and Specificity were respectively higher than 80 and 70 percent.
Chess Player by Co-Evolutionary Algorithm
Venue: arXiv cs.NE 2016
Year: 2016

A co-evolutionary algorithm (CA) based chess player is presented. Implementation details of the algorithms, namely coding, population, variation operators are described. The alpha-beta or mini-max like behaviour of the player is achieved through two competitive or cooperative populations. Special attention is given to the fitness function evaluation (the heart of the solution). Test results on algorithms vs. algorithms or human player is provided.
Evolutionary Demographic Algorithms
Venue: arXiv cs.NE 2016
Year: 2016

Most of the problems in genetic algorithms are very complex and demand a large amount of resources that current technology can not offer. Our purpose was to develop a Java-JINI distributed library that implements Genetic Algorithms with sub-populations (coarse grain) and a graphical interface in order to configure and follow the evolution of the search. The sub-populations are simulated/evaluated in personal computers connected trough a network, keeping in mind different models of sub-populations, migration policies and network topologies. We show that this model delays the convergence of the population keeping a higher level of genetic diversity and allows a much greater number of evaluations since they are distributed among several computers compared with the traditional Genetic Algorithms.
The Game-Theoretic Formation of Interconnections Between Networks
Venue: arXiv cs.GT 2016
Year: 2016

We introduce a network design game where the objective of the players is to design the interconnections between the nodes of two different networks $G_1$ and $G_2$ in order to maximize certain local utility functions. In this setting, each player is associated with a node in $G_1$ and has functional dependencies on certain nodes in $G_2$. We use a distance-based utility for the players in which the goal of each player is to purchase a set of edges (incident to its associated node) such that the sum of the distances between its associated node and the nodes it depends on in $G_2$ is minimized. We consider a heterogeneous set of players (i.e., players have their own costs and benefits for constructing edges). We show that finding a best response of a player in this game is NP-hard. Despite this, we characterize some properties of the best response actions which are helpful in determining a Nash equilibrium for certain instances of this game. In particular, we prove existence of pure Nash equilibria in this game when $G_2$ contains a star subgraph, and provide an algorithm that outputs such an equilibrium for any set of players. Finally, we show that the price of anarchy in this game can be arbitrarily large.