OpenRaiser/Intern-Atlas huggingface dataset:
Adaptive Multi-Feature Budgeted Profit Maximization in Social Networks
Venue: arXiv cs.SI 2022
Year: 2022

Online social network has been one of the most important platforms for viral marketing. Most of existing researches about diffusion of adoptions of new products on networks are about one diffusion. That is, only one piece of information about the product is spread on the network. However, in fact, one product may have multiple features and the information about different features may spread independently in social network. When a user would like to purchase the product, he would consider all of the features of the product comprehensively not just consider one. Based on this, we propose a novel problem, multi-feature budgeted profit maximization (MBPM) problem, which first considers budgeted profit maximization under multiple features propagation of one product. Given a social network with each node having an activation cost and a profit, MBPM problem seeks for a seed set with expected cost no more than the budget to make the total expected profit as large as possible. We consider MBPM problem under the adaptive setting, where seeds are chosen iteratively and next seed is selected according to current diffusion results. We study adaptive MBPM problem under two models, oracle model and noise model. The oracle model assumes conditional expected marginal profit of any node could be obtained in O(1) time and a (1-1/e) expected approximation policy is proposed. Under the noise model, we estimate conditional expected marginal profit of a node by modifying the EPIC algorithm and propose an efficient policy, which could return a (1-exp(ε-1)) expected approximation ratio. Several experiments are conducted on six realistic datasets to compare our proposed policies with their corresponding non-adaptive algorithms and some heuristic adaptive policies. Experimental results show efficiencies and superiorities of our policies.
Providing reliability in Recommender Systems through Bernoulli Matrix Factorization
Venue: arXiv cs.LG 2022
Year: 2022

Beyond accuracy, quality measures are gaining importance in modern recommender systems, with reliability being one of the most important indicators in the context of collaborative filtering. This paper proposes Bernoulli Matrix Factorization (BeMF), which is a matrix factorization model, to provide both prediction values and reliability values. BeMF is a very innovative approach from several perspectives: a) it acts on model-based collaborative filtering rather than on memory-based filtering, b) it does not use external methods or extended architectures, such as existing solutions, to provide reliability, c) it is based on a classification-based model instead of traditional regression-based models, and d) matrix factorization formalism is supported by the Bernoulli distribution to exploit the binary nature of the designed classification model. The experimental results show that the more reliable a prediction is, the less liable it is to be wrong: recommendation quality improves after the most reliable predictions are selected. State-of-the-art quality measures for reliability have been tested, which shows that BeMF outperforms previous baseline methods and models.
EDropout: Energy-Based Dropout and Pruning of Deep Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

Dropout is a well-known regularization method by sampling a sub-network from a larger deep neural network and training different sub-networks on different subsets of the data. Inspired by the dropout concept, we propose EDropout as an energy-based framework for pruning neural networks in classification tasks. In this approach, a set of binary pruning state vectors (population) represents a set of corresponding sub-networks from an arbitrary provided original neural network. An energy loss function assigns a scalar energy loss value to each pruning state. The energy-based model stochastically evolves the population to find states with lower energy loss. The best pruning state is then selected and applied to the original network. Similar to dropout, the kept weights are updated using backpropagation in a probabilistic model. The energy-based model again searches for better pruning states and the cycle continuous. Indeed, this procedure is in fact switching between the energy model, which manages the pruning states, and the probabilistic model, which updates the temporarily unpruned weights, in each iteration. The population can dynamically converge to a pruning state. This can be interpreted as dropout leading to pruning the network. From an implementation perspective, EDropout can prune typical neural networks without modification of the network architecture. We evaluated the proposed method on different flavours of ResNets, AlexNet, and SqueezeNet on the Kuzushiji, Fashion, CIFAR-10, CIFAR-100, and Flowers datasets, and compared the pruning rate and classification performance of the models. On average the networks trained with EDropout achieved a pruning rate of more than $50\%$ of the trainable parameters with approximately $<5\%$ and $<1\%$ drop of Top-1 and Top-5 classification accuracy, respectively.
Visual-based Kinematics and Pose Estimation for Skid-Steering Robots
Venue: arXiv cs.RO 2022
Year: 2022

To build commercial robots, skid-steering mechanical design is of increased popularity due to its manufacturing simplicity and unique mechanism. However, these also cause significant challenges on software and algorithm design, especially for the pose estimation (i.e., determining the robot's rotation and position) of skid-steering robots, since they change their orientation with an inevitable skid. To tackle this problem, we propose a probabilistic sliding-window estimator dedicated to skid-steering robots, using measurements from a monocular camera, the wheel encoders, and optionally an inertial measurement unit (IMU). Specifically, we explicitly model the kinematics of skid-steering robots by both track instantaneous centers of rotation (ICRs) and correction factors, which are capable of compensating for the complexity of track-to-terrain interaction, the imperfectness of mechanical design, terrain conditions and smoothness, etc. To prevent performance reduction in robots' long-term missions, the time- and location- varying kinematic parameters are estimated online along with pose estimation states in a tightly-coupled manner. More importantly, we conduct in-depth observability analysis for different sensors and design configurations in this paper, which provides us with theoretical tools in making the correct choice when building real commercial robots. In our experiments, we validate the proposed method by both simulation tests and real-world experiments, which demonstrate that our method outperforms competing methods by wide margins.
Vertex removal in biclique graphs
Venue: arXiv cs.DM 2022
Year: 2022

A \textit{biclique} is a maximal induced complete bipartite subgraph. The \textit{biclique graph} of a graph $H$, denoted by $KB(H)$, is the intersection graph of the family of all bicliques of $H$. In this work we address the following question: Given a biclique graph $G=KB(H)$, is it possible to remove a vertex $q$ of $G$, such that $G - \{q\}$ is a biclique graph? And if possible, can we obtain a graph $H'$ such that $G - \{q\} = KB(H')$? We show that the general question has a "no" for answer. However, we prove that if $G$ has a vertex $q$ such that $d(q) = 2$, then $G-\{q\}$ is a biclique graph and we show how to obtain $H'$.
Adversarial Feature Desensitization
Venue: arXiv cs.LG 2022
Year: 2022

Neural networks are known to be vulnerable to adversarial attacks -- slight but carefully constructed perturbations of the inputs which can drastically impair the network's performance. Many defense methods have been proposed for improving robustness of deep networks by training them on adversarially perturbed inputs. However, these models often remain vulnerable to new types of attacks not seen during training, and even to slightly stronger versions of previously seen attacks. In this work, we propose a novel approach to adversarial robustness, which builds upon the insights from the domain adaptation field. Our method, called Adversarial Feature Desensitization (AFD), aims at learning features that are invariant towards adversarial perturbations of the inputs. This is achieved through a game where we learn features that are both predictive and robust (insensitive to adversarial attacks), i.e. cannot be used to discriminate between natural and adversarial data. Empirical results on several benchmarks demonstrate the effectiveness of the proposed approach against a wide range of attack types and attack strengths. Our code is available at https://github.com/BashivanLab/afd.
Axiomatizing recursion-free, regular monitors
Venue: arXiv cs.LO 2022
Year: 2022

Monitors are a key tool in the field of runtime verification, where they are used to verify system properties by analyzing execution traces generated by processes. Work on runtime monitoring carried out in a series of papers by Aceto et al.$~$has specified monitors using a variation on the regular fragment of Milner's CCS and studied two trace-based notions of equivalence over monitors, namely verdict and $ω$-verdict equivalence. This article is devoted to the study of the equational logic of monitors modulo those two notions of equivalence. It presents complete equational axiomatizations of verdict and $ω$-verdict equivalence for closed and open terms over recursion-free monitors. It is also shown that verdict equivalence has no finite equational axiomatization over open monitors when the set of actions is finite and contains at least two actions.
Analysis of Trade-offs in Fair Principal Component Analysis Based on Multi-objective Optimization
Venue: arXiv cs.LG 2022
Year: 2022

In dimensionality reduction problems, the adopted technique may produce disparities between the representation errors of different groups. For instance, in the projected space, a specific class can be better represented in comparison with another one. In some situations, this unfair result may introduce ethical concerns. Aiming at overcoming this inconvenience, a fairness measure can be considered when performing dimensionality reduction through Principal Component Analysis. However, a solution that increases fairness tends to increase the overall re-construction error. In this context, this paper proposes to address this trade-off by means of a multi-objective-based approach. For this purpose, we adopt a fairness measure associated with the disparity between the representation errors of different groups. Moreover, we investigate if the solution of a classical Principal Component Analysis can be used to find a fair projection. Numerical experiments attest that a fairer result can be achieved with a very small loss in the overall reconstruction error.
Sensorimotor Visual Perception on Embodied System Using Free Energy Principle
Venue: arXiv cs.NE 2022
Year: 2022

We propose an embodied system based on the free energy principle (FEP) for sensorimotor visual perception. We evaluated it in a character-recognition task using the MNIST dataset. Although the FEP has successfully described a rule that living things obey mathematically and claims that a biological system continues to change its internal models and behaviors to minimize the difference in predicting sensory input, it is not enough to model sensorimotor visual perception. An embodiment of the system is the key to achieving sensorimotor visual perception. The proposed embodied system is configured by a body and memory. The body has an ocular motor system controlling the direction of eye gaze, which means that the eye can only observe a small focused area of the environment. The memory is not photographic, but is a generative model implemented with a variational autoencoder that contains prior knowledge about the environment, and that knowledge is classified. By limiting body and memory abilities and operating according to the FEP, the embodied system repeatedly takes action to obtain the next sensory input based on various potentials of future sensory inputs. In the evaluation, the inference of the environment was represented as an approximate posterior distribution of characters (0 - 9). As the number of repetitions increased, the attention area moved continuously, gradually reducing the uncertainty of characters. Finally, the probability of the correct character became the highest among the characters. Changing the initial attention position provides a different final distribution, suggesting that the proposed system has a confirmation bias.
Towards control of opinion diversity by introducing zealots into a polarised social group
Venue: arXiv cs.SI 2022
Year: 2022

We explore a method to influence or even control the diversity of opinions within a polarised social group. We leverage the voter model in which users hold binary opinions and repeatedly update their beliefs based on others they connect with. Stubborn agents who never change their minds ("zealots") are also disseminated through the network, which is modelled by a connected graph. Building on earlier results, we provide a closed-form expression for the average opinion of the group at equilibrium. This leads us to a strategy to inject zealots into a polarised network in order to shift the average opinion towards any target value. We account for the possible presence of a backfire effect, which may lead the group to react negatively and reinforce its level of polarisation in response. Our results are supported by numerical experiments on synthetic data.
Balanced Allocation on Hypergraphs
Venue: arXiv cs.DS 2022
Year: 2022

We consider a variation of balls-into-bins which randomly allocates $m$ balls into $n$ bins. Following Godfrey's model (SODA, 2008), we assume that each ball $t$, $1\le t\le m$, comes with a hypergraph $\mathcal{H}^{(t)}=\{B_1,B_2,\ldots,B_{s_t}\}$, and each edge $B\in\mathcal{H}^{(t)}$ contains at least a logarithmic number of bins. Given $d\ge 2$, our $d$-choice algorithm chooses an edge $B\in \mathcal{H}^{(t)}$, uniformly at random, and then chooses a set $D$ of $d$ random bins from the selected edge $B$. The ball is allocated to a least-loaded bin from $D$, with ties are broken randomly. We prove that if the hypergraphs $\mathcal{H}^{(1)},\ldots, \mathcal{H}^{(m)}$ satisfy a \emph{balancedness} condition and have low \emph{pair visibility}, then after allocating $m=Θ(n)$ balls, the maximum number of balls at any bin, called the \emph{maximum load}, is at most $\log_d\log n+O(1)$, with high probability. The balancedness condition enforces that bins appear almost uniformly within the hyperedges of $\mathcal{H}^{(t)}$, $1\le t\le m$, while the pair visibility condition measures how frequently a pair of bins is chosen during the allocation of balls. Moreover, we establish a lower bound for the maximum load attained by the balanced allocation for a sequence of hypergraphs in terms of pair visibility, showing the relevance of the visibility parameter to the maximum load. In Godfrey's model, each ball is forced to probe all bins in a randomly selected hyperedge and the ball is then allocated in a least-loaded bin. Godfrey showed that if each $\mathcal{H}^{(t)}$, $1\le t\le m$, is balanced and $m=O(n)$, then the maximum load is at most one, with high probability. However, we apply the power of $d$ choices paradigm, and only query the load information of $d$ random bins per ball, while achieving very slow growth in the maximum load.
ForMIC: Foraging via Multiagent RL with Implicit Communication
Venue: arXiv cs.RO 2022
Year: 2022

Multi-agent foraging (MAF) involves distributing a team of agents to search an environment and extract resources from it. Nature provides several examples of highly effective foragers, where individuals within the foraging collective use biological markers (e.g., pheromones) to communicate critical information to others via the environment. In this work, we propose ForMIC, a distributed reinforcement learning MAF approach that endows agents with implicit communication abilities via their shared environment. However, learning efficient policies with stigmergic interactions is highly nontrivial, since agents need to perform well to send each other useful signals, but also need to sense others' signals to perform well. In this work, we develop several key learning techniques for training policies with stigmergic interactions, where such a circular dependency is present. By relying on clever curriculum learning design, action filtering, and the introduction of non-learning agents to increase the agent density at training time at low computational cost, we develop a minimal learning framework that leads to the stable training of efficient stigmergic policies. We present simulation results which demonstrate that our learned policy outperforms existing state-of-the-art MAF algorithms in a set of experiments that vary team size, number and placement of resources, and key environmental dynamics not seen at training time.
Precise expressions for random projections: Low-rank approximation and randomized Newton
Venue: arXiv cs.LG 2022
Year: 2022

It is often desirable to reduce the dimensionality of a large dataset by projecting it onto a low-dimensional subspace. Matrix sketching has emerged as a powerful technique for performing such dimensionality reduction very efficiently. Even though there is an extensive literature on the worst-case performance of sketching, existing guarantees are typically very different from what is observed in practice. We exploit recent developments in the spectral analysis of random matrices to develop novel techniques that provide provably accurate expressions for the expected value of random projection matrices obtained via sketching. These expressions can be used to characterize the performance of dimensionality reduction in a variety of common machine learning tasks, ranging from low-rank approximation to iterative stochastic optimization. Our results apply to several popular sketching methods, including Gaussian and Rademacher sketches, and they enable precise analysis of these methods in terms of spectral properties of the data. Empirical results show that the expressions we derive reflect the practical performance of these sketching methods, down to lower-order effects and even constant factors.
On morphisms preserving palindromic richness
Venue: arXiv cs.FL 2022
Year: 2022

It is known that each word of length $n$ contains at most $n+1$ distinct palindromes. A finite rich word is a word with maximal number of palindromic factors. The definition of palindromic richness can be naturally extended to infinite words. Sturmian words and Rote complementary symmetric sequences form two classes of binary rich words, while episturmian words and words coding symmetric $d$-interval exchange transformations give us other examples on larger alphabets. In this paper we look for morphisms of the free monoid, which allow us to construct new rich words from already known rich words. We focus on morphisms in Class $P_{ret}$. This class contains morphisms injective on the alphabet and satisfying a particular palindromicity property: for every morphism $φ$ in the class there exists a palindrome $w$ such that $φ(a)w$ is a first complete return word to $w$ for each letter $a$. We characterize $P_{ret}$ morphisms which preserve richness over a binary alphabet. We also study marked $P_{ret}$ morphisms acting on alphabets with more letters. In particular we show that every Arnoux-Rauzy morphism is conjugated to a morphism in Class $P_{ret}$ and that it preserves richness.
Fanoos: Multi-Resolution, Multi-Strength, Interactive Explanations for Learned Systems
Venue: arXiv cs.AI 2022
Year: 2022

Machine learning is becoming increasingly important to control the behavior of safety and financially critical components in sophisticated environments, where the inability to understand learned components in general, and neural nets in particular, poses serious obstacles to their adoption. Explainability and interpretability methods for learned systems have gained considerable academic attention, but the focus of current approaches on only one aspect of explanation, at a fixed level of abstraction, and limited if any formal guarantees, prevents those explanations from being digestible by the relevant stakeholders (e.g., end users, certification authorities, engineers) with their diverse backgrounds and situation-specific needs. We introduce Fanoos, a framework for combining formal verification techniques, heuristic search, and user interaction to explore explanations at the desired level of granularity and fidelity. We demonstrate the ability of Fanoos to produce and adjust the abstractness of explanations in response to user requests on a learned controller for an inverted double pendulum and on a learned CPU usage model.
Post-hoc Calibration of Neural Networks by g-Layers
Venue: arXiv cs.LG 2022
Year: 2022

Calibration of neural networks is a critical aspect to consider when incorporating machine learning models in real-world decision-making systems where the confidence of decisions are equally important as the decisions themselves. In recent years, there is a surge of research on neural network calibration and the majority of the works can be categorized into post-hoc calibration methods, defined as methods that learn an additional function to calibrate an already trained base network. In this work, we intend to understand the post-hoc calibration methods from a theoretical point of view. Especially, it is known that minimizing Negative Log-Likelihood (NLL) will lead to a calibrated network on the training set if the global optimum is attained (Bishop, 1994). Nevertheless, it is not clear learning an additional function in a post-hoc manner would lead to calibration in the theoretical sense. To this end, we prove that even though the base network ($f$) does not lead to the global optimum of NLL, by adding additional layers ($g$) and minimizing NLL by optimizing the parameters of $g$ one can obtain a calibrated network $g \circ f$. This not only provides a less stringent condition to obtain a calibrated network but also provides a theoretical justification of post-hoc calibration methods. Our experiments on various image classification benchmarks confirm the theory.
Multi-source Domain Adaptation via Weighted Joint Distributions Optimal Transport
Venue: arXiv cs.LG 2022
Year: 2022

The problem of domain adaptation on an unlabeled target dataset using knowledge from multiple labelled source datasets is becoming increasingly important. A key challenge is to design an approach that overcomes the covariate and target shift both among the sources, and between the source and target domains. In this paper, we address this problem from a new perspective: instead of looking for a latent representation invariant between source and target domains, we exploit the diversity of source distributions by tuning their weights to the target task at hand. Our method, named Weighted Joint Distribution Optimal Transport (WJDOT), aims at finding simultaneously an Optimal Transport-based alignment between the source and target distributions and a re-weighting of the sources distributions. We discuss the theoretical aspects of the method and propose a conceptually simple algorithm. Numerical experiments indicate that the proposed method achieves state-of-the-art performance on simulated and real-life datasets.