OpenRaiser/Intern-Atlas huggingface dataset:
Large Scale Generation of Labeled Type Data for Python
Venue: arXiv cs.PL 2022
Year: 2022

Recently, dynamically typed languages, such as Python, have gained unprecedented popularity. Although these languages alleviate the need for mandatory type annotations, types still play a critical role in program understanding and preventing runtime errors. An attractive option is to infer types automatically to get static guarantees without writing types. Existing inference techniques rely mostly on static typing tools such as PyType for direct type inference; more recently, neural type inference has been proposed. However, neural type inference is data hungry, and depends on collecting labeled data based on static typing. Such tools, however, are poor at inferring user defined types. Furthermore, type annotation by developers in these languages is quite sparse. In this work, we propose novel techniques for generating high quality types using 1) information retrieval techniques that work on well documented libraries to extract types and 2) usage patterns by analyzing a large repository of programs. Our results show that these techniques are more precise and address the weaknesses of static tools, and can be useful for generating a large labeled dataset for type inference by machine learning methods. F1 scores are 0.52-0.58 for our techniques, compared to static typing tools which are at 0.06, and we use them to generate over 37,000 types for over 700 modules.
A Joint Exponential Mechanism For Differentially Private Top-$k$
Venue: arXiv cs.CR 2022
Year: 2022

We present a differentially private algorithm for releasing the sequence of $k$ elements with the highest counts from a data domain of $d$ elements. The algorithm is a "joint" instance of the exponential mechanism, and its output space consists of all $O(d^k)$ length-$k$ sequences. Our main contribution is a method to sample this exponential mechanism in time $O(dk\log(k) + d\log(d))$ and space $O(dk)$. Experiments show that this approach outperforms existing pure differential privacy methods and improves upon even approximate differential privacy methods for moderate $k$.
Automatic Audio Captioning using Attention weighted Event based Embeddings
Venue: arXiv cs.SD 2022
Year: 2022

Automatic Audio Captioning (AAC) refers to the task of translating audio into a natural language that describes the audio events, source of the events and their relationships. The limited samples in AAC datasets at present, has set up a trend to incorporate transfer learning with Audio Event Detection (AED) as a parent task. Towards this direction, in this paper, we propose an encoder-decoder architecture with light-weight (i.e. with lesser learnable parameters) Bi-LSTM recurrent layers for AAC and compare the performance of two state-of-the-art pre-trained AED models as embedding extractors. Our results show that an efficient AED based embedding extractor combined with temporal attention and augmentation techniques is able to surpass existing literature with computationally intensive architectures. Further, we provide evidence of the ability of the non-uniform attention weighted encoding generated as a part of our model to facilitate the decoder glance over specific sections of the audio while generating each token.
On the Kolmogorov Complexity of Binary Classifiers
Venue: arXiv cs.CC 2022
Year: 2022

We provide tight upper and lower bounds on the expected minimum Kolmogorov complexity of binary classifiers that are consistent with labeled samples. The expected size is not more than complexity of the target concept plus the conditional entropy of the labels given the sample.
Better Algorithms for Online Bin Stretching via Computer Search
Venue: arXiv cs.DS 2022
Year: 2022

We present an algorithm for computing upper bounds for the Online Bin Stretching Problem with a small number of bins and the resulting upper bounds for 4, 5 and 6 bins. This both demonstrates the possibility of using computer search for upper bounds on a fundamentally real-valued online problem and improves upon the best bounds know so far, some of which have remained unchanged since 2001.
Competitive Algorithms and Reinforcement Learning for NOMA in IoT Networks
Venue: arXiv cs.NI 2022
Year: 2022

This paper studies the problem of massive Internet of things (IoT) access in beyond fifth generation (B5G) networks using non-orthogonal multiple access (NOMA) technique. The problem involves massive IoT devices grouping and power allocation in order to respect the low latency as well as the limited operating energy of the IoT devices. The considered objective function, maximizing the number of successfully received IoT packets, is different from the classical sum-rate-related objective functions. The problem is first divided into multiple NOMA grouping subproblems. Then, using competitive analysis, an efficient online competitive algorithm (CA) is proposed to solve each subproblem. Next, to solve the power allocation problem, we propose a new reinforcement learning (RL) framework in which a RL agent learns to use the CA as a black box and combines the obtained solutions to each subproblem to determine the power allocation for each NOMA group. Our simulations results reveal that the proposed innovative RL framework outperforms deep-Q-learning methods and is close-to-optimal.
Interconnect Parasitics and Partitioning in Fully-Analog In-Memory Computing Architectures
Venue: arXiv cs.AR 2022
Year: 2022

Fully-analog in-memory computing (IMC) architectures that implement both matrix-vector multiplication and non-linear vector operations within the same memory array have shown promising performance benefits over conventional IMC systems due to the removal of energy-hungry signal conversion units. However, maintaining the computation in the analog domain for the entire deep neural network (DNN) comes with potential sensitivity to interconnect parasitics. Thus, in this paper, we investigate the effect of wire parasitic resistance and capacitance on the accuracy of DNN models deployed on fully-analog IMC architectures. Moreover, we propose a partitioning mechanism to alleviate the impact of the parasitic while keeping the computation in the analog domain through dividing large arrays into multiple partitions. The SPICE circuit simulation results for a 400 X 120 X 84 X 10 DNN model deployed on a fully-analog IMC circuit show that a 94.84% accuracy could be achieved for MNIST classification application with 16, 8, and 8 horizontal partitions, as well as 8, 8, and 1 vertical partitions for first, second, and third layers of the DNN, respectively, which is comparable to the ~97% accuracy realized by digital implementation on CPU. It is shown that accuracy benefits are achieved at the cost of higher power consumption due to the extra circuitry required for handling partitioning.
The Geography of Facebook Groups in the United States
Venue: arXiv cs.SI 2022
Year: 2022

We use exploratory factor analysis to investigate the online persistence of known community-level patterns of social capital variance in the U.S. context. Our analysis focuses on Facebook groups, specifically those that tend to connect users in the same local area. We investigate the relationship between established, localized measures of social capital at the county level and patterns of participation in Facebook groups in the same areas. We identify four main factors that distinguish Facebook group engagement by county. The first captures small, private groups, dense with friendship connections. The second captures very local and small groups. The third captures non-local, large, public groups, with more age mixing. The fourth captures partially local groups of medium to large size. The first and third factor correlate with community level social capital measures, while the second and fourth do not. Together and individually, the factors are predictive of offline social capital measures, even controlling for various demographic attributes of the counties. Our analysis reveals striking patterns of correlation between established measures of social capital and patterns of online interaction in local Facebook groups. To our knowledge this is the first systematic test of the association between offline regional social capital and patterns of online community engagement in the same regions.
Modeling Complex Dependencies for Session-based Recommendations via Graph Neural Networks
Venue: arXiv cs.IR 2022
Year: 2022

Session-based recommendations (SBRs) capture items' dependencies from the sessions to recommend the next item. In recent years, Graph neural networks (GNN) based SBRs have become the mainstream of SBRs benefited from the superiority of GNN in modeling complex dependencies. Based on a strong assumption of adjacent dependency, any two adjacent items in a session are necessarily dependent in most GNN-based SBRs. However, we argue that due to the uncertainty and complexity of user behaviors, adjacency does not necessarily indicate dependency. However, the above assumptions do not always hold in actual recommendation scenarios, so it can easily lead to two drawbacks: (1) false dependencies occur in the session because there are adjacent but not really dependent items, and (2) the missing of true dependencies occur in the session because there are non-adjacent but actually dependent items. These drawbacks significantly affect item representation learning, degrading the downstream recommendation performance. To address these deficiencies, we propose a novel review-refined inter-item graph neural network (RI-GNN), which utilizes topic information extracted from the reviews of items to improve dependencies between items. Experiments on two public real-world datasets demonstrate that RI-GNN outperforms SOTA methods.
Aper: Evolution-Aware Runtime Permission Misuse Detection for Android Apps
Venue: arXiv cs.SE 2022
Year: 2022

The Android platform introduces the runtime permission model in version 6.0. The new model greatly improves data privacy and user experience, but brings new challenges for app developers. First, it allows users to freely revoke granted permissions. Hence, developers cannot assume that the permissions granted to an app would keep being granted. Instead, they should make their apps carefully check the permission status before invoking dangerous APIs. Second, the permission specification keeps evolving, bringing new types of compatibility issues into the ecosystem. To understand the impact of the challenges, we conducted an empirical study on 13,352 popular Google Play apps. We found that 86.0% apps used dangerous APIs asynchronously after permission management and 61.2% apps used evolving dangerous APIs. If an app does not properly handle permission revocations or platform differences, unexpected runtime issues may happen and even cause app crashes. We call such Android Runtime Permission issues as ARP bugs. Unfortunately, existing runtime permission issue detection tools cannot effectively deal with the ARP bugs induced by asynchronous permission management and permission specification evolution. To fill the gap, we designed a static analyzer, Aper, that performs reaching definition and dominator analysis on Android apps to detect the two types of ARP bugs. To compare Aper with existing tools, we built a benchmark, ARPfix, from 60 real ARP bugs. Our experiment results show that Aper significantly outperforms two academic tools, ARPDroid and RevDroid, and an industrial tool, Lint, on ARPfix, with an average improvement of 46.3% on F1-score. In addition, Aper successfully found 34 ARP bugs in 214 opensource Android apps, most of which can result in abnormal app behaviors (such as app crashes) according to our manual validation.
Logical Pseudocode: Connecting Algorithms with Proofs
Venue: arXiv cs.LO 2022
Year: 2022

Proofs (sequent calculus, natural deduction) and imperative algorithms (pseudocodes) are two well-known coexisting concepts. Then what is their relationship? Our answer is that \[ imperative\ algorithms\ =\ proofs\ with\ cuts \] This observation leads to a generalization to pseudocodes which we call {\it logical pseudocodes}. It is similar to natural deduction proof of computability logic\cite{Jap03,Jap08}. Each statement in it corresponds to a proof step in natural deduction. Therefore, the merit over pseudocode is that each statement is guaranteed to be correct and safe with respect to the initial specifications. It can also be seen as an extension to computability logic web (\colw) with forward reasoning capability.
Scale-arbitrary Invertible Image Downscaling
Venue: arXiv cs.CV 2022
Year: 2022

Conventional social media platforms usually downscale the HR images to restrict their resolution to a specific size for saving transmission/storage cost, which leads to the super-resolution (SR) being highly ill-posed. Recent invertible image downscaling methods jointly model the downscaling/upscaling problems and achieve significant improvements. However, they only consider fixed integer scale factors that cannot downscale HR images with various resolutions to meet the resolution restriction of social media platforms. In this paper, we propose a scale-Arbitrary Invertible image Downscaling Network (AIDN), to natively downscale HR images with arbitrary scale factors. Meanwhile, the HR information is embedded in the downscaled low-resolution (LR) counterparts in a nearly imperceptible form such that our AIDN can also restore the original HR images solely from the LR images. The key to supporting arbitrary scale factors is our proposed Conditional Resampling Module (CRM) that conditions the downscaling/upscaling kernels and sampling locations on both scale factors and image content. Extensive experimental results demonstrate that our AIDN achieves top performance for invertible downscaling with both arbitrary integer and non-integer scale factors. Code will be released upon publication.
Map Equation Centrality: Community-aware Centrality based on the Map Equation
Venue: arXiv cs.SI 2022
Year: 2022

To measure node importance, network scientists employ centrality scores that typically take a microscopic or macroscopic perspective, relying on node features or global network structure. However, traditional centrality measures such as degree centrality, betweenness centrality, or PageRank neglect the community structure found in real-world networks. To study node importance based on network flows from a mesoscopic perspective, we analytically derive a community-aware information-theoretic centrality score based on network flow and the coding principles behind the map equation: map equation centrality. Map equation centrality measures how much further we can compress the network's modular description by not coding for random walker transitions to the respective node, using an adapted coding scheme and determining node importance from a network flow-based point of view. The information-theoretic centrality measure can be determined from a node's local network context alone because changes to the coding scheme only affect other nodes in the same module. Map equation centrality is agnostic to the chosen network flow model and allows researchers to select the model that best reflects the dynamics of the process under study. Applied to synthetic networks, we highlight how our approach enables a more fine-grained differentiation between nodes than node-local or network-global measures. Predicting influential nodes for two different dynamical processes on real-world networks with traditional and other community-aware centrality measures, we find that activating nodes based on map equation centrality scores tends to create the largest cascades in a linear threshold model.
Semantic-assisted image compression
Venue: arXiv cs.CV 2022
Year: 2022

Conventional image compression methods typically aim at pixel-level consistency while ignoring the performance of downstream AI tasks.To solve this problem, this paper proposes a Semantic-Assisted Image Compression method (SAIC), which can maintain semantic-level consistency to enable high performance of downstream AI tasks.To this end, we train the compression network using semantic-level loss function. In particular, semantic-level loss is measured using gradient-based semantic weights mechanism (GSW). GSW directly consider downstream AI tasks' perceptual results. Then, this paper proposes a semantic-level distortion evaluation metric to quantify the amount of semantic information retained during the compression process. Experimental results show that the proposed SAIC method can retain more semantic-level information and achieve better performance of downstream AI tasks compared to the traditional deep learning-based method and the advanced perceptual method at the same compression ratio.
BatteryLab: A Collaborative Platform for Power Monitoring
Venue: arXiv cs.NI 2022
Year: 2022

Advances in cloud computing have simplified the way that both software development and testing are performed. This is not true for battery testing for which state of the art test-beds simply consist of one phone attached to a power meter. These test-beds have limited resources, access, and are overall hard to maintain; for these reasons, they often sit idle with no experiment to run. In this paper, we propose to share existing battery testbeds and transform them into vantage points of BatteryLab, a power monitoring platform offering heterogeneous devices and testing conditions. We have achieved this vision with a combination of hardware and software which allow to augment existing battery test-beds with remote capabilities. BatteryLab currently counts three vantage points, one in Europe and two in the US, hosting three Android devices and one iPhone 7. We benchmark BatteryLab with respect to the accuracy of its battery readings, system performance, and platform heterogeneity. Next, we demonstrate how measurements can be run atop of BatteryLab by developing the "Web Power Monitor" (WPM), a tool which can measure website power consumption at scale. We released WPM and used it to report on the energy consumption of Alexa's top 1,000 websites across 3 locations and 4 devices (both Android and iOS).
A visualization tool for data analysis on higher education dropout: a case study at UFES
Venue: arXiv cs.CY 2022
Year: 2022

Through the analysis of cultural, socioeconomic and academic performance aspects it is possible to map the profile of the students and their motivations to drop out. This article aims to create a computational tool for data visualization that allows drawing the profile of students to support educational institutions managers in the definition of dropout avoidance policies. We present a method to treat data collected by higher education institutions over the years, analyze them to understand the dropout and provide that information to the university and the general public. Eight questions were proposed to clarify the dropout from the Federal University of Espírito Santo, Brazil. The questions were answered through the dashboard that helps to understand the causes of dropout. It is expected that this tool can be used by others educational institutions to draw student profiles contributing to possible resolution of the problem.
Deep Learning based Multi-User Power Allocation and Hybrid Precoding in Massive MIMO Systems
Venue: arXiv cs.IT 2022
Year: 2022

This paper proposes a deep learning based power allocation (DL-PA) and hybrid precoding technique for multiuser massive multiple-input multiple-output (MU-mMIMO) systems. We first utilize an angular-based hybrid precoding technique for reducing the number of RF chains and channel estimation overhead. Then, we develop the DL-PA algorithm via a fully-connected deep neural network (DNN). DL-PA has two phases: (i) offline supervised learning with the optimal allocated powers obtained by particle swarm optimization based PA (PSO-PA) algorithm, (ii) online power prediction by the trained DNN. In comparison to the computationally expensive PSO-PA, it is shown that DL-PA greatly reduces the runtime by 98.6%-99.9%, while closely achieving the optimal sum-rate capacity. It makes DL-PA a promising algorithm for the real-time online applications in MU-mMIMO systems.
A Deep CNN Architecture with Novel Pooling Layer Applied to Two Sudanese Arabic Sentiment Datasets
Venue: arXiv cs.CL 2022
Year: 2022

Arabic sentiment analysis has become an important research field in recent years. Initially, work focused on Modern Standard Arabic (MSA), which is the most widely-used form. Since then, work has been carried out on several different dialects, including Egyptian, Levantine and Moroccan. Moreover, a number of datasets have been created to support such work. However, up until now, less work has been carried out on Sudanese Arabic, a dialect which has 32 million speakers. In this paper, two new publicly available datasets are introduced, the 2-Class Sudanese Sentiment Dataset (SudSenti2) and the 3-Class Sudanese Sentiment Dataset (SudSenti3). Furthermore, a CNN architecture, SCM, is proposed, comprising five CNN layers together with a novel pooling layer, MMA, to extract the best features. This SCM+MMA model is applied to SudSenti2 and SudSenti3 with accuracies of 92.75% and 84.39%. Next, the model is compared to other deep learning classifiers and shown to be superior on these new datasets. Finally, the proposed model is applied to the existing Saudi Sentiment Dataset and to the MSA Hotel Arabic Review Dataset with accuracies 85.55% and 90.01%.
Robotic Wireless Energy Transfer in Dynamic Environments: System Design and Experimental Validation
Venue: arXiv cs.RO 2022
Year: 2022

Wireless energy transfer (WET) is a ground-breaking technology for cutting the last wire between mobile sensors and power grids in smart cities. Yet, WET only offers effective transmission of energy over a short distance. Robotic WET is an emerging paradigm that mounts the energy transmitter on a mobile robot and navigates the robot through different regions in a large area to charge remote energy harvesters. However, it is challenging to determine the robotic charging strategy in an unknown and dynamic environment due to the uncertainty of obstacles. This paper proposes a hardware-in-the-loop joint optimization framework that offers three distinctive features: 1) efficient model updates and re-optimization based on the last-round experimental data; 2) iterative refinement of the anchor list for adaptation to different environments; 3) verification of algorithms in a high-fidelity Gazebo simulator and a multi-robot testbed. Experimental results show that the proposed framework significantly saves the WET mission completion time while satisfying collision avoidance and energy harvesting constraints.