OpenRaiser/Intern-Atlas huggingface dataset:
Decomposition Strategies for Solving Scheduling Problems in Industrial Applications
Venue: arXiv cs.LO 2022
Year: 2022

This article presents an overview of a research study of a crucial optimization problem in the Computer Science/Operations research field: The Job-shop Scheduling Problem (JSP). The JSP is a challenging task in which a set of operations must be processed using a set of scarce machines to optimize a particular objective. The main purpose of the JSP is to determine the execution order of the processes assigned to each machine to optimize an objective. Our main interest in this study is to investigate developing decomposition strategies using logic programming to solve the JSP. We split our goal into two main phases. The first phase is to apply the decomposition approach and evaluate the proposed model by solving a set of known benchmark instances. The second phase is to apply the successful decomposition methods obtained from the first phase to solve a scheduling problem in the real-life application. In the current state, we finished the first phase and started the second one aiming to have a model that can provide a schedule of a factory for a short-time period.
Motivating explanations in Bayesian networks using MAP-independence
Venue: arXiv cs.AI 2022
Year: 2022

In decision support systems the motivation and justification of the system's diagnosis or classification is crucial for the acceptance of the system by the human user. In Bayesian networks a diagnosis or classification is typically formalized as the computation of the most probable joint value assignment to the hypothesis variables, given the observed values of the evidence variables (generally known as the MAP problem). While solving the MAP problem gives the most probable explanation of the evidence, the computation is a black box as far as the human user is concerned and it does not give additional insights that allow the user to appreciate and accept the decision. For example, a user might want to know to whether an unobserved variable could potentially (upon observation) impact the explanation, or whether it is irrelevant in this aspect. In this paper we introduce a new concept, MAP- independence, which tries to capture this notion of relevance, and explore its role towards a potential justification of an inference to the best explanation. We formalize several computational problems based on this concept and assess their computational complexity.
A PTAS for Minimizing Weighted Flow Time on a Single Machine
Venue: arXiv cs.DS 2022
Year: 2022

An important objective in scheduling literature is to minimize the sum of weighted flow times. We are given a set of jobs where each job is characterized by a release time, a processing time, and a weight. Our goal is to find a preemptive schedule on a single machine that minimizes the sum of the weighted flow times of the jobs, where the flow time of a job is the time between its completion time and its release time. The currently best known polynomial time algorithm for the problem is a (2+eps)-approximation by Rohwedder and Wiese [STOC 2021] which builds on the prior break-through result by Batra, Garg, and Kumar [FOCS 2018] who found the first pseudo-polynomial time constant factor approximation algorithm for the problem, and on the result by Feige, Kulkarni, and Li [SODA 2019] who turned the latter into a polynomial time algorithm. However, it remains open whether the problem admits a PTAS. We answer this question in the affirmative and present a polynomial time (1+eps)-approximation algorithm for weighted flow time on a single machine. We rely on a reduction of the problem to a geometric covering problem, which was introduced in the mentioned (2+eps)-approximation algorithm, losing a factor 1+eps in the approximation ratio. However, unlike that algorithm, we solve the resulting instances of this problem exactly, rather than losing a factor 2+eps. Key for this is to identify and exploit structural properties of instances of the geometric covering problem which arise in the reduction from weighted flow time.
TransPillars: Coarse-to-Fine Aggregation for Multi-Frame 3D Object Detection
Venue: arXiv cs.CV 2022
Year: 2022

3D object detection using point clouds has attracted increasing attention due to its wide applications in autonomous driving and robotics. However, most existing studies focus on single point cloud frames without harnessing the temporal information in point cloud sequences. In this paper, we design TransPillars, a novel transformer-based feature aggregation technique that exploits temporal features of consecutive point cloud frames for multi-frame 3D object detection. TransPillars aggregates spatial-temporal point cloud features from two perspectives. First, it fuses voxel-level features directly from multi-frame feature maps instead of pooled instance features to preserve instance details with contextual information that are essential to accurate object localization. Second, it introduces a hierarchical coarse-to-fine strategy to fuse multi-scale features progressively to effectively capture the motion of moving objects and guide the aggregation of fine features. Besides, a variant of deformable transformer is introduced to improve the effectiveness of cross-frame feature matching. Extensive experiments show that our proposed TransPillars achieves state-of-art performance as compared to existing multi-frame detection approaches. Code will be released.
Local Detour Centrality: A Novel Local Centrality Measure for Weighted Networks
Venue: arXiv cs.SI 2022
Year: 2022

Centrality, in some sense, captures the extent to which a vertex controls the flow of information in a network. Here, we propose Local Detour Centrality as a novel centrality-based betweenness measure that captures the extent to which a vertex shortens paths between neighboring vertices as compared to alternative paths. After presenting our measure, we demonstrate empirically that it differs from other leading central measures, such as betweenness, degree, closeness, and the number of triangles. Through an empirical case study, we provide a possible interpretation for Local Detour Centrality as a measure that captures the extent to which a word is characterized by contextual diversity within a semantic network. We then examine the relationship between our measure and the accessibility to knowledge stored in memory. To do so, we show that words that occur in several different and distinct contexts are significantly more effective in facilitating the retrieval of subsequent words than are words that lack this contextual diversity.
Discover the Mysteries of the Maya: Selected Contributions from the Machine Learning Challenge & The Discovery Challenge Workshop at ECML PKDD 2021
Venue: arXiv cs.CV 2022
Year: 2022

The volume contains selected contributions from the Machine Learning Challenge "Discover the Mysteries of the Maya", presented at the Discovery Challenge Track of The European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2021). Remote sensing has greatly accelerated traditional archaeological landscape surveys in the forested regions of the ancient Maya. Typical exploration and discovery attempts, beside focusing on whole ancient cities, focus also on individual buildings and structures. Recently, there have been several successful attempts of utilizing machine learning for identifying ancient Maya settlements. These attempts, while relevant, focus on narrow areas and rely on high-quality aerial laser scanning (ALS) data which covers only a fraction of the region where ancient Maya were once settled. Satellite image data, on the other hand, produced by the European Space Agency's (ESA) Sentinel missions, is abundant and, more importantly, publicly available. The "Discover the Mysteries of the Maya" challenge aimed at locating and identifying ancient Maya architectures (buildings, aguadas, and platforms) by performing integrated image segmentation of different types of satellite imagery (from Sentinel-1 and Sentinel-2) data and ALS (lidar) data.
Basic Elements of Logical Graphs
Venue: arXiv cs.LO 2022
Year: 2022

We considers how a particular kind of graph corresponds to multiplicative intuitionistic linear logic formula. The main feature of the graphical notation is that it absorbs certain symmetries between conjunction and implication. We look at the basic definitions and present details of an implementation in the functional programming language Standard ML. This provides a functional approach to graph traversal and demonstrates how graph isomorphism be implemented in just a few lines of readable code. This works takes the initial steps towards a graphical language and toolkit for working with logic formula and derivations.
Defining Cases and Variants for Object-Centric Event Data
Venue: arXiv cs.DB 2022
Year: 2022

The execution of processes leaves traces of event data in information systems. These event data can be analyzed through process mining techniques. For traditional process mining techniques, one has to associate each event with exactly one object, e.g., the company's customer. Events related to one object form an event sequence called a case. A case describes an end-to-end run through a process. The cases contained in event data can be used to discover a process model, detect frequent bottlenecks, or learn predictive models. However, events encountered in real-life information systems, e.g., ERP systems, can often be associated with multiple objects. The traditional sequential case concept falls short of these object-centric event data as these data exhibit a graph structure. One might force object-centric event data into the traditional case concept by flattening it. However, flattening manipulates the data and removes information. Therefore, a concept analogous to the case concept of traditional event logs is necessary to enable the application of different process mining tasks on object-centric event data. In this paper, we introduce the case concept for object-centric process mining: process executions. These are graph-based generalizations of cases as considered in traditional process mining. Furthermore, we provide techniques to extract process executions. Based on these executions, we determine equivalent process behavior with respect to an attribute using graph isomorphism. Equivalent process executions with respect to the event's activity are object-centric variants, i.e., a generalization of variants in traditional process mining. We provide a visualization technique for object-centric variants. The contribution's scalability and efficiency are extensively evaluated. Furthermore, we provide a case study showing the most frequent object-centric variants of a real-life event log.
Recurrence extraction and denotational semantics with recursive definitions
Venue: arXiv cs.PL 2022
Year: 2022

With one exception, our previous work on recurrence extraction and denotational semantics has focused on a source language that supports inductive types and structural recursion. The exception handles general recursion via an initial translation into call-by-push-value. In this note we give an extraction function from a language with general recursive function definitions and recursive types directly to a PCF-like recurrence language. We prove the main soundness result (that the syntactic recurrences in fact bound the operational cost) without the use of a logical relation, thereby significantly simplifying the proof compared to our previous work (at the cost of placing more demands on the models of the recurrence language). We then define two models of the recurrence language, one for analyzing merge sort, and another for analyzing quick sort, as case studies to understand model definitions for justifying the extracted recurrences.
Real-time Gesture Animation Generation from Speech for Virtual Human Interaction
Venue: arXiv cs.CV 2022
Year: 2022

We propose a real-time system for synthesizing gestures directly from speech. Our data-driven approach is based on Generative Adversarial Neural Networks to model the speech-gesture relationship. We utilize the large amount of speaker video data available online to train our 3D gesture model. Our model generates speaker-specific gestures by taking consecutive audio input chunks of two seconds in length. We animate the predicted gestures on a virtual avatar. We achieve a delay below three seconds between the time of audio input and gesture animation. Code and videos are available at https://github.com/mrebol/Gestures-From-Speech
Parameter Averaging for Feature Ranking
Venue: arXiv cs.LG 2022
Year: 2022

Neural Networks are known to be sensitive to initialisation. The methods that rely on neural networks for feature ranking are not robust since they can have variations in their ranking when the model is initialized and trained with different random seeds. In this work, we introduce a novel method based on parameter averaging to estimate accurate and robust feature importance in tabular data setting, referred as XTab. We first initialize and train multiple instances of a shallow network (referred as local masks) with "different random seeds" for a downstream task. We then obtain a global mask model by "averaging the parameters" of local masks. We show that although the parameter averaging might result in a global model with higher loss, it still leads to the discovery of the ground-truth feature importance more consistently than an individual model does. We conduct extensive experiments on a variety of synthetic and real-world data, demonstrating that the XTab can be used to obtain the global feature importance that is not sensitive to sub-optimal model initialisation.
Learning New Skills after Deployment: Improving open-domain internet-driven dialogue with human feedback
Venue: arXiv cs.CL 2022
Year: 2022

Frozen models trained to mimic static datasets can never improve their performance. Models that can employ internet-retrieval for up-to-date information and obtain feedback from humans during deployment provide the promise of both adapting to new information, and improving their performance. In this work we study how to improve internet-driven conversational skills in such a learning framework. We collect deployment data, which we make publicly available, of human interactions, and collect various types of human feedback -- including binary quality measurements, free-form text feedback, and fine-grained reasons for failure. We then study various algorithms for improving from such feedback, including standard supervised learning, rejection sampling, model-guiding and reward-based learning, in order to make recommendations on which type of feedback and algorithms work best. We find the recently introduced Director model (Arora et al., '22) shows significant improvements over other existing approaches.
Convolutional Ensembling based Few-Shot Defect Detection Technique
Venue: arXiv cs.CV 2022
Year: 2022

Over the past few years, there has been a significant improvement in the domain of few-shot learning. This learning paradigm has shown promising results for the challenging problem of anomaly detection, where the general task is to deal with heavy class imbalance. Our paper presents a new approach to few-shot classification, where we employ the knowledge-base of multiple pre-trained convolutional models that act as the backbone for our proposed few-shot framework. Our framework uses a novel ensembling technique for boosting the accuracy while drastically decreasing the total parameter count, thus paving the way for real-time implementation. We perform an extensive hyperparameter search using a power-line defect detection dataset and obtain an accuracy of 92.30% for the 5-way 5-shot task. Without further tuning, we evaluate our model on competing standards with the existing state-of-the-art methods and outperform them.
Keys to Better Image Inpainting: Structure and Texture Go Hand in Hand
Venue: arXiv cs.CV 2022
Year: 2022

Deep image inpainting has made impressive progress with recent advances in image generation and processing algorithms. We claim that the performance of inpainting algorithms can be better judged by the generated structures and textures. Structures refer to the generated object boundary or novel geometric structures within the hole, while texture refers to high-frequency details, especially man-made repeating patterns filled inside the structural regions. We believe that better structures are usually obtained from a coarse-to-fine GAN-based generator network while repeating patterns nowadays can be better modeled using state-of-the-art high-frequency fast fourier convolutional layers. In this paper, we propose a novel inpainting network combining the advantages of the two designs. Therefore, our model achieves a remarkable visual quality to match state-of-the-art performance in both structure generation and repeating texture synthesis using a single network. Extensive experiments demonstrate the effectiveness of the method, and our conclusions further highlight the two critical factors of image inpainting quality, structures, and textures, as the future design directions of inpainting networks.
Amplitude Constrained Vector Gaussian Wiretap Channel: Properties of the Secrecy-Capacity-Achieving Input Distribution
Venue: arXiv cs.IT 2022
Year: 2022

This paper studies secrecy-capacity of an $n$-dimensional Gaussian wiretap channel under a peak-power constraint. This work determines the largest peak-power constraint $\bar{\mathsf{R}}_n$ such that an input distribution uniformly distributed on a single sphere is optimal; this regime is termed the low amplitude regime. The asymptotic of $\bar{\mathsf{R}}_n$ as $n$ goes to infinity is completely characterized as a function of noise variance at both receivers. Moreover, the secrecy-capacity is also characterized in a form amenable for computation. Several numerical examples are provided, such as the example of the secrecy-capacity-achieving distribution beyond the low amplitude regime. Furthermore, for the scalar case $(n=1)$ we show that the secrecy-capacity-achieving input distribution is discrete with finitely many points at most of the order of $\frac{\mathsf{R}^2}{σ_1^2}$, where $σ_1^2$ is the variance of the Gaussian noise over the legitimate channel.
Multi-view deep learning for reliable post-disaster damage classification
Venue: arXiv cs.CV 2022
Year: 2022

This study aims to enable more reliable automated post-disaster building damage classification using artificial intelligence (AI) and multi-view imagery. The current practices and research efforts in adopting AI for post-disaster damage assessment are generally (a) qualitative, lacking refined classification of building damage levels based on standard damage scales, and (b) trained based on aerial or satellite imagery with limited views, which, although indicative, are not completely descriptive of the damage scale. To enable more accurate and reliable automated quantification of damage levels, the present study proposes the use of more comprehensive visual data in the form of multiple ground and aerial views of the buildings. To have such a spatially-aware damage prediction model, a Multi-view Convolution Neural Network (MV-CNN) architecture is used that combines the information from different views of a damaged building. This spatial 3D context damage information will result in more accurate identification of damages and reliable quantification of damage levels. The proposed model is trained and validated on reconnaissance visual dataset containing expert-labeled, geotagged images of the inspected buildings following hurricane Harvey. The developed model demonstrates reasonably good accuracy in predicting the damage levels and can be used to support more informed and reliable AI-assisted disaster management practices.
Log-linear Error State Model Derivation without Approximation for INS
Venue: arXiv cs.RO 2022
Year: 2022

Through assembling the navigation parameters as matrix Lie group state, the corresponding inertial navigation system (INS) kinematic model possesses a group-affine property. The Lie logarithm of the navigation state estimation error satisfies a log-linear autonomous differential equation. These log-linear models are still applicable even with arbitrarily large initial errors, which is very attractive for INS initial alignment. However, in existing works, the log-linear models are all derived based on first-order linearization approximation, which seemingly goes against their successful applications in INS initial alignment with large misalignments. In this work, it is shown that the log-linear models can also be derived without any approximation, the error dynamics for both left and right invariant error in continuous time are given in matrix Lie group SE_2 (3) for the first time. This work provides another evidence for the validity of the log-linear model in situations with arbitrarily large initial errors.
An Optimal "It Ain't Over Till It's Over" Theorem
Venue: arXiv cs.CC 2022
Year: 2022

We study the probability of Boolean functions with small max influence to become constant under random restrictions. Let $f$ be a Boolean function such that the variance of $f$ is $Ω(1)$ and all its individual influences are bounded by $τ$. We show that when restricting all but a $ρ=\tildeΩ((\log(1/τ))^{-1})$ fraction of the coordinates, the restricted function remains nonconstant with overwhelming probability. This bound is essentially optimal, as witnessed by the tribes function $\mathrm{TRIBES}=\mathrm{AND}_{n/C\log n}\circ\mathrm{OR}_{C\log n}$. We extend it to an anti-concentration result, showing that the restricted function has nontrivial variance with probability $1-o(1)$. This gives a sharp version of the "it ain't over till it's over" theorem due to Mossel, O'Donnell, and Oleszkiewicz. Our proof is discrete, and avoids the use of the invariance principle. We also show two consequences of our above result: (i) As a corollary, we prove that for a uniformly random input $x$, the block sensitivity of $f$ at $x$ is $\tildeΩ(\log(1/τ))$ with probability $1-o(1)$. This should be compared with the implication of Kahn, Kalai, and Linial's result, which implies that the average block sensitivity of $f$ is $Ω(\log(1/τ))$. (ii) Combining our proof with a well-known result due to O'Donnell, Saks, Schramm, and Servedio, one can also conclude that: Restricting all but a $ρ=\tildeΩ(1/\sqrt{\log (1/τ) })$ fraction of the coordinates of a monotone function $f$, then the restricted function has decision tree complexity $Ω(τ^{-Θ(ρ)})$ with probability $Ω(1)$.
Learning Human Cognitive Appraisal Through Reinforcement Memory Unit
Venue: arXiv cs.CV 2022
Year: 2022

We propose a novel memory-enhancing mechanism for recurrent neural networks that exploits the effect of human cognitive appraisal in sequential assessment tasks. We conceptualize the memory-enhancing mechanism as Reinforcement Memory Unit (RMU) that contains an appraisal state together with two positive and negative reinforcement memories. The two reinforcement memories are decayed or strengthened by stronger stimulus. Thereafter the appraisal state is updated through the competition of positive and negative reinforcement memories. Therefore, RMU can learn the appraisal variation under violent changing of the stimuli for estimating human affective experience. As shown in the experiments of video quality assessment and video quality of experience tasks, the proposed reinforcement memory unit achieves superior performance among recurrent neural networks, that demonstrates the effectiveness of RMU for modeling human cognitive appraisal.