OpenRaiser/Intern-Atlas huggingface dataset:
An extension of Overbeck's attack with an application to cryptanalysis of Twisted Gabidulin-based schemes
Venue: arXiv cs.CR 2023
Year: 2023

In this article, we discuss the decoding of Gabidulin and related codes from a cryptographic point of view, and we observe that these codes can be decoded solely from the knowledge of a generator matrix. We then extend and revisit Gibson and Overbeck attacks on the generalized GPT encryption scheme (instantiated with the Gabidulin code) for different ranks of the distortion matrix. We apply our attack to the case of an instantiation with twisted Gabidulin codes.
Two-sets cut-uncut on planar graphs
Venue: arXiv cs.DS 2023
Year: 2023

We study the following Two-Sets Cut-Uncut problem on planar graphs. Therein, one is given an undirected planar graph $G$ and two sets of vertices $S$ and $T$. The question is, what is the minimum number of edges to remove from $G$, such that we separate all of $S$ from all of $T$, while maintaining that every vertex in $S$, and respectively in $T$, stays in the same connected component. We show that this problem can be solved in time $2^{|S|+|T|} n^{O(1)}$ with a one-sided error randomized algorithm. Our algorithm implies a polynomial-time algorithm for the network diversion problem on planar graphs, which resolves an open question from the literature. More generally, we show that Two-Sets Cut-Uncut remains fixed-parameter tractable even when parameterized by the number $r$ of faces in the plane graph covering the terminals $S \cup T$, by providing an algorithm of running time $4^{r + O(\sqrt r)} n^{O(1)}$.
The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
Venue: arXiv cs.DS 2023
Year: 2023

In this paper, we present a low-diameter decomposition algorithm in the LOCAL model of distributed computing that succeeds with probability $1 - 1/poly(n)$. Specifically, we show how to compute an $\left(ε, O\left(\frac{\log n}ε\right)\right)$ low-diameter decomposition in $O\left(\frac{\log^3(1/ε)\log n}ε\right)$ round Further developing our techniques, we show new distributed algorithms for approximating general packing and covering integer linear programs in the LOCAL model. For packing problems, our algorithm finds an $(1-ε)$-approximate solution in $O\left(\frac{\log^3 (1/ε) \log n}ε\right)$ rounds with probability $1 - 1/poly(n)$. For covering problems, our algorithm finds an $(1+ε)$-approximate solution in $O\left(\frac{\left(\log \log n + \log (1/ε)\right)^3 \log n}ε\right)$ rounds with probability $1 - 1/poly(n)$. These results improve upon the previous $O\left(\frac{\log^3 n}ε\right)$-round algorithm by Ghaffari, Kuhn, and Maus [STOC 2017] which is based on network decompositions. Our algorithms are near-optimal for many fundamental combinatorial graph optimization problems in the LOCAL model, such as minimum vertex cover and minimum dominating set, as their $(1\pm ε)$-approximate solutions require $Ω\left(\frac{\log n}ε\right)$ rounds to compute.
Validation of massively-parallel adaptive testing using dynamic control matching
Venue: arXiv cs.LG 2023
Year: 2023

A/B testing is a widely-used paradigm within marketing optimization because it promises identification of causal effects and because it is implemented out of the box in most messaging delivery software platforms. Modern businesses, however, often run many A/B/n tests at the same time and in parallel, and package many content variations into the same messages, not all of which are part of an explicit test. Whether as the result of many teams testing at the same time, or as part of a more sophisticated reinforcement learning (RL) approach that continuously adapts tests and test condition assignment based on previous results, dynamic parallel testing cannot be evaluated the same way traditional A/B tests are evaluated. This paper presents a method for disentangling the causal effects of the various tests under conditions of continuous test adaptation, using a matched-synthetic control group that adapts alongside the tests.
Attacker Profiling Through Analysis of Attack Patterns in Geographically Distributed Honeypots
Venue: arXiv cs.CR 2023
Year: 2023

Honeypots are a well-known and widely used technology in the cybersecurity community, where it is assumed that placing honeypots in different geographical locations provides better visibility and increases effectiveness. However, how geolocation affects the usefulness of honeypots is not well-studied, especially for threat intelligence as early warning systems. This paper examines attack patterns in a large public dataset of geographically distributed honeypots by answering methodological questions and creating behavioural profiles of attackers. Results show that the location of honeypots helps identify attack patterns and build profiles for the attackers. We conclude that not all the intelligence collected from geographically distributed honeypots is equally valuable and that a good early warning system against resourceful attackers may be built with only two distributed honeypots and a production server.
Boosting Adversarial Transferability via Fusing Logits of Top-1 Decomposed Feature
Venue: arXiv cs.CV 2023
Year: 2023

Recent research has shown that Deep Neural Networks (DNNs) are highly vulnerable to adversarial samples, which are highly transferable and can be used to attack other unknown black-box models. To improve the transferability of adversarial samples, several feature-based adversarial attack methods have been proposed to disrupt neuron activation in the middle layers. However, current state-of-the-art feature-based attack methods typically require additional computation costs for estimating the importance of neurons. To address this challenge, we propose a Singular Value Decomposition (SVD)-based feature-level attack method. Our approach is inspired by the discovery that eigenvectors associated with the larger singular values decomposed from the middle layer features exhibit superior generalization and attention properties. Specifically, we conduct the attack by retaining the decomposed Top-1 singular value-associated feature for computing the output logits, which are then combined with the original logits to optimize adversarial examples. Our extensive experimental results verify the effectiveness of our proposed method, which can be easily integrated into various baselines to significantly enhance the transferability of adversarial samples for disturbing normally trained CNNs and advanced defense strategies. The source code of this study is available at https://github.com/WJJLL/SVD-SSA
Adopting AI: How Familiarity Breeds Both Trust and Contempt
Venue: arXiv cs.CY 2023
Year: 2023

Despite pronouncements about the inevitable diffusion of artificial intelligence and autonomous technologies, in practice it is human behavior, not technology in a vacuum, that dictates how technology seeps into -- and changes -- societies. In order to better understand how human preferences shape technological adoption and the spread of AI-enabled autonomous technologies, we look at representative adult samples of US public opinion in 2018 and 2020 on the use of four types of autonomous technologies: vehicles, surgery, weapons, and cyber defense. By focusing on these four diverse uses of AI-enabled autonomy that span transportation, medicine, and national security, we exploit the inherent variation between these AI-enabled autonomous use cases. We find that those with familiarity and expertise with AI and similar technologies were more likely to support all of the autonomous applications we tested (except weapons) than those with a limited understanding of the technology. Individuals that had already delegated the act of driving by using ride-share apps were also more positive about autonomous vehicles. However, familiarity cut both ways; individuals are also less likely to support AI-enabled technologies when applied directly to their life, especially if technology automates tasks they are already familiar with operating. Finally, opposition to AI-enabled military applications has slightly increased over time.
Extrinsic Infrastructure Calibration Using the Hand-Eye Robot-World Formulation
Venue: arXiv cs.RO 2023
Year: 2023

We propose a certifiably globally optimal approach for solving the hand-eye robot-world problem supporting multiple sensors and targets at once. Further, we leverage this formulation for estimating a geo-referenced calibration of infrastructure sensors. Since vehicle motion recorded by infrastructure sensors is mostly planar, obtaining a unique solution for the respective hand-eye robot-world problem is unfeasible without incorporating additional knowledge. Hence, we extend our proposed method to include a-priori knowledge, i.e., the translation norm of calibration targets, to yield a unique solution. Our approach achieves state-of-the-art results on simulated and real-world data. Especially on real-world intersection data, our approach utilizing the translation norm is the only method providing accurate results.
From Local to Global: Navigating Linguistic Diversity in the African Context
Venue: arXiv cs.CL 2023
Year: 2023

The focus is on critical problems in NLP related to linguistic diversity and variation across the African continent, specifically with regards to African local dialects and Arabic dialects that have received little attention. We evaluated our various approaches, demonstrating their effectiveness while highlighting the potential impact of the proposed approach on businesses seeking to improve customer experience and product development in African local dialects. The idea of using the model as a teaching tool for product-based instruction is interesting, as it could potentially stimulate interest in learners and trigger techno entrepreneurship. Overall, our modified approach offers a promising analysis of the challenges of dealing with African local dialects. Particularly Arabic dialects, which could have a significant impact on businesses seeking to improve customer experience and product development.
Enumerating proofs of positive formulae
Venue: arXiv cs.LO 2023
Year: 2023

We provide a semi-grammatical description of the set of normal proofs of positive formulae in minimal predicate logic, i.e. a grammar that generates a set of schemes, from each of which we can produce a finite number of normal proofs. This method is complete in the sense that each normal proof-term of the formula is produced by some scheme generated by the grammar. As a corollary, we get a similar description of the set of normal proofs of positive formulae for a large class of theories including simple type theory and System F.
A Direct Construction of Optimal Symmetrical Z-Complementary Code Sets of Prime Power Lengths
Venue: arXiv cs.IT 2023
Year: 2023

This paper presents a direct construction of an optimal symmetrical Z-complementary code set (SZCCS) of prime power lengths using a multi-variable function (MVF). SZCCS is a natural extension of the Z-complementary code set (ZCCS), which has only front-end zero correlation zone (ZCZ) width. SZCCS has both front-end and tail-end ZCZ width. SZCCSs are used in developing optimal training sequences for broadband generalized spatial modulation systems over frequency-selective channels because they have ZCZ width on both the front and tail ends. The construction of optimal SZCCS with large set sizes and prime power lengths is presented for the first time in this paper. Furthermore, it is worth noting that several existing works on ZCCS and SZCCS can be viewed as special cases of the proposed construction.
Forecast reconciliation for vaccine supply chain optimization
Venue: arXiv cs.LG 2023
Year: 2023

Vaccine supply chain optimization can benefit from hierarchical time series forecasting, when grouping the vaccines by type or location. However, forecasts of different hierarchy levels become incoherent when higher levels do not match the sum of the lower levels forecasts, which can be addressed by reconciliation methods. In this paper, we tackle the vaccine sale forecasting problem by modeling sales data from GSK between 2010 and 2021 as a hierarchical time series. After forecasting future values with several ARIMA models, we systematically compare the performance of various reconciliation methods, using statistical tests. We also compare the performance of the forecast before and after COVID. The results highlight Minimum Trace and Weighted Least Squares with Structural scaling as the best performing methods, which provided a coherent forecast while reducing the forecast error of the baseline ARIMA.
FPT Approximations for Capacitated/Fair Clustering with Outliers
Venue: arXiv cs.DS 2023
Year: 2023

Clustering problems such as $k$-Median, and $k$-Means, are motivated from applications such as location planning, unsupervised learning among others. In such applications, it is important to find the clustering of points that is not ``skewed'' in terms of the number of points, i.e., no cluster should contain too many points. This is modeled by capacity constraints on the sizes of clusters. In an orthogonal direction, another important consideration in clustering is how to handle the presence of outliers in the data. Indeed, these clustering problems have been generalized in the literature to separately handle capacity constraints and outliers. To the best of our knowledge, there has been very little work on studying the approximability of clustering problems that can simultaneously handle both capacities and outliers. We initiate the study of the Capacitated $k$-Median with Outliers (C$k$MO) problem. Here, we want to cluster all except $m$ outlier points into at most $k$ clusters, such that (i) the clusters respect the capacity constraints, and (ii) the cost of clustering, defined as the sum of distances of each non-outlier point to its assigned cluster-center, is minimized. We design the first constant-factor approximation algorithms for C$k$MO. In particular, our algorithm returns a (3+ε)-approximation for C$k$MO in general metric spaces, and a (1+ε)-approximation in Euclidean spaces of constant dimension, that runs in time in time $f(k, m, ε) \cdot |I_m|^{O(1)}$, where $|I_m|$ denotes the input size. We can also extend these results to a broader class of problems, including Capacitated k-Means/k-Facility Location with Outliers, and Size-Balanced Fair Clustering problems with Outliers. For each of these problems, we obtain an approximation ratio that matches the best known guarantee of the corresponding outlier-free problem.
Multitask learning in Audio Captioning: a sentence embedding regression loss acts as a regularizer
Venue: arXiv cs.SD 2023
Year: 2023

In this work, we propose to study the performance of a model trained with a sentence embedding regression loss component for the Automated Audio Captioning task. This task aims to build systems that can describe audio content with a single sentence written in natural language. Most systems are trained with the standard Cross-Entropy loss, which does not take into account the semantic closeness of the sentence. We found that adding a sentence embedding loss term reduces overfitting, but also increased SPIDEr from 0.397 to 0.418 in our first setting on the AudioCaps corpus. When we increased the weight decay value, we found our model to be much closer to the current state-of-the-art methods, with a SPIDEr score up to 0.444 compared to a 0.475 score. Moreover, this model uses eight times less trainable parameters. In this training setting, the sentence embedding loss has no more impact on the model performance.
An Adaptive Behaviour-Based Strategy for SARs interacting with Older Adults with MCI during a Serious Game Scenario
Venue: arXiv cs.RO 2023
Year: 2023

The monotonous nature of repetitive cognitive training may cause losing interest in it and dropping out by older adults. This study introduces an adaptive technique that enables a Socially Assistive Robot (SAR) to select the most appropriate actions to maintain the engagement level of older adults while they play the serious game in cognitive training. The goal is to develop an adaptation strategy for changing the robot's behaviour that uses reinforcement learning to encourage the user to remain engaged. A reinforcement learning algorithm was implemented to determine the most effective adaptation strategy for the robot's actions, encompassing verbal and nonverbal interactions. The simulation results demonstrate that the learning algorithm achieved convergence and offers promising evidence to validate the strategy's effectiveness.
Discovering the Effectiveness of Pre-Training in a Large-scale Car-sharing Platform
Venue: arXiv cs.CV 2023
Year: 2023

Recent progress of deep learning has empowered various intelligent transportation applications, especially in car-sharing platforms. While the traditional operations of the car-sharing service highly relied on human engagements in fleet management, modern car-sharing platforms let users upload car images before and after their use to inspect the cars without a physical visit. To automate the aforementioned inspection task, prior approaches utilized deep neural networks. They commonly employed pre-training, a de-facto technique to establish an effective model under the limited number of labeled datasets. As candidate practitioners who deal with car images would presumably get suffered from the lack of a labeled dataset, we analyzed a sophisticated analogy into the effectiveness of pre-training is important. However, prior studies primarily shed a little spotlight on the effectiveness of pre-training. Motivated by the aforementioned lack of analysis, our study proposes a series of analyses to unveil the effectiveness of various pre-training methods in image recognition tasks at the car-sharing platform. We set two real-world image recognition tasks in the car-sharing platform in a live service, established them under the many-shot and few-shot problem settings, and scrutinized which pre-training method accomplishes the most effective performance in which setting. Furthermore, we analyzed how does the pre-training and fine-tuning convey different knowledge to the neural networks for a precise understanding.
Learning-based Framework for US Signals Super-resolution
Venue: arXiv cs.CV 2023
Year: 2023

We propose a novel deep-learning framework for super-resolution ultrasound images and videos in terms of spatial resolution and line reconstruction. We up-sample the acquired low-resolution image through a vision-based interpolation method; then, we train a learning-based model to improve the quality of the up-sampling. We qualitatively and quantitatively test our model on different anatomical districts (e.g., cardiac, obstetric) images and with different up-sampling resolutions (i.e., 2X, 4X). Our method improves the PSNR median value with respect to SOTA methods of $1.7\%$ on obstetric 2X raw images, $6.1\%$ on cardiac 2X raw images, and $4.4\%$ on abdominal raw 4X images; it also improves the number of pixels with a low prediction error of $9.0\%$ on obstetric 4X raw images, $5.2\%$ on cardiac 4X raw images, and $6.2\%$ on abdominal 4X raw images. The proposed method is then applied to the spatial super-resolution of 2D videos, by optimising the sampling of lines acquired by the probe in terms of the acquisition frequency. Our method specialises trained networks to predict the high-resolution target through the design of the network architecture and the loss function, taking into account the anatomical district and the up-sampling factor and exploiting a large ultrasound data set. The use of deep learning on large data sets overcomes the limitations of vision-based algorithms that are general and do not encode the characteristics of the data. Furthermore, the data set can be enriched with images selected by medical experts to further specialise the individual networks. Through learning and high-performance computing, our super-resolution is specialised to different anatomical districts by training multiple networks. Furthermore, the computational demand is shifted to centralised hardware resources with a real-time execution of the network's prediction on local devices.
Retrieving Comparative Arguments using Ensemble Methods and Neural Information Retrieval
Venue: arXiv cs.IR 2023
Year: 2023

In this paper, we present a submission to the Touche lab's Task 2 on Argument Retrieval for Comparative Questions. Our team Katana supplies several approaches based on decision tree ensembles algorithms to rank comparative documents in accordance with their relevance and argumentative support. We use PyTerrier library to apply ensembles models to a ranking problem, considering statistical text features and features based on comparative structures. We also employ large contextualized language modelling techniques, such as BERT, to solve the proposed ranking task. To merge this technique with ranking modelling, we leverage neural ranking library OpenNIR. Our systems substantially outperforming the proposed baseline and scored first in relevance and second in quality according to the official metrics of the competition (for measure NDCG@5 score). Presented models could help to improve the performance of processing comparative queries in information retrieval and dialogue systems.
Towards Unified AI Drug Discovery with Multiple Knowledge Modalities
Venue: arXiv cs.LG 2023
Year: 2023

In recent years, AI models that mine intrinsic patterns from molecular structures and protein sequences have shown promise in accelerating drug discovery. However, these methods partly lag behind real-world pharmaceutical approaches of human experts that additionally grasp structured knowledge from knowledge bases and unstructured knowledge from biomedical literature. To bridge this gap, we propose KEDD, a unified, end-to-end, and multimodal deep learning framework that optimally incorporates both structured and unstructured knowledge for vast AI drug discovery tasks. The framework first extracts underlying characteristics from heterogeneous inputs, and then applies multimodal fusion for accurate prediction. To mitigate the problem of missing modalities, we leverage multi-head sparse attention and a modality masking mechanism to extract relevant information robustly. Benefiting from integrated knowledge, our framework achieves a deeper understanding of molecule entities, brings significant improvements over state-of-the-art methods on a wide range of tasks and benchmarks, and reveals its promising potential in assisting real-world drug discovery.