OpenRaiser/Intern-Atlas huggingface dataset:
Autonomous Intelligent Cyber-defense Agent (AICA) Reference Architecture. Release 2.0
Venue: arXiv cs.CR 2023
Year: 2023

This report - a major revision of its previous release - describes a reference architecture for intelligent software agents performing active, largely autonomous cyber-defense actions on military networks of computing and communicating devices. The report is produced by the North Atlantic Treaty Organization (NATO) Research Task Group (RTG) IST-152 "Intelligent Autonomous Agents for Cyber Defense and Resilience". In a conflict with a technically sophisticated adversary, NATO military tactical networks will operate in a heavily contested battlefield. Enemy software cyber agents - malware - will infiltrate friendly networks and attack friendly command, control, communications, computers, intelligence, surveillance, and reconnaissance and computerized weapon systems. To fight them, NATO needs artificial cyber hunters - intelligent, autonomous, mobile agents specialized in active cyber defense. With this in mind, in 2016, NATO initiated RTG IST-152. Its objective has been to help accelerate the development and transition to practice of such software agents by producing a reference architecture and technical roadmap. This report presents the concept and architecture of an Autonomous Intelligent Cyber-defense Agent (AICA). We describe the rationale of the AICA concept, explain the methodology and purpose that drive the definition of the AICA Reference Architecture, and review some of the main features and challenges of AICAs.
The clustered Sparrow algorithm
Venue: arXiv cs.DS 2023
Year: 2023

In this paper, we study an extension of Schoning's algorithm [Schoning, 1991] for 3SAT, the clustered Sparrow algorithm We also present strong arguments that this algorithm is polynomial.
The Energy Complexity of Diameter and Minimum Cut Computation in Bounded-Genus Networks
Venue: arXiv cs.DS 2023
Year: 2023

This paper investigates the energy complexity of distributed graph problems in multi-hop radio networks, where the energy cost of an algorithm is measured by the maximum number of awake rounds of a vertex. Recent works revealed that some problems, such as broadcast, breadth-first search, and maximal matching, can be solved with energy-efficient algorithms that consume only $\text{poly} \log n$ energy. However, there exist some problems, such as computing the diameter of the graph, that require $Ω(n)$ energy to solve. To improve energy efficiency for these problems, we focus on a special graph class: bounded-genus graphs. We present algorithms for computing the exact diameter, the exact global minimum cut size, and a $(1 \pmε)$-approximate $s$-$t$ minimum cut size with $\tilde{O}(\sqrt{n})$ energy for bounded-genus graphs. Our approach is based on a generic framework that divides the vertex set into high-degree and low-degree parts and leverages the structural properties of bounded-genus graphs to control the number of certain connected components in the subgraph induced by the low-degree part.
A hybrid shifted Laplacian multigrid and domain decomposition preconditioner for the elastic Helmholtz equations
Venue: arXiv cs.CE 2023
Year: 2023

In this work we extend the shifted Laplacian approach to the elastic Helmholtz equation. The shifted Laplacian multigrid method is a common preconditioning approach for the discretized acoustic Helmholtz equation. In some cases, like geophysical seismic imaging, one needs to consider the elastic Helmholtz equation, which is harder to solve: it is three times larger and contains a nullity-rich grad-div term. These properties make the solution of the equation more difficult for multigrid solvers. The key idea in this work is combining the shifted Laplacian with approaches for linear elasticity. We provide local Fourier analysis and numerical evidence that the convergence rate of our method is independent of the Poisson's ratio. Moreover, to better handle the problem size, we complement our multigrid method with the domain decomposition approach, which works in synergy with the local nature of the shifted Laplacian, so we enjoy the advantages of both methods without sacrificing performance. We demonstrate the efficiency of our solver on 2D and 3D problems in heterogeneous media.
Learning and Matching Multi-View Descriptors for Registration of Point Clouds
Venue: arXiv cs.CV 2023
Year: 2023

Critical to the registration of point clouds is the establishment of a set of accurate correspondences between points in 3D space. The correspondence problem is generally addressed by the design of discriminative 3D local descriptors on the one hand, and the development of robust matching strategies on the other hand. In this work, we first propose a multi-view local descriptor, which is learned from the images of multiple views, for the description of 3D keypoints. Then, we develop a robust matching approach, aiming at rejecting outlier matches based on the efficient inference via belief propagation on the defined graphical model. We have demonstrated the boost of our approaches to registration on the public scanning and multi-view stereo datasets. The superior performance has been verified by the intensive comparisons against a variety of descriptors and matching methods.
A Note on Clustering Aggregation for Binary Clusterings
Venue: arXiv cs.CC 2023
Year: 2023

We consider the clustering aggregation problem in which we are given a set of clusterings and want to find an aggregated clustering which minimizes the sum of mismatches to the input clusterings. In the binary case (each clustering is a bipartition) this problem was known to be NP-hard under Turing reductions. We strengthen this result by providing a polynomial-time many-one reduction. Our result also implies that no $2^{o(n)}\cdot |I'|^{O(1)}$-time algorithm exists that solves any given clustering instance $I'$ with $n$ elements, unless the Ð fails. On the positive side, we show that the problem is fixed-parameter tractable with respect to the number of input clusterings and we give an integer linear programming formulation.
Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity
Venue: arXiv cs.DS 2023
Year: 2023

Submodular maximization is a general optimization problem with a wide range of applications in machine learning (e.g., active learning, clustering, and feature selection). In large-scale optimization, the parallel running time of an algorithm is governed by its adaptivity, which measures the number of sequential rounds needed if the algorithm can execute polynomially-many independent oracle queries in parallel. While low adaptivity is ideal, it is not sufficient for an algorithm to be efficient in practice -- there are many applications of distributed submodular optimization where the number of function evaluations becomes prohibitively expensive. Motivated by these applications, we study the adaptivity and query complexity of submodular maximization. In this paper, we give the first constant-factor approximation algorithm for maximizing a non-monotone submodular function subject to a cardinality constraint $k$ that runs in $O(\log(n))$ adaptive rounds and makes $O(n \log(k))$ oracle queries in expectation. In our empirical study, we use three real-world applications to compare our algorithm with several benchmarks for non-monotone submodular maximization. The results demonstrate that our algorithm finds competitive solutions using significantly fewer rounds and queries.
Temporal Information Extraction by Predicting Relative Time-lines
Venue: arXiv cs.CL 2023
Year: 2023

The current leading paradigm for temporal information extraction from text consists of three phases: (1) recognition of events and temporal expressions, (2) recognition of temporal relations among them, and (3) time-line construction from the temporal relations. In contrast to the first two phases, the last phase, time-line construction, received little attention and is the focus of this work. In this paper, we propose a new method to construct a linear time-line from a set of (extracted) temporal relations. But more importantly, we propose a novel paradigm in which we directly predict start and end-points for events from the text, constituting a time-line without going through the intermediate step of prediction of temporal relations as in earlier work. Within this paradigm, we propose two models that predict in linear complexity, and a new training loss using TimeML-style annotations, yielding promising results.
Approximating Bimatrix Nash Equilibrium Via Trilinear Minimax
Venue: arXiv cs.GT 2023
Year: 2023

The Bimatrix Nash Equilibrium (NE) for $m \times n$ real matrices $R$ and $C$, denoted as the {\it Row} and {\it Column} players, is characterized as follows: Let $Δ=S_m \times S_n$, where $S_k$ denotes the unit simplex in $\mathbb{R}^k$. For a given point $p=(x,y) \in Δ$, define $R[p]=x^TRy$ and $C[p]=x^TCy$. Consequently, there exists a subset $Δ_* \subset Δ$ such that for any $p_*=(x_*,y_*) \in Δ_*$, $\max_{p \in Δ, y=y_*}R[p]=R[p_*]$ and $\max_{p \in Δ, x=x_* } C[p]=C[p_*]$. The computational complexity of bimatrix NE falls within the class of {\it PPAD-complete}. Although the von Neumann Minimax Theorem is a special case of bimatrix NE, we introduce a novel extension termed {\it Trilinear Minimax Relaxation} (TMR) with the following implications: Let $λ^*=\min_{α\in S_{2}} \max_{p \in Δ} (α_1 R[p]+ α_2C[p])$ and $λ_*=\max_{p \in Δ} \min_{α\in S_{2}} (α_1 R[p]+ α_2C[p])$. $λ^* \geq λ_*$. $λ^*$ is computable as a linear programming in $O(mn)$ time, ensuring $\max_{p_* \in Δ_*}\min \{R[p_*], C[p_*]\} \leq λ^*$, meaning that in any Nash Equilibrium it is not possible to have both players' payoffs to exceed $λ^*$. $λ^*=λ_*$ if and only if there exists $p^* \in Δ$ such that $λ^*= \min\{R[p^*], C[p^*]\}$. Such a $p^*$ serves as an approximate Nash Equilibrium. We analyze the cases where such $p^*$ exists and is computable. Even when $λ^* > λ_*$, we derive approximate Nash Equilibria. In summary, the aforementioned properties of TMR and its efficient computational aspects underscore its significance and relevance for Nash Equilibrium, irrespective of the computational complexity associated with bimatrix Nash Equilibrium. Finally, we extend TMR to scenarios involving three or more players.
Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise
Venue: arXiv cs.IT 2023
Year: 2023

It has long been known that the existence of certain superquantum nonlocal correlations would cause communication complexity to collapse. The absurdity of a world in which any nonlocal binary function could be evaluated with a constant amount of communication in turn provides a tantalizing way to distinguish quantum mechanics from incorrect theories of physics; the statement "communication complexity is nontrivial" has even been conjectured to be a concise information-theoretic axiom for characterizing quantum mechanics. We directly address the viability of that perspective with two results. First, we exhibit a nonlocal game such that communication complexity collapses in any physical theory whose maximal winning probability exceeds the quantum value. Second, we consider the venerable CHSH game that initiated this line of inquiry. In that case, the quantum value is about 0.85 but it is known that a winning probability of approximately 0.91 would collapse communication complexity. We provide evidence that the 0.91 result is the best possible using a large class of proof strategies, suggesting that the communication complexity axiom is insufficient for characterizing CHSH correlations. Both results build on new insights about reliable classical computation. The first exploits our formalization of an equivalence between amplification and reliable computation, while the second follows from an upper bound on the threshold for reliable computation with formulas of noisy XOR and AND gates.
Logic program proportions
Venue: arXiv cs.LO 2023
Year: 2023

The purpose of this paper is to present a fresh idea on how symbolic learning might be realized via analogical reasoning. For this, we introduce directed analogical proportions between logic programs of the form "$P$ transforms into $Q$ as $R$ transforms into $S$" as a mechanism for deriving similar programs by analogy-making. The idea is to instantiate a fragment of a recently introduced abstract algebraic framework of analogical proportions in the domain of logic programming. Technically, we define proportions in terms of modularity where we derive abstract forms of concrete programs from a "known" source domain which can then be instantiated in an "unknown" target domain to obtain analogous programs. To this end, we introduce algebraic operations for syntactic logic program composition and concatenation. Interestingly, our work suggests a close relationship between modularity, generalization, and analogy which we believe should be explored further in the future. In a broader sense, this paper is a further step towards a mathematical theory of logic-based analogical reasoning and learning with potential applications to open AI-problems like commonsense reasoning and computational learning and creativity.
Batch DropBlock Network for Person Re-identification and Beyond
Venue: arXiv cs.CV 2023
Year: 2023

Since the person re-identification task often suffers from the problem of pose changes and occlusions, some attentive local features are often suppressed when training CNNs. In this paper, we propose the Batch DropBlock (BDB) Network which is a two branch network composed of a conventional ResNet-50 as the global branch and a feature dropping branch. The global branch encodes the global salient representations. Meanwhile, the feature dropping branch consists of an attentive feature learning module called Batch DropBlock, which randomly drops the same region of all input feature maps in a batch to reinforce the attentive feature learning of local regions. The network then concatenates features from both branches and provides a more comprehensive and spatially distributed feature representation. Albeit simple, our method achieves state-of-the-art on person re-identification and it is also applicable to general metric learning tasks. For instance, we achieve 76.4% Rank-1 accuracy on the CUHK03-Detect dataset and 83.0% Recall-1 score on the Stanford Online Products dataset, outperforming the existing works by a large margin (more than 6%).
Better Trees: An empirical study on hyperparameter tuning of classification decision tree induction algorithms
Venue: arXiv cs.LG 2023
Year: 2023

Machine learning algorithms often contain many hyperparameters (HPs) whose values affect the predictive performance of the induced models in intricate ways. Due to the high number of possibilities for these HP configurations and their complex interactions, it is common to use optimization techniques to find settings that lead to high predictive performance. However, insights into efficiently exploring this vast space of configurations and dealing with the trade-off between predictive and runtime performance remain challenging. Furthermore, there are cases where the default HPs fit the suitable configuration. Additionally, for many reasons, including model validation and attendance to new legislation, there is an increasing interest in interpretable models, such as those created by the Decision Tree (DT) induction algorithms. This paper provides a comprehensive approach for investigating the effects of hyperparameter tuning for the two DT induction algorithms most often used, CART and C4.5. DT induction algorithms present high predictive performance and interpretable classification models, though many HPs need to be adjusted. Experiments were carried out with different tuning strategies to induce models and to evaluate HPs' relevance using 94 classification datasets from OpenML. The experimental results point out that different HP profiles for the tuning of each algorithm provide statistically significant improvements in most of the datasets for CART, but only in one-third for C4.5. Although different algorithms may present different tuning scenarios, the tuning techniques generally required few evaluations to find accurate solutions. Furthermore, the best technique for all the algorithms was the IRACE. Finally, we found out that tuning a specific small subset of HPs is a good alternative for achieving optimal predictive performance.
Improving SGD convergence by online linear regression of gradients in multiple statistically relevant directions
Venue: arXiv cs.LG 2023
Year: 2023

Deep neural networks are usually trained with stochastic gradient descent (SGD), which minimizes objective function using very rough approximations of gradient, only averaging to the real gradient. Standard approaches like momentum or ADAM only consider a single direction, and do not try to model distance from extremum - neglecting valuable information from calculated sequence of gradients, often stagnating in some suboptimal plateau. Second order methods could exploit these missed opportunities, however, beside suffering from very large cost and numerical instabilities, many of them attract to suboptimal points like saddles due to negligence of signs of curvatures (as eigenvalues of Hessian). Saddle-free Newton method is a rare example of addressing this issue - changes saddle attraction into repulsion, and was shown to provide essential improvement for final value this way. However, it neglects noise while modelling second order behavior, focuses on Krylov subspace for numerical reasons, and requires costly eigendecomposion. Maintaining SFN advantages, there are proposed inexpensive ways for exploiting these opportunities. Second order behavior is linear dependence of first derivative - we can optimally estimate it from sequence of noisy gradients with least square linear regression, in online setting here: with weakening weights of old gradients. Statistically relevant subspace is suggested by PCA of recent noisy gradients - in online setting it can be made by slowly rotating considered directions toward new gradients, gradually replacing old directions with recent statistically relevant. Eigendecomposition can be also performed online: with regularly performed step of QR method to maintain diagonal Hessian. Outside the second order modeled subspace we can simultaneously perform gradient descent.
Adaptive Estimators Show Information Compression in Deep Neural Networks
Venue: arXiv cs.LG 2023
Year: 2023

To improve how neural networks function it is crucial to understand their learning process. The information bottleneck theory of deep learning proposes that neural networks achieve good generalization by compressing their representations to disregard information that is not relevant to the task. However, empirical evidence for this theory is conflicting, as compression was only observed when networks used saturating activation functions. In contrast, networks with non-saturating activation functions achieved comparable levels of task performance but did not show compression. In this paper we developed more robust mutual information estimation techniques, that adapt to hidden activity of neural networks and produce more sensitive measurements of activations from all functions, especially unbounded functions. Using these adaptive estimation techniques, we explored compression in networks with a range of different activation functions. With two improved methods of estimation, firstly, we show that saturation of the activation function is not required for compression, and the amount of compression varies between different activation functions. We also find that there is a large amount of variation in compression between different network initializations. Secondary, we see that L2 regularization leads to significantly increased compression, while preventing overfitting. Finally, we show that only compression of the last layer is positively correlated with generalization.
Why Learning of Large-Scale Neural Networks Behaves Like Convex Optimization
Venue: arXiv cs.LG 2023
Year: 2023

In this paper, we present some theoretical work to explain why simple gradient descent methods are so successful in solving non-convex optimization problems in learning large-scale neural networks (NN). After introducing a mathematical tool called canonical space, we have proved that the objective functions in learning NNs are convex in the canonical model space. We further elucidate that the gradients between the original NN model space and the canonical space are related by a pointwise linear transformation, which is represented by the so-called disparity matrix. Furthermore, we have proved that gradient descent methods surely converge to a global minimum of zero loss provided that the disparity matrices maintain full rank. If this full-rank condition holds, the learning of NNs behaves in the same way as normal convex optimization. At last, we have shown that the chance to have singular disparity matrices is extremely slim in large NNs. In particular, when over-parameterized NNs are randomly initialized, the gradient decent algorithms converge to a global minimum of zero loss in probability.
Token Swapping on Trees
Venue: arXiv cs.CC 2023
Year: 2023

The input to the token swapping problem is a graph with vertices $v_1, v_2, \ldots, v_n$, and $n$ tokens with labels $1, 2, \ldots, n$, one on each vertex. The goal is to get token $i$ to vertex $v_i$ for all $i= 1, \ldots, n$ using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge. We present some results about token swapping on a tree, also known as "sorting with a transposition tree": 1. An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a "happy leaf"), disproving a conjecture of Vaughan. 2. Any algorithm that fixes happy leaves -- as all known approximation algorithms for the problem do -- has approximation factor at least $4/3$. Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2. 3. A generalized problem -- weighted coloured token swapping -- is NP-complete on trees, even when they are restricted to be subdivided stars, but solvable in polynomial time on paths and stars. In this version, tokens and vertices have colours, and colours have weights. The goal is to get every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved.
Stabilize Deep ResNet with A Sharp Scaling Factor $τ$
Venue: arXiv cs.LG 2023
Year: 2023

We study the stability and convergence of training deep ResNets with gradient descent. Specifically, we show that the parametric branch in the residual block should be scaled down by a factor $τ=O(1/\sqrt{L})$ to guarantee stable forward/backward process, where $L$ is the number of residual blocks. Moreover, we establish a converse result that the forward process is unbounded when $τ>L^{-\frac{1}{2}+c}$, for any positive constant $c$. The above two results together establish a sharp value of the scaling factor in determining the stability of deep ResNet. Based on the stability result, we further show that gradient descent finds the global minima if the ResNet is properly over-parameterized, which significantly improves over the previous work with a much larger range of $τ$ that admits global convergence. Moreover, we show that the convergence rate is independent of the depth, theoretically justifying the advantage of ResNet over vanilla feedforward network. Empirically, with such a factor $τ$, one can train deep ResNet without normalization layer. Moreover, for ResNets with normalization layer, adding such a factor $τ$ also stabilizes the training and obtains significant performance gain for deep ResNet.