OpenRaiser/Intern-Atlas huggingface dataset:
Pricing Fresh Data
Venue: arXiv cs.NI 2021
Year: 2021

We introduce the concept of {\it fresh data trading}, in which a destination user requests, and pays for, fresh data updates from a source provider, and data freshness is captured by the {\it age of information} (AoI) metric. Keeping data fresh relies on frequent data updates by the source, which motivates the source to {\it price fresh data}. In this work, the destination incurs an age-related cost, modeled as a general increasing function of the AoI. The source designs a pricing mechanism to maximize its profit; the destination chooses a data update schedule to trade off its payments to the source and its age-related cost. Depending on different real-time applications and scenarios, we study both a predictable-deadline and an unpredictable-deadline models. The key challenge of designing the optimal pricing scheme lies in the destination's time-interdependent valuations, due to the nature of AoI and the infinite-dimensional and dynamic optimization. To this end, we consider three pricing schemes that exploit and understand the profitability of three different dimensions in designing pricing: a {\it time-dependent} pricing scheme, in which the price for each update depends on when it is requested; a {\it quantity-based} pricing scheme, in which the price of each update depends on how many updates have been previously requested; a {\it subscription-based} pricing scheme, in which the price for each update is flat-rate but the source charges an additional subscription fee. Our analysis reveals that the optimal subscription-based pricing maximizes the source's profit among all possible pricing schemes under both predictable deadline and unpredictable deadline models; the optimal quantity-based pricing scheme is only optimal with a predictable deadline; the time-dependent pricing scheme, under the unpredictable deadline, is asymptotically optimal under significant time discounting.
The Effect of Robo-taxi User Experience on User Acceptance: Field Test Data Analysis
Venue: arXiv cs.HC 2021
Year: 2021

With the advancement of self-driving technology, the commercialization of Robo-taxi services is just a matter of time. However, there is some skepticism regarding whether such taxi services will be successfully accepted by real customers due to perceived safety-related concerns; therefore, studies focused on user experience have become more crucial. Although many studies statistically analyze user experience data obtained by surveying individuals' perceptions of Robo-taxi or indirectly through simulators, there is a lack of research that statistically analyzes data obtained directly from actual Robo-taxi service experiences. Accordingly, based on the user experience data obtained by implementing a Robo-taxi service in the downtown of Seoul and Daejeon in South Korea, this study quantitatively analyzes the effect of user experience on user acceptance through structural equation modeling and path analysis. We also obtained balanced and highly valid insights by reanalyzing meaningful causal relationships obtained through statistical models based on in-depth interview results. Results revealed that the experience of the traveling stage had the greatest effect on user acceptance, and the cutting edge of the service and apprehension of technology were emotions that had a great effect on user acceptance. Based on these findings, we suggest guidelines for the design and marketing of future Robo-taxi services.
Deep Feature Space: A Geometrical Perspective
Venue: arXiv cs.CV 2021
Year: 2021

One of the most prominent attributes of Neural Networks (NNs) constitutes their capability of learning to extract robust and descriptive features from high dimensional data, like images. Hence, such an ability renders their exploitation as feature extractors particularly frequent in an abundant of modern reasoning systems. Their application scope mainly includes complex cascade tasks, like multi-modal recognition and deep Reinforcement Learning (RL). However, NNs induce implicit biases that are difficult to avoid or to deal with and are not met in traditional image descriptors. Moreover, the lack of knowledge for describing the intra-layer properties -- and thus their general behavior -- restricts the further applicability of the extracted features. With the paper at hand, a novel way of visualizing and understanding the vector space before the NNs' output layer is presented, aiming to enlighten the deep feature vectors' properties under classification tasks. Main attention is paid to the nature of overfitting in the feature space and its adverse effect on further exploitation. We present the findings that can be derived from our model's formulation, and we evaluate them on realistic recognition scenarios, proving its prominence by improving the obtained results.
Enforcing Almost-Sure Reachability in POMDPs
Venue: arXiv cs.AI 2021
Year: 2021

Partially-Observable Markov Decision Processes (POMDPs) are a well-known stochastic model for sequential decision making under limited information. We consider the EXPTIME-hard problem of synthesising policies that almost-surely reach some goal state without ever visiting a bad state. In particular, we are interested in computing the winning region, that is, the set of system configurations from which a policy exists that satisfies the reachability specification. A direct application of such a winning region is the safe exploration of POMDPs by, for instance, restricting the behavior of a reinforcement learning agent to the region. We present two algorithms: A novel SAT-based iterative approach and a decision-diagram based alternative. The empirical evaluation demonstrates the feasibility and efficacy of the approaches.
Future Urban Scenes Generation Through Vehicles Synthesis
Venue: arXiv cs.CV 2021
Year: 2021

In this work we propose a deep learning pipeline to predict the visual future appearance of an urban scene. Despite recent advances, generating the entire scene in an end-to-end fashion is still far from being achieved. Instead, here we follow a two stages approach, where interpretable information is included in the loop and each actor is modelled independently. We leverage a per-object novel view synthesis paradigm; i.e. generating a synthetic representation of an object undergoing a geometrical roto-translation in the 3D space. Our model can be easily conditioned with constraints (e.g. input trajectories) provided by state-of-the-art tracking methods or by the user itself. This allows us to generate a set of diverse realistic futures starting from the same input in a multi-modal fashion. We visually and quantitatively show the superiority of this approach over traditional end-to-end scene-generation methods on CityFlow, a challenging real world dataset.
Distributed Linearly Separable Computation
Venue: arXiv cs.IT 2021
Year: 2021

This paper formulates a distributed computation problem, where a master asks $N$ distributed workers to compute a linearly separable function. The task function can be expressed as $K_c$ linear combinations of $K$ messages, where each message is a function of one dataset. Our objective is to find the optimal tradeoff between the computation cost (number of uncoded datasets assigned to each worker) and the communication cost (number of symbols the master must download), such that from the answers of any $N_r$ out of $N$ workers the master can recover the task function with high probability, where the coefficients of the $K_c$ linear combinations are uniformly i.i.d. over some large enough finite field. The formulated problem can be seen as a generalized version of some existing problems, such as distributed gradient coding and distributed linear transform. In this paper, we consider the specific case where the computation cost is minimum, and propose novel achievability schemes and converse bounds for the optimal communication cost. Achievability and converse bounds coincide for some system parameters; when they do not match, we prove that the achievable distributed computing scheme is optimal under the constraint of a widely used `cyclic assignment' scheme on the datasets. Our results also show that when $K = N$, with the same communication cost as the optimal distributed gradient coding scheme proposed by Tandon et al. from which the master recovers one linear combination of $K$ messages, our proposed scheme can let the master recover any additional $N_r - 1$ independent linear combinations of messages with high probability.
Multi-Layer Bilinear Generalized Approximate Message Passing
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we extend the bilinear generalized approximate message passing (BiG-AMP) approach, originally proposed for high-dimensional generalized bilinear regression, to the multi-layer case for the handling of cascaded problem such as matrix-factorization problem arising in relay communication among others. Assuming statistically independent matrix entries with known priors, the new algorithm called ML-BiGAMP could approximate the general sum-product loopy belief propagation (LBP) in the high-dimensional limit enjoying a substantial reduction in computational complexity. We demonstrate that, in large system limit, the asymptotic MSE performance of ML-BiGAMP could be fully characterized via a set of simple one-dimensional equations termed state evolution (SE). We establish that the asymptotic MSE predicted by ML-BiGAMP' SE matches perfectly the exact MMSE predicted by the replica method, which is well known to be Bayes-optimal but infeasible in practice. This consistency indicates that the ML-BiGAMP may still retain the same Bayes-optimal performance as the MMSE estimator in high-dimensional applications, although ML-BiGAMP's computational burden is far lower. As an illustrative example of the general ML-BiGAMP, we provide a detector design that could estimate the channel fading and the data symbols jointly with high precision for the two-hop amplify-and-forward relay communication systems.
GSoFa: Scalable Sparse Symbolic LU Factorization on GPUs
Venue: arXiv cs.DC 2021
Year: 2021

Decomposing matrix A into a lower matrix L and an upper matrix U, which is also known as LU decomposition, is an essential operation in numerical linear algebra. For a sparse matrix, LU decomposition often introduces more nonzero entries in the L and U factors than in the original matrix. A symbolic factorization step is needed to identify the nonzero structures of L and U matrices. Attracted by the enormous potentials of the Graphics Processing Units (GPUs), an array of efforts have surged to deploy various LU factorization steps except for the symbolic factorization, to the best of our knowledge, on GPUs. This paper introduces gSoFa, the first GPU-based Symbolic factorization design with the following three optimizations to enable scalable LU symbolic factorization for nonsymmetric pattern sparse matrices on GPUs. First, we introduce a novel fine-grained parallel symbolic factorization algorithm that is well suited for the Single Instruction Multiple Thread (SIMT) architecture of GPUs. Second, we tailor supernode detection into a SIMT friendly process and strive to balance the workload, minimize the communication and saturate the GPU computing resources during supernode detection. Third, we introduce a three-pronged optimization to reduce the excessive space consumption problem faced by multi-source concurrent symbolic factorization. Taken together, gSoFa achieves up to 31x speedup from 1 to 44 Summit nodes (6 to 264 GPUs) and outperforms the state-of-the-art CPU project, on average, by 5x. Notably, gSoFa also achieves {up to 47%} of the peak memory throughput of a V100 GPU in Summit.
Hardware Acceleration of Sparse and Irregular Tensor Computations of ML Models: A Survey and Insights
Venue: arXiv cs.AR 2021
Year: 2021

Machine learning (ML) models are widely used in many important domains. For efficiently processing these computational- and memory-intensive applications, tensors of these over-parameterized models are compressed by leveraging sparsity, size reduction, and quantization of tensors. Unstructured sparsity and tensors with varying dimensions yield irregular computation, communication, and memory access patterns; processing them on hardware accelerators in a conventional manner does not inherently leverage acceleration opportunities. This paper provides a comprehensive survey on the efficient execution of sparse and irregular tensor computations of ML models on hardware accelerators. In particular, it discusses enhancement modules in the architecture design and the software support; categorizes different hardware designs and acceleration techniques and analyzes them in terms of hardware and execution costs; analyzes achievable accelerations for recent DNNs; highlights further opportunities in terms of hardware/software/model co-design optimizations (inter/intra-module). The takeaways from this paper include: understanding the key challenges in accelerating sparse, irregular-shaped, and quantized tensors; understanding enhancements in accelerator systems for supporting their efficient computations; analyzing trade-offs in opting for a specific design choice for encoding, storing, extracting, communicating, computing, and load-balancing the non-zeros; understanding how structured sparsity can improve storage efficiency and balance computations; understanding how to compile and map models with sparse tensors on the accelerators; understanding recent design trends for efficient accelerations and further opportunities.
Deep Learning for Neuroimaging-based Diagnosis and Rehabilitation of Autism Spectrum Disorder: A Review
Venue: arXiv cs.LG 2021
Year: 2021

Accurate diagnosis of Autism Spectrum Disorder (ASD) followed by effective rehabilitation is essential for the management of this disorder. Artificial intelligence (AI) techniques can aid physicians to apply automatic diagnosis and rehabilitation procedures. AI techniques comprise traditional machine learning (ML) approaches and deep learning (DL) techniques. Conventional ML methods employ various feature extraction and classification techniques, but in DL, the process of feature extraction and classification is accomplished intelligently and integrally. DL methods for diagnosis of ASD have been focused on neuroimaging-based approaches. Neuroimaging techniques are non-invasive disease markers potentially useful for ASD diagnosis. Structural and functional neuroimaging techniques provide physicians substantial information about the structure (anatomy and structural connectivity) and function (activity and functional connectivity) of the brain. Due to the intricate structure and function of the brain, proposing optimum procedures for ASD diagnosis with neuroimaging data without exploiting powerful AI techniques like DL may be challenging. In this paper, studies conducted with the aid of DL networks to distinguish ASD are investigated. Rehabilitation tools provided for supporting ASD patients utilizing DL networks are also assessed. Finally, we will present important challenges in the automated detection and rehabilitation of ASD and propose some future works.
Uncertainty Prediction for Deep Sequential Regression Using Meta Models
Venue: arXiv cs.LG 2021
Year: 2021

Generating high quality uncertainty estimates for sequential regression, particularly deep recurrent networks, remains a challenging and open problem. Existing approaches often make restrictive assumptions (such as stationarity) yet still perform poorly in practice, particularly in presence of real world non-stationary signals and drift. This paper describes a flexible method that can generate symmetric and asymmetric uncertainty estimates, makes no assumptions about stationarity, and outperforms competitive baselines on both drift and non drift scenarios. This work helps make sequential regression more effective and practical for use in real-world applications, and is a powerful new addition to the modeling toolbox for sequential uncertainty quantification in general.
Detecting Ongoing Events Using Contextual Word and Sentence Embeddings
Venue: arXiv cs.CL 2021
Year: 2021

This paper introduces the Ongoing Event Detection (OED) task, which is a specific Event Detection task where the goal is to detect ongoing event mentions only, as opposed to historical, future, hypothetical, or other forms or events that are neither fresh nor current. Any application that needs to extract structured information about ongoing events from unstructured texts can take advantage of an OED system. The main contribution of this paper are the following: (1) it introduces the OED task along with a dataset manually labeled for the task; (2) it presents the design and implementation of an RNN model for the task that uses BERT embeddings to define contextual word and contextual sentence embeddings as attributes, which to the best of our knowledge were never used before for detecting ongoing events in news; (3) it presents an extensive empirical evaluation that includes (i) the exploration of different architectures and hyperparameters, (ii) an ablation test to study the impact of each attribute, and (iii) a comparison with a replication of a state-of-the-art model. The results offer several insights into the importance of contextual embeddings and indicate that the proposed approach is effective in the OED task, outperforming the baseline models.
Persistent Neurons
Venue: arXiv cs.LG 2021
Year: 2021

Neural networks (NN)-based learning algorithms are strongly affected by the choices of initialization and data distribution. Different optimization strategies have been proposed for improving the learning trajectory and finding a better optima. However, designing improved optimization strategies is a difficult task under the conventional landscape view. Here, we propose persistent neurons, a trajectory-based strategy that optimizes the learning task using information from previous converged solutions. More precisely, we utilize the end of trajectories and let the parameters explore new landscapes by penalizing the model from converging to the previous solutions under the same initialization. Persistent neurons can be regarded as a stochastic gradient method with informed bias where individual updates are corrupted by deterministic error terms. Specifically, we show that persistent neurons, under certain data distribution, is able to converge to more optimal solutions while initializations under popular framework find bad local minima. We further demonstrate that persistent neurons helps improve the model's performance under both good and poor initializations. We evaluate the full and partial persistent model and show it can be used to boost the performance on a range of NN structures, such as AlexNet and residual neural network (ResNet).
Flexibility in an asymmetric system with prolonged service time at non-dedicated servers
Venue: arXiv cs.PF 2021
Year: 2021

The prolonged service time at non-dedicated servers has been observed in [1]. Motivated by such real problems, we propose a stylized model which characterizes the feature of the prolonged service time at non-dedicated servers in an asymmetric system. We study the independent system, the full flexibility system and the partial flexibility system when the occupation rate of the system, the degree of the prolonged service time and the degree of the asymmetry are allowed to change. We show that under certain circumstances, the partial flexibility scheme outperforms the full flexibility system and the independent system in such a model. Our results also provide instructions on how to introduce flexibility when the service time at non-dedicated servers is prolonged in an asymmetric system.
Domain Adaptation without Source Data
Venue: arXiv cs.CV 2021
Year: 2021

Domain adaptation assumes that samples from source and target domains are freely accessible during a training phase. However, such an assumption is rarely plausible in the real-world and possibly causes data-privacy issues, especially when the label of the source domain can be a sensitive attribute as an identifier. To avoid accessing source data that may contain sensitive information, we introduce Source data-Free Domain Adaptation (SFDA). Our key idea is to leverage a pre-trained model from the source domain and progressively update the target model in a self-learning manner. We observe that target samples with lower self-entropy measured by the pre-trained source model are more likely to be classified correctly. From this, we select the reliable samples with the self-entropy criterion and define these as class prototypes. We then assign pseudo labels for every target sample based on the similarity score with class prototypes. Furthermore, to reduce the uncertainty from the pseudo labeling process, we propose set-to-set distance-based filtering which does not require any tunable hyperparameters. Finally, we train the target model with the filtered pseudo labels with regularization from the pre-trained source model. Surprisingly, without direct usage of labeled source samples, our PrDA outperforms conventional domain adaptation methods on benchmark datasets. Our code is publicly available at https://github.com/youngryan1993/SFDA-SourceFreeDA
The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
Venue: arXiv cs.CC 2021
Year: 2021

Convex relaxations have been instrumental in solvability of constraint satisfaction problems (CSPs), as well as in the three different generalisations of CSPs: valued CSPs, infinite-domain CSPs, and most recently promise CSPs. In this work, we extend an existing tractability result to the three generalisations of CSPs combined: We give a sufficient condition for the combined basic linear programming and affine integer programming relaxation for exact solvability of promise valued CSPs over infinite-domains. This extends a result of Brakensiek and Guruswami [SODA'20] for promise (non-valued) CSPs (on finite domains).
Expected Eligibility Traces
Venue: arXiv cs.LG 2021
Year: 2021

The question of how to determine which states and actions are responsible for a certain outcome is known as the credit assignment problem and remains a central research question in reinforcement learning and artificial intelligence. Eligibility traces enable efficient credit assignment to the recent sequence of states and actions experienced by the agent, but not to counterfactual sequences that could also have led to the current state. In this work, we introduce expected eligibility traces. Expected traces allow, with a single update, to update states and actions that could have preceded the current state, even if they did not do so on this occasion. We discuss when expected traces provide benefits over classic (instantaneous) traces in temporal-difference learning, and show that sometimes substantial improvements can be attained. We provide a way to smoothly interpolate between instantaneous and expected traces by a mechanism similar to bootstrapping, which ensures that the resulting algorithm is a strict generalisation of TD($λ$). Finally, we discuss possible extensions and connections to related ideas, such as successor features.