OpenRaiser/Intern-Atlas huggingface dataset:
Interdependent Strategic Security Risk Management with Bounded Rationality in the Internet of Things
Venue: arXiv cs.GT 2019
Year: 2019

With the increasing connectivity enabled by the Internet of Things (IoT), security becomes a critical concern, and the users should invest to secure their IoT applications. Due to the massive devices in the IoT network, users cannot be aware of the security policies taken by all its connected neighbors. Instead, a user makes security decisions based on the cyber risks he perceives by observing a selected number of nodes. To this end, we propose a model which incorporates the limited attention or bounded rationality nature of players in the IoT. Specifically, each individual builds a sparse cognitive network of nodes to respond to. Based on this simplified cognitive network representation, each user then determines his security management policy by minimizing his own real-world security cost. The bounded rational decision-makings of players and their cognitive network formations are interdependent and thus should be addressed in a holistic manner. We establish a games-in-games framework and propose a Gestalt Nash equilibrium (GNE) solution concept to characterize the decisions of agents, and quantify their risk of bounded perception due to the limited attention. In addition, we design a proximal-based iterative algorithm to compute the GNE. With case studies of smart communities, the designed algorithm can successfully identify the critical users whose decisions need to be taken into account by the other users during the security management.
Towards Global Asset Management in Blockchain Systems
Venue: arXiv cs.DB 2019
Year: 2019

Permissionless blockchains (e.g., Bitcoin, Ethereum, etc) have shown a wide success in implementing global scale peer-to-peer cryptocurrency systems. In such blockchains, new currency units are generated through the mining process and are used in addition to transaction fees to incentivize miners to maintain the blockchain. Although it is clear how currency units are generated and transacted on, it is unclear how to use the infrastructure of permissionless blockchains to manage other assets than the blockchain's currency units (e.g., cars, houses, etc). In this paper, we propose a global asset management system by unifying permissioned and permissionless blockchains. A governmental permissioned blockchain authenticates the registration of end-user assets through smart contract deployments on a permissionless blockchain. Afterwards, end-users can transact on their assets through smart contract function calls (e.g., sell a car, rent a room in a house, etc). In return, end-users get paid in currency units of the same blockchain or other blockchains through atomic cross-chain transactions and governmental offices receive taxes on these transactions in cryptocurrency units.
Comparing and Combining Lexicase Selection and Novelty Search
Venue: arXiv cs.NE 2019
Year: 2019

Lexicase selection and novelty search, two parent selection methods used in evolutionary computation, emphasize exploring widely in the search space more than traditional methods such as tournament selection. However, lexicase selection is not explicitly driven to select for novelty in the population, and novelty search suffers from lack of direction toward a goal, especially in unconstrained, highly-dimensional spaces. We combine the strengths of lexicase selection and novelty search by creating a novelty score for each test case, and adding those novelty scores to the normal error values used in lexicase selection. We use this new novelty-lexicase selection to solve automatic program synthesis problems, and find it significantly outperforms both novelty search and lexicase selection. Additionally, we find that novelty search has very little success in the problem domain of program synthesis. We explore the effects of each of these methods on population diversity and long-term problem solving performance, and give evidence to support the hypothesis that novelty-lexicase selection resists converging to local optima better than lexicase selection.
On the Critical Difference of Almost Bipartite Graphs
Venue: arXiv cs.DM 2019
Year: 2019

A set $S\subseteq V$ is \textit{independent} in a graph $G=\left( V,E\right) $ if no two vertices from $S$ are adjacent. The \textit{independence number} $α(G)$ is the cardinality of a maximum independent set, while $μ(G)$ is the size of a maximum matching in $G$. If $α(G)+μ(G)$ equals the order of $G$, then $G$ is called a \textit{König-Egerváry graph }\cite{dem,ster}. The number $d\left( G\right) =\max\{\left\vert A\right\vert -\left\vert N\left( A\right) \right\vert :A\subseteq V\}$ is called the \textit{critical difference} of $G$ \cite{Zhang} (where $N\left( A\right) =\left\{ v:v\in V,N\left( v\right) \cap A\neq\emptyset\right\} $). It is known that $α(G)-μ(G)\leq d\left( G\right) $ holds for every graph \cite{Levman2011a,Lorentzen1966,Schrijver2003}. In \cite{LevMan5} it was shown that $d(G)=α(G)-μ(G)$ is true for every König-Egerváry graph. A graph $G$ is \textit{(i)} \textit{unicyclic} if it has a unique cycle, \textit{(ii)} \textit{almost bipartite} if it has only one odd cycle. It was conjectured in \cite{LevMan2012a,LevMan2013a} and validated in \cite{Bhattacharya2018} that $d(G)=α(G)-μ(G)$ holds for every unicyclic non-König-Egerváry graph $G$. In this paper we prove that if $G$ is an almost bipartite graph of order $n\left( G\right) $, then $α(G)+μ(G)\in\left\{ n\left( G\right) -1,n\left( G\right) \right\} $. Moreover, for each of these two values, we characterize the corresponding graphs. Further, using these findings, we show that the critical difference of an almost bipartite graph $G$ satisfies \[ d(G)=α(G)-μ(G)=\left\vert \mathrm{core}(G)\right\vert -\left\vert N(\mathrm{core}(G))\right\vert , \] where by \textrm{core}$\left( G\right) $ we mean the intersection of all maximum independent sets.
Private Queries on Public Certificate Transparency Data
Venue: arXiv cs.CR 2019
Year: 2019

Despite increasing advancements in today's information exchange infrastructure, the preservation of user data and privacy still remains a problem. Both insecure baselines and secure solutions leak user data. For example, Certificate Transparency (CT) promises significant security improvements to existing Public Key Infrastructure solutions that up-to-now have solely relied on the Certificate Authority hierarchy. CT provides a robust auditing layer and transparency solution to quickly detect such compromises, but introduces the requirement that client browsers interact with third-party servers when validating a site certificate. In the existing CT system, these requests leak information about each user's browsing habits to the hosting server. It is not a stretch to think that this valuable data could be collected and exploited, as corporations and governments have plenty of financial and political incentive to do so. In this project, we seek to address this problem by using an oblivious file sharing system with strong anonymity properties, to provide a more scalable, performant solution to privacy-preserving queries.
Towards Generation and Evaluation of Comprehensive Mapping Robot Datasets
Venue: arXiv cs.RO 2019
Year: 2019

This paper presents a fully hardware synchronized mapping robot with support for a hardware synchronized external tracking system, for super-precise timing and localization. We also employ a professional, static 3D scanner for ground truth map collection. Three datasets are generated to evaluate the performance of mapping algorithms within a room and between rooms. Based on these datasets we generate maps and trajectory data, which is then fed into evaluation algorithms. The mapping and evaluation procedures are made in a very easily reproducible manner for maximum comparability. In the end we can draw a couple of conclusions about the tested SLAM algorithms.
Simple Bounds for the Symmetric Capacity of the Rayleigh Fading Multiple Access Channel
Venue: arXiv cs.IT 2019
Year: 2019

Communication over the i.i.d. Rayleigh slow-fading MAC is considered, where all terminals are equipped with a single antenna. Further, a communication protocol is considered where all users transmit at (just below) the symmetric capacity (per user) of the channel, a rate which is fed back (dictated) to the users by the base station. Tight bounds are established on the distribution of the rate attained by the protocol. In particular, these bounds characterize the probability that the dominant face of the MAC capacity region contains a symmetric rate point, i.e., that the considered protocol strictly attains the sum capacity of the channel. The analysis provides a non-asymptotic counterpart to the diversity-multiplexing tradeoff of the multiple access channel. Finally, a practical scheme based on integer-forcing and space-time precoding is shown to be an effective coding architecture for this communication scenario.
The African Wildlife Ontology tutorial ontologies: requirements, design, and content
Venue: arXiv cs.AI 2019
Year: 2019

Background. Most tutorial ontologies focus on illustrating one aspect of ontology development, notably language features and automated reasoners, but ignore ontology development factors, such as emergent modelling guidelines and ontological principles. Yet, novices replicate examples from the exercises they carry out. Not providing good examples holistically causes the propagation of sub-optimal ontology development, which may negatively affect the quality of a real domain ontology. Results. We identified 22 requirements that a good tutorial ontology should satisfy regarding subject domain, logics and reasoning, and engineering aspects. We developed a set of ontologies about African Wildlife to serve as tutorial ontologies. A majority of the requirements have been met with the set of African Wildlife Ontology tutorial ontologies, which are introduced in this paper. The African Wildlife Ontology is mature and has been used yearly in an ontology engineering course or tutorial since 2010 and is included in a recent ontology engineering textbook with relevant examples and exercises. Conclusion. The African Wildlife Ontology provides a wide range of options concerning examples and exercises for ontology engineering well beyond illustrating only language features and automated reasoning. It assists in demonstrating tasks about ontology quality, such as alignment to a foundational ontology and satisfying competency questions, versioning, and multilingual ontologies.
Hierarchical Annotation of Images with Two-Alternative-Forced-Choice Metric Learning
Venue: arXiv cs.LG 2019
Year: 2019

Many tasks such as retrieval and recommendations can significantly benefit from structuring the data, commonly in a hierarchical way. To achieve this through annotations of high dimensional data such as images or natural text can be significantly labor intensive. We propose an approach for uncovering the hierarchical structure of data based on efficient discriminative testing rather than annotations of individual datapoints. Using two-alternative-forced-choice (2AFC) testing and deep metric learning we achieve embedding of the data in semantic space where we are able to successfully hierarchically cluster. We actively select triplets for the 2AFC test such that the modeling process is highly efficient with respect to the number of tests presented to the annotator. We empirically demonstrate the feasibility of the method by confirming the shape bias on synthetic data and extract hierarchical structure on the Fashion-MNIST dataset to a finer granularity than the original labels.
ENIGMAWatch: ProofWatch Meets ENIGMA
Venue: arXiv cs.AI 2019
Year: 2019

In this work we describe a new learning-based proof guidance -- ENIGMAWatch -- for saturation-style first-order theorem provers. ENIGMAWatch combines two guiding approaches for the given-clause selection implemented for the E ATP system: ProofWatch and ENIGMA. ProofWatch is motivated by the watchlist (hints) method and based on symbolic matching of multiple related proofs, while ENIGMA is based on statistical machine learning. The two methods are combined by using the evolving information about symbolic proof matching as an additional information that characterizes the saturation-style proof search for the statistical learning methods. The new system is experimentally evaluated on a large set of problems from the Mizar Library. We show that the added proof-matching information is considered important by the statistical machine learners, and that it leads to improvements in E's Performance over ProofWatch and ENIGMA.
Variational Inference with Mixture Model Approximation: Robotic Applications
Venue: arXiv cs.RO 2019
Year: 2019

We propose a method to approximate the distribution of robot configurations satisfying multiple objectives. Our approach uses variational inference, a popular method in Bayesian computation, which has several advantages over sampling-based techniques. To be able to represent the complex and multimodal distribution of configurations, we propose to use a mixture model as approximate distribution, an approach that has gained popularity recently. In this work, we show the interesting properties of this approach and how it can be applied to a wide range of problems in robotics.
An Improved Reversible Data Hiding in Encrypted Images using Parametric Binary Tree Labeling
Venue: arXiv cs.MM 2019
Year: 2019

This work proposes an improved reversible data hiding scheme in encrypted images using parametric binary tree labeling(IPBTL-RDHEI), which takes advantage of the spatial correlation in the entire original image but not in small image blocks to reserve room for hiding data. Then the original image is encrypted with an encryption key and the parametric binary tree is used to label encrypted pixels into two different categories. Finally, one of the two categories of encrypted pixels can embed secret information by bit replacement. According to the experimental results, compared with several state-of-the-art methods, the proposed IPBTL-RDHEI method achieves higher embedding rate and outperforms the competitors. Due to the reversibility of IPBTL-RDHEI, the original plaintext image and the secret information can be restored and extracted losslessly and separately.
StrongChain: Transparent and Collaborative Proof-of-Work Consensus
Venue: arXiv cs.CR 2019
Year: 2019

Bitcoin is the most successful cryptocurrency so far. This is mainly due to its novel consensus algorithm, which is based on proof-of-work combined with a cryptographically-protected data structure and a rewarding scheme that incentivizes nodes to participate. However, despite its unprecedented success Bitcoin suffers from many inefficiencies. For instance, Bitcoin's consensus mechanism has been proved to be incentive-incompatible, its high reward variance causes centralization, and its hardcoded deflation raises questions about its long-term sustainability. In this work, we revise the Bitcoin consensus mechanism by proposing StrongChain, a scheme that introduces transparency and incentivizes participants to collaborate rather than to compete. The core design of our protocol is to reflect and utilize the computing power aggregated on the blockchain which is invisible and "wasted" in Bitcoin today. Introducing relatively easy, although important changes to Bitcoin's design enables us to improve many crucial aspects of Bitcoin-like cryptocurrencies making it more secure, efficient, and profitable for participants. We thoroughly analyze our approach and we present an implementation of StrongChain. The obtained results confirm its efficiency, security, and deployability.
Deep Q-Learning with Q-Matrix Transfer Learning for Novel Fire Evacuation Environment
Venue: arXiv cs.AI 2019
Year: 2019

We focus on the important problem of emergency evacuation, which clearly could benefit from reinforcement learning that has been largely unaddressed. Emergency evacuation is a complex task which is difficult to solve with reinforcement learning, since an emergency situation is highly dynamic, with a lot of changing variables and complex constraints that makes it difficult to train on. In this paper, we propose the first fire evacuation environment to train reinforcement learning agents for evacuation planning. The environment is modelled as a graph capturing the building structure. It consists of realistic features like fire spread, uncertainty and bottlenecks. We have implemented the environment in the OpenAI gym format, to facilitate future research. We also propose a new reinforcement learning approach that entails pretraining the network weights of a DQN based agents to incorporate information on the shortest path to the exit. We achieved this by using tabular Q-learning to learn the shortest path on the building model's graph. This information is transferred to the network by deliberately overfitting it on the Q-matrix. Then, the pretrained DQN model is trained on the fire evacuation environment to generate the optimal evacuation path under time varying conditions. We perform comparisons of the proposed approach with state-of-the-art reinforcement learning algorithms like PPO, VPG, SARSA, A2C and ACKTR. The results show that our method is able to outperform state-of-the-art models by a huge margin including the original DQN based models. Finally, we test our model on a large and complex real building consisting of 91 rooms, with the possibility to move to any other room, hence giving 8281 actions. We use an attention based mechanism to deal with large action spaces. Our model achieves near optimal performance on the real world emergency environment.
DEEP-BO for Hyperparameter Optimization of Deep Networks
Venue: arXiv cs.LG 2019
Year: 2019

The performance of deep neural networks (DNN) is very sensitive to the particular choice of hyper-parameters. To make it worse, the shape of the learning curve can be significantly affected when a technique like batchnorm is used. As a result, hyperparameter optimization of deep networks can be much more challenging than traditional machine learning models. In this work, we start from well known Bayesian Optimization solutions and provide enhancement strategies specifically designed for hyperparameter optimization of deep networks. The resulting algorithm is named as DEEP-BO (Diversified, Early-termination-Enabled, and Parallel Bayesian Optimization). When evaluated over six DNN benchmarks, DEEP-BO easily outperforms or shows comparable performance with some of the well-known solutions including GP-Hedge, Hyperband, BOHB, Median Stopping Rule, and Learning Curve Extrapolation. The code used is made publicly available at https://github.com/snu-adsl/DEEP-BO.
The Convolutional Tsetlin Machine
Venue: arXiv cs.LG 2019
Year: 2019

Convolutional neural networks (CNNs) have obtained astounding successes for important pattern recognition tasks, but they suffer from high computational complexity and the lack of interpretability. The recent Tsetlin Machine (TM) attempts to address this lack by using easy-to-interpret conjunctive clauses in propositional logic to solve complex pattern recognition problems. The TM provides competitive accuracy in several benchmarks, while keeping the important property of interpretability. It further facilitates hardware-near implementation since inputs, patterns, and outputs are expressed as bits, while recognition and learning rely on straightforward bit manipulation. In this paper, we exploit the TM paradigm by introducing the Convolutional Tsetlin Machine (CTM), as an interpretable alternative to CNNs. Whereas the TM categorizes an image by employing each clause once to the whole image, the CTM uses each clause as a convolution filter. That is, a clause is evaluated multiple times, once per image patch taking part in the convolution. To make the clauses location-aware, each patch is further augmented with its coordinates within the image. The output of a convolution clause is obtained simply by ORing the outcome of evaluating the clause on each patch. In the learning phase of the TM, clauses that evaluate to 1 are contrasted against the input. For the CTM, we instead contrast against one of the patches, randomly selected among the patches that made the clause evaluate to 1. Accordingly, the standard Type I and Type II feedback of the classic TM can be employed directly, without further modification. The CTM obtains a peak test accuracy of 99.4% on MNIST, 96.31% on Kuzushiji-MNIST, 91.5% on Fashion-MNIST, and 100.0% on the 2D Noisy XOR Problem, which is competitive with results reported for simple 4-layer CNNs, BinaryConnect, Logistic Circuits and an FPGA-accelerated Binary CNN.
Meta-GNN: On Few-shot Node Classification in Graph Meta-learning
Venue: arXiv cs.LG 2019
Year: 2019

Meta-learning has received a tremendous recent attention as a possible approach for mimicking human intelligence, i.e., acquiring new knowledge and skills with little or even no demonstration. Most of the existing meta-learning methods are proposed to tackle few-shot learning problems such as image and text, in rather Euclidean domain. However, there are very few works applying meta-learning to non-Euclidean domains, and the recently proposed graph neural networks (GNNs) models do not perform effectively on graph few-shot learning problems. Towards this, we propose a novel graph meta-learning framework -- Meta-GNN -- to tackle the few-shot node classification problem in graph meta-learning settings. It obtains the prior knowledge of classifiers by training on many similar few-shot learning tasks and then classifies the nodes from new classes with only few labeled samples. Additionally, Meta-GNN is a general model that can be straightforwardly incorporated into any existing state-of-the-art GNN. Our experiments conducted on three benchmark datasets demonstrate that our proposed approach not only improves the node classification performance by a large margin on few-shot learning problems in meta-learning paradigm, but also learns a more general and flexible model for task adaption.
Approximation schemes for the generalized extensible bin packing problem
Venue: arXiv cs.DS 2019
Year: 2019

We present a new generalization of the extensible bin packing with unequal bin sizes problem. In our generalization the cost of exceeding the bin size depends on the index of the bin and not only on the amount in which the size of the bin is exceeded. This generalization does not satisfy the assumptions on the cost function that were used to present the existing polynomial time approximation scheme (PTAS) for the extensible bin packing with unequal bin sizes problem. In this work, we show the existence of an efficient PTAS (EPTAS) for this new generalization and thus in particular we improve the earlier PTAS for the extensible bin packing with unequal bin sizes problem into an EPTAS. Our new scheme is based on using the shifting technique followed by a solution of polynomial number of $n$-fold programming instances. In addition, we present an asymptotic fully polynomial time approximation scheme (AFPTAS) for the related bin packing type variant of the problem.
Randomized Reference Classifier with Gaussian Distribution and Soft Confusion Matrix Applied to the Improving Weak Classifiers
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, an issue of building the RRC model using probability distributions other than beta distribution is addressed. More precisely, in this paper, we propose to build the RRR model using the truncated normal distribution. Heuristic procedures for expected value and the variance of the truncated-normal distribution are also proposed. The proposed approach is tested using SCM-based model for testing the consequences of applying the truncated normal distribution in the RRC model. The experimental evaluation is performed using four different base classifiers and seven quality measures. The results showed that the proposed approach is comparable to the RRC model built using beta distribution. What is more, for some base classifiers, the truncated-normal-based SCM algorithm turned out to be better at discovering objects coming from minority classes.