OpenRaiser/Intern-Atlas huggingface dataset:
Order Effects for Queries in Intelligent Systems
Venue: arXiv cs.AI 2018
Year: 2018

This paper examines common assumptions regarding the decision-making internal environment for intelligent agents and investigates issues related to processing of memory and belief states to help obtain better understanding of the responses. In specific, we consider order effects and discuss both classical and non-classical explanations for them. We also consider implicit cognition and explore if certain inaccessible states may be best modeled as quantum states. We propose that the hypothesis that quantum states are at the basis of order effects be tested on large databases such as those related to medical treatment and drug efficacy. A problem involving a maze network is considered and comparisons made between classical and quantum decision scenarios for it.
Automatically assembling a full census of an academic field
Venue: arXiv cs.DL 2018
Year: 2018

The composition of the scientific workforce shapes the direction of scientific research, directly through the selection of questions to investigate, and indirectly through its influence on the training of future scientists. In most fields, however, complete census information is difficult to obtain, complicating efforts to study workforce dynamics and the effects of policy. This is particularly true in computer science, which lacks a single, all-encompassing directory or professional organization. A full census of computer science would serve many purposes, not the least of which is a better understanding of the trends and causes of unequal representation in computing. Previous academic census efforts have relied on narrow or biased samples, or on professional society membership rolls. A full census can be constructed directly from online departmental faculty directories, but doing so by hand is prohibitively expensive and time-consuming. Here, we introduce a topical web crawler for automating the collection of faculty information from web-based department rosters, and demonstrate the resulting system on the 205 PhD-granting computer science departments in the U.S. and Canada. This method constructs a complete census of the field within a few minutes, and achieves over 99% precision and recall. We conclude by comparing the resulting 2017 census to a hand-curated 2011 census to quantify turnover and retention in computer science, in general and for female faculty in particular, demonstrating the types of analysis made possible by automated census construction.
Maximizing the Number of Spanning Trees in a Connected Graph
Venue: arXiv cs.DS 2018
Year: 2018

We study the problem of maximizing the number of spanning trees in a connected graph by adding at most $k$ edges from a given candidate edge set. We give both algorithmic and hardness results for this problem: - We give a greedy algorithm that, using submodularity, obtains an approximation ratio of $(1 - 1/e - ε)$ in the exponent of the number of spanning trees for any $ε> 0$ in time $\tilde{O}(m ε^{-1} + (n + q) ε^{-3})$, where $m$ and $q$ is the number of edges in the original graph and the candidate edge set, respectively. Our running time is optimal with respect to the input size up to logarithmic factors, and substantially improves upon the $O(n^3)$ running time of the previous proposed greedy algorithm with approximation ratio $(1 - 1/e)$ in the exponent. Notably, the independence of our running time of $k$ is novel, comparing to conventional top-$k$ selections on graphs that usually run in $Ω(mk)$ time. A key ingredient of our greedy algorithm is a routine for maintaining effective resistances under edge additions in an online-offline hybrid setting. - We show the exponential inapproximability of this problem by proving that there exists a constant $c > 0$ such that it is NP-hard to approximate the optimum number of spanning trees in the exponent within $(1 - c)$. This inapproximability result follows from a reduction from the minimum path cover in undirected graphs, whose hardness again follows from the constant inapproximability of the Traveling Salesman Problem (TSP) with distances 1 and 2. Thus, the approximation ratio of our algorithm is also optimal up to a constant factor in the exponent. To our knowledge, this is the first hardness of approximation result for maximizing the number of spanning trees in a graph, or equivalently, by Kirchhoff's matrix-tree theorem, maximizing the determinant of an SDDM matrix.
Prior Independent Equilibria and Linear Multi-dimensional Bayesian Games
Venue: arXiv cs.GT 2018
Year: 2018

We show that a Bayesian strategy map profile is a Bayesian Nash Equilibrium independent of any prior if and only if the Bayesian strategy map profile, evaluated at any type profile, is the Nash equilibrium of the so-called local deterministic game corresponding to that type profile. We call such a Bayesian game type-regular. We then show that an m-dimensional n-agent Bayesian game whose utilities are linearly dependent on the types of the agents is equivalent, following a normalisation of the type space of each agent into the (m-1)-simplex, to a simultaneous competition in nm so-called basic n-agent games. If the game is own-type-linear, i.e., the utility of each player only depends linearly on its own type, then the Bayesian game is equivalent to a simultaneous competition in m basic n-agent games, called a multi-game. We then prove that an own-type-linear Bayesian game is type-regular if it is type-regular on the vertices of the (m-1)-simplex, a result which provides a large class of type-regular Bayesian maps. The class of m-dimensional own-type-linear Bayesian games can model, via their equivalence with multi-games, simultaneous decision-making in m different environments. We show that a two dimensional own-type-linear Bayesian game can be used to give a new model of the Prisoner's Dilemma (PD) in which the prosocial tendencies of the agents are considered as their types and the two agents play simultaneously in the PD as well as in a prosocial game. This Bayesian game addresses the materialistic and the prosocial tendencies of the agents. Similarly, we present a new two dimensional Bayesian model of the Trust game in which the type of the two agents reflect their prosocial tendency or trustfulness, which leads to more reasonable Nash equilibria. We finally consider an example of such multi-environment decision making in production by several companies in multi-markets.
An Adaptive Learning Method of Personality Trait Based Mood in Mental State Transition Network by Recurrent Neural Network
Venue: arXiv cs.HC 2018
Year: 2018

Mental State Transition Network (MSTN) is a basic concept of approximating to human psychological and mental responses. A stimulus calculated by Emotion Generating Calculations (EGC) method can cause the transition of mood from an emotional state to others. In this paper, the agent can interact with human to realize smooth communication by an adaptive learning method of the user's personality trait based mood. The learning method consists of the profit sharing (PS) method and the recurrent neural network (RNN). An emotion for sensor inputs to MSTN is calculated by EGC and the variance of emotion leads to the change of mental state, and then the sequence of states forms an episode. In order to learn the tendency of personality trait effectively, the ineffective rules should be removed from the episode. PS method finds out a detour in episode and should be deleted. Furthermore, RNN works to realize the variance of user's mood. Some experimental results were shown the success of representing a various human's delicate emotion.
Information and Set Algebras: Interpretation and Uniqueness of Conditional Independence
Venue: arXiv cs.LO 2018
Year: 2018

A new seemingly weak axiomatic formulation of information algebras is given. It is shown how such information algebras can be embedded into set (information) algebras. In set algebras there is a natural relation of conditional independence between partitions. Via the embedding of information algebras this relation carries over to information algebras. The new axiomatic formulation is thereby shown to be equivalent to the one given in arXiv:1701.02658. In this way the abstract concept of conditional independence in information algebras gets a concrete interpretation in terms of set theoretical relations.
Variational 3D-PIV with Sparse Descriptors
Venue: arXiv cs.CV 2018
Year: 2018

3D Particle Imaging Velocimetry (3D-PIV) aim to recover the flow field in a volume of fluid, which has been seeded with tracer particles and observed from multiple camera viewpoints. The first step of 3D-PIV is to reconstruct the 3D locations of the tracer particles from synchronous views of the volume. We propose a new method for iterative particle reconstruction (IPR), in which the locations and intensities of all particles are inferred in one joint energy minimization. The energy function is designed to penalize deviations between the reconstructed 3D particles and the image evidence, while at the same time aiming for a sparse set of particles. We find that the new method, without any post-processing, achieves significantly cleaner particle volumes than a conventional, tomographic MART reconstruction, and can handle a wide range of particle densities. The second step of 3D-PIV is to then recover the dense motion field from two consecutive particle reconstructions. We propose a variational model, which makes it possible to directly include physical properties, such as incompressibility and viscosity, in the estimation of the motion field. To further exploit the sparse nature of the input data, we propose a novel, compact descriptor of the local particle layout. Hence, we avoid the memory-intensive storage of high-resolution intensity volumes. Our framework is generic and allows for a variety of different data costs (correlation measures) and regularizers. We quantitatively evaluate it with both the sum of squared differences (SSD) and the normalized cross-correlation (NCC), respectively with both a hard and a soft version of the incompressibility constraint.
Abdominal Aortic Aneurysm Segmentation with a Small Number of Training Subjects
Venue: arXiv cs.CV 2018
Year: 2018

Pre-operative Abdominal Aortic Aneurysm (AAA) 3D shape is critical for customized stent-graft design in Fenestrated Endovascular Aortic Repair (FEVAR). Traditional segmentation approaches implement expert-designed feature extractors while recent deep neural networks extract features automatically with multiple non-linear modules. Usually, a large training dataset is essential for applying deep learning on AAA segmentation. In this paper, the AAA was segmented using U-net with a small number (two) of training subjects. Firstly, Computed Tomography Angiography (CTA) slices were augmented with gray value variation and translation to avoid the overfitting caused by the small number of training subjects. Then, U-net was trained to segment the AAA. Dice Similarity Coefficients (DSCs) over 0.8 were achieved on the testing subjects. The PLZ, DLZ and aortic branches are all reconstructed reasonably, which will facilitate stent graft customization and help shape instantiation for intra-operative surgery navigation in FEVAR.
Learning at the Ends: From Hand to Tool Affordances in Humanoid Robots
Venue: arXiv cs.RO 2018
Year: 2018

One of the open challenges in designing robots that operate successfully in the unpredictable human environment is how to make them able to predict what actions they can perform on objects, and what their effects will be, i.e., the ability to perceive object affordances. Since modeling all the possible world interactions is unfeasible, learning from experience is required, posing the challenge of collecting a large amount of experiences (i.e., training data). Typically, a manipulative robot operates on external objects by using its own hands (or similar end-effectors), but in some cases the use of tools may be desirable, nevertheless, it is reasonable to assume that while a robot can collect many sensorimotor experiences using its own hands, this cannot happen for all possible human-made tools. Therefore, in this paper we investigate the developmental transition from hand to tool affordances: what sensorimotor skills that a robot has acquired with its bare hands can be employed for tool use? By employing a visual and motor imagination mechanism to represent different hand postures compactly, we propose a probabilistic model to learn hand affordances, and we show how this model can generalize to estimate the affordances of previously unseen tools, ultimately supporting planning, decision-making and tool selection tasks in humanoid robots. We present experimental results with the iCub humanoid robot, and we publicly release the collected sensorimotor data in the form of a hand posture affordances dataset.
Optimal Transport over Deterministic Discrete-time Nonlinear Systems using Stochastic Feedback Laws
Venue: arXiv cs.SY 2018
Year: 2018

This paper considers the relaxed version of the transport problem for general nonlinear control systems, where the objective is to design time-varying feedback laws that transport a given initial probability measure to a target probability measure under the action of the closed-loop system. To make the problem analytically tractable, we consider control laws that are stochastic, i.e., the control laws are maps from the state space of the control system to the space of probability measures on the set of admissible control inputs. Under some controllability assumptions on the control system as defined on the state space, we show that the transport problem, considered as a controllability problem for the lifted control system on the space of probability measures, is well-posed for a large class of initial and target measures. We use this to prove the well-posedness of a fixed-endpoint optimal control problem defined on the space of probability measures, where along with the terminal constraints, the goal is to optimize an objective functional along the trajectory of the control system. This optimization problem can be posed as an infinite-dimensional linear programming problem. This formulation facilitates numerical solutions of the transport problem for low-dimensional control systems, as we show in two numerical examples.
Beating the integrality ratio for s-t-tours in graphs
Venue: arXiv cs.DM 2018
Year: 2018

Among various variants of the traveling salesman problem, the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3/2, and an approximation algorithm matching this ratio. In this paper, we go below this threshold: we devise a polynomial-time algorithm for the s-t-path graph TSP with approximation ratio 1.497. Our algorithm can be viewed as a refinement of the 3/2-approximation algorithm by Sebő and Vygen [2014], but we introduce several completely new techniques. These include a new type of ear-decomposition, an enhanced ear induction that reveals a novel connection to matroid union, a stronger lower bound, and a reduction of general instances to instances in which s and t have small distance (which works for general metrics).
Full version: An evaluation of estimation techniques for probabilistic reachability
Venue: arXiv cs.LO 2018
Year: 2018

We evaluate numerically-precise Monte Carlo (MC), Quasi-Monte Carlo (QMC) and Randomised Quasi-Monte Carlo (RQMC) methods for computing probabilistic reachability in hybrid systems with random parameters. Computing reachability probability amounts to computing (multidimensional) integrals. In particular, we pay attention to QMC methods due to their theoretical benefits in convergence speed with respect to the MC method. The Koksma-Hlawka inequality is a standard result that bounds the approximation of an integral by QMC techniques. However, it is not useful in practice because it depends on the variation of the integrand function, which is in general difficult to compute. The question arises whether it is possible to apply statistical or empirical methods for estimating the approximation error. In this paper we compare a number of interval estimation techniques based on the Central Limit Theorem (CLT), and we also introduce a new approach based on the CLT for computing confidence intervals for probability near the borders of the [0,1] interval. Based on our analysis, we provide justification for the use of the developed approach and suggest usage guidelines for probability estimation techniques.
Data2Vis: Automatic Generation of Data Visualizations Using Sequence to Sequence Recurrent Neural Networks
Venue: arXiv cs.HC 2018
Year: 2018

Rapidly creating effective visualizations using expressive grammars is challenging for users who have limited time and limited skills in statistics and data visualization. Even high-level, dedicated visualization tools often require users to manually select among data attributes, decide which transformations to apply, and specify mappings between visual encoding variables and raw or transformed attributes. In this paper we introduce Data2Vis, a neural translation model for automatically generating visualizations from given datasets. We formulate visualization generation as a sequence to sequence translation problem where data specifications are mapped to visualization specifications in a declarative language (Vega-Lite). To this end, we train a multilayered attention-based recurrent neural network (RNN) with long short-term memory (LSTM) units on a corpus of visualization specifications. Qualitative results show that our model learns the vocabulary and syntax for a valid visualization specification, appropriate transformations (count, bins, mean) and how to use common data selection patterns that occur within data visualizations. Data2Vis generates visualizations that are comparable to manually-created visualizations in a fraction of the time, with potential to learn more complex visualization strategies at scale.
Data Driven Optimizations for MTJ based Stochastic Computing
Venue: arXiv cs.ET 2018
Year: 2018

Stochastic computing, a form of computation with probabilities, presents an alternative to conventional arithmetic units. Magnetic Tunnel Junctions (MTJs), which exhibit probabilistic switching, have been explored as Stochastic Number Generators (SNGs). We provide a perspective of the energy requirements of such an application and design an energy-efficient and data-sensitive MTJ-based SNG. We discuss its benefits when used for stochastic computations, illustrating with the help of a multiplier circuit, in terms of energy savings when compared to computing with the baseline MTJ-SNG.
Restructuring expression dags for efficient parallelization
Venue: arXiv cs.CG 2018
Year: 2018

In the field of robust geometric computation it is often necessary to make exact decisions based on inexact floating-point arithmetic. One common approach is to store the computation history in an arithmetic expression dag and to re-evaluate the expression with increasing precision until an exact decision can be made. We show that exact-decisions number types based on expression dags can be evaluated faster in practice through parallelization on multiple cores. We compare the impact of several restructuring methods for the expression dag on its running time in a parallel environment.
On the Robustness of the CVPR 2018 White-Box Adversarial Example Defenses
Venue: arXiv cs.CV 2018
Year: 2018

Neural networks are known to be vulnerable to adversarial examples. In this note, we evaluate the two white-box defenses that appeared at CVPR 2018 and find they are ineffective: when applying existing techniques, we can reduce the accuracy of the defended models to 0%.
A Mathematical Framework for Superintelligent Machines
Venue: arXiv cs.AI 2018
Year: 2018

We describe a class calculus that is expressive enough to describe and improve its own learning process. It can design and debug programs that satisfy given input/output constraints, based on its ontology of previously learned programs. It can improve its own model of the world by checking the actual results of the actions of its robotic activators. For instance, it could check the black box of a car crash to determine if it was probably caused by electric failure, a stuck electronic gate, dark ice, or some other condition that it must add to its ontology in order to meet its sub-goal of preventing such crashes in the future. Class algebra basically defines the eval/eval-1 Galois connection between the residuated Boolean algebras of 1. equivalence classes and super/sub classes of class algebra type expressions, and 2. a residual Boolean algebra of biclique relationships. It distinguishes which formulas are equivalent, entailed, or unrelated, based on a simplification algorithm that may be thought of as producing a unique pair of Karnaugh maps that describe the rough sets of maximal bicliques of relations. Such maps divide the n-dimensional space of up to 2n-1 conjunctions of up to n propositions into clopen (i.e. a closed set of regions and their boundaries) causal sets. This class algebra is generalized to type-2 fuzzy class algebra by using relative frequencies as probabilities. It is also generalized to a class calculus involving assignments that change the states of programs. INDEX TERMS 4-valued Boolean Logic, Artificial Intelligence, causal sets, class algebra, consciousness, intelligent design, IS-A hierarchy, mathematical logic, meta-theory, pointless topological space, residuated lattices, rough sets, type-2 fuzzy sets
TIDBD: Adapting Temporal-difference Step-sizes Through Stochastic Meta-descent
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we introduce a method for adapting the step-sizes of temporal difference (TD) learning. The performance of TD methods often depends on well chosen step-sizes, yet few algorithms have been developed for setting the step-size automatically for TD learning. An important limitation of current methods is that they adapt a single step-size shared by all the weights of the learning system. A vector step-size enables greater optimization by specifying parameters on a per-feature basis. Furthermore, adapting parameters at different rates has the added benefit of being a simple form of representation learning. We generalize Incremental Delta Bar Delta (IDBD)---a vectorized adaptive step-size method for supervised learning---to TD learning, which we name TIDBD. We demonstrate that TIDBD is able to find appropriate step-sizes in both stationary and non-stationary prediction tasks, outperforming ordinary TD methods and TD methods with scalar step-size adaptation; we demonstrate that it can differentiate between features which are relevant and irrelevant for a given task, performing representation learning; and we show on a real-world robot prediction task that TIDBD is able to outperform ordinary TD methods and TD methods augmented with AlphaBound and RMSprop.
The AGINAO Self-Programming Engine
Venue: arXiv cs.AI 2018
Year: 2018

The AGINAO is a project to create a human-level artificial general intelligence system (HL AGI) embodied in the Aldebaran Robotics' NAO humanoid robot. The dynamical and open-ended cognitive engine of the robot is represented by an embedded and multi-threaded control program, that is self-crafted rather than hand-crafted, and is executed on a simulated Universal Turing Machine (UTM). The actual structure of the cognitive engine emerges as a result of placing the robot in a natural preschool-like environment and running a core start-up system that executes self-programming of the cognitive layer on top of the core layer. The data from the robot's sensory devices supplies the training samples for the machine learning methods, while the commands sent to actuators enable testing hypotheses and getting a feedback. The individual self-created subroutines are supposed to reflect the patterns and concepts of the real world, while the overall program structure reflects the spatial and temporal hierarchy of the world dependencies. This paper focuses on the details of the self-programming approach, limiting the discussion of the applied cognitive architecture to a necessary minimum.