OpenRaiser/Intern-Atlas huggingface dataset:
VoiceGrad: Non-Parallel Any-to-Many Voice Conversion with Annealed Langevin Dynamics
Venue: arXiv cs.SD 2024
Year: 2024

In this paper, we propose a non-parallel any-to-many voice conversion (VC) method termed VoiceGrad. Inspired by WaveGrad, a recently introduced novel waveform generation method, VoiceGrad is based upon the concepts of score matching and Langevin dynamics. It uses weighted denoising score matching to train a score approximator, a fully convolutional network with a U-Net structure designed to predict the gradient of the log density of the speech feature sequences of multiple speakers, and performs VC by using annealed Langevin dynamics to iteratively update an input feature sequence towards the nearest stationary point of the target distribution based on the trained score approximator network. Thanks to the nature of this concept, VoiceGrad enables any-to-many VC, a VC scenario in which the speaker of input speech can be arbitrary, and allows for non-parallel training, which requires no parallel utterances or transcriptions.
Nonstationary Reinforcement Learning with Linear Function Approximation
Venue: arXiv cs.LG 2024
Year: 2024

We consider reinforcement learning (RL) in episodic Markov decision processes (MDPs) with linear function approximation under drifting environment. Specifically, both the reward and state transition functions can evolve over time but their total variations do not exceed a $\textit{variation budget}$. We first develop $\texttt{LSVI-UCB-Restart}$ algorithm, an optimistic modification of least-squares value iteration with periodic restart, and bound its dynamic regret when variation budgets are known. Then we propose a parameter-free algorithm $\texttt{Ada-LSVI-UCB-Restart}$ that extends to unknown variation budgets. We also derive the first minimax dynamic regret lower bound for nonstationary linear MDPs and as a byproduct establish a minimax regret lower bound for linear MDPs unsolved by Jin et al. (2020). Finally, we provide numerical experiments to demonstrate the effectiveness of our proposed algorithms.
Incremental Processing in the Age of Non-Incremental Encoders: An Empirical Assessment of Bidirectional Models for Incremental NLU
Venue: arXiv cs.CL 2024
Year: 2024

While humans process language incrementally, the best language encoders currently used in NLP do not. Both bidirectional LSTMs and Transformers assume that the sequence that is to be encoded is available in full, to be processed either forwards and backwards (BiLSTMs) or as a whole (Transformers). We investigate how they behave under incremental interfaces, when partial output must be provided based on partial input seen up to a certain time step, which may happen in interactive systems. We test five models on various NLU datasets and compare their performance using three incremental evaluation metrics. The results support the possibility of using bidirectional encoders in incremental mode while retaining most of their non-incremental quality. The "omni-directional" BERT model, which achieves better non-incremental performance, is impacted more by the incremental access. This can be alleviated by adapting the training regime (truncated training), or the testing procedure, by delaying the output until some right context is available or by incorporating hypothetical right contexts generated by a language model like GPT-2.
Computability of the Zero-Error Capacity of Noisy Channels
Venue: arXiv cs.IT 2024
Year: 2024

Zero-error capacity plays an important role in a whole range of operational tasks, in addition to the fact that it is necessary for practical applications. Due to the importance of zero-error capacity, it is necessary to investigate its algorithmic computability, as there has been no known closed formula for the zero-error capacity until now. We show that the zero-error capacity of noisy channels is not Banach-Mazur computable and therefore not Borel-Turing computable. We also investigate the relationship between the zero-error capacity of discrete memoryless channels, the Shannon capacity of graphs, and Ahlswede's characterization of the zero-error-capacity of noisy channels with respect to the maximum error capacity of 0-1-arbitrarily varying channels. We will show that important questions regarding semi-decidability are equivalent for all three capacities. So far, the Borel-Turing computability of the Shannon capacity of graphs is completely open. This is why the coupling with semi-decidability is interesting.
Distributed Representations of Entities in Open-World Knowledge Graphs
Venue: arXiv cs.LG 2024
Year: 2024

Graph neural network (GNN)-based methods have demonstrated remarkable performance in various knowledge graph (KG) tasks. However, most existing approaches rely on observing all entities during training, posing a challenge in real-world knowledge graphs where new entities emerge frequently. To address this limitation, we introduce Decentralized Attention Network (DAN). DAN leverages neighbor context as the query vector to score the neighbors of an entity, thereby distributing the entity semantics only among its neighbor embeddings. To effectively train a DAN, we introduce self-distillation, a technique that guides the network in generating desired representations. Theoretical analysis validates the effectiveness of our approach. We implement an end-to-end framework and conduct extensive experiments to evaluate our method, showcasing competitive performance on conventional entity alignment and entity prediction tasks. Furthermore, our method significantly outperforms existing methods in open-world settings.
Restless reachability problems in temporal graphs
Venue: arXiv cs.DS 2024
Year: 2024

We study a family of reachability problems under waiting-time restrictions in temporal and vertex-colored temporal graphs. Given a temporal graph and a set of source vertices, we find the set of vertices that are reachable from a source via a time-respecting path, where the difference in timestamps between consecutive edges is at most a resting time. Given a vertex-colored temporal graph and a multiset query of colors, we find the set of vertices reachable from a source via a time-respecting path such that the vertex colors of the path agree with the multiset query and the difference in timestamps between consecutive edges is at most a resting time. These kind of problems have applications in understanding the spread of a disease in a network, tracing contacts in epidemic outbreaks, finding signaling pathways in the brain network, and recommending tours for tourists, among other. We present an algebraic algorithmic framework based on constrained multi\-linear sieving for solving the restless reachability problems we propose. In particular, parameterized by the length $k$ of a path sought, we show that the proposed problems can be solved in $O(2^k k m Δ)$ time and $O(n Δ)$ space, where $n$ is the number of vertices, $m$ the number of edges, and $Δ$ the maximum resting time of an input temporal graph. In addition, we prove that our algorithms for the restless reachability problems in vertex-colored temporal graphs are optimal under plausible complexity-theoretic assumptions. Finally, with an open-source implementation, we demonstrate that our algorithm scales to large graphs with up to one billion temporal edges, despite the problems being NP-hard. Specifically, we present extensive experiments to evaluate our scalability claims both on synthetic and real-world graphs. Our implementation is efficiently engineered and highly optimized.
Structure-based Optical Logics Without Using Transistors
Venue: arXiv cs.ET 2024
Year: 2024

The commercialization of transistors capable of both switching and amplification in 1960 resulted in the development of second-generation computers, which resulted in the miniaturization and lightening while accelerating the reduction and development of production costs. However, the self-resistance and the resistance used in conjunction with semiconductors, which are the basic principles of computers, generate a lot of heat, which results in semiconductor obsolescence, and limits the computation speed (clock rate). In implementing logic operation, this paper proposes the concept of Structure-based Computer which can implement NOT gate made of semiconductor transistor only by Structure-based twist of cable without resistance. In Structure-based computer, the theory of 'inverse signal pair' of digital signals was introduced so that it could operate in a different way than semiconductor-based transistors. In this paper, we propose a new hardware called Structure-based computer that can solve various problems in semiconductor computers only with the wiring structure of the conductor itself, not with the silicon-based semiconductor. Furthermore, we propose a deep-priority exploration-based simulation method that can easily implement and test complex Structure-based computer circuits. Furthermore, this paper suggests a mechanism to implement optical computers currently under development and research based on structures rather than devices.
Playing With Friends -- The Importance of Social Play During the COVID-19 Pandemic
Venue: arXiv cs.HC 2024
Year: 2024

In early 2020, the virus SARS-CoV-2 evolved into a new pandemic, forcing governments worldwide to establish social distancing measures. Consequently, people had to switch to online media, such as social networks or videotelephony, to keep in touch with friends and family. In this context, online games, combining entertainment with social interactions, also experienced a notable growth. In our work, we focused on the potential of games as a replacement for social contacts in the COVID-19 crisis. Our online survey results indicate that the value of games for social needs depends on individual gaming habits. Participants playing mostly multiplayer games increased their playtime and mentioned social play as a key motivator. Contrarily, non-players were not motivated to add games as communication channels. We deduce that such crises mainly catalyze existing gaming habits.
Fast Biconnectivity Restoration in Multi-Robot Systems for Robust Communication Maintenance
Venue: arXiv cs.RO 2024
Year: 2024

Maintaining a robust communication network plays an important role in the success of a multi-robot team jointly performing an optimization task. A key characteristic of a robust multi-robot system is the ability to repair the communication topology itself in the case of robot failure. In this paper, we focus on the Fast Biconnectivity Restoration (FBR) problem, which aims to repair a connected network to make it biconnected as fast as possible, where a biconnected network is a communication topology that cannot be disconnected by removing one node. We develop a Quadratically Constrained Program (QCP) formulation of the FBR problem, which provides a way to optimally solve the problem. We also propose an approximation algorithm for the FBR problem based on graph theory. By conducting empirical studies, we demonstrate that our proposed approximation algorithm performs close to the optimal while significantly outperforming the existing solutions.
Optimal Control-Based Baseline for Guided Exploration in Policy Gradient Methods
Venue: arXiv cs.LG 2024
Year: 2024

In this paper, a novel optimal control-based baseline function is presented for the policy gradient method in deep reinforcement learning (RL). The baseline is obtained by computing the value function of an optimal control problem, which is formed to be closely associated with the RL task. In contrast to the traditional baseline aimed at variance reduction of policy gradient estimates, our work utilizes the optimal control value function to introduce a novel aspect to the role of baseline -- providing guided exploration during policy learning. This aspect is less discussed in prior works. We validate our baseline on robot learning tasks, showing its effectiveness in guided exploration, particularly in sparse reward environments.
Combinatorial Bernoulli Factories
Venue: arXiv cs.DS 2024
Year: 2024

A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter $p \in [0,1]$ means the algorithm does not know $p$, but has sample access to independent draws of a Bernoulli random variable with mean equal to $p$. In this paper, we study the problem of Bernoulli factories for polytopes: given Bernoulli access to a vector $x\in P$ for a given polytope $P\subset [0,1]^n$, output a randomized vertex such that the expected value of the $i$-th coordinate is \emph{exactly} equal to $x_i$. For example, for the special case of the perfect matching polytope, one is given Bernoulli access to the entries of a doubly stochastic matrix $[x_{ij}]$ and asked to sample a matching such that the probability of each edge $(i,j)$ be present in the matching is exactly equal to $x_{ij}$. We show that a polytope $P$ admits a Bernoulli factory if and and only if $P$ is the intersection of $[0,1]^n$ with an affine subspace. Our construction is based on an algebraic formulation of the problem, involving identifying a family of Bernstein polynomials (one per vertex) that satisfy a certain algebraic identity on $P$. The main technical tool behind our construction is a connection between these polynomials and the geometry of zonotope tilings. We apply these results to construct an explicit factory for the perfect matching polytope. The resulting factory is deeply connected to the combinatorial enumeration of arborescences and may be of independent interest. For the $k$-uniform matroid polytope, we recover a sampling procedure known in statistics as Sampford sampling.
Proposal of Automatic Offloading Method in Mixed Offloading Destination Environment
Venue: arXiv cs.DC 2024
Year: 2024

When using heterogeneous hardware, barriers of technical skills such as OpenMP, CUDA and OpenCL are high. Based on that, I have proposed environment-adaptive software that enables automatic conversion, configuration. However, including existing technologies, there has been no research to properly and automatically offload the mixed offloading destination environment such as GPU, FPGA and many core CPU. In this paper, as a new element of environment-adaptive software, I study a method for offloading applications properly and automatically in the environment where the offloading destination is mixed with GPU, FPGA and many core CPU. Y. Yamato, "Proposal of Automatic Offloading Method in Mixed Offloading Destination Environment," 2020 Eighth International Symposium on Computing and Networking Workshops (CANDARW 2020), pp.460-464, DOI: 10.1109/CANDARW51189.2020.00094, Nov. 2020. "(c) 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works."
Video Self-Stitching Graph Network for Temporal Action Localization
Venue: arXiv cs.CV 2024
Year: 2024

Temporal action localization (TAL) in videos is a challenging task, especially due to the large variation in action temporal scales. Short actions usually occupy a major proportion in the datasets, but tend to have the lowest performance. In this paper, we confront the challenge of short actions and propose a multi-level cross-scale solution dubbed as video self-stitching graph network (VSGN). We have two key components in VSGN: video self-stitching (VSS) and cross-scale graph pyramid network (xGPN). In VSS, we focus on a short period of a video and magnify it along the temporal dimension to obtain a larger scale. We stitch the original clip and its magnified counterpart in one input sequence to take advantage of the complementary properties of both scales. The xGPN component further exploits the cross-scale correlations by a pyramid of cross-scale graph networks, each containing a hybrid module to aggregate features from across scales as well as within the same scale. Our VSGN not only enhances the feature representations, but also generates more positive anchors for short actions and more short training samples. Experiments demonstrate that VSGN obviously improves the localization performance of short actions as well as achieving the state-of-the-art overall performance on THUMOS-14 and ActivityNet-v1.3.
Creativity of Deep Learning: Conceptualization and Assessment
Venue: arXiv cs.AI 2024
Year: 2024

While the potential of deep learning (DL) for automating simple tasks is already well explored, recent research has started investigating the use of deep learning for creative design, both for complete artifact creation and supporting humans in the creation process. In this paper, we use insights from computational creativity to conceptualize and assess current applications of generative deep learning in creative domains identified in a literature review. We highlight parallels between current systems and different models of human creativity as well as their shortcomings. While deep learning yields results of high value, such as high-quality images, their novelty is typically limited due to multiple reasons such as being tied to a conceptual space defined by training data. Current DL methods also do not allow for changes in the internal problem representation, and they lack the capability to identify connections across highly different domains, both of which are seen as major drivers of human creativity.
Bid-aggregation based clearing of day-ahead electricity markets
Venue: arXiv cs.GT 2024
Year: 2024

In this work we propose a heuristic clearing method of day-ahead electricity markets. In the first part of the process, a computationally less demanding problem is solved using an approximation of the cumulative demand and supply curves, which are derived via the aggregation of simple bids. Based on the outcome of this problem, estimated ranges for the clearing prices of individual periods are determined. In the final step, the clearing for the original bid set is solved, taking into account the price ranges determined previously as constraints. Adding such constraints reduces the feasibility region of the clearing problem. By removing simple bids whose acceptance or rejection is already determined by the assumed price range constraints, the size of the problem is also significantly reduced. Via simple examples, we show that due to the possible paradox rejection of block bids the proposed bid-aggregation based approach may result in a suboptimal solution or in an infeasible problem, but we also point out that these pitfalls of the algorithm may be avoided by using different aggregation patterns. We propose to construct multiple different aggregation patterns and to use parallel computing to enhance the performance of the algorithm. We test the proposed approach on setups of various problem sizes, and conclude that in the case of parallel computing with 4 threads a high success rate and a significant gain in computational speed may be achieved.
Exploiting Intrinsic Kinematic Null Space for Supernumerary Robotic Limbs Control
Venue: arXiv cs.RO 2024
Year: 2024

Supernumerary robotic limbs (SRLs) gained increasing interest in the last years for their applicability as healthcare and assistive technologies. These devices can either support or augment human sensorimotor capabilities, allowing users to complete tasks that are more complex than those feasible for their natural limbs. However, for a successful coordination between natural and artificial limbs, intuitiveness of interaction and perception of autonomy are key enabling features, especially for people suffering from motor disorders and impairments. The development of suitable human-robot interfaces is thus fundamental to foster the adoption of SRLs. With this work, we describe how to control an extra degree of freedom by taking advantage of what we defined the Intrinsic Kinematic Null Space, i.e. the redundancy of the human kinematic chain involved in the ongoing task. Obtained results demonstrated that the proposed control strategy is effective for performing complex tasks with a supernumerary robotic finger, and that practice improves users' control ability.
Periocular Embedding Learning with Consistent Knowledge Distillation from Face
Venue: arXiv cs.CV 2024
Year: 2024

Periocular biometric, the peripheral area of the ocular, is a collaborative alternative to the face, especially when the face is occluded or masked. However, in practice, sole periocular biometric capture the least salient facial features, thereby lacking discriminative information, particularly in wild environments. To address these problems, we transfer discriminatory information from the face to support the training of a periocular network by using knowledge distillation. Specifically, we leverage face images for periocular embedding learning, but periocular alone is utilized for identity identification or verification. To enhance periocular embeddings by face effectively, we proposeConsistent Knowledge Distillation (CKD) that imposes consistency between face and periocular networks across prediction and feature layers. We find that imposing consistency at the prediction layer enables (1) extraction of global discriminative relationship information from face images and (2) effective transfer of the information from the face network to the periocular network. Particularly, consistency regularizes the prediction units to extract and store profound inter-class relationship information of face images. (3) The feature layer consistency, on the other hand, makes the periocular features robust against identity-irrelevant attributes. Overall, CKD empowers the sole periocular network to produce robust discriminative embeddings for periocular recognition in the wild. We theoretically and empirically validate the core principles of the distillation mechanism in CKD, discovering that CKD is equivalent to label smoothing with a novel sparsity-oriented regularizer that helps the network prediction to capture the global discriminative relationship. Extensive experiments reveal that CKD achieves state-of-the-art results on standard periocular recognition benchmark datasets.
SpAtten: Efficient Sparse Attention Architecture with Cascade Token and Head Pruning
Venue: arXiv cs.AR 2024
Year: 2024

The attention mechanism is becoming increasingly popular in Natural Language Processing (NLP) applications, showing superior performance than convolutional and recurrent architectures. However, attention becomes the compution bottleneck because of its quadratic computational complexity to input length, complicated data movement and low arithmetic intensity. Moreover, existing NN accelerators mainly focus on optimizing convolutional or recurrent models, and cannot efficiently support attention. In this paper, we present SpAtten, an efficient algorithm-architecture co-design that leverages token sparsity, head sparsity, and quantization opportunities to reduce the attention computation and memory access. Inspired by the high redundancy of human languages, we propose the novel cascade token pruning to prune away unimportant tokens in the sentence. We also propose cascade head pruning to remove unessential heads. Cascade pruning is fundamentally different from weight pruning since there is no trainable weight in the attention mechanism, and the pruned tokens and heads are selected on the fly. To efficiently support them on hardware, we design a novel top-k engine to rank token and head importance scores with high throughput. Furthermore, we propose progressive quantization that first fetches MSBs only and performs the computation; if the confidence is low, it fetches LSBs and recomputes the attention outputs, trading computation for memory reduction. Extensive experiments on 30 benchmarks show that, on average, SpAtten reduces DRAM access by 10.0x with no accuracy loss, and achieves 1.6x, 3.0x, 162x, 347x speedup, and 1,4x, 3.2x, 1193x, 4059x energy savings over A3 accelerator, MNNFast accelerator, TITAN Xp GPU, Xeon CPU, respectively.