OpenRaiser/Intern-Atlas huggingface dataset:
Large-Scale Maintenance and Unit Commitment: A Decentralized Subgradient Approach
Venue: arXiv cs.DC 2022
Year: 2022

Unit Commitment (UC) is a fundamental problem in power system operations. When coupled with generation maintenance, the joint optimization problem poses significant computational challenges due to coupling constraints linking maintenance and UC decisions. Obviously, these challenges grow with the size of the network. With the introduction of sensors for monitoring generator health and condition-based maintenance(CBM), these challenges have been magnified. ADMM-based decentralized methods have shown promise in solving large-scale UC problems, especially in vertically integrated power systems. However, in their current form, these methods fail to deliver similar computational performance and scalability when considering the joint UC and CBM problem. This paper provides a novel decentralized optimization framework for solving large-scale, joint UC and CBM problems. Our approach relies on the novel use of the subgradient method to temporally decouple various subproblems of the ADMM-based formulation of the joint problem along the maintenance horizon. By effectively utilizing multithreading, our decentralized subgradient approach delivers superior computational performance and eliminates the need to move sensor data thereby alleviating privacy and security concerns. Using experiments on large scale test cases, we show that our framework can provide a speedup of upto 50x as compared to various state of the art benchmarks without compromising on solution quality.
SelfVoxeLO: Self-supervised LiDAR Odometry with Voxel-based Deep Neural Networks
Venue: arXiv cs.CV 2022
Year: 2022

Recent learning-based LiDAR odometry methods have demonstrated their competitiveness. However, most methods still face two substantial challenges: 1) the 2D projection representation of LiDAR data cannot effectively encode 3D structures from the point clouds; 2) the needs for a large amount of labeled data for training limit the application scope of these methods. In this paper, we propose a self-supervised LiDAR odometry method, dubbed SelfVoxeLO, to tackle these two difficulties. Specifically, we propose a 3D convolution network to process the raw LiDAR data directly, which extracts features that better encode the 3D geometric patterns. To suit our network to self-supervised learning, we design several novel loss functions that utilize the inherent properties of LiDAR point clouds. Moreover, an uncertainty-aware mechanism is incorporated in the loss functions to alleviate the interference of moving objects/noises. We evaluate our method's performances on two large-scale datasets, i.e., KITTI and Apollo-SouthBay. Our method outperforms state-of-the-art unsupervised methods by 27%/32% in terms of translational/rotational errors on the KITTI dataset and also performs well on the Apollo-SouthBay dataset. By including more unlabelled training data, our method can further improve performance comparable to the supervised methods.
Algorithmic Stability and Generalization of an Unsupervised Feature Selection Algorithm
Venue: arXiv cs.LG 2022
Year: 2022

Feature selection, as a vital dimension reduction technique, reduces data dimension by identifying an essential subset of input features, which can facilitate interpretable insights into learning and inference processes. Algorithmic stability is a key characteristic of an algorithm regarding its sensitivity to perturbations of input samples. In this paper, we propose an innovative unsupervised feature selection algorithm attaining this stability with provable guarantees. The architecture of our algorithm consists of a feature scorer and a feature selector. The scorer trains a neural network (NN) to globally score all the features, and the selector adopts a dependent sub-NN to locally evaluate the representation abilities for selecting features. Further, we present algorithmic stability analysis and show that our algorithm has a performance guarantee via a generalization error bound. Extensive experimental results on real-world datasets demonstrate superior generalization performance of our proposed algorithm to strong baseline methods. Also, the properties revealed by our theoretical analysis and the stability of our algorithm-selected features are empirically confirmed.
The bi-objective multimodal car-sharing problem
Venue: arXiv cs.AI 2022
Year: 2022

The aim of the bi-objective multimodal car-sharing problem (BiO-MMCP) is to determine the optimal mode of transport assignment for trips and to schedule the routes of available cars and users whilst minimizing cost and maximizing user satisfaction. We investigate the BiO-MMCP from a user-centred point of view. As user satisfaction is a crucial aspect in shared mobility systems, we consider user preferences in a second objective. Users may choose and rank their preferred modes of transport for different times of the day. In this way we account for, e.g., different traffic conditions throughout the planning horizon. We study different variants of the problem. In the base problem, the sequence of tasks a user has to fulfill is fixed in advance and travel times as well as preferences are constant over the planning horizon. In variant 2, time-dependent travel times and preferences are introduced. In variant 3, we examine the challenges when allowing additional routing decisions. Variant 4 integrates variants 2 and 3. For this last variant, we develop a branch-and-cut algorithm which is embedded in two bi-objective frameworks, namely the $ε$-constraint method and a weighting binary search method. Computational experiments show that the branch-and cut algorithm outperforms the MIP formulation and we discuss changing solutions along the Pareto frontier.
Counterfactual Explanations and Algorithmic Recourses for Machine Learning: A Review
Venue: arXiv cs.LG 2022
Year: 2022

Machine learning plays a role in many deployed decision systems, often in ways that are difficult or impossible to understand by human stakeholders. Explaining, in a human-understandable way, the relationship between the input and output of machine learning models is essential to the development of trustworthy machine learning based systems. A burgeoning body of research seeks to define the goals and methods of explainability in machine learning. In this paper, we seek to review and categorize research on counterfactual explanations, a specific class of explanation that provides a link between what could have happened had input to a model been changed in a particular way. Modern approaches to counterfactual explainability in machine learning draw connections to the established legal doctrine in many countries, making them appealing to fielded systems in high-impact areas such as finance and healthcare. Thus, we design a rubric with desirable properties of counterfactual explanation algorithms and comprehensively evaluate all currently proposed algorithms against that rubric. Our rubric provides easy comparison and comprehension of the advantages and disadvantages of different approaches and serves as an introduction to major research themes in this field. We also identify gaps and discuss promising research directions in the space of counterfactual explainability.
Misleading Repurposing on Twitter
Venue: arXiv cs.SI 2022
Year: 2022

We present the first in-depth and large-scale study of misleading repurposing, in which a malicious user changes the identity of their social media account via, among other things, changes to the profile attributes in order to use the account for a new purpose while retaining their followers. We propose a definition for the behavior and a methodology that uses supervised learning on data mined from the Internet Archive's Twitter Stream Grab to flag repurposed accounts. We found over 100,000 accounts that may have been repurposed. We also characterize repurposed accounts and found that they are more likely to be repurposed after a period of inactivity and deleting old tweets. We also provide evidence that adversaries target accounts with high follower counts to repurpose, and some make them have high follower counts by participating in follow-back schemes. The results we present have implications for the security and integrity of social media platforms, for data science studies in how historical data is considered, and for society at large in how users can be deceived about the popularity of an opinion.
MINVO Basis: Finding Simplexes with Minimum Volume Enclosing Polynomial Curves
Venue: arXiv cs.CG 2022
Year: 2022

This paper studies the polynomial basis that generates the smallest $n$-simplex enclosing a given $n^{\text{th}}$-degree polynomial curve in $\mathbb{R}^n$. Although the Bernstein and B-Spline polynomial bases provide feasible solutions to this problem, the simplexes obtained by these bases are not the smallest possible, which leads to overly conservative results in many CAD (computer-aided design) applications. We first prove that the polynomial basis that solves this problem (MINVO basis) also solves for the $n^\text{th}$-degree polynomial curve with largest convex hull enclosed in a given $n$-simplex. Then, we present a formulation that is independent of the $n$-simplex or $n^{\text{th}}$-degree polynomial curve given. By using Sum-Of-Squares (SOS) programming, branch and bound, and moment relaxations, we obtain high-quality feasible solutions for any $n\in\mathbb{N}$, and prove (numerical) global optimality for $n=1,2,3$ and (numerical) local optimality for $n=4$. The results obtained for $n=3$ show that, for any given $3^{\text{rd}}$-degree polynomial curve in $\mathbb{R}^3$, the MINVO basis is able to obtain an enclosing simplex whose volume is $2.36$ and $254.9$ times smaller than the ones obtained by the Bernstein and B-Spline bases, respectively. When $n=7$, these ratios increase to $902.7$ and $2.997\cdot10^{21}$, respectively.
Fast-HotStuff: A Fast and Resilient HotStuff Protocol
Venue: arXiv cs.DC 2022
Year: 2022

The HotStuff protocol is a breakthrough in Byzantine Fault Tolerant (BFT) consensus that enjoys both responsiveness and linear view change. It creatively adds an additional round to classic BFT protocols (like PBFT) using two rounds. This brings us to an interesting question: Is this additional round really necessary in practice? In this paper, we answer this question by designing a new two-round BFT protocol called Fast-HotStuff, which enjoys responsiveness and efficient view change that is comparable to linear view change in terms of performance. Compared to (three-round) HotStuff, Fast-HotStuff has lower latency and is more robust against performance attacks that HotStuff is susceptible to.
Load balancing policies without feedback using timed replicas
Venue: arXiv cs.DC 2022
Year: 2022

Dispatching policies such as the join shortest queue (JSQ), join smallest work (JSW) and their power of two variants are used in load balancing systems where the instantaneous queue length or workload information at all queues or a subset of them can be queried. In situations where the dispatcher has an associated memory, one can minimize this query overhead by maintaining a list of idle servers to which jobs can be dispatched. Recent alternative approaches that do not require querying such information include the cancel on start and cancel on complete based replication policies. The downside of such policies however is that the servers must communicate the start or completion of each service to the dispatcher and must allow cancellation of redundant copies. In practice, the requirements of query messaging, memory, and replica cancellation pose challenges in their implementation and their advantages are not clear. In this work, we consider load balancing policies that do not query load information, do not have a memory, and do not cancel replicas. Surprisingly, we were able to identify operating regimes where such policies have better performance when compared to some of the popular policies that utilize server feedback information. Our policies allow the dispatcher to append a timer to each job or its replica. A job or a replica is discarded if its timer expires before it starts receiving service. We analyze several variants of this policy which are novel, simple to implement, and also have remarkably good performance in some operating regimes, despite no feedback from servers to the dispatcher.
Active Learning for Human-in-the-Loop Customs Inspection
Venue: arXiv cs.LG 2022
Year: 2022

We study the human-in-the-loop customs inspection scenario, where an AI-assisted algorithm supports customs officers by recommending a set of imported goods to be inspected. If the inspected items are fraudulent, the officers can levy extra duties. Th formed logs are then used as additional training data for successive iterations. Choosing to inspect suspicious items first leads to an immediate gain in customs revenue, yet such inspections may not bring new insights for learning dynamic traffic patterns. On the other hand, inspecting uncertain items can help acquire new knowledge, which will be used as a supplementary training resource to update the selection systems. Based on multiyear customs datasets obtained from three countries, we demonstrate that some degree of exploration is necessary to cope with domain shifts in trade data. The results show that a hybrid strategy of selecting likely fraudulent and uncertain items will eventually outperform the exploitation-only strategy.
Nested Grassmannians for Dimensionality Reduction with Applications
Venue: arXiv cs.CV 2022
Year: 2022

In the recent past, nested structures in Riemannian manifolds has been studied in the context of dimensionality reduction as an alternative to the popular principal geodesic analysis (PGA) technique, for example, the principal nested spheres. In this paper, we propose a novel framework for constructing a nested sequence of homogeneous Riemannian manifolds. Common examples of homogeneous Riemannian manifolds include the $n$-sphere, the Stiefel manifold, the Grassmann manifold and many others. In particular, we focus on applying the proposed framework to the Grassmann manifold, giving rise to the nested Grassmannians (NG). An important application in which Grassmann manifolds are encountered is planar shape analysis. Specifically, each planar (2D) shape can be represented as a point in the complex projective space which is a complex Grass-mann manifold. Some salient features of our framework are: (i) it explicitly exploits the geometry of the homogeneous Riemannian manifolds and (ii) the nested lower-dimensional submanifolds need not be geodesic. With the proposed NG structure, we develop algorithms for the supervised and unsupervised dimensionality reduction problems respectively. The proposed algorithms are compared with PGA via simulation studies and real data experiments and are shown to achieve a higher ratio of expressed variance compared to PGA.
Bayesian Deep Learning via Subnetwork Inference
Venue: arXiv cs.LG 2022
Year: 2022

The Bayesian paradigm has the potential to solve core issues of deep neural networks such as poor calibration and data inefficiency. Alas, scaling Bayesian inference to large weight spaces often requires restrictive approximations. In this work, we show that it suffices to perform inference over a small subset of model weights in order to obtain accurate predictive posteriors. The other weights are kept as point estimates. This subnetwork inference framework enables us to use expressive, otherwise intractable, posterior approximations over such subsets. In particular, we implement subnetwork linearized Laplace as a simple, scalable Bayesian deep learning method: We first obtain a MAP estimate of all weights and then infer a full-covariance Gaussian posterior over a subnetwork using the linearized Laplace approximation. We propose a subnetwork selection strategy that aims to maximally preserve the model's predictive uncertainty. Empirically, our approach compares favorably to ensembles and less expressive posterior approximations over full networks. Our proposed subnetwork (linearized) Laplace method is implemented within the laplace PyTorch library at https://github.com/AlexImmer/Laplace.
Crop and weed classification based on AutoML
Venue: arXiv cs.AI 2022
Year: 2022

CNN models already play an important role in classification of crop and weed with high accuracy, more than 95% as reported in literature. However, to manually choose and fine-tune the deep learning models becomes laborious and indispensable in most traditional practices and research. Moreover, the classic objective functions are not thoroughly compatible with agricultural farming tasks as the corresponding models suffer from misclassifying crop to weed, often more likely than in other deep learning application domains. In this paper, we applied autonomous machine learning with a new objective function for crop and weed classification, achieving higher accuracy and lower crop killing rate (rate of identifying a crop as a weed). The experimental results show that our method outperforms state-of-the-art applications, for example, ResNet and VGG19.
Learning Objective Functions Incrementally by Inverse Optimal Control
Venue: arXiv cs.RO 2022
Year: 2022

This paper proposes an inverse optimal control method which enables a robot to incrementally learn a control objective function from a collection of trajectory segments. By saying incrementally, it means that the collection of trajectory segments is enlarged because additional segments are provided as time evolves. The unknown objective function is parameterized as a weighted sum of features with unknown weights. Each trajectory segment is a small snippet of optimal trajectory. The proposed method shows that each trajectory segment, if informative, can pose a linear constraint to the unknown weights, thus, the objective function can be learned by incrementally incorporating all informative segments. Effectiveness of the method is shown on a simulated 2-link robot arm and a 6-DoF maneuvering quadrotor system, in each of which only small demonstration segments are available.
Feedback Insertion-Deletion Codes
Venue: arXiv cs.IT 2022
Year: 2022

In this paper, a new problem of transmitting information over the adversarial insertion-deletion channel with feedback is introduced. Suppose that the encoder transmits $n$ binary symbols one-by-one over a channel, in which some symbols can be deleted and some additional symbols can be inserted. After each transmission, the encoder is notified about the insertions or deletions that have occurred within the previous transmission and the encoding strategy can be adapted accordingly. The goal is to design an encoder that is able to transmit error-free as much information as possible under the assumption that the total number of deletions and insertions is limited by $τn$, $0<τ<1$. We show how this problem can be reduced to the problem of transmitting messages over the substitution channel. Thereby, the maximal asymptotic rate of feedback insertion-deletion codes is completely established. The maximal asymptotic rate for the adversarial substitution channel has been partially determined by Berlekamp and later finished by Zigangirov. However, the analysis of the lower bound by Zigangirov is quite complicated. We revisit Zigangirov's result and present a more elaborate version of his proof.
What is the T-Algorithm? A case study to evaluate a new University
Venue: arXiv cs.CY 2022
Year: 2022

We evaluate Scott Galloway's T-algorithm as a thinking framework via a simulated case. We explain how we applied it to analyze the investment strategies when starting a new university. We note that the algorithm can be used to describe but also prescribe the strategy design space. We also point weak and strong points of the said algorithm and compare it to existing tools such as the Business canvas model and SWOT.
VIO-UWB-Based Collaborative Localization and Dense Scene Reconstruction within Heterogeneous Multi-Robot Systems
Venue: arXiv cs.RO 2022
Year: 2022

Effective collaboration in multi-robot systems requires accurate and robust estimation of relative localization: from cooperative manipulation to collaborative sensing, and including cooperative exploration or cooperative transportation. This paper introduces a novel approach to collaborative localization for dense scene reconstruction in heterogeneous multi-robot systems comprising ground robots and micro-aerial vehicles (MAVs). We solve the problem of full relative pose estimation without sliding time windows by relying on UWB-based ranging and Visual Inertial Odometry (VIO)-based egomotion estimation for localization, while exploiting lidars onboard the ground robots for full relative pose estimation in a single reference frame. During operation, the rigidity eigenvalue provides feedback to the system. To tackle the challenge of path planning and obstacle avoidance of MAVs in GNSS-denied environments, we maintain line-of-sight between ground robots and MAVs. Because lidars capable of dense reconstruction have limited FoV, this introduces new constraints to the system. Therefore, we propose a novel formulation with a variant of the Dubins multiple traveling salesman problem with neighborhoods (DMTSPN) where we include constraints related to the limited FoV of the ground robots. Our approach is validated with simulations and experiments with real robots for the different parts of the system.
Compressed Sensing with Upscaled Vector Approximate Message Passing
Venue: arXiv cs.IT 2022
Year: 2022

The Recently proposed Vector Approximate Message Passing (VAMP) algorithm demonstrates a great reconstruction potential at solving compressed sensing related linear inverse problems. VAMP provides high per-iteration improvement, can utilize powerful denoisers like BM3D, has rigorously defined dynamics and is able to recover signals measured by highly undersampled and ill-conditioned linear operators. Yet, its applicability is limited to relatively small problem sizes due to the necessity to compute the expensive LMMSE estimator at each iteration. In this work we consider the problem of upscaling VAMP by utilizing Conjugate Gradient (CG) to approximate the intractable LMMSE estimator. We propose a rigorous method for correcting and tuning CG withing CG-VAMP to achieve a stable and efficient reconstruction. To further improve the performance of CG-VAMP, we design a warm-starting scheme for CG and develop theoretical models for the Onsager correction and the State Evolution of Warm-Started CG-VAMP (WS-CG-VAMP). Additionally, we develop robust and accurate methods for implementing the WS-CG-VAMP algorithm. The numerical experiments on large-scale image reconstruction problems demonstrate that WS-CG-VAMP requires much fewer CG iterations compared to CG-VAMP to achieve the same or superior level of reconstruction.