OpenRaiser/Intern-Atlas huggingface dataset:
A reworked SOBI algorithm based on SCHUR Decomposition for EEG data processing
Venue: arXiv cs.HC 2018
Year: 2018

In brain machine interfaces (BMI) that are used to control motor rehabilitation devices there is the need to process the monitored brain signals with the purpose of recognizing patient's intentions to move his hands or limbs and reject artifact and noise superimposed on these signals. This kind of processing has to take place within time limits imposed by the on-line control requirements of such devices. A widely-used algorithm is the Second Order Blind Identification (SOBI) independent component analysis (ICA) algorithm. This algorithm, however, presents long processing time and therefor it not suitable for use in the brain-based control of rehabilitation devices. A rework of this algorithm that is presented in this paper and based on SCHUR decomposition results to significantly reduced processing time. This new algorithm is quite appropriate for use in brain-based control of rehabilitation devices.
The Computational Complexity of Finding Hamiltonian Cycles in Grid Graphs of Semiregular Tessellations
Venue: arXiv cs.CC 2018
Year: 2018

Finding Hamitonian Cycles in square grid graphs is a well studied and important questions. More recent work has extended these results to triangular and hexagonal grids, as well as further restricted versions. In this paper, we examine a class of more complex grids, as well as looking at the problem with restricted types of paths. We investigate the hardness of Hamiltonian cycle problem in grid graphs of semiregular tessellations. We give NP-hardness reductions for finding Hamiltonian paths in grid graphs based on all eight of the semiregular tessilations. Next, we investigate variations on the problem of finding Hamiltonian Paths in grid graphs when the path is forced to turn at every vertex. We give a polynomial time algorithm for deciding if a square grid graph admits a Hamiltonian cycle which turns at every vertex. We then show deciding if cubic grid graphs, even if the height is restricted to $2$, admit a Hamiltonian cycle is NP-complete.
Wisdom in Sum of Parts: Multi-Platform Activity Prediction in Social Collaborative Sites
Venue: arXiv cs.SI 2018
Year: 2018

In this paper, we proposed a novel framework which uses user interests inferred from activities (a.k.a., activity interests) in multiple social collaborative platforms to predict users' platform activities. Included in the framework are two prediction approaches: (i) direct platform activity prediction, which predicts a user's activities in a platform using his or her activity interests from the same platform (e.g., predict if a user answers a given Stack Overflow question using the user's interests inferred from his or her prior answer and favorite activities in Stack Overflow), and (ii) cross-platform activity prediction, which predicts a user's activities in a platform using his or her activity interests from another platform (e.g., predict if a user answers a given Stack Overflow question using the user's interests inferred from his or her fork and watch activities in GitHub). To evaluate our proposed method, we conduct prediction experiments on two widely used social collaborative platforms in the software development community: GitHub and Stack Overflow. Our experiments show that combining both direct and cross-platform activity prediction approaches yield the best accuracies for predicting user activities in GitHub (AUC=0.75) and Stack Overflow (AUC=0.89).
Optimally Sorting Evolving Data
Venue: arXiv cs.DS 2018
Year: 2018

We give optimal sorting algorithms in the evolving data framework, where an algorithm's input data is changing while the algorithm is executing. In this framework, instead of producing a final output, an algorithm attempts to maintain an output close to the correct output for the current state of the data, repeatedly updating its best estimate of a correct output over time. We show that a simple repeated insertion-sort algorithm can maintain an O(n) Kendall tau distance, with high probability, between a maintained list and an underlying total order of n items in an evolving data model where each comparison is followed by a swap between a random consecutive pair of items in the underlying total order. This result is asymptotically optpimal, since there is an Omega(n) lower bound for Kendall tau distance for this problem. Our result closes the gap between this lower bound and the previous best algorithm for this problem, which maintains a Kendall tau distance of O(n log log n) with high probability. It also confirms previous experimental results that suggested that insertion sort tends to perform better than quicksort in practice.
Symmetric Rendezvous With Advice: How to Rendezvous in a Disk
Venue: arXiv cs.DM 2018
Year: 2018

In the classic Symmetric Rendezvous problem on a Line (SRL), two robots at known distance 2 but unknown direction execute the same randomized algorithm trying to minimize the expected rendezvous time. A long standing conjecture is that the best possible rendezvous time is 4.25 with known upper and lower bounds being very close to that value. We introduce and study a geometric variation of SRL that we call Symmetric Rendezvous in a Disk (SRD) where two robots at distance 2 have a common reference point at distance $ρ$. We show that even when $ρ$ is not too small, the two robots can meet in expected time that is less than $4.25$. Part of our contribution is that we demonstrate how to adjust known, even simple and provably non-optimal, algorithms for SRL, effectively improving their performance in the presence of a reference point. Special to our algorithms for SRD is that, unlike in SRL, for every fixed $ρ$ the worst case distance traveled, i.e. energy that is used, in our algorithms is finite. In particular, we show that the energy of our algorithms is $O\left(ρ^2\right)$, while we also explore time-energy tradeoffs, concluding that one may be efficient both with respect to time and energy, with only a minor compromise on the optimal termination time.
Real-World Evolution Adapts Robot Morphology and Control to Hardware Limitations
Venue: arXiv cs.RO 2018
Year: 2018

For robots to handle the numerous factors that can affect them in the real world, they must adapt to changes and unexpected events. Evolutionary robotics tries to solve some of these issues by automatically optimizing a robot for a specific environment. Most of the research in this field, however, uses simplified representations of the robotic system in software simulations. The large gap between performance in simulation and the real world makes it challenging to transfer the resulting robots to the real world. In this paper, we apply real world multi-objective evolutionary optimization to optimize both control and morphology of a four-legged mammal-inspired robot. We change the supply voltage of the system, reducing the available torque and speed of all joints, and study how this affects both the fitness, as well as the morphology and control of the solutions. In addition to demonstrating that this real-world evolutionary scheme for morphology and control is indeed feasible with relatively few evaluations, we show that evolution under the different hardware limitations results in comparable performance for low and moderate speeds, and that the search achieves this by adapting both the control and the morphology of the robot.
Parameterized circuit complexity of model checking first-order logic on sparse structures
Venue: arXiv cs.DM 2018
Year: 2018

We prove that for every class $C$ of graphs with effectively bounded expansion, given a first-order sentence $φ$ and an $n$-element structure $\mathbb{A}$ whose Gaifman graph belongs to $C$, the question whether $φ$ holds in $\mathbb{A}$ can be decided by a family of AC-circuits of size $f(φ)\cdot n^c$ and depth $f(φ)+c\log n$, where $f$ is a computable function and $c$ is a universal constant. This places the model-checking problem for classes of bounded expansion in the parameterized circuit complexity class $para-AC^1$. On the route to our result we prove that the basic decomposition toolbox for classes of bounded expansion, including orderings with bounded weak coloring numbers and low treedepth decompositions, can be computed in $para-AC^1$.
FlowFields++: Accurate Optical Flow Correspondences Meet Robust Interpolation
Venue: arXiv cs.CV 2018
Year: 2018

Optical Flow algorithms are of high importance for many applications. Recently, the Flow Field algorithm and its modifications have shown remarkable results, as they have been evaluated with top accuracy on different data sets. In our analysis of the algorithm we have found that it produces accurate sparse matches, but there is room for improvement in the interpolation. Thus, we propose in this paper FlowFields++, where we combine the accurate matches of Flow Fields with a robust interpolation. In addition, we propose improved variational optimization as post-processing. Our new algorithm is evaluated on the challenging KITTI and MPI Sintel data sets with public top results on both benchmarks.
Learning Coordinated Tasks using Reinforcement Learning in Humanoids
Venue: arXiv cs.RO 2018
Year: 2018

With the advent of artificial intelligence and machine learning, humanoid robots are made to learn a variety of skills which humans possess. One of fundamental skills which humans use in day-to-day activities is performing tasks with coordination between both the hands. In case of humanoids, learning such skills require optimal motion planning which includes avoiding collisions with the surroundings. In this paper, we propose a framework to learn coordinated tasks in cluttered environments based on DiGrad - A multi-task reinforcement learning algorithm for continuous action-spaces. Further, we propose an algorithm to smooth the joint space trajectories obtained by the proposed framework in order to reduce the noise instilled during training. The proposed framework was tested on a 27 degrees of freedom (DoF) humanoid with articulated torso for performing coordinated object-reaching task with both the hands in four different environments with varying levels of difficulty. It is observed that the humanoid is able to plan collision free trajectory in real-time. Simulation results also reveal the usefulness of the articulated torso for performing tasks which require coordination between both the arms.
Adversarial Contrastive Estimation
Venue: arXiv cs.CL 2018
Year: 2018

Learning by contrasting positive and negative samples is a general strategy adopted by many methods. Noise contrastive estimation (NCE) for word embeddings and translating embeddings for knowledge graphs are examples in NLP employing this approach. In this work, we view contrastive learning as an abstraction of all such methods and augment the negative sampler into a mixture distribution containing an adversarially learned sampler. The resulting adaptive sampler finds harder negative examples, which forces the main model to learn a better representation of the data. We evaluate our proposal on learning word embeddings, order embeddings and knowledge graph embeddings and observe both faster convergence and improved results on multiple metrics.
The Dataset Nutrition Label: A Framework To Drive Higher Data Quality Standards
Venue: arXiv cs.DB 2018
Year: 2018

Artificial intelligence (AI) systems built on incomplete or biased data will often exhibit problematic outcomes. Current methods of data analysis, particularly before model development, are costly and not standardized. The Dataset Nutrition Label (the Label) is a diagnostic framework that lowers the barrier to standardized data analysis by providing a distilled yet comprehensive overview of dataset "ingredients" before AI model development. Building a Label that can be applied across domains and data types requires that the framework itself be flexible and adaptable; as such, the Label is comprised of diverse qualitative and quantitative modules generated through multiple statistical and probabilistic modelling backends, but displayed in a standardized format. To demonstrate and advance this concept, we generated and published an open source prototype with seven sample modules on the ProPublica Dollars for Docs dataset. The benefits of the Label are manyfold. For data specialists, the Label will drive more robust data analysis practices, provide an efficient way to select the best dataset for their purposes, and increase the overall quality of AI models as a result of more robust training datasets and the ability to check for issues at the time of model development. For those building and publishing datasets, the Label creates an expectation of explanation, which will drive better data collection practices. We also explore the limitations of the Label, including the challenges of generalizing across diverse datasets, and the risk of using "ground truth" data as a comparison dataset. We discuss ways to move forward given the limitations identified. Lastly, we lay out future directions for the Dataset Nutrition Label project, including research and public policy agendas to further advance consideration of the concept.
Mitigating the Risk of Voltage Collapse using Statistical Measures from PMU Data
Venue: arXiv cs.SY 2018
Year: 2018

With the continued deployment of synchronized Phasor Measurement Units (PMUs), high sample rate data are rapidly increasing the real time observability of power systems. Prior research has shown that the statistics of these data can provide useful information regarding network stability, but it is not yet known how this statistical information can be actionably used to improve power system stability. To address this issue, this paper presents a method that gauges and improves the voltage stability of a system using the statistics present in PMU data streams. Leveraging an analytical solver to determine a range of "critical" bus voltage variances, the presented methods monitor raw statistical data in an observable load pocket to determine when control actions are needed to mitigate the risk of voltage collapse. A simple reactive power controller is then implemented, which acts dynamically to maintain an acceptable voltage stability margin within the system. Time domain simulations on 3-bus and 39-bus test cases demonstrate that the resulting statistical controller can out-perform more conventional feedback control systems by maintaining voltage stability margins while loads simultaneously increase and fluctuate.
Deep Learning of Geometric Constellation Shaping including Fiber Nonlinearities
Venue: arXiv cs.IT 2018
Year: 2018

A new geometric shaping method is proposed, leveraging unsupervised machine learning to optimize the constellation design. The learned constellation mitigates nonlinear effects with gains up to 0.13 bit/4D when trained with a simplified fiber channel model.
Human Capital in Software Engineering: A Systematic Mapping of Reconceptualized Human Aspect Studies
Venue: arXiv cs.SE 2018
Year: 2018

The human capital invested into software development plays a vital role in the success of any software project. By human capital, we do not mean the individuals themselves, but involves the range of knowledge and skills (i.e., human aspects) invested to create value during development. However, there is still no consensus on how these broad terms of human aspects relate to the health of a project. In this study, we reconceptualize human aspects of software engineering (SE) into a framework (i.e., SE human capital). The study presents a systematic mapping to survey and classify existing human aspect studies into four dimensions of the framework: capacity, deployment, development, and know-how (based on the Global Human Capital Index). From premium SE publishing venues (five journal articles and four conferences), we extract 2,698 hits of papers published between 2013 to 2017. Using a search criteria, we then narrow our results to 340 papers. Finally, we use inclusion and exclusion criteria to manually select 78 papers (49 quantitative and 29 qualitative studies). Using research questions, we uncover related topics, theories and data origins. The key outcome of this paper is a set of indicators for SE human capital. This work is towards the creation of a SE Human Capital Index (SE-HCI) to capture and rank human aspects, with the potential to assess progress within projects, and point to opportunities for cross-project learning and exchange across software projects.
Structure-from-Motion using Dense CNN Features with Keypoint Relocalization
Venue: arXiv cs.CV 2018
Year: 2018

Structure from Motion (SfM) using imagery that involves extreme appearance changes is yet a challenging task due to a loss of feature repeatability. Using feature correspondences obtained by matching densely extracted convolutional neural network (CNN) features significantly improves the SfM reconstruction capability. However, the reconstruction accuracy is limited by the spatial resolution of the extracted CNN features which is not even pixel-level accuracy in the existing approach. Providing dense feature matches with precise keypoint positions is not trivial because of memory limitation and computational burden of dense features. To achieve accurate SfM reconstruction with highly repeatable dense features, we propose an SfM pipeline that uses dense CNN features with relocalization of keypoint position that can efficiently and accurately provide pixel-level feature correspondences. Then, we demonstrate on the Aachen Day-Night dataset that the proposed SfM using dense CNN features with the keypoint relocalization outperforms a state-of-the-art SfM (COLMAP using RootSIFT) by a large margin.
Ring Exploration with Myopic Luminous Robots
Venue: arXiv cs.DC 2018
Year: 2018

We investigate exploration algorithms for autonomous mobile robots evolving in uniform ring-shaped networks. Different from the usual Look-Compute-Move (LCM) model, we consider two characteristics: myopia and luminosity. Myopia means each robot has a limited visibility. We consider the weakest assumption for myopia: each robot can only observe its neighboring nodes. Luminosity means each robot maintains a non-volatile visible light. We consider the weakest assumption for luminosity: each robot can use only two colors for its light. The main interest of this paper is to clarify the impact of luminosity on exploration with myopic robots. As a main contribution, we prove that 1) in the fully synchronous model, two and three robots are necessary and sufficient to achieve perpetual and terminating exploration, respectively, and 2) in the semi-synchronous and asynchronous models, three and four robots are necessary and sufficient to achieve perpetual and terminating exploration, respectively. These results clarify the power of lights for myopic robots since, without lights, five robots are necessary and sufficient to achieve terminating exploration in the fully synchronous model, and no terminating exploration algorithm exists in the semi-synchronous and asynchronous models. We also show that, in the fully synchronous model (resp., the semi-synchronous and asynchronous models), the proposed perpetual exploration algorithm is universal, that is, the algorithm solves perpetual exploration from any solvable initial configuration with two (resp., three) robots and two colors. On the other hand, we show that, in the fully synchronous model (resp., the semi-synchronous and asynchronous models), no universal algorithm exists for terminating exploration, that is, no algorithm may solve terminating exploration from any solvable initial configuration with three (resp., four) robots and two colors.
Energy-Efficient Mobile Network I/O
Venue: arXiv cs.NI 2018
Year: 2018

By year 2020, the number of smartphone users globally will reach 3 Billion and the mobile data traffic (cellular + WiFi) will exceed PC Internet traffic the first time. As the number of smartphone users and the amount of data transferred per smartphone grow exponentially, limited battery power is becoming an increasingly critical problem for mobile devices which heavily depend on network I/O. Despite the growing body of research in power management techniques for the mobile devices at the hardware layer as well as the lower layers of the networking stack, there has been little work focusing on saving energy at the application layer for the mobile systems during network I/O. In this paper, we show that significant energy savings can be achieved with application-layer solutions at the mobile systems during data transfer with no performance penalty. In many cases, performance increase and energy savings can be achieved simultaneously.
Efficient Explicit Time Stepping of High Order Discontinuous Galerkin Schemes for Waves
Venue: arXiv cs.NA 2018
Year: 2018

This work presents algorithms for the efficient implementation of discontinuous Galerkin methods with explicit time stepping for acoustic wave propagation on unstructured meshes of quadrilaterals or hexahedra. A crucial step towards efficiency is to evaluate operators in a matrix-free way with sum-factorization kernels. The method allows for general curved geometries and variable coefficients. Temporal discretization is carried out by low-storage explicit Runge-Kutta schemes and the arbitrary derivative (ADER) method. For ADER, we propose a flexible basis change approach that combines cheap face integrals with cell evaluation using collocated nodes and quadrature points. Additionally, a degree reduction for the optimized cell evaluation is presented to decrease the computational cost when evaluating higher order spatial derivatives as required in ADER time stepping. We analyze and compare the performance of state-of-the-art Runge-Kutta schemes and ADER time stepping with the proposed optimizations. ADER involves fewer operations and additionally reaches higher throughput by higher arithmetic intensities and hence decreases the required computational time significantly. Comparison of Runge-Kutta and ADER at their respective CFL stability limit renders ADER especially beneficial for higher orders when the Butcher barrier implies an overproportional amount of stages. Moreover, vector updates in explicit Runge--Kutta schemes are shown to take a substantial amount of the computational time due to their memory intensity.
On the Annihilator Ideal of an Inverse Form. A Simplification
Venue: arXiv cs.SC 2018
Year: 2018

We simplify an earlier paper of the same title by not using syzygy polynomials and by not using a trichotomy of inverse forms. Let $\K$ be a field and $\M=\K[x^{-1},z^{-1}]$ denote Macaulay's $\K[x,z]$ module of inverse polynomials; here $z$ and $z^{-1}$ are homogenising variables. An inverse form $F\in\M$ has a homogeneous annihilator ideal, $\I_F$\,. In an earlier paper we inductively constructed an ordered pair ($f_1$\,,\,$f_2$) of forms in $\K[x,z]$ which generate $\I_F$. We used syzygy polynomials to show that the intermediate forms give a minimal grlex Groebner basis, which can be efficiently reduced. We give a significantly shorter proof that the intermediate forms are a minimal grlex Groebner basis for $\I_F$\,. We also simplify our proof that either $ F$ is already reduced or a monomial of $f_1$ can be reduced by $f_2$\,. The algorithm that computes $f_1\,,f_2$ yields a variant of the Berlekamp-Massey algorithm which does not use the last 'length change' approach of Massey. These new proofs avoid the three separate cases, 'triples' and the technical factorisation of intermediate 'essential' forms. We also show that $f_1,f_2$ is a maximal $\R$ regular sequence for $\I_F$\,, so that $\I_F$ is a complete intersection.