OpenRaiser/Intern-Atlas huggingface dataset:
Graph Similarity and Approximate Isomorphism
Venue: arXiv cs.DS 2018
Year: 2018

The graph similarity problem, also known as approximate graph isomorphism or graph matching problem, has been extensively studied in the machine learning community, but has not received much attention in the algorithms community: Given two graphs $G,H$ of the same order $n$ with adjacency matrices $A_G,A_H$, a well-studied measure of similarity is the Frobenius distance \[ \mathrm{dist}(G,H):=\min_π\|A_G^π-A_H\|_F, \] where $π$ ranges over all permutations of the vertex set of $G$, where $A_G^π$ denotes the matrix obtained from $A_G$ by permuting rows and columns according to $π$, and where $\|M\|_F$ is the Frobenius norm of a matrix $M$. The (weighted) graph similarity problem, denoted by SIM (WSIM), is the problem of computing this distance for two graphs of same order. This problem is closely related to the notoriously hard quadratic assignment problem (QAP), which is known to be NP-hard even for severely restricted cases. It is known that SIM (WSIM) is NP-hard; we strengthen this hardness result by showing that the problem remains NP-hard even for the class of trees. Identifying the boundary of tractability for WSIM is best done in the framework of linear algebra. We show that WSIM is NP-hard as long as one of the matrices has unbounded rank or negative eigenvalues: hence, the realm of tractability is restricted to positive semi-definite matrices of bounded rank. Our main result is a polynomial time algorithm for the special case where one of the matrices has a bounded clustering number, a parameter arising from spectral graph drawing techniques.
6D Pose Estimation using an Improved Method based on Point Pair Features
Venue: arXiv cs.CV 2018
Year: 2018

The Point Pair Feature (Drost et al. 2010) has been one of the most successful 6D pose estimation method among model-based approaches as an efficient, integrated and compromise alternative to the traditional local and global pipelines. During the last years, several variations of the algorithm have been proposed. Among these extensions, the solution introduced by Hinterstoisser et al. (2016) is a major contribution. This work presents a variation of this PPF method applied to the SIXD Challenge datasets presented at the 3rd International Workshop on Recovering 6D Object Pose held at the ICCV 2017. We report an average recall of 0.77 for all datasets and overall recall of 0.82, 0.67, 0.85, 0.37, 0.97 and 0.96 for hinterstoisser, tless, tudlight, rutgers, tejani and doumanoglou datasets, respectively.
Optimal Stochastic Delivery Planning in Full-Truckload and Less-Than-Truckload Delivery
Venue: arXiv cs.AI 2018
Year: 2018

With an increasing demand from emerging logistics businesses, Vehicle Routing Problem with Private fleet and common Carrier (VRPPC) has been introduced to manage package delivery services from a supplier to customers. However, almost all of existing studies focus on the deterministic problem that assumes all parameters are known perfectly at the time when the planning and routing decisions are made. In reality, some parameters are random and unknown. Therefore, in this paper, we consider VRPPC with hard time windows and random demand, called Optimal Delivery Planning (ODP). The proposed ODP aims to minimize the total package delivery cost while meeting the customer time window constraints. We use stochastic integer programming to formulate the optimization problem incorporating the customer demand uncertainty. Moreover, we evaluate the performance of the ODP using test data from benchmark dataset and from actual Singapore road map.
SmartUnit: Empirical Evaluations for Automated Unit Testing of Embedded Software in Industry
Venue: arXiv cs.SE 2018
Year: 2018

In this paper, we aim at the automated unit coverage-based testing for embedded software. To achieve the goal, by analyzing the industrial requirements and our previous work on automated unit testing tool CAUT, we rebuild a new tool, SmartUnit, to solve the engineering requirements that take place in our partner companies. SmartUnit is a dynamic symbolic execution implementation, which supports statement, branch, boundary value and MC/DC coverage. SmartUnit has been used to test more than one million lines of code in real projects. For confidentiality motives, we select three in-house real projects for the empirical evaluations. We also carry out our evaluations on two open source database projects, SQLite and PostgreSQL, to test the scalability of our tool since the scale of the embedded software project is mostly not large, 5K-50K lines of code on average. From our experimental results, in general, more than 90% of functions in commercial embedded software achieve 100% statement, branch, MC/DC coverage, more than 80% of functions in SQLite achieve 100% MC/DC coverage, and more than 60% of functions in PostgreSQL achieve 100% MC/DC coverage. Moreover, SmartUnit is able to find the runtime exceptions at the unit testing level. We also have reported exceptions like array index out of bounds and divided-by-zero in SQLite. Furthermore, we analyze the reasons of low coverage in automated unit testing in our setting and give a survey on the situation of manual unit testing with respect to automated unit testing in industry.
Implicit definability of truth constants in Łukasiewicz logic
Venue: arXiv cs.LO 2018
Year: 2018

In the framework of propositional Łukasiewicz logic, a suitable notion of implicit definability, tailored to the intended real-valued semantics and referring to the elements of its domain, is introduced. Several variants of implicitly defining each of the rational elements in the standard semantics are explored, and based on that, a faithful interpretation of theories in Rational Pavelka logic in theories in Łukasiewicz logic is obtained. Some of these results were already presented in Hájek's "Metamathematics of Fuzzy Logic" as technical statements. A connection to the lack of (deductive) Beth property in Łukasiewicz logic is drawn. Moreover, while irrational elements of the standard semantics are not implicitly definable by finitary means, a parallel development is possible for them in the infinitary Łukasiewicz logic. As an application of definability of the rationals, it is shown how computational complexity results for Rational Pavelka logic can be obtained from analogous results for Łukasiewicz logic. The complexity of the definability notion itself is studied as well. Finally, we review the import of these results for the precision/vagueness discussion for fuzzy logic, and for the general standing of truth constants in Łukasiewicz logic.
DataSite: Proactive Visual Data Exploration with Computation of Insight-based Recommendations
Venue: arXiv cs.HC 2018
Year: 2018

Effective data analysis ideally requires the analyst to have high expertise as well as high knowledge of the data. Even with such familiarity, manually pursuing all potential hypotheses and exploring all possible views is impractical. We present DataSite, a proactive visual analytics system where the burden of selecting and executing appropriate computations is shared by an automatic server-side computation engine. Salient features identified by these automatic background processes are surfaced as notifications in a feed timeline. DataSite effectively turns data analysis into a conversation between analyst and computer, thereby reducing the cognitive load and domain knowledge requirements. We validate the system with a user study comparing it to a recent visualization recommendation system, yielding significant improvement, particularly for complex analyses that existing analytics systems do not support well.
An Approach to Vehicle Trajectory Prediction Using Automatically Generated Traffic Maps
Venue: arXiv cs.CV 2018
Year: 2018

Trajectory and intention prediction of traffic participants is an important task in automated driving and crucial for safe interaction with the environment. In this paper, we present a new approach to vehicle trajectory prediction based on automatically generated maps containing statistical information about the behavior of traffic participants in a given area. These maps are generated based on trajectory observations using image processing and map matching techniques and contain all typical vehicle movements and probabilities in the considered area. Our prediction approach matches an observed trajectory to a behavior contained in the map and uses this information to generate a prediction. We evaluated our approach on a dataset containing over 14000 trajectories and found that it produces significantly more precise mid-term predictions compared to motion model-based prediction approaches.
Homomorphism Extension
Venue: arXiv cs.DS 2018
Year: 2018

We define the Homomorphism Extension (HomExt) problem: given a group $G$, a subgroup $M \leq G$ and a homomorphism $φ: M \to H$, decide whether or not there exists a homomorphism $\widetildeφ: G\to H$ extending $φ$, i.e., $\widetildeφ|_M = φ$. This problem arose in the context of list-decoding homomorphism codes but is also of independent interest, both as a problem in computational group theory and as a new and natural problem in NP of unsettled complexity status. We consider the case $H=S_m$ (the symmetric group of degree $m$), i.e., $φ: G \to H$ is a $G$-action on a set of $m$ elements. We assume $G\le S_n$ is given as a permutation group by a list of generators. We characterize the equivalence classes of extensions in terms of a multidimensional oracle subset-sum problem. From this we infer that for bounded $G$ the HomExt problem can be solved in polynomial time. Our main result concerns the case $G=A_n$ (the alternating group of degree $n$) for variable $n$ under the assumption that the index of $M$ in $G$ is bounded by poly$(n)$. We solve this case in polynomial time for all $m < 2^{n-1}/\sqrt{n}$. This is the case with direct relevance to homomorphism codes (Babai, Black, and Wuu, arXiv 2018); it is used as a component of one of the main algorithms in that paper.
"You are no Jack Kennedy": On Media Selection of Highlights from Presidential Debates
Venue: arXiv cs.SI 2018
Year: 2018

Political speeches and debates play an important role in shaping the images of politicians, and the public often relies on media outlets to select bits of political communication from a large pool of utterances. It is an important research question to understand what factors impact this selection process. To quantitatively explore the selection process, we build a three- decade dataset of presidential debate transcripts and post-debate coverage. We first examine the effect of wording and propose a binary classification framework that controls for both the speaker and the debate situation. We find that crowdworkers can only achieve an accuracy of 60% in this task, indicating that media choices are not entirely obvious. Our classifiers outperform crowdworkers on average, mainly in primary debates. We also compare important factors from crowdworkers' free-form explanations with those from data-driven methods and find interesting differences. Few crowdworkers mentioned that "context matters", whereas our data show that well-quoted sentences are more distinct from the previous utterance by the same speaker than less-quoted sentences. Finally, we examine the aggregate effect of media preferences towards different wordings to understand the extent of fragmentation among media outlets. By analyzing a bipartite graph built from quoting behavior in our data, we observe a decreasing trend in bipartisan coverage.
Facial Expression Analysis under Partial Occlusion: A Survey
Venue: arXiv cs.CV 2018
Year: 2018

Automatic machine-based Facial Expression Analysis (FEA) has made substantial progress in the past few decades driven by its importance for applications in psychology, security, health, entertainment and human computer interaction. The vast majority of completed FEA studies are based on non-occluded faces collected in a controlled laboratory environment. Automatic expression recognition tolerant to partial occlusion remains less understood, particularly in real-world scenarios. In recent years, efforts investigating techniques to handle partial occlusion for FEA have seen an increase. The context is right for a comprehensive perspective of these developments and the state of the art from this perspective. This survey provides such a comprehensive review of recent advances in dataset creation, algorithm development, and investigations of the effects of occlusion critical for robust performance in FEA systems. It outlines existing challenges in overcoming partial occlusion and discusses possible opportunities in advancing the technology. To the best of our knowledge, it is the first FEA survey dedicated to occlusion and aimed at promoting better informed and benchmarked future work.
Single Image Super-Resolution via Cascaded Multi-Scale Cross Network
Venue: arXiv cs.CV 2018
Year: 2018

The deep convolutional neural networks have achieved significant improvements in accuracy and speed for single image super-resolution. However, as the depth of network grows, the information flow is weakened and the training becomes harder and harder. On the other hand, most of the models adopt a single-stream structure with which integrating complementary contextual information under different receptive fields is difficult. To improve information flow and to capture sufficient knowledge for reconstructing the high-frequency details, we propose a cascaded multi-scale cross network (CMSC) in which a sequence of subnetworks is cascaded to infer high resolution features in a coarse-to-fine manner. In each cascaded subnetwork, we stack multiple multi-scale cross (MSC) modules to fuse complementary multi-scale information in an efficient way as well as to improve information flow across the layers. Meanwhile, by introducing residual-features learning in each stage, the relative information between high-resolution and low-resolution features is fully utilized to further boost reconstruction performance. We train the proposed network with cascaded-supervision and then assemble the intermediate predictions of the cascade to achieve high quality image reconstruction. Extensive quantitative and qualitative evaluations on benchmark datasets illustrate the superiority of our proposed method over state-of-the-art super-resolution methods.
PSO-based Fuzzy Markup Language for Student Learning Performance Evaluation and Educational Application
Venue: arXiv cs.AI 2018
Year: 2018

This paper proposes an agent with particle swarm optimization (PSO) based on a Fuzzy Markup Language (FML) for students learning performance evaluation and educational applications, and the proposed agent is according to the response data from a conventional test and an item response theory. First, we apply a GS-based parameter estimation mechanism to estimate the items parameters according to the response data, and then to compare its results with those of an IRT-based Bayesian parameter estimation mechanism. In addition, we propose a static-IRT test assembly mechanism to assemble a form for the conventional test. The presented FML-based dynamic assessment mechanism infers the probability of making a correct response to the item for a student with various abilities. Moreover, this paper also proposes a novel PFML learning mechanism for optimizing the parameters between items and students. Finally, we adopt a K-fold cross validation mechanism to evaluate the performance of the proposed agent. Experimental results show that the novel PFML learning mechanism for the parameter estimation and learning optimization performs favorably. We believe the proposed PFML will be a reference for education research and pedagogy and an important co-learning mechanism for future human-machine educational applications.
One Big Net For Everything
Venue: arXiv cs.AI 2018
Year: 2018

I apply recent work on "learning to think" (2015) and on PowerPlay (2011) to the incremental training of an increasingly general problem solver, continually learning to solve new tasks without forgetting previous skills. The problem solver is a single recurrent neural network (or similar general purpose computer) called ONE. ONE is unusual in the sense that it is trained in various ways, e.g., by black box optimization / reinforcement learning / artificial evolution as well as supervised / unsupervised learning. For example, ONE may learn through neuroevolution to control a robot through environment-changing actions, and learn through unsupervised gradient descent to predict future inputs and vector-valued reward signals as suggested in 1990. User-given tasks can be defined through extra goal-defining input patterns, also proposed in 1990. Suppose ONE has already learned many skills. Now a copy of ONE can be re-trained to learn a new skill, e.g., through neuroevolution without a teacher. Here it may profit from re-using previously learned subroutines, but it may also forget previous skills. Then ONE is retrained in PowerPlay style (2011) on stored input/output traces of (a) ONE's copy executing the new skill and (b) previous instances of ONE whose skills are still considered worth memorizing. Simultaneously, ONE is retrained on old traces (even those of unsuccessful trials) to become a better predictor, without additional expensive interaction with the enviroment. More and more control and prediction skills are thus collapsed into ONE, like in the chunker-automatizer system of the neural history compressor (1991). This forces ONE to relate partially analogous skills (with shared algorithmic information) to each other, creating common subroutines in form of shared subnetworks of ONE, to greatly speed up subsequent learning of additional, novel but algorithmically related skills.
Lovász Meets Weisfeiler and Leman
Venue: arXiv cs.DS 2018
Year: 2018

In this paper, we relate a beautiful theory by Lovász with a popular heuristic algorithm for the graph isomorphism problem, namely the color refinement algorithm and its k-dimensional generalization known as the Weisfeiler-Leman algorithm. We prove that two graphs G and H are indistinguishable by the color refinement algorithm if and only if, for all trees T, the number Hom(T,G) of homomorphisms from T to G equals the corresponding number Hom(T,H) for H. There is a natural system of linear equations whose nonnegative integer solutions correspond to the isomorphisms between two graphs. The nonnegative real solutions to this system are called fractional isomorphisms, and two graphs are fractionally isomorphic if and only if the color refinement algorithm cannot distinguish them (Tinhofer 1986, 1991). We show that, if we drop the nonnegativity constraints, that is, if we look for arbitrary real solutions, then a solution to the linear system exists if and only if, for all t, the two graphs have the same number of length-t walks. We lift the results for trees to an equivalence between numbers of homomorphisms from graphs of tree width k, the k-dimensional Weisfeiler-Leman algorithm, and the level-k Sherali-Adams relaxation of our linear program. We also obtain a partial result for graphs of bounded path width and solutions to our system where we drop the nonnegativity constraints. A consequence of our results is a quasi-linear time algorithm to decide whether, for two given graphs G and H, there is a tree T with Hom(T,G) = Hom(T,H).
Importance of initial conditions in the polarization of complex networks
Venue: arXiv cs.SI 2018
Year: 2018

Currently used models of opinion formation use random initial conditions. In reality, most people in a social network, except for a small fraction of the population, are initially either unaware of, or indifferent to, the disputed issue. To explore the consequences of such specific initial conditions, we study the polarization of social networks when conflicting ideas arise on two different seed nodes and then spread according to a majority rule. Using the configuration model and the stochastic block model as examples, we show that this framework leads to substantially different outcomes than those which employ random initial conditions. Moreover, the empirically observed splits in the karate and the dolphins' networks naturally come out of this paradigm. Our work thus suggests that the existing opinion dynamics models should be reevaluated to incorporate the initial condition dependence.
Product Kernel Interpolation for Scalable Gaussian Processes
Venue: arXiv cs.LG 2018
Year: 2018

Recent work shows that inference for Gaussian processes can be performed efficiently using iterative methods that rely only on matrix-vector multiplications (MVMs). Structured Kernel Interpolation (SKI) exploits these techniques by deriving approximate kernels with very fast MVMs. Unfortunately, such strategies suffer badly from the curse of dimensionality. We develop a new technique for MVM based learning that exploits product kernel structure. We demonstrate that this technique is broadly applicable, resulting in linear rather than exponential runtime with dimension for SKI, as well as state-of-the-art asymptotic complexity for multi-task GPs.
Free-breathing cardiac MRI using bandlimited manifold modelling
Venue: arXiv cs.CV 2018
Year: 2018

We introduce a novel bandlimited manifold framework and an algorithm to recover freebreathing and ungated cardiac MR images from highly undersampled measurements. The image frames in the free breathing and ungated dataset are assumed to be points on a bandlimited manifold. We introduce a novel kernel low-rank algorithm to estimate the manifold structure (Laplacian) from a navigator-based acquisition scheme. The structure of the manifold is then used to recover the images from highly undersampled measurements. A computationally efficient algorithm, which relies on the bandlimited approximation of the Laplacian matrix, is used to recover the images. The proposed scheme is demonstrated on several patients with different breathing patterns and cardiac rates, without requiring the need for manually tuning the reconstruction parameters in each case. The proposed scheme enabled the recovery of free-breathing and ungated data, providing reconstructions that are qualitatively similar to breath-held scans performed on the same patients. This shows the potential of the technique as a clinical protocol for free-breathing cardiac scans.
OhioState at SemEval-2018 Task 7: Exploiting Data Augmentation for Relation Classification in Scientific Papers using Piecewise Convolutional Neural Networks
Venue: arXiv cs.CL 2018
Year: 2018

We describe our system for SemEval-2018 Shared Task on Semantic Relation Extraction and Classification in Scientific Papers where we focus on the Classification task. Our simple piecewise convolution neural encoder performs decently in an end to end manner. A simple inter-task data augmentation signifi- cantly boosts the performance of the model. Our best-performing systems stood 8th out of 20 teams on the classification task on noisy data and 12th out of 28 teams on the classification task on clean data.
The Mutual Information in Random Linear Estimation Beyond i.i.d. Matrices
Venue: arXiv cs.IT 2018
Year: 2018

There has been definite progress recently in proving the variational single-letter formula given by the heuristic replica method for various estimation problems. In particular, the replica formula for the mutual information in the case of noisy linear estimation with random i.i.d. matrices, a problem with applications ranging from compressed sensing to statistics, has been proven rigorously. In this contribution we go beyond the restrictive i.i.d. matrix assumption and discuss the formula proposed by Takeda, Uda, Kabashima and later by Tulino, Verdu, Caire and Shamai who used the replica method. Using the recently introduced adaptive interpolation method and random matrix theory, we prove this formula for a relevant large sub-class of rotationally invariant matrices.