OpenRaiser/Intern-Atlas huggingface dataset:
Tiers for peers: a practical algorithm for discovering hierarchy in weighted networks
Venue: arXiv cs.DS 2019
Year: 2019

Interactions in many real-world phenomena can be explained by a strong hierarchical structure. Typically, this structure or ranking is not known; instead we only have observed outcomes of the interactions, and the goal is to infer the hierarchy from these observations. Discovering a hierarchy in the context of directed networks can be formulated as follows: given a graph, partition vertices into levels such that, ideally, there are only edges from upper levels to lower levels. The ideal case can only happen if the graph is acyclic. Consequently, in practice we have to introduce a penalty function that penalizes edges violating the hierarchy. A practical variant for such penalty is agony, where each violating edge is penalized based on the severity of the violation. Hierarchy minimizing agony can be discovered in $O(m^2)$ time, and much faster in practice. In this paper we introduce several extensions to agony. We extend the definition for weighted graphs and allow a cardinality constraint that limits the number of levels. While, these are conceptually trivial extensions, current algorithms cannot handle them, nor they can be easily extended. We solve the problem by showing the connection to the capacitated circulation problem, and we demonstrate that we can compute the exact solution fast in practice for large datasets. We also introduce a provably fast heuristic algorithm that produces rankings with competitive scores. In addition, we show that we can compute agony in polynomial time for any convex penalty, and, to complete the picture, we show that minimizing hierarchy with any concave penalty is an NP-hard problem.
On the Density of Context-Free and Counter Languages
Venue: arXiv cs.FL 2019
Year: 2019

A language $L$ is said to be dense if every word in the universe is an infix of some word in $L$. This notion has been generalized from the infix operation to arbitrary word operations $\varrho$ in place of the infix operation ($\varrho$-dense, with infix-dense being the standard notion of dense). It is shown here that it is decidable, for a language $L$ accepted by a one-way nondeterministic reversal-bounded pushdown automaton, whether $L$ is infix-dense. However, it becomes undecidable for both deterministic pushdown automata (with no reversal-bound), and for nondeterministic one-counter automata. When examining suffix-density, it is undecidable for more restricted families such as deterministic one-counter automata that make three reversals on the counter, but it is decidable with less reversals. Other decidability results are also presented on dense languages, and contrasted with a marked version called $\varrho$-marked-density. Also, new languages are demonstrated to be outside various deterministic language families after applying different deletion operations from smaller families. Lastly, bounded-dense languages are defined and examined.
Performance study of distributed Apriori-like frequent itemsets mining
Venue: arXiv cs.LG 2019
Year: 2019

In this article, we focus on distributed Apriori-based frequent itemsets mining. We present a new distributed approach which takes into account inherent characteristics of this algorithm. We study the distribution aspect of this algorithm and give a comparison of the proposed approach with a classical Apriori-like distributed algorithm, using both analytical and experimental studies. We find that under a wide range of conditions and datasets, the performance of a distributed Apriori-like algorithm is not related to global strategies of pruning since the performance of the local Apriori generation is usually characterized by relatively high success rates of candidate sets frequency at low levels which switch to very low rates at some stage, and often drops to zero. This means that the intermediate communication steps and remote support counts computation and collection in classical distributed schemes are computationally inefficient locally, and then constrains the global performance. Our performance evaluation is done on a large cluster of workstations using the Condor system and its workflow manager DAGMan. The results show that the presented approach greatly enhances the performance and achieves good scalability compared to a typical distributed Apriori founded algorithm.
Attack Type Agnostic Perceptual Enhancement of Adversarial Images
Venue: arXiv cs.CV 2019
Year: 2019

Adversarial images are samples that are intentionally modified to deceive machine learning systems. They are widely used in applications such as CAPTHAs to help distinguish legitimate human users from bots. However, the noise introduced during the adversarial image generation process degrades the perceptual quality and introduces artificial colours; making it also difficult for humans to classify images and recognise objects. In this letter, we propose a method to enhance the perceptual quality of these adversarial images. The proposed method is attack type agnostic and could be used in association with the existing attacks in the literature. Our experiments show that the generated adversarial images have lower Euclidean distance values while maintaining the same adversarial attack performance. Distances are reduced by 5.88% to 41.27% with an average reduction of 22% over the different attack and network types.
Label Embedded Dictionary Learning for Image Classification
Venue: arXiv cs.CV 2019
Year: 2019

Recently, label consistent k-svd (LC-KSVD) algorithm has been successfully applied in image classification. The objective function of LC-KSVD is consisted of reconstruction error, classification error and discriminative sparse codes error with L0-norm sparse regularization term. The L0-norm, however, leads to NP-hard problem. Despite some methods such as orthogonal matching pursuit can help solve this problem to some extent, it is quite difficult to find the optimum sparse solution. To overcome this limitation, we propose a label embedded dictionary learning (LEDL) method to utilise the L1-norm as the sparse regularization term so that we can avoid the hard-to-optimize problem by solving the convex optimization problem. Alternating direction method of multipliers and blockwise coordinate descent algorithm are then exploited to optimize the corresponding objective function. Extensive experimental results on six benchmark datasets illustrate that the proposed algorithm has achieved superior performance compared to some conventional classification algorithms.
Linear quadratic regulation of polytopic time-inhomogeneous Markov jump linear systems (extended version)
Venue: arXiv cs.SY 2019
Year: 2019

In most real cases transition probabilities between operational modes of Markov jump linear systems cannot be computed exactly and are time-varying. We take into account this aspect by considering Markov jump linear systems where the underlying Markov chain is polytopic and time-inhomogeneous, i.e. its transition probability matrix is varying over time, with variations that are arbitrary within a polytopic set of stochastic matrices. We address and solve for this class of systems the infinite-horizon optimal control problem. In particular, we show that the optimal controller can be obtained from a set of coupled algebraic Riccati equations, and that for mean square stabilizable systems the optimal finite-horizon cost corresponding to the solution to a parsimonious set of coupled difference Riccati equations converges exponentially fast to the optimal infinite-horizon cost related to the set of coupled algebraic Riccati equations. All the presented concepts are illustrated on a numerical example showing the efficiency of the provided solution.
Dynamic Anonymized Evaluation for Behavioral Continuous Authentication
Venue: arXiv cs.CR 2019
Year: 2019

Emerging technology demands reliable authentication mechanisms, particularly in interconnected systems. Current systems rely on a single moment of authentication, however continuous authentication systems assess a users identity utilizing a constant biometric analysis. Spy Hunter, a continuous authentication mechanism uses keystroke dynamics to validate users over blocks of data. This easily-incorporated periodic biometric authentication system validates genuine users and detects intruders quickly. Because it verifies users in the background, Spy Hunter is not constrained to a password box. Instead, it is flexible and can be layered with other mechanisms to provide high-level security. Where other continuous authentication techniques rely on scripted typing, Spy Hunter validates over free text in authentic environments. This is accomplished in two phases, one where the user is provided a prompt and another where the user is allowed free access to their computer. Additionally, Spy Hunter focuses on the timing of different keystrokes rather than the specific key being pressed. This allows for anonymous data to authenticate users and avoids holding personal data. Utilizing a couple K-fold cross-validation techniques, Spy Hunter is assessed based on how often the system falsely accepts an intruder, how often the system falsely rejects a genuine user, and the time it takes to validate a users identity. Spy Hunter maintains error rates below 6% and identifies users in minimal numbers of keystrokes. Continuous authentication provides higher level security than one-time verification processes and Spy Hunter expands on the possibilities for behavioral analysis based on keystroke dynamics.
Anatomical Priors in Convolutional Networks for Unsupervised Biomedical Segmentation
Venue: arXiv cs.CV 2019
Year: 2019

We consider the problem of segmenting a biomedical image into anatomical regions of interest. We specifically address the frequent scenario where we have no paired training data that contains images and their manual segmentations. Instead, we employ unpaired segmentation images to build an anatomical prior. Critically these segmentations can be derived from imaging data from a different dataset and imaging modality than the current task. We introduce a generative probabilistic model that employs the learned prior through a convolutional neural network to compute segmentations in an unsupervised setting. We conducted an empirical analysis of the proposed approach in the context of structural brain MRI segmentation, using a multi-study dataset of more than 14,000 scans. Our results show that an anatomical prior can enable fast unsupervised segmentation which is typically not possible using standard convolutional networks. The integration of anatomical priors can facilitate CNN-based anatomical segmentation in a range of novel clinical problems, where few or no annotations are available and thus standard networks are not trainable. The code is freely available at http://github.com/adalca/neuron.
Holdable Haptic Device for 4-DOF Motion Guidance
Venue: arXiv cs.RO 2019
Year: 2019

Hand-held haptic devices can allow for greater freedom of motion and larger workspaces than traditional grounded haptic devices. They can also provide more compelling haptic sensations to the users' fingertips than many wearable haptic devices because reaction forces can be distributed over a larger area of skin far away from the stimulation site. This paper presents a hand-held kinesthetic gripper that provides guidance cues in four degrees of freedom (DOF). 2-DOF tangential forces on the thumb and index finger combine to create cues to translate or rotate the hand. We demonstrate the device's capabilities in a three-part user study. First, users moved their hands in response to haptic cues before receiving instruction or training. Then, they trained on cues in eight directions in a forced-choice task. Finally, they repeated the first part, now knowing what each cue intended to convey. Users were able to discriminate each cue over 90% of the time. Users moved correctly in response to the guidance cues both before and after the training and indicated that the cues were easy to follow. The results show promise for holdable kinesthetic devices in haptic feedback and guidance for applications such as virtual reality, medical training, and teleoperation.
Input-Output Stability of Barrier-Based Model Predictive Control
Venue: arXiv cs.SY 2019
Year: 2019

Conditions for input-output stability of barrier-based model predictive control of linear systems with linear and convex nonlinear (hard or soft) constraints are established through the construction of integral quadratic constraints (IQCs). The IQCs can be used to establish sufficient conditions for global closed-loop stability. In particular conditions for robust stability can be obtained in the presence of unstructured model uncertainty. IQCs with both static and dynamic multipliers are developed and appropriate convex searches for the multipliers are presented. The effectiveness of the robust stability analysis is demonstrated with an illustrative numerical example.
Impact of Social Learning on Privacy-Preserving Data Collection
Venue: arXiv cs.GT 2019
Year: 2019

We study a model where a data collector obtains data from users through a payment mechanism, aiming to learn the underlying state from the elicited data. The private signal of each user represents her knowledge about the state; and through social interactions each user can also learn noisy versions of her social friends' signals, which is called `learned group signals'. Thanks to social learning, users have richer information about the state beyond their private signals. Based on both her private signal and learned group signals, each user makes strategic decisions to report a privacy-preserved version of her data to the data collector. We develop a Bayesian game theoretic framework to study the impact of social learning on users' data reporting strategies and devise the payment mechanism for the data collector accordingly. Our findings reveal that, in general, the desired data reporting strategy at the Bayesian-Nash equilibrium can be in the form of either a symmetric randomized response (SR) strategy or an informative non-disclosive (ND) strategy. Specifically, a generalized majority voting rule is applied by each user to her noisy group signals to determine which strategy to follow. Further, when a user plays the ND strategy, she reports privacy-preserving data completely based on her group signals, independent of her private signal, which indicates that her privacy cost is zero. We emphasize that the reported data when a user plays the ND strategy is still informative about the underlying state because it is based on her learned group signals. As a result, both the data collector and the users can benefit from social learning which drives down the privacy costs and helps to improve the state estimation at a given payment budget. We further derive bounds on the minimum total payment required to achieve a given level of state estimation accuracy.
Explicit-risk-aware Path Planning with Reward Maximization
Venue: arXiv cs.RO 2019
Year: 2019

This paper develops a path planner that minimizes risk (e.g. motion execution) while maximizing accumulated reward (e.g., quality of sensor viewpoint) motivated by visual assistance or tracking scenarios in unstructured or confined environments. In these scenarios, the robot should maintain the best viewpoint as it moves to the goal. However, in unstructured or confined environments, some paths may increase the risk of collision; therefore there is a tradeoff between risk and reward. Conventional state-dependent risk or probabilistic uncertainty modeling do not consider path-level risk or is difficult to acquire. This risk-reward planner explicitly represents risk as a function of motion plans, i.e., paths. Without manual assignment of the negative impact to the planner caused by risk, this planner takes in a pre-established viewpoint quality map and plans target location and path leading to it simultaneously, in order to maximize overall reward along the entire path while minimizing risk. Exact and approximate algorithms are presented, whose solution is further demonstrated on a physical tethered aerial vehicle. Other than the visual assistance problem, the proposed framework also provides a new planning paradigm to address minimum-risk planning under dynamical risk and absence of substructure optimality and to balance the trade-off between reward and risk.
Local Reasoning for Parameterized First Order Protocols
Venue: arXiv cs.LO 2019
Year: 2019

First Order Logic (FOL) is a powerful reasoning tool for program verification. Recent work on Ivy shows that FOL is well suited for verification of parameterized distributed systems. However, specifying many natural objects, such as a ring topology, in FOL is unexpectedly inconvenient. We present a framework based on FOL for specifying distributed multi-process protocols in a process-local manner together with an implicit network topology. In the specification framework, we provide an auto-active analysis technique to reason about the protocols locally, in a process-modular way. Our goal is to mirror the way designers often describe and reason about protocols. By hiding the topology behind the FOL structure, we simplify the modelling, but complicate the reasoning. To deal with that, we use an oracle for the topology to develop a sound and relatively complete proof rule that reduces reasoning about the implicit topology back to pure FOL. This completely avoids the need to axiomatize the topology. Using the rule, we establish a property that reduces verification to a fixed number of processes bounded by the size of local neighbourhoods. We show how to use the framework on two examples, including leader election on a ring.
Quadratic Probabilistic Algorithms for Normal Bases
Venue: arXiv cs.SC 2019
Year: 2019

It is well known that for any finite Galois extension field $K/F$, with Galois group $G = \mathrm{Gal}(K/F)$, there exists an element $α\in K$ whose orbit $G\cdotα$ forms an $F$-basis of $K$. Such an element $α$ is called \emph{normal} and $G\cdotα$ is called a normal basis. In this paper we introduce a probabilistic algorithm for finding a normal element when $G$ is either a finite abelian or a metacyclic group. The algorithm is based on the fact that deciding whether a random element $α\in K$ is normal can be reduced to deciding whether $\sum_{σ\in G} σ(α)σ\in K[G]$ is invertible. In an algebraic model, the cost of our algorithm is quadratic in the size of $G$ for metacyclic $G$ and slightly subquadratic for abelian $G$.
Let's Play Mahjong!
Venue: arXiv cs.AI 2019
Year: 2019

Mahjong is a very popular tile-based game commonly played by four players. Each player begins with a hand of 13 tiles and, in turn, players draw and discard (i.e., change) tiles until they complete a legal hand using a 14th tile. In this paper, we initiate a mathematical and AI study of the Mahjong game and try to answer two fundamental questions: how bad is a hand of 14 tiles? and which tile should I discard? We define and characterise the notion of deficiency and present an optimal policy to discard a tile in order to increase the chance of completing a legal hand within $k$ tile changes for each $k\geq 1$.
Multi-Process Fusion: Visual Place Recognition Using Multiple Image Processing Methods
Venue: arXiv cs.RO 2019
Year: 2019

Typical attempts to improve the capability of visual place recognition techniques include the use of multi-sensor fusion and integration of information over time from image sequences. These approaches can improve performance but have disadvantages including the need for multiple physical sensors and calibration processes, both for multiple sensors and for tuning the image matching sequence length. In this paper we address these shortcomings with a novel "multi-sensor" fusion approach applied to multiple image processing methods for a single visual image stream, combined with a dynamic sequence matching length technique and an automatic processing method weighting scheme. In contrast to conventional single method approaches, our approach reduces the performance requirements of a single image processing methodology, instead requiring that within the suite of image processing methods, at least one performs well in any particular environment. In comparison to static sequence length techniques, the dynamic sequence matching technique enables reduced localization latencies through analysis of recognition quality metrics when re-entering familiar locations. We evaluate our approach on multiple challenging benchmark datasets, achieving superior performance to two state-of-the-art visual place recognition systems across environmental changes including winter to summer, afternoon to morning and night to day. Across the four benchmark datasets our proposed approach achieves an average F1 score of 0.96, compared to 0.78 for NetVLAD and 0.49 for SeqSLAM. We provide source code for the multi-fusion method and present analysis explaining how superior performance is achieved despite the multiple, disparate, image processing methods all being applied to a single source of imagery, rather than to multiple separate sensors.
One-Bit Sigma-Delta MIMO Precoding
Venue: arXiv cs.IT 2019
Year: 2019

Coarsely quantized MIMO signalling methods have gained popularity in the recent developments of massive MIMO as they open up opportunities for massive MIMO implementation using cheap and power-efficient radio-frequency front-ends. This paper presents a new one-bit MIMO precoding approach using spatial Sigma-Delta ($ΣΔ$) modulation. In previous one-bit MIMO precoding research, one mainly focuses on using optimization to tackle the difficult binary signal optimization problem that arises from the precoding design. Our approach attempts a different route. Assuming angular MIMO channels, we apply $ΣΔ$ modulation---a classical concept in analog-to-digital conversion of temporal signals---in space. The resulting $ΣΔ$ precoding approach has two main advantages: First, we no longer need to deal with binary optimization in $ΣΔ$ precoding design. Particularly, the binary signal restriction is replaced by peak signal amplitude constraints. Second, the impact of the quantization error can be well controlled via modulator design and under appropriate operating conditions. Through symbol error probability analysis, we reveal that the very large number of antennas in massive MIMO provides favorable operating conditions for $ΣΔ$ precoding. In addition, we develop a new $ΣΔ$ modulation architecture that is capable of adapting the channel to achieve nearly zero quantization error for a targeted user. Furthermore, we consider multi-user $ΣΔ$ precoding using the zero-forcing and symbol-level precoding schemes. These two $ΣΔ$ precoding schemes perform considerably better than their direct one-bit quantized counterparts, as simulation results show.
From Helmut Jürgensen's Former Students: The Game of Informatics Research
Venue: arXiv cs.GL 2019
Year: 2019

Personal reflections are given on being students of Helmut Jürgensen. Then, we attempt to address his hypothesis that informatics follows trend-like behaviours through the use of a content analysis of university job advertisements, and then via simulation techniques from the area of quantitative economics.
Towards a Framework to Manage Perceptual Uncertainty for Safe Automated Driving
Venue: arXiv cs.AI 2019
Year: 2019

Perception is a safety-critical function of autonomous vehicles and machine learning (ML) plays a key role in its implementation. This position paper identifies (1) perceptual uncertainty as a performance measure used to define safety requirements and (2) its influence factors when using supervised ML. This work is a first step towards a framework for measuring and controling the effects of these factors and supplying evidence to support claims about perceptual uncertainty.