OpenRaiser/Intern-Atlas huggingface dataset:
Freeform shape optimization of a compact DC photo-electron gun using isogeometric analysis
Venue: arXiv cs.CE 2022
Year: 2022

Compact DC high-voltage photo-electron guns are able to meet the sophisticated demands of high-current applications such as energy recovery linacs. A main design parameter for such sources is the electric field strength, which depends on the electrode geometry and is limited by the field emission threshold of the electrode material. In order to minimize the maximum field strength for optimal gun operation, isogeometric analysis (IGA) can be used to exploit the axisymmetric geometry and describe its cross section by non-uniform rational B-splines, the control points of which are the parameters to be optimized. This computationally efficient method is capable of describing CAD-generated geometries using open source software (GeoPDEs, NLopt, Octave) and it can simplify the step from design to simulation. We will present the mathematical formulation, the software workflow, and the results of an IGA-based shape optimization for a planned high-voltage upgrade of the DC photogun teststand Photo-CATCH at TU Darmstadt. The software builds on a general framework for isogeometric analysis and allows for easy adaptations to other geometries or quantities of interest. Simulations assuming a bias voltage of -300 kV yielded maximum field gradients of 9.06 MV/m on the surface of an inverted insulator electrode and below 3 MV/m on the surface of the photocathode.
Enhanced spatio-temporal electric load forecasts using less data with active deep learning
Venue: arXiv cs.LG 2022
Year: 2022

An effective way to oppose global warming and mitigate climate change is to electrify our energy sectors and supply their electric power from renewable wind and solar. Spatio-temporal predictions of electric load become increasingly important for planning this transition, while deep learning prediction models provide increasingly accurate predictions for it. The data used for training deep learning models, however, is usually collected at random using a passive learning approach. This naturally results in a large demand for data and associated costs for sensors like smart meters, posing a large barrier for electric utilities in decarbonizing their grids. Here, we test active learning where we leverage additional computation for collecting a more informative subset of data. We show how electric utilities can apply active learning to better distribute smart meters and collect their data for more accurate predictions of load with about half the data compared to when applying passive learning.
A gentle introduction to Girard's Transcendental Syntax for the linear logician
Venue: arXiv cs.LO 2022
Year: 2022

Technically speaking, the transcendental syntax is about designing logics with a computational foundation. It suggests a new framework for proof theory where logic (proofs, formulas, truth, ...) is no more primitive but computation is. All the logical entities and activities will be presented as formatting/structuring on a given model of computation which should be as general, simple and natural as possible. The selected ground for logic in the transcendental syntax is a model of computation I call "stellar resolution" which is basically a logic-free reformulation of Robinson's first-order clausal resolution with a dynamics related to tile systems. An initial goal of the transcendental syntax is to retrieve linear logic from this new framework. In particular, this model naturally encodes cut-elimination for proof-structures. By using an idea of "interactive typing" reminiscent of realisability theory, it is possible to design formulas/types generalising the connectives of linear logic. Thanks to interactive typing, we are able to reach a semantic-free space where correctness criteria are seen as tests (as in unit testing or model checking) certifying logical correctness, thus allowing an effective use of logical entities.
Data Appraisal Without Data Sharing
Venue: arXiv cs.LG 2022
Year: 2022

One of the most effective approaches to improving the performance of a machine learning model is to procure additional training data. A model owner seeking relevant training data from a data owner needs to appraise the data before acquiring it. However, without a formal agreement, the data owner does not want to share data. The resulting Catch-22 prevents efficient data markets from forming. This paper proposes adding a data appraisal stage that requires no data sharing between data owners and model owners. Specifically, we use multi-party computation to implement an appraisal function computed on private data. The appraised value serves as a guide to facilitate data selection and transaction. We propose an efficient data appraisal method based on forward influence functions that approximates data value through its first-order loss reduction on the current model. The method requires no additional hyper-parameters or re-training. We show that in private, forward influence functions provide an appealing trade-off between high quality appraisal and required computation, in spite of label noise, class imbalance, and missing data. Our work seeks to inspire an open market that incentivizes efficient, equitable exchange of domain-specific training data.
Classifying CELESTE as NP Complete
Venue: arXiv cs.CC 2022
Year: 2022

We analyze the computational complexity of the video game "CELESTE" and prove that solving a generalized level in it is NP-Complete. Further, we also show how, upon introducing a small change in the game mechanics (adding a new game entity), we can make it PSPACE-complete.
Scalable Verification of Quantized Neural Networks (Technical Report)
Venue: arXiv cs.AI 2022
Year: 2022

Formal verification of neural networks is an active topic of research, and recent advances have significantly increased the size of the networks that verification tools can handle. However, most methods are designed for verification of an idealized model of the actual network which works over real arithmetic and ignores rounding imprecisions. This idealization is in stark contrast to network quantization, which is a technique that trades numerical precision for computational efficiency and is, therefore, often applied in practice. Neglecting rounding errors of such low-bit quantized neural networks has been shown to lead to wrong conclusions about the network's correctness. Thus, the desired approach for verifying quantized neural networks would be one that takes these rounding errors into account. In this paper, we show that verifying the bit-exact implementation of quantized neural networks with bit-vector specifications is PSPACE-hard, even though verifying idealized real-valued networks and satisfiability of bit-vector specifications alone are each in NP. Furthermore, we explore several practical heuristics toward closing the complexity gap between idealized and bit-exact verification. In particular, we propose three techniques for making SMT-based verification of quantized neural networks more scalable. Our experiments demonstrate that our proposed methods allow a speedup of up to three orders of magnitude over existing approaches.
Generative model for reciprocity and community detection in networks
Venue: arXiv cs.SI 2022
Year: 2022

We present a probabilistic generative model and efficient algorithm to model reciprocity in directed networks. Unlike other methods that address this problem such as exponential random graphs, it assigns latent variables as community memberships to nodes and a reciprocity parameter to the whole network rather than fitting order statistics. It formalizes the assumption that a directed interaction is more likely to occur if an individual has already observed an interaction towards her. It provides a natural framework for relaxing the common assumption in network generative models of conditional independence between edges, and it can be used to perform inference tasks such as predicting the existence of an edge given the observation of an edge in the reverse direction. Inference is performed using an efficient expectation-maximization algorithm that exploits the sparsity of the network, leading to an efficient and scalable implementation. We illustrate these findings by analyzing synthetic and real data, including social networks, academic citations and the Erasmus student exchange program. Our method outperforms others in both predicting edges and generating networks that reflect the reciprocity values observed in real data, while at the same time inferring an underlying community structure. We provide an open-source implementation of the code online.
Objective-Based Hierarchical Clustering of Deep Embedding Vectors
Venue: arXiv cs.LG 2022
Year: 2022

We initiate a comprehensive experimental study of objective-based hierarchical clustering methods on massive datasets consisting of deep embedding vectors from computer vision and NLP applications. This includes a large variety of image embedding (ImageNet, ImageNetV2, NaBirds), word embedding (Twitter, Wikipedia), and sentence embedding (SST-2) vectors from several popular recent models (e.g. ResNet, ResNext, Inception V3, SBERT). Our study includes datasets with up to $4.5$ million entries with embedding dimensions up to $2048$. In order to address the challenge of scaling up hierarchical clustering to such large datasets we propose a new practical hierarchical clustering algorithm B++&C. It gives a 5%/20% improvement on average for the popular Moseley-Wang (MW) / Cohen-Addad et al. (CKMM) objectives (normalized) compared to a wide range of classic methods and recent heuristics. We also introduce a theoretical algorithm B2SAT&C which achieves a $0.74$-approximation for the CKMM objective in polynomial time. This is the first substantial improvement over the trivial $2/3$-approximation achieved by a random binary tree. Prior to this work, the best poly-time approximation of $\approx 2/3 + 0.0004$ was due to Charikar et al. (SODA'19).
Group Handover for Drone Base Stations
Venue: arXiv cs.CR 2022
Year: 2022

The widespread use of new technologies such as the Internet of things (IoT) and machine type communication(MTC) forces an increase on the number of user equipments(UEs) and MTC devices that are connecting to mobile networks. Inherently, as the number of UEs inside a base station's (BS) coverage area surges, the quality of service (QoS) tends to decline. The use of drone-mounted BS (UxNB) is a solution in places where UEs are densely populated, such as stadiums. UxNB emerges as a promising technology that can be used for capacity injection purposes in the future due to its fast deployment. However, this emerging technology introduces a new security issue. Mutual authentication, creating a communication channel between terrestrial BS and UxNB, and fast handover operations may cause security issues in the use of UxNB for capacity injection. This new protocol also suggests performing UE handover from terrestrial to UxNB as a group. To the best of the authors' knowledge, there is no authentication solution between BSs according to LTE and 5G standards. The proposed scheme provides a solution for the authentication of UxNB by the terrestrial BS. Additionally, a credential sharing phase for each UE in handover is not required in the proposed method. The absence of a credential sharing step saves resources by reducing the number of communications between BSs. Moreover, many UE handover operations are completed in concise time within the proposed group handover method.
Stochastic Compositional Gradient Descent under Compositional Constraints
Venue: arXiv cs.LG 2022
Year: 2022

This work studies constrained stochastic optimization problems where the objective and constraint functions are convex and expressed as compositions of stochastic functions. The problem arises in the context of fair classification, fair regression, and the design of queuing systems. Of particular interest is the large-scale setting where an oracle provides the stochastic gradients of the constituent functions, and the goal is to solve the problem with a minimal number of calls to the oracle. Owing to the compositional form, the stochastic gradients provided by the oracle do not yield unbiased estimates of the objective or constraint gradients. Instead, we construct approximate gradients by tracking the inner function evaluations, resulting in a quasi-gradient saddle point algorithm. We prove that the proposed algorithm is guaranteed to find the optimal and feasible solution almost surely. We further establish that the proposed algorithm requires $\mathcal{O}(1/ε^4)$ data samples in order to obtain an $ε$-approximate optimal point while also ensuring zero constraint violation. The result matches the sample complexity of the stochastic compositional gradient descent method for unconstrained problems and improves upon the best-known sample complexity results for the constrained settings. The efficacy of the proposed algorithm is tested on both fair classification and fair regression problems. The numerical results show that the proposed algorithm outperforms the state-of-the-art algorithms in terms of the convergence rate.
Detection and Prediction of Nutrient Deficiency Stress using Longitudinal Aerial Imagery
Venue: arXiv cs.CV 2022
Year: 2022

Early, precise detection of nutrient deficiency stress (NDS) has key economic as well as environmental impact; precision application of chemicals in place of blanket application reduces operational costs for the growers while reducing the amount of chemicals which may enter the environment unnecessarily. Furthermore, earlier treatment reduces the amount of loss and therefore boosts crop production during a given season. With this in mind, we collect sequences of high-resolution aerial imagery and construct semantic segmentation models to detect and predict NDS across the field. Our work sits at the intersection of agriculture, remote sensing, and modern computer vision and deep learning. First, we establish a baseline for full-field detection of NDS and quantify the impact of pretraining, backbone architecture, input representation, and sampling strategy. We then quantify the amount of information available at different points in the season by building a single-timestamp model based on a UNet. Next, we construct our proposed spatiotemporal architecture, which combines a UNet with a convolutional LSTM layer, to accurately detect regions of the field showing NDS; this approach has an impressive IOU score of 0.53. Finally, we show that this architecture can be trained to predict regions of the field which are expected to show NDS in a later flight -- potentially more than three weeks in the future -- maintaining an IOU score of 0.47-0.51 depending on how far in advance the prediction is made. We will also release a dataset which we believe will benefit the computer vision, remote sensing, as well as agriculture fields. This work contributes to the recent developments in deep learning for remote sensing and agriculture, while addressing a key social challenge with implications for economics and sustainability.
Perception-Based Temporal Logic Planning in Uncertain Semantic Maps
Venue: arXiv cs.RO 2022
Year: 2022

This paper addresses a multi-robot planning problem in environments with partially unknown semantics. The environment is assumed to have known geometric structure (e.g., walls) and to be occupied by static labeled landmarks with uncertain positions and classes. This modeling approach gives rise to an uncertain semantic map generated by semantic SLAM algorithms. Our goal is to design control policies for robots equipped with noisy perception systems so that they can accomplish collaborative tasks captured by global temporal logic specifications. To specify missions that account for environmental and perceptual uncertainty, we employ a fragment of Linear Temporal Logic (LTL), called co-safe LTL, defined over perception-based atomic predicates modeling probabilistic satisfaction requirements. The perception-based LTL planning problem gives rise to an optimal control problem, solved by a novel sampling-based algorithm, that generates open-loop control policies that are updated online to adapt to a continuously learned semantic map. We provide extensive experiments to demonstrate the efficiency of the proposed planning architecture.
Unsupervised Scale-Invariant Multispectral Shape Matching
Venue: arXiv cs.CV 2022
Year: 2022

Alignment between non-rigid stretchable structures is one of the most challenging tasks in computer vision, as the invariant properties are hard to define, and there is no labeled data for real datasets. We present unsupervised neural network architecture based upon the spectral domain of scale-invariant geometry. We build on top of the functional maps architecture, but show that learning local features, as done until now, is not enough once the isometry assumption breaks. We demonstrate the use of multiple scale-invariant geometries for solving this problem. Our method is agnostic to local-scale deformations and shows superior performance for matching shapes from different domains when compared to existing spectral state-of-the-art solutions.
Memory AMP
Venue: arXiv cs.IT 2022
Year: 2022

Approximate message passing (AMP) is a low-cost iterative parameter-estimation technique for certain high-dimensional linear systems with non-Gaussian distributions. AMP only applies to independent identically distributed (IID) transform matrices, but may become unreliable (e.g., perform poorly or even diverge) for other matrix ensembles, especially for ill-conditioned ones. To solve this issue, orthogonal/vector AMP (OAMP/VAMP) was proposed for general right-unitarily-invariant matrices. However, the Bayes-optimal OAMP/VAMP (BO-OAMP/VAMP) requires a high-complexity linear minimum mean square error (MMSE) estimator. This prevents OAMP/VAMP from being used in large-scale systems. To address the drawbacks of AMP and BO-OAMP/VAMP, this paper offers a memory AMP (MAMP) framework based on the orthogonality principle, which ensures that estimation errors in MAMP are asymptotically IID Gaussian. To realize the required orthogonality for MAMP, we provide an orthogonalization procedure for the local memory estimators. In addition, we propose a Bayes-optimal MAMP (BO-MAMP), in which a long-memory matched filter is used for interference suppression. The complexity of BO-MAMP is comparable to AMP. To asymptotically characterize the performance of BO-MAMP, a state evolution is derived. The relaxation parameters and damping vector in BO-MAMP are optimized based on state evolution. Most crucially, the state evolution of the optimized BO-MAMP converges to the same fixed point as that of the high-complexity BO-OAMP/VAMP for all right-unitarily-invariant matrices, and achieves the Bayes optimal MSE predicted by the replica method if its state evolution has a unique fixed point. Finally, simulations are provided to verify the theoretical results' validity and accuracy.
Analysis of shape grammars: continuity of rules
Venue: arXiv cs.FL 2022
Year: 2022

The rules in a shape grammar apply in terms of embedding to take advantage of the parts that emerge visually in the appearance of shapes. While the shapes are kept unanalyzed as a computation moves forward, part-structures for shapes can be defined retrospectively by analyzing how the rules were applied. An important outcome of this is that rule continuity is not builtin but it is "fabricated" retrospectively to analyze the computation as a continuous process. An aspect of continuity analysis that has not been addressed in the literature is how to decide which mapping forms to use to study the continuity of rule applications. This is addressed in this paper using recent results on shape topology and continuous mappings. A characterization is provided that distinguishes the suitable mapping forms from those that are inherently discontinuous or practically inconsequential for continuity analysis. It is also shown that certain intrinsic properties of shape topologies and continuous mappings provide an effective method of computing topologies algorithmically.
DAQ: Channel-Wise Distribution-Aware Quantization for Deep Image Super-Resolution Networks
Venue: arXiv cs.CV 2022
Year: 2022

Quantizing deep convolutional neural networks for image super-resolution substantially reduces their computational costs. However, existing works either suffer from a severe performance drop in ultra-low precision of 4 or lower bit-widths, or require a heavy fine-tuning process to recover the performance. To our knowledge, this vulnerability to low precisions relies on two statistical observations of feature map values. First, distribution of feature map values varies significantly per channel and per input image. Second, feature maps have outliers that can dominate the quantization error. Based on these observations, we propose a novel distribution-aware quantization scheme (DAQ) which facilitates accurate training-free quantization in ultra-low precision. A simple function of DAQ determines dynamic range of feature maps and weights with low computational burden. Furthermore, our method enables mixed-precision quantization by calculating the relative sensitivity of each channel, without any training process involved. Nonetheless, quantization-aware training is also applicable for auxiliary performance gain. Our new method outperforms recent training-free and even training-based quantization methods to the state-of-the-art image super-resolution networks in ultra-low precision.
A Bayesian multiscale CNN framework to predict local stress fields in structures with microscale features
Venue: arXiv cs.CE 2022
Year: 2022

Multiscale computational modelling is challenging due to the high computational cost of direct numerical simulation by finite elements. To address this issue, concurrent multiscale methods use the solution of cheaper macroscale surrogates as boundary conditions to microscale sliding windows. The microscale problems remain a numerically challenging operation both in terms of implementation and cost. In this work we propose to replace the local microscale solution by an Encoder-Decoder Convolutional Neural Network that will generate fine-scale stress corrections to coarse predictions around unresolved microscale features, without prior parametrisation of local microscale problems. We deploy a Bayesian approach providing credible intervals to evaluate the uncertainty of the predictions, which is then used to investigate the merits of a selective learning framework. We will demonstrate the capability of the approach to predict equivalent stress fields in porous structures using linearised and finite strain elasticity theories.
Information Leakage Games: Exploring Information as a Utility Function
Venue: arXiv cs.CR 2022
Year: 2022

A common goal in the areas of secure information flow and privacy is to build effective defenses against unwanted leakage of information. To this end, one must be able to reason about potential attacks and their interplay with possible defenses. In this paper, we propose a game-theoretic framework to formalize strategies of attacker and defender in the context of information leakage, and provide a basis for developing optimal defense methods. A novelty of our games is that their utility is given by information leakage, which in some cases may behave in a non-linear way. This causes a significant deviation from classic game theory, in which utility functions are linear with respect to players' strategies. Hence, a key contribution of this paper is the establishment of the foundations of information leakage games. We consider two kinds of games, depending on the notion of leakage considered. The first kind, the QIF-games, is tailored for the theory of quantitative information flow (QIF). The second one, the DP-games, corresponds to differential privacy (DP).