OpenRaiser/Intern-Atlas huggingface dataset:
A journey in modal proof theory: From minimal normal modal logic to discrete linear temporal logic
Venue: arXiv cs.LO 2020
Year: 2020

Extending and generalizing the approach of 2-sequents (Masini, 1992), we present sequent calculi for the classical modal logics in the K, D, T, S4 spectrum. The systems are presented in a uniform way-different logics are obtained by tuning a single parameter, namely a constraint on the applicability of a rule. Cut-elimination is proved only once, since the proof goes through independently from the constraints giving rise to the different systems. A sequent calculus for the discrete linear temporal logic ltl is also given and proved complete. Leitmotiv of the paper is the formal analogy between modality and first-order quantification.
Quantifying Polarization on Twitter: the Kavanaugh Nomination
Venue: arXiv cs.SI 2020
Year: 2020

This paper addresses polarization quantification, particularly as it pertains to the nomination of Brett Kavanaugh to the US Supreme Court and his subsequent confirmation with the narrowest margin since 1881. Republican (GOP) and Democratic (DNC) senators voted overwhelmingly along party lines. In this paper, we examine political polarization concerning the nomination among Twitter users. To do so, we accurately identify the stance of more than 128 thousand Twitter users towards Kavanaugh's nomination using both semi-supervised and supervised classification. Next, we quantify the polarization between the different groups in terms of who they retweet and which hashtags they use. We modify existing polarization quantification measures to make them more efficient and more effective. We also characterize the polarization between users who supported and opposed the nomination.
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
Venue: arXiv cs.CC 2020
Year: 2020

We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greater-than. We apply our generalized theorem to solve two open problems: * We present the first result that demonstrates a separation in proof power for cutting planes with unbounded versus polynomially bounded coefficients. Specifically, we exhibit CNF formulas that can be refuted in quadratic length and constant line space in cutting planes with unbounded coefficients, but for which there are no refutations in subexponential length and subpolynomial line space if coefficients are restricted to be of polynomial magnitude. * We give the first explicit separation between monotone Boolean formulas and monotone real formulas. Specifically, we give an explicit family of functions that can be computed with monotone real formulas of nearly linear size but require monotone Boolean formulas of exponential size. Previously only a non-explicit separation was known. An important technical ingredient, which may be of independent interest, is that we show that the Nullstellensatz degree of refuting the pebbling formula over a DAG G over any field coincides exactly with the reversible pebbling price of G. In particular, this implies that the standard decision tree complexity and the parity decision tree complexity of the corresponding falsified clause search problem are equal.
Transition Property for $α$-Power Free Languages with $α\geq 2$ and $k\geq 3$ Letters
Venue: arXiv cs.DM 2020
Year: 2020

In 1985, Restivo and Salemi presented a list of five problems concerning power free languages. Problem $4$ states: Given $α$-power-free words $u$ and $v$, decide whether there is a transition from $u$ to $v$. Problem $5$ states: Given $α$-power-free words $u$ and $v$, find a transition word $w$, if it exists. Let $Σ_k$ denote an alphabet with $k$ letters. Let $L_{k,α}$ denote the $α$-power free language over the alphabet $Σ_k$, where $α$ is a rational number or a rational "number with $+$". If $α$ is a "number with $+$" then suppose $k\geq 3$ and $α\geq 2$. If $α$ is "only" a number then suppose $k=3$ and $α>2$ or $k>3$ and $α\geq 2$. We show that: If $u\in L_{k,α}$ is a right extendable word in $L_{k,α}$ and $v\in L_{k,α}$ is a left extendable word in $L_{k,α}$ then there is a (transition) word $w$ such that $uwv\in L_{k,α}$. We also show a construction of the word $w$.
An Exploration of Embodied Visual Exploration
Venue: arXiv cs.CV 2020
Year: 2020

Embodied computer vision considers perception for robots in novel, unstructured environments. Of particular importance is the embodied visual exploration problem: how might a robot equipped with a camera scope out a new environment? Despite the progress thus far, many basic questions pertinent to this problem remain unanswered: (i) What does it mean for an agent to explore its environment well? (ii) Which methods work well, and under which assumptions and environmental settings? (iii) Where do current approaches fall short, and where might future work seek to improve? Seeking answers to these questions, we first present a taxonomy for existing visual exploration algorithms and create a standard framework for benchmarking them. We then perform a thorough empirical study of the four state-of-the-art paradigms using the proposed framework with two photorealistic simulated 3D environments, a state-of-the-art exploration architecture, and diverse evaluation metrics. Our experimental results offer insights and suggest new performance metrics and baselines for future work in visual exploration. Code, models and data are publicly available: https://github.com/facebookresearch/exploring_exploration
Dynamic Task Weighting Methods for Multi-task Networks in Autonomous Driving Systems
Venue: arXiv cs.CV 2020
Year: 2020

Deep multi-task networks are of particular interest for autonomous driving systems. They can potentially strike an excellent trade-off between predictive performance, hardware constraints and efficient use of information from multiple types of annotations and modalities. However, training such models is non-trivial and requires balancing learning over all tasks as their respective losses display different scales, ranges and dynamics across training. Multiple task weighting methods that adjust the losses in an adaptive way have been proposed recently on different datasets and combinations of tasks, making it difficult to compare them. In this work, we review and systematically evaluate nine task weighting strategies on common grounds on three automotive datasets (KITTI, Cityscapes and WoodScape). We then propose a novel method combining evolutionary meta-learning and task-based selective backpropagation, for computing task weights leading to reliable network training. Our method outperforms state-of-the-art methods by a significant margin on a two-task application.
Revealing Neural Network Bias to Non-Experts Through Interactive Counterfactual Examples
Venue: arXiv cs.HC 2020
Year: 2020

AI algorithms are not immune to biases. Traditionally, non-experts have little control in uncovering potential social bias (e.g., gender bias) in the algorithms that may impact their lives. We present a preliminary design for an interactive visualization tool CEB to reveal biases in a commonly used AI method, Neural Networks (NN). CEB combines counterfactual examples and abstraction of an NN decision process to empower non-experts to detect bias. This paper presents the design of CEB and initial findings of an expert panel (n=6) with AI, HCI, and Social science experts.
Efficient network navigation with partial information
Venue: arXiv cs.SI 2020
Year: 2020

We propose a information theoretical framework to capture transition and information costs of network navigation models. Based on the minimum description length principle and the Markov decision process, we demonstrate that efficient global navigation can be achieved with only partial information. Additionally, we derived a scalable algorithm for optimal solutions under certain conditions. The proposed algorithm can be interpreted as a dynamical process on network, making it a useful tool for analysing and understanding navigation strategies on real world networks.
Aggressive Perception-Aware Navigation using Deep Optical Flow Dynamics and PixelMPC
Venue: arXiv cs.RO 2020
Year: 2020

Recently, vision-based control has gained traction by leveraging the power of machine learning. In this work, we couple a model predictive control (MPC) framework to a visual pipeline. We introduce deep optical flow (DOF) dynamics, which is a combination of optical flow and robot dynamics. Using the DOF dynamics, MPC explicitly incorporates the predicted movement of relevant pixels into the planned trajectory of a robot. Our implementation of DOF is memory-efficient, data-efficient, and computationally cheap so that it can be computed in real-time for use in an MPC framework. The suggested Pixel Model Predictive Control (PixelMPC) algorithm controls the robot to accomplish a high-speed racing task while maintaining visibility of the important features (gates). This improves the reliability of vision-based estimators for localization and can eventually lead to safe autonomous flight. The proposed algorithm is tested in a photorealistic simulation with a high-speed drone racing task.
High-Level Plan for Behavioral Robot Navigation with Natural Language Directions and R-NET
Venue: arXiv cs.AI 2020
Year: 2020

When the navigational environment is known, it can be represented as a graph where landmarks are nodes, the robot behaviors that move from node to node are edges, and the route is a set of behavioral instructions. The route path from source to destination can be viewed as a class of combinatorial optimization problems where the path is a sequential subset from a set of discrete items. The pointer network is an attention-based recurrent network that is suitable for such a task. In this paper, we utilize a modified R-NET with gated attention and self-matching attention translating natural language instructions to a high-level plan for behavioral robot navigation by developing an understanding of the behavioral navigational graph to enable the pointer network to produce a sequence of behaviors representing the path. Tests on the navigation graph dataset show that our model outperforms the state-of-the-art approach for both known and unknown environments.
What can robotics research learn from computer vision research?
Venue: arXiv cs.RO 2020
Year: 2020

The computer vision and robotics research communities are each strong. However progress in computer vision has become turbo-charged in recent years due to big data, GPU computing, novel learning algorithms and a very effective research methodology. By comparison, progress in robotics seems slower. It is true that robotics came later to exploring the potential of learning -- the advantages over the well-established body of knowledge in dynamics, kinematics, planning and control is still being debated, although reinforcement learning seems to offer real potential. However, the rapid development of computer vision compared to robotics cannot be only attributed to the former's adoption of deep learning. In this paper, we argue that the gains in computer vision are due to research methodology -- evaluation under strict constraints versus experiments; bold numbers versus videos.
LiftTiles: Constructive Building Blocks for Prototyping Room-scale Shape-changing Interfaces
Venue: arXiv cs.HC 2020
Year: 2020

Large-scale shape-changing interfaces have great potential, but creating such systems requires substantial time, cost, space, and efforts, which hinders the research community to explore interactions beyond the scale of human hands. We introduce modular inflatable actuators as building blocks for prototyping room-scale shape-changing interfaces. Each actuator can change its height from 15cm to 150cm, actuated and controlled by air pressure. Each unit is low-cost (8 USD), lightweight (10 kg), compact (15 cm), and robust, making it well-suited for prototyping room-scale shape transformations. Moreover, our modular and reconfigurable design allows researchers and designers to quickly construct different geometries and to explore various applications. This paper contributes to the design and implementation of highly extendable inflatable actuators, and demonstrates a range of scenarios that can leverage this modular building block.
A Condition for Multiplicity Structure of Univariate Polynomials
Venue: arXiv cs.SC 2020
Year: 2020

We consider the problem of finding a condition for a univariate polynomial having a given multiplicity structure when the number of distinct roots is given. It is well known that such conditions can be written as conjunctions of several polynomial equations and one inequation in the coefficients, by using repeated parametric gcd's. In this paper, we give a novel condition which is not based on repeated gcd's. Furthermore, it is shown that the number of polynomials in the condition is optimal and the degree of polynomials is smaller than that in the previous condition based on repeated gcd's.
ILS-MPM: an implicit level-set-based material point method for frictional particulate contact mechanics of deformable particles
Venue: arXiv cs.CE 2020
Year: 2020

Finite element simulations of frictional multi-body contact problems via conformal meshes can be challenging and computationally demanding. To render geometrical features, unstructured meshes must be used and this unavoidably increases the degrees of freedom and therefore makes the construction of slave/master pairs more demanding. In this work, we introduce an implicit material point method designed to bypass the meshing of bodies by employing level set functions to represent boundaries at structured grids. This implicit function representation provides an elegant mean to link an unbiased intermediate reference surface with the true boundaries by closest point projection as shown in leichner et al. (2019). We then enforce the contact constraints by a penalty method where the Coulomb friction law is implemented as an elastoplastic constitutive model such that a return mapping algorithm can be used to provide constitutive updates for both the stick and slip states. To evolve the geometry of the contacts properly, the Hamilton-Jacobi equation is solved incrementally such that the level set and material points are both updated accord to the deformation field. To improve the accuracy and regularity of the numerical integration of the material point method, a moving least square method is used to project numerical values of the material points back to the standard locations for Gaussian-Legendre quadrature. Several benchmarks are used to verify the proposed model. Comparisons with discrete element simulations are made to analyze the importance of stress fields on predicting the macroscopic responses of granular assemblies.
Fast Neural Network Adaptation via Parameter Remapping and Architecture Search
Venue: arXiv cs.CV 2020
Year: 2020

Deep neural networks achieve remarkable performance in many computer vision tasks. Most state-of-the-art (SOTA) semantic segmentation and object detection approaches reuse neural network architectures designed for image classification as the backbone, commonly pre-trained on ImageNet. However, performance gains can be achieved by designing network architectures specifically for detection and segmentation, as shown by recent neural architecture search (NAS) research for detection and segmentation. One major challenge though, is that ImageNet pre-training of the search space representation (a.k.a. super network) or the searched networks incurs huge computational cost. In this paper, we propose a Fast Neural Network Adaptation (FNA) method, which can adapt both the architecture and parameters of a seed network (e.g. a high performing manually designed backbone) to become a network with different depth, width, or kernels via a Parameter Remapping technique, making it possible to utilize NAS for detection/segmentation tasks a lot more efficiently. In our experiments, we conduct FNA on MobileNetV2 to obtain new networks for both segmentation and detection that clearly out-perform existing networks designed both manually and by NAS. The total computation cost of FNA is significantly less than SOTA segmentation/detection NAS approaches: 1737$\times$ less than DPC, 6.8$\times$ less than Auto-DeepLab and 7.4$\times$ less than DetNAS. The code is available at https://github.com/JaminFong/FNA.
Joint Optimization of File Placement and Delivery in Cache-Assisted Wireless Networks with Limited Lifetime and Cache Space
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, the scheduling of downlink file transmission in one cell with the assistance of cache nodes with finite cache space is studied. Specifically, requesting users arrive randomly and the base station (BS) reactively multicasts files to the requesting users and selected cache nodes. The latter can offload the traffic in their coverage areas from the BS. We consider the joint optimization of the abovementioned file placement and delivery within a finite lifetime subject to the cache space constraint. Within the lifetime, the allocation of multicast power and symbol number for each file transmission at the BS is formulated as a dynamic programming problem with a random stage number. Note that there are no existing solutions to this problem. We develop an asymptotically optimal solution framework by transforming the original problem to an equivalent finite-horizon Markov decision process (MDP) with a fixed stage number. A novel approximation approach is then proposed to address the curse of dimensionality, where the analytical expressions of approximate value functions are provided. We also derive analytical bounds on the exact value function and approximation error. The approximate value functions depend on some system statistics, e.g., requesting users' distribution. One reinforcement learning algorithm is proposed for the scenario where these statistics are unknown.
A Group Norm Regularized Factorization Model for Subspace Segmentation
Venue: arXiv cs.LG 2020
Year: 2020

Subspace segmentation assumes that data comes from the union of different subspaces and the purpose of segmentation is to partition the data into the corresponding subspace. Low-rank representation (LRR) is a classic spectral-type method for solving subspace segmentation problems, that is, one first obtains an affinity matrix by solving a LRR model and then performs spectral clustering for segmentation. This paper proposes a group norm regularized factorization model (GNRFM) inspired by the LRR model for subspace segmentation and then designs an Accelerated Augmented Lagrangian Method (AALM) algorithm to solve this model. Specifically, we adopt group norm regularization to make the columns of the factor matrix sparse, thereby achieving a purpose of low rank, which means no Singular Value Decompositions (SVD) are required and the computational complexity of each step is greatly reduced. We obtain affinity matrices by using different LRR models and then performing cluster testing on different sets of synthetic noisy data and real data, respectively. Compared with traditional models and algorithms, the proposed method is faster and more robust to noise, so the final clustering results are better. Moreover, the numerical results show that our algorithm converges fast and only requires approximately ten iterations.
D3BA: A Tool for Optimizing Business Processes Using Non-Deterministic Planning
Venue: arXiv cs.AI 2020
Year: 2020

This paper builds upon recent work in the declarative design of dialogue agents and proposes an exciting new tool -- D3BA -- Declarative Design for Digital Business Automation, built to optimize business processes using the power of AI planning. The tool provides a powerful framework to build, optimize, and maintain complex business processes and optimize them by composing with services that automate one or more subtasks. We illustrate salient features of this composition technique, compare with other philosophies of composition, and highlight exciting opportunities for research in this emerging field of business process automation.
Natural Steganography in JPEG Domain with a Linear Development Pipeline
Venue: arXiv cs.MM 2020
Year: 2020

In order to achieve high practical security, Natural Steganography (NS) uses cover images captured at ISO sensitivity $ISO_{1}$ and generates stego images mimicking ISO sensitivity $ISO_{2}>ISO_{1}$. This is achieved by adding a stego signal to the cover that mimics the sensor photonic noise. This paper proposes an embedding mechanism to perform NS in the JPEG domain after linear developments by explicitly computing the correlations between DCT coefficients before quantization. In order to compute the covariance matrix of the photonic noise in the DCT domain, we first develop the matrix representation of demosaicking, luminance averaging, pixel section, and 2D-DCT. A detailed analysis of the resulting covariance matrix is done in order to explain the origins of the correlations between the coefficients of $3\times3$ DCT blocks. An embedding scheme is then presented that takes in order to take into account all the correlations. It employs 4 sub-lattices and 64 lattices per sub-lattices. The modification probabilities of each DCT coefficient are then derived by computing conditional probabilities from the multivariate Gaussian distribution using the Cholesky decomposition of the covariance matrix. This derivation is also used to compute the embedding capacity of each image. Using a specific database called E1 Base, we show that in the JPEG domain NS (J-Cov-NS) enables to achieve high capacity (more than 2 bits per non-zero AC DCT) and with high practical security ($P_{\mathrm{E}}\simeq40\%$ using DCTR from QF 75 to QF 100).
SirenLess: reveal the intention behind news
Venue: arXiv cs.HC 2020
Year: 2020

News articles tend to be increasingly misleading nowadays, preventing readers from making subjective judgments towards certain events. While some machine learning approaches have been proposed to detect misleading news, most of them are black boxes that provide limited help for humans in decision making. In this paper, we present SirenLess, a visual analytical system for misleading news detection by linguistic features. The system features article explorer, a novel interactive tool that integrates news metadata and linguistic features to reveal semantic structures of news articles and facilitate textual analysis. We use SirenLess to analyze 18 news articles from different sources and summarize some helpful patterns for misleading news detection. A user study with journalism professionals and university students is conducted to confirm the usefulness and effectiveness of our system.
Spinneret: Aiding Creative Ideation through Non-Obvious Concept Associations
Venue: arXiv cs.HC 2020
Year: 2020

Mind mapping is a popular way to explore a design space in creative thinking exercises, allowing users to form associations between concepts. Yet, most existing digital tools for mind mapping focus on authoring and organization, with little support for addressing the challenges of mind mapping such as stagnation and design fixation. We present Spinneret, a functional approach to aid mind mapping by providing suggestions based on a knowledge graph. Spinneret uses biased random walks to explore the knowledge graph in the neighborhood of an existing concept node in the mind map, and provides "suggestions" for the user to add to the mind map. A comparative study with a baseline mind-mapping tool reveals that participants created more diverse and distinct concepts with Spinneret, and reported that the suggestions inspired them to think of ideas they would otherwise not have explored.