OpenRaiser/Intern-Atlas huggingface dataset:
Probabilistic estimation of the algebraic degree of Boolean functions
Venue: arXiv cs.CR 2023
Year: 2023

The algebraic degree is an important parameter of Boolean functions used in cryptography. When a function in a large number of variables is not given explicitly in algebraic normal form, it might not be feasible to compute its degree. Instead, one can try to estimate the degree using probabilistic tests. We propose a probabilistic test for deciding whether the algebraic degree of a Boolean function $f$ is below a certain value $k$. The test involves picking an affine space of dimension $k$ and testing whether the values on $f$ on that space sum up to zero. If $deg(f)<k$, then $f$ will always pass the test, otherwise it will sometimes pass and sometimes fail the test, depending on which affine space was chosen. The probability of failing the proposed test is closely related to the number of monomials of degree $k$ in a polynomial $g$, averaged over all the polynomials $g$ which are affine equivalent to $f$. We initiate the study of the probability of failing the proposed ``$deg(f)<k$'' test. We show that in the particular case when the degree of $f$ is actually equal to $k$, the probability will be in the interval $(0.288788, 0.5]$, and therefore a small number of runs of the test is sufficient to give, with very high probability, the correct answer. Exact values of this probability for all the polynomials in 8 variables were computed using the representatives listed by Hou and by Langevin and Leander.
Opening the Black Box: Analyzing Attention Weights and Hidden States in Pre-trained Language Models for Non-language Tasks
Venue: arXiv cs.CL 2023
Year: 2023

Investigating deep learning language models has always been a significant research area due to the ``black box" nature of most advanced models. With the recent advancements in pre-trained language models based on transformers and their increasing integration into daily life, addressing this issue has become more pressing. In order to achieve an explainable AI model, it is essential to comprehend the procedural steps involved and compare them with human thought processes. Thus, in this paper, we use simple, well-understood non-language tasks to explore these models' inner workings. Specifically, we apply a pre-trained language model to constrained arithmetic problems with hierarchical structure, to analyze their attention weight scores and hidden states. The investigation reveals promising results, with the model addressing hierarchical problems in a moderately structured manner, similar to human problem-solving strategies. Additionally, by inspecting the attention weights layer by layer, we uncover an unconventional finding that layer 10, rather than the model's final layer, is the optimal layer to unfreeze for the least parameter-intensive approach to fine-tune the model. We support these findings with entropy analysis and token embeddings similarity analysis. The attention analysis allows us to hypothesize that the model can generalize to longer sequences in ListOps dataset, a conclusion later confirmed through testing on sequences longer than those in the training set. Lastly, by utilizing a straightforward task in which the model predicts the winner of a Tic Tac Toe game, we identify limitations in attention analysis, particularly its inability to capture 2D patterns.
Tailstorm: A Secure and Fair Blockchain for Cash Transactions
Venue: arXiv cs.CR 2023
Year: 2023

Proof-of-work (PoW) cryptocurrencies rely on a balance of security and fairness in order to maintain a sustainable ecosystem of miners and users. Users demand fast and consistent transaction confirmation, and in exchange drive the adoption and valuation of the cryptocurrency. Miners provide the confirmations, however, they primarily seek rewards. In unfair systems, miners can amplify their rewards by consolidating mining power. Centralization however, undermines the security guarantees of the system and might discourage users. In this paper we present Tailstorm, a cryptocurrency that strikes this balance. Tailstorm merges multiple recent protocol improvements addressing security, confirmation latency, and throughput with a novel incentive mechanism improving fairness. We implement a parallel proof-of-work consensus mechanism with $k$ PoWs per block to obtain state-of-the-art consistency guarantees. Inspired by Bobtail and Storm, we structure the individual PoWs in a tree which, by including a list of transactions with each PoW, reduces confirmation latency and improves throughput. Our proposed incentive mechanism discounts rewards based on the depth of this tree. Thereby, it effectively punishes information withholding, the core attack strategy used to reap an unfair share of rewards. We back our claims with a comprehensive analysis. We present a generic system model which allows us to specify Bitcoin, $B_k$, and Tailstorm from a joint set of assumptions. We provide an analytical bound for the fairness of Tailstorm and Bitcoin in honest networks and we confirm the results through simulation. We evaluate the effectiveness of dishonest behaviour through reinforcement learning. Our attack search reproduces known optimal strategies against Bitcoin, uncovers new ones against $B_k$, and confirms that Tailstorm's reward discounting makes it more resilient to incentive layer attacks.
Online Resource Allocation with Convex-set Machine-Learned Advice
Venue: arXiv cs.DS 2023
Year: 2023

Decision-makers often have access to a machine-learned prediction about demand, referred to as advice, which can potentially be utilized in online decision-making processes for resource allocation. However, exploiting such advice poses challenges due to its potential inaccuracy. To address this issue, we propose a framework that enhances online resource allocation decisions with potentially unreliable machine-learned (ML) advice. We assume here that this advice is represented by a general convex uncertainty set for the demand vector. We introduce a parameterized class of Pareto optimal online resource allocation algorithms that strike a balance between consistent and robust ratios. The consistent ratio measures the algorithm's performance (compared to the optimal hindsight solution) when the ML advice is accurate, while the robust ratio captures performance under an adversarial demand process when the advice is inaccurate. Specifically, in a C-Pareto optimal setting, we maximize the robust ratio while ensuring that the consistent ratio is at least C. Our proposed C-Pareto optimal algorithm is an adaptive protection level algorithm, which extends the classical fixed protection level algorithm introduced in Littlewood (2005) and Ball and Queyranne (2009). Solving a complex non-convex continuous optimization problem characterizes the adaptive protection level algorithm. To complement our algorithms, we present a simple method for computing the maximum achievable consistent ratio, which serves as an estimate for the maximum value of the ML advice. Additionally, we present numerical studies to evaluate the performance of our algorithm in comparison to benchmark algorithms. The results demonstrate that by adjusting the parameter C, our algorithms effectively strike a balance between worst-case and average performance, outperforming the benchmark algorithms.
Resilient Sparse Array Radar with the Aid of Deep Learning
Venue: arXiv cs.LG 2023
Year: 2023

In this paper, we address the problem of direction of arrival (DOA) estimation for multiple targets in the presence of sensor failures in a sparse array. Generally, sparse arrays are known with very high-resolution capabilities, where N physical sensors can resolve up to $\mathcal{O}(N^2)$ uncorrelated sources. However, among the many configurations introduced in the literature, the arrays that provide the largest hole-free co-array are the most susceptible to sensor failures. We propose here two machine learning (ML) methods to mitigate the effect of sensor failures and maintain the DOA estimation performance and resolution. The first method enhances the conventional spatial smoothing using deep neural network (DNN), while the second one is an end-to-end data-driven method. Numerical results show that both approaches can significantly improve the performance of MRA with two failed sensors. The data-driven method can maintain the performance of the array with no failures at high signal-tonoise ratio (SNR). Moreover, both approaches can even perform better than the original array at low SNR thanks to the denoising effect of the proposed DNN
StarVQA+: Co-training Space-Time Attention for Video Quality Assessment
Venue: arXiv cs.CV 2023
Year: 2023

Self-attention based Transformer has achieved great success in many computer vision tasks. However, its application to video quality assessment (VQA) has not been satisfactory so far. Evaluating the quality of in-the-wild videos is challenging due to the unknown of pristine reference and shooting distortion. This paper presents a co-trained Space-Time Attention network for the VQA problem, termed StarVQA+. Specifically, we first build StarVQA+ by alternately concatenating the divided space-time attention. Then, to facilitate the training of StarVQA+, we design a vectorized regression loss by encoding the mean opinion score (MOS) to the probability vector and embedding a special token as the learnable variable of MOS, leading to better fitting of human's rating process. Finally, to solve the data hungry problem with Transformer, we propose to co-train the spatial and temporal attention weights using both images and videos. Various experiments are conducted on the de-facto in-the-wild video datasets, including LIVE-Qualcomm, LIVE-VQC, KoNViD-1k, YouTube-UGC, LSVQ, LSVQ-1080p, and DVL2021. Experimental results demonstrate the superiority of the proposed StarVQA+ over the state-of-the-art.
The Effect of Noise on the Emergence of Continuous Norms and its Evolutionary Dynamics
Venue: arXiv cs.MA 2023
Year: 2023

We examine the effect of noise on societies of agents using an agent-based model of evolutionary norm emergence. Generally, we see that noisy societies are more selfish, smaller and discontent, and are caught in rounds of perpetual punishment preventing them from flourishing. Surprisingly, despite the effect of noise on the population, it does not seem to evolve away. We carry out further analysis and provide reasons for why this may be the case. Furthermore, we claim that our framework that evolves the noise/ambiguity of norms may be a new way to model the tight/loose framework of norms, suggesting that despite ambiguous norms detrimental effect on society, evolution does not favour clarity.
On the Validation of Gibbs Algorithms: Training Datasets, Test Datasets and their Aggregation
Venue: arXiv cs.LG 2023
Year: 2023

The dependence on training data of the Gibbs algorithm (GA) is analytically characterized. By adopting the expected empirical risk as the performance metric, the sensitivity of the GA is obtained in closed form. In this case, sensitivity is the performance difference with respect to an arbitrary alternative algorithm. This description enables the development of explicit expressions involving the training errors and test errors of GAs trained with different datasets. Using these tools, dataset aggregation is studied and different figures of merit to evaluate the generalization capabilities of GAs are introduced. For particular sizes of such datasets and parameters of the GAs, a connection between Jeffrey's divergence, training and test errors is established.
Improving Software Requirements Prioritization through the Lens of Constraint Solving
Venue: arXiv cs.SE 2023
Year: 2023

Requirements prioritization is a critical activity during the early software development process, which produces a set of key requirements to implement. The prioritization process offers a parity among the requirements based on multiple characteristics, including end-users' preferences, cost to implement, and technical dependencies. This paper presents an interactive method to requirements prioritization that leverages the pairwise comparisons and a constraint solver. Our method employs an interactive accumulation of knowledge from the requirements analyst when the relative priority among the requirements cannot be determined based on the existing knowledge from the requirements documents. The final ranking of the requirements is produced via the constraint solver and interactive pairwise comparisons. We evaluate the proposed method using the requirements from a real healthcare project. The proposed prioritization method relying on a constraint solver outperforms state-of-the-art interactive prioritization methods in terms of effectiveness and robustness to analyst's errors.
A VM-Agnostic and Backwards Compatible Protected Modifier for Dynamically-Typed Languages
Venue: arXiv cs.PL 2023
Year: 2023

In object-oriented languages, method visibility modifiers hold a key role in separating internal methods from the public API. Protected visibility modifiers offer a way to hide methods from external objects while authorizing internal use and overriding in subclasses. While present in main statically-typed languages, visibility modifiers are not as common or mature in dynamically-typed languages. In this article, we present ProtDyn, a self-send-based visibility model calculated at compile time for dynamically-typed languages relying on name-mangling and syntactic differentiation of self vs non self sends. We present #Pharo, a ProtDyn implementation of this model that is backwards compatible with existing programs, and its port to Python. Using these implementations we study the performance impact of ProtDyn on the method lookup, in the presence of global lookup caches and polymorphic inline caches. We show that our name mangling and double method registration technique has a very low impact on performance and keeps the benefits from the global lookup cache and polymorphic inline cache. We also show that the memory overhead on a real use case is between 2% and 13% in the worst-case scenario. Protected modifier semantics enforces encapsulation such as private but allow developers to still extend the class in subclasses. ProtDyn offers a VM-agnostic and backwards-compatible design to introduce protected semantics in dynamically-typed languages.
Sleptsov Nets are Turing-complete
Venue: arXiv cs.CC 2023
Year: 2023

The present paper proves that a Sleptsov net (SN) is Turing-complete, that considerably improves, with a brief construct, the previous result that a strong SN is Turing-complete. Remind that, unlike Petri nets, an SN always fires enabled transitions at their maximal firing multiplicity, as a single step, leaving for a nondeterministic choice of which fireable transitions to fire. A strong SN restricts nondeterministic choice to firing only the transitions having the highest firing multiplicity.
On-orbit model training for satellite imagery with label proportions
Venue: arXiv cs.CV 2023
Year: 2023

This work addresses the challenge of training supervised machine or deep learning models on orbiting platforms where we are generally constrained by limited on-board hardware capabilities and restricted uplink bandwidths to upload. We aim at enabling orbiting spacecrafts to (1) continuously train a lightweight model as it acquires imagery; and (2) receive new labels while on orbit to refine or even change the predictive task being trained. For this, we consider chip level regression tasks (i.e. predicting the vegetation percentage of a 20 km$^2$ patch) when we only have coarser label proportions, such as municipality level vegetation statistics (a municipality containing several patches). Such labels proportions have the additional advantage that usually come in tabular data and are widely available in many regions of the world and application areas. This can be framed as a Learning from Label Proportions (LLP) problem setup. LLP applied to Earth Observation (EO) data is still an emerging field and performing comparative studies in applied scenarios remains a challenge due to the lack of standardized datasets. In this work, first, we show how very simple deep learning and probabilistic methods (with {\raise.17ex\hbox{$\scriptstyle\sim$}}5K parameters) generally perform better than standard more complex ones, providing a surprising level of finer grained spatial detail when trained with much coarser label proportions. Second, we publish a set of benchmarking datasets enabling comparative LLP applied to EO, providing both fine grained labels and aggregated data according to existing administrative divisions. Finally, we show how this approach fits an on-orbit training scenario by reducing vastly both the amount of computing and the size of the labels sets. Source code is available at https://github.com/rramosp/llpeo
Misinformation as Information Pollution
Venue: arXiv cs.SI 2023
Year: 2023

Social media feed algorithms are designed to optimize online social engagements for the purpose of maximizing advertising profits, and therefore have an incentive to promote controversial posts including misinformation. By thinking about misinformation as information pollution, we can draw parallels with environmental policy for countering pollution such as carbon taxes. Similar to pollution, a Pigouvian tax on misinformation provides economic incentives for social media companies to control the spread of misinformation more effectively to avoid or reduce their misinformation tax, while preserving some degree of freedom in platforms' response. In this paper, we highlight a bird's eye view of a Pigouvian misinformation tax and discuss the key questions and next steps for implementing such a taxing scheme.
Mixed-model Sequencing with Stochastic Failures: A Case Study for Automobile Industry
Venue: arXiv cs.CY 2023
Year: 2023

In the automotive industry, the sequence of vehicles to be produced is determined ahead of the production day. However, there are some vehicles, failed vehicles, that cannot be produced due to some reasons such as material shortage or paint failure. These vehicles are pulled out of the sequence, and the vehicles in the succeeding positions are moved forward, potentially resulting in challenges for logistics or other scheduling concerns. This paper proposes a two-stage stochastic program for the mixed-model sequencing (MMS) problem with stochastic product failures, and provides improvements to the second-stage problem. To tackle the exponential number of scenarios, we employ the sample average approximation approach and two solution methodologies. On one hand, we develop an L-shaped decomposition-based algorithm, where the computational experiments show its superiority over solving the deterministic equivalent formulation with an off-the-shelf solver. Moreover, we provide a tabu search algorithm in addition to a greedy heuristic to tackle case study instances inspired by our car manufacturer partner. Numerical experiments show that the proposed solution methodologies generate high quality solutions by utilizing a sample of scenarios. Particularly, a robust sequence that is generated by considering car failures can decrease the expected work overload by more than 20\% for both small- and large-sized instances.
Identifying and Extracting Rare Disease Phenotypes with Large Language Models
Venue: arXiv cs.CL 2023
Year: 2023

Rare diseases (RDs) are collectively common and affect 300 million people worldwide. Accurate phenotyping is critical for informing diagnosis and treatment, but RD phenotypes are often embedded in unstructured text and time-consuming to extract manually. While natural language processing (NLP) models can perform named entity recognition (NER) to automate extraction, a major bottleneck is the development of a large, annotated corpus for model training. Recently, prompt learning emerged as an NLP paradigm that can lead to more generalizable results without any (zero-shot) or few labeled samples (few-shot). Despite growing interest in ChatGPT, a revolutionary large language model capable of following complex human prompts and generating high-quality responses, none have studied its NER performance for RDs in the zero- and few-shot settings. To this end, we engineered novel prompts aimed at extracting RD phenotypes and, to the best of our knowledge, are the first the establish a benchmark for evaluating ChatGPT's performance in these settings. We compared its performance to the traditional fine-tuning approach and conducted an in-depth error analysis. Overall, fine-tuning BioClinicalBERT resulted in higher performance (F1 of 0.689) than ChatGPT (F1 of 0.472 and 0.591 in the zero- and few-shot settings, respectively). Despite this, ChatGPT achieved similar or higher accuracy for certain entities (i.e., rare diseases and signs) in the one-shot setting (F1 of 0.776 and 0.725). This suggests that with appropriate prompt engineering, ChatGPT has the potential to match or outperform fine-tuned language models for certain entity types with just one labeled sample. While the proliferation of large language models may provide opportunities for supporting RD diagnosis and treatment, researchers and clinicians should critically evaluate model outputs and be well-informed of their limitations.
Decidable Exponentials in Nonassociative Noncommutative Linear Logic
Venue: arXiv cs.LO 2023
Year: 2023

The use of exponentials in linear logic greatly enhances its expressive power. In this paper we focus on nonassociative noncommutative multiplicative linear logic, and systematically explore modal axioms K, T, and 4 as well as the structural rules of contraction and weakening. We give sequent systems for each subset of these axioms; these enjoy cut elimination and have analogues in more structural logics. We then appeal to work of Bulinska extending work of Buszkowski to show that several of these logics are PTIME decidable and generate context free languages as categorial grammars. This contrasts associative systems where similar logics are known to generate all recursively enumerable languages, and are thus in particular undecidable.
Mapping and Cleaning Open Commonsense Knowledge Bases with Generative Translation
Venue: arXiv cs.CL 2023
Year: 2023

Structured knowledge bases (KBs) are the backbone of many know\-ledge-intensive applications, and their automated construction has received considerable attention. In particular, open information extraction (OpenIE) is often used to induce structure from a text. However, although it allows high recall, the extracted knowledge tends to inherit noise from the sources and the OpenIE algorithm. Besides, OpenIE tuples contain an open-ended, non-canonicalized set of relations, making the extracted knowledge's downstream exploitation harder. In this paper, we study the problem of mapping an open KB into the fixed schema of an existing KB, specifically for the case of commonsense knowledge. We propose approaching the problem by generative translation, i.e., by training a language model to generate fixed-schema assertions from open ones. Experiments show that this approach occupies a sweet spot between traditional manual, rule-based, or classification-based canonicalization and purely generative KB construction like COMET. Moreover, it produces higher mapping accuracy than the former while avoiding the association-based noise of the latter.