OpenRaiser/Intern-Atlas huggingface dataset:
Perfect Sampling for (Atomic) Lovász Local Lemma
Venue: arXiv cs.DS 2021
Year: 2021

We give a Markov chain based perfect sampler for uniform sampling solutions of constraint satisfaction problems (CSP). Under some mild Lovász local lemma conditions where each constraint of the CSP has a small number of forbidden local configurations, our algorithm is accurate and efficient: it outputs a perfect uniform random solution and its expected running time is quasilinear in the number of variables. Prior to our work, perfect samplers are only shown to exist for CSPs under much more restrictive conditions (Guo, Jerrum, and Liu, JACM'19). Our algorithm has two components: 1. A simple perfect sampling algorithm using bounding chains (Huber, STOC'98; Haggstrom and Nelander, Scandinavian Journal of Statistics'99). This sampler is efficient if each variable domain is small. 2. A simple but powerful state tensorization trick to reduce large domains to smaller ones. This trick is a generalization of state compression (Feng, He, and Yin, STOC'21). The crux of our analysis is a simple information percolation argument which allows us to achieve bounds even beyond current best approximate samplers (Jain, Pham, and Vuong, ArXiv'21). Previous related works either use intricate algorithms or need sophisticated analysis or even both. Thus we view the simplicity of both our algorithm and analysis as a strength of our work.
Task Fingerprinting for Meta Learning in Biomedical Image Analysis
Venue: arXiv cs.CV 2021
Year: 2021

Shortage of annotated data is one of the greatest bottlenecks in biomedical image analysis. Meta learning studies how learning systems can increase in efficiency through experience and could thus evolve as an important concept to overcome data sparsity. However, the core capability of meta learning-based approaches is the identification of similar previous tasks given a new task - a challenge largely unexplored in the biomedical imaging domain. In this paper, we address the problem of quantifying task similarity with a concept that we refer to as task fingerprinting. The concept involves converting a given task, represented by imaging data and corresponding labels, to a fixed-length vector representation. In fingerprint space, different tasks can be directly compared irrespective of their data set sizes, types of labels or specific resolutions. An initial feasibility study in the field of surgical data science (SDS) with 26 classification tasks from various medical and non-medical domains suggests that task fingerprinting could be leveraged for both (1) selecting appropriate data sets for pretraining and (2) selecting appropriate architectures for a new task. Task fingerprinting could thus become an important tool for meta learning in SDS and other fields of biomedical image analysis.
Privacy Concerns in Chatbot Interactions: When to Trust and When to Worry
Venue: arXiv cs.CY 2021
Year: 2021

Through advances in their conversational abilities, chatbots have started to request and process an increasing variety of sensitive personal information. The accurate disclosure of sensitive information is essential where it is used to provide advice and support to users in the healthcare and finance sectors. In this study, we explore users' concerns regarding factors associated with the use of sensitive data by chatbot providers. We surveyed a representative sample of 491 British citizens. Our results show that the user concerns focus on deleting personal information and concerns about their data's inappropriate use. We also identified that individuals were concerned about losing control over their data after a conversation with conversational agents. We found no effect from a user's gender or education but did find an effect from the user's age, with those over 45 being more concerned than those under 45. We also considered the factors that engender trust in a chatbot. Our respondents' primary focus was on the chatbot's technical elements, with factors such as the response quality being identified as the most critical factor. We again found no effect from the user's gender or education level; however, when we considered some social factors (e.g. avatars or perceived 'friendliness'), we found those under 45 years old rated these as more important than those over 45. The paper concludes with a discussion of these results within the context of designing inclusive, digital systems that support a wide range of users.
Expanding IceCube GPU computing into the Clouds
Venue: arXiv cs.DC 2021
Year: 2021

The IceCube collaboration relies on GPU compute for many of its needs, including ray tracing simulation and machine learning activities. GPUs are however still a relatively scarce commodity in the scientific resource provider community, so we expanded the available resource pool with GPUs provisioned from the commercial Cloud providers. The provisioned resources were fully integrated into the normal IceCube workload management system through the Open Science Grid (OSG) infrastructure and used CloudBank for budget management. The result was an approximate doubling of GPU wall hours used by IceCube over a period of 2 weeks, adding over 3.1 fp32 EFLOP hours for a price tag of about $58k. This paper describes the setup used and the operational experience.
Study of Block Diagonalization Precoding and Power Allocation for Multiple-Antenna Systems with Coarsely Quantized Signals
Venue: arXiv cs.IT 2021
Year: 2021

In this work, we present block diagonalization and power allocation algorithms for large-scale multiple-antenna systems with coarsely quantized signals. In particular, we develop Coarse Quantization-Aware Block Diagonalization ${\scriptstyle\mathrm{\left(CQA-BD\right)}}$ and Coarse Quantization-Aware Regularized Block Diagonalization ${\scriptstyle\mathrm{\left(CQA-RBD\right)}}$ precoding algorithms that employ the Bussgang decomposition and can mitigate the effects of low-resolution signals and interference. Moreover, we also devise the Coarse Quantization-Aware Most Advantageous Allocation Strategy ${\scriptstyle\mathrm{\left(CQA-MAAS\right)}}$ power allocation algorithm to improve the sum rate of precoders that operate with low-resolution signals. An analysis of the sum-rate performance is carried out along with computational complexity and power consumption studies of the proposed and existing techniques. Simulation results illustrate the performance of the proposed ${\scriptstyle\mathrm{CQA-BD}}$ and ${\scriptstyle\mathrm{CQA-RBD}}$ precoding algorithms, and the proposed ${\scriptstyle\mathrm{CQA-MAAS}}$ power allocation strategy against existing approaches.
Incorporating Gaze into Social Navigation
Venue: arXiv cs.RO 2021
Year: 2021

Most current approaches to social navigation focus on the trajectory and position of participants in the interaction. Our current work on the topic focuses on integrating gaze into social navigation, both to cue nearby pedestrians as to the intended trajectory of the robot and to enable the robot to read the intentions of nearby pedestrians. This paper documents a series of experiments in our laboratory investigating the role of gaze in social navigation.
Inspiration through Observation: Demonstrating the Influence of Automatically Generated Text on Creative Writing
Venue: arXiv cs.CL 2021
Year: 2021

Getting machines to generate text perceived as creative is a long-pursued goal. A growing body of research directs this goal towards augmenting the creative writing abilities of human authors. In this paper, we pursue this objective by analyzing how observing examples of automatically generated text influences writing. In particular, we examine a task referred to as sentence infilling, which involves transforming a list of words into a complete sentence. We emphasize "storiability" as a desirable feature of the resulting sentences, where "storiable" sentences are those that suggest a story a reader would be curious to hear about. Both humans and an automated system (based on a neural language model) performed this sentence infilling task. In one setting, people wrote sentences on their own; in a different setting, people observed the sentences produced by the model while writing their own sentences. Readers then assigned storiability preferences to the resulting sentences in a subsequent evaluation. We find that human-authored sentences were judged as more storiable when authors observed the generated examples, and that storiability increased as authors derived more semantic content from the examples. This result gives evidence of an "inspiration through observation" paradigm for human-computer collaborative writing, through which human writing can be enhanced by text generation models without directly copying their output.
The Show Must Go On -- Examination During a Pandemic
Venue: arXiv cs.CY 2021
Year: 2021

When unexpected incidents occur, new innovative and flexible solutions are required. If this event is something such radical and dramatic like the COVID-19 pandemic, these solutions must aim to guarantee as much normality as possible while protecting lives. After a moment of shock our university decided that the students have to be able to pursue their studies for guaranteeing a degree in the expected time since most of them faced immediate financial problems due to the loss of their student jobs. This implied, for us as teachers, that we had to reorganise not only the teaching methods from nearly one day to the next, but we also had to come up with an adjusted way of examinations which had to take place in person with pen and paper under strict hygiene rules. On the other hand the correction should avoid personal contacts. We developed a framework which allowed us to correct the digitalised exams safely at home while providing the high standards given by the general data protection regulation of our country. Moreover, the time spent in the offices could be reduced to a minimum thanks to automatically generated exam sheets, automatically re-digitalised and sorted worked-on exams.
TGHop: An Explainable, Efficient and Lightweight Method for Texture Generation
Venue: arXiv cs.CV 2021
Year: 2021

An explainable, efficient and lightweight method for texture generation, called TGHop (an acronym of Texture Generation PixelHop), is proposed in this work. Although synthesis of visually pleasant texture can be achieved by deep neural networks, the associated models are large in size, difficult to explain in theory, and computationally expensive in training. In contrast, TGHop is small in its model size, mathematically transparent, efficient in training and inference, and able to generate high quality texture. Given an exemplary texture, TGHop first crops many sample patches out of it to form a collection of sample patches called the source. Then, it analyzes pixel statistics of samples from the source and obtains a sequence of fine-to-coarse subspaces for these patches by using the PixelHop++ framework. To generate texture patches with TGHop, we begin with the coarsest subspace, which is called the core, and attempt to generate samples in each subspace by following the distribution of real samples. Finally, texture patches are stitched to form texture images of a large size. It is demonstrated by experimental results that TGHop can generate texture images of superior quality with a small model size and at a fast speed.
CVEH: A Dynamic Framework To Profile Vehicle Movements To Mitigate Hit And Run Cases Using Crowdsourcing
Venue: arXiv cs.CY 2021
Year: 2021

In developed countries like the USA, Germany, and the UK, the security forces used highly sophisticated equipment, fast vehicles, drones, and helicopters to catch offenders' vehicles. Whereas, in developing countries with limited resources such schemes cannot be utilized due to management cost and other constraints. In this paper, we proposed a framework called CVEH that enables developing countries to profile the offender vehicle movements through crowdsourcing technique and act as an early warning system to the law forcing agencies. It also engages citizens to play their role in improving security conditions. The proposed CVEH framework allows Vehicle-to-Infrastructure (V2I) communication to monitor the movement of the offender's vehicle and shared its information with the Command and Control (CC) centre. The CC centre projects the path and engages nearly located law enforcement agencies. CVEH is developed and evaluated on android smartphones. Simulations conducted for this study exhibit the effectiveness of our framework.
A Triangle Inequality for Cosine Similarity
Venue: arXiv cs.LG 2021
Year: 2021

Similarity search is a fundamental problem for many data analysis techniques. Many efficient search techniques rely on the triangle inequality of metrics, which allows pruning parts of the search space based on transitive bounds on distances. Recently, Cosine similarity has become a popular alternative choice to the standard Euclidean metric, in particular in the context of textual data and neural network embeddings. Unfortunately, Cosine similarity is not metric and does not satisfy the standard triangle inequality. Instead, many search techniques for Cosine rely on approximation techniques such as locality sensitive hashing. In this paper, we derive a triangle inequality for Cosine similarity that is suitable for efficient similarity search with many standard search structures (such as the VP-tree, Cover-tree, and M-tree); show that this bound is tight and discuss fast approximations for it. We hope that this spurs new research on accelerating exact similarity search for cosine similarity, and possible other similarity measures beyond the existing work for distance metrics.
An Integer Linear Programming Model for Tilings
Venue: arXiv cs.DM 2021
Year: 2021

In this paper, we propose an Integer Linear Model whose solutions are the aperiodic rhythms tiling with a given rhythm A. We show how this model can be used to efficiently check the necessity of the Coven-Meyerowitz's $(T2)$ condition and also to define an iterative algorithm that finds all the possible tilings of the rhythm A. To conclude, we run several experiments to validate the time efficiency of this model.
Safe Learning of Lifted Action Models
Venue: arXiv cs.AI 2021
Year: 2021

Creating a domain model, even for classical, domain-independent planning, is a notoriously hard knowledge-engineering task. A natural approach to solve this problem is to learn a domain model from observations. However, model learning approaches frequently do not provide safety guarantees: the learned model may assume actions are applicable when they are not, and may incorrectly capture actions' effects. This may result in generating plans that will fail when executed. In some domains such failures are not acceptable, due to the cost of failure or inability to replan online after failure. In such settings, all learning must be done offline, based on some observations collected, e.g., by some other agents or a human. Through this learning, the task is to generate a plan that is guaranteed to be successful. This is called the model-free planning problem. Prior work proposed an algorithm for solving the model-free planning problem in classical planning. However, they were limited to learning grounded domains, and thus they could not scale. We generalize this prior work and propose the first safe model-free planning algorithm for lifted domains. We prove the correctness of our approach, and provide a statistical analysis showing that the number of trajectories needed to solve future problems with high probability is linear in the potential size of the domain model. We also present experiments on twelve IPC domains showing that our approach is able to learn the real action model in all cases with at most two trajectories.
Emotion Recognition with Incomplete Labels Using Modified Multi-task Learning Technique
Venue: arXiv cs.CV 2021
Year: 2021

The task of predicting affective information in the wild such as seven basic emotions or action units from human faces has gradually become more interesting due to the accessibility and availability of massive annotated datasets. In this study, we propose a method that utilizes the association between seven basic emotions and twelve action units from the AffWild2 dataset. The method based on the architecture of ResNet50 involves the multi-task learning technique for the incomplete labels of the two tasks. By combining the knowledge for two correlated tasks, both performances are improved by a large margin compared to those with the model employing only one kind of label.
Mitigating Imperfections in Mixed-Signal Neuromorphic Circuits
Venue: arXiv cs.ET 2021
Year: 2021

The progress in neuromorphic computing is fueled by the development of novel nonvolatile memories capable of storing analog information and implementing neural computation efficiently. However, like most other analog circuits, these devices and circuits are prone to imperfections, such as temperature dependency, noise, tuning error, etc., often leading to considerable performance degradation in neural network implementations. Indeed, imperfections are major obstacles in the path of further progress and ultimate commercialization of these technologies. Hence, a practically viable approach should be developed to deal with these nonidealities and unleash the full potential of nonvolatile memories in neuromorphic systems. Here, for the first time, we report a comprehensive characterization of critical imperfections in two analog-grade memories, namely passively-integrated memristors and redesigned eFlash memories, which both feature long-term retention, high endurance, analog storage, low-power operation, and compact nano-scale footprint. Then, we propose a holistic approach that includes modifications in the training, tuning algorithm, memory state optimization, and circuit design to mitigate these imperfections. Our proposed methodology is corroborated on a hybrid software/experimental framework using two benchmarks: a moderate-size convolutional neural network and ResNet-18 trained on CIFAR-10 and ImageNet datasets, respectively. Our proposed approaches allow 2.5x to 9x improvements in the energy consumption of memory arrays during inference and sub-percent accuracy drop across 25-100 C temperature range. The defect tolerance is improved by >100x, and a sub-percent accuracy drop is demonstrated in deep neural networks built with 64x64 passive memristive crossbars featuring 25% normalized switching threshold variations.
WinoCNN: Kernel Sharing Winograd Systolic Array for Efficient Convolutional Neural Network Acceleration on FPGAs
Venue: arXiv cs.AR 2021
Year: 2021

The combination of Winograd's algorithm and systolic array architecture has demonstrated the capability of improving DSP efficiency in accelerating convolutional neural networks (CNNs) on FPGA platforms. However, handling arbitrary convolution kernel sizes in FPGA-based Winograd processing elements and supporting efficient data access remain underexplored. In this work, we are the first to propose an optimized Winograd processing element (WinoPE), which can naturally support multiple convolution kernel sizes with the same amount of computing resources and maintains high runtime DSP efficiency. Using the proposed WinoPE, we construct a highly efficient systolic array accelerator, termed WinoCNN. We also propose a dedicated memory subsystem to optimize the data access. Based on the accelerator architecture, we build accurate resource and performance modeling to explore optimal accelerator configurations under different resource constraints. We implement our proposed accelerator on multiple FPGAs, which outperforms the state-of-the-art designs in terms of both throughput and DSP efficiency. Our implementation achieves DSP efficiency up to 1.33 GOPS/DSP and throughput up to 3.1 TOPS with the Xilinx ZCU102 FPGA. These are 29.1\% and 20.0\% better than the best solutions reported previously, respectively.
Sensitivity analysis in differentially private machine learning using hybrid automatic differentiation
Venue: arXiv cs.LG 2021
Year: 2021

In recent years, formal methods of privacy protection such as differential privacy (DP), capable of deployment to data-driven tasks such as machine learning (ML), have emerged. Reconciling large-scale ML with the closed-form reasoning required for the principled analysis of individual privacy loss requires the introduction of new tools for automatic sensitivity analysis and for tracking an individual's data and their features through the flow of computation. For this purpose, we introduce a novel \textit{hybrid} automatic differentiation (AD) system which combines the efficiency of reverse-mode AD with an ability to obtain a closed-form expression for any given quantity in the computational graph. This enables modelling the sensitivity of arbitrary differentiable function compositions, such as the training of neural networks on private data. We demonstrate our approach by analysing the individual DP guarantees of statistical database queries. Moreover, we investigate the application of our technique to the training of DP neural networks. Our approach can enable the principled reasoning about privacy loss in the setting of data processing, and further the development of automatic sensitivity analysis and privacy budgeting systems.
Prior-Guided Multi-View 3D Head Reconstruction
Venue: arXiv cs.CV 2021
Year: 2021

Recovery of a 3D head model including the complete face and hair regions is still a challenging problem in computer vision and graphics. In this paper, we consider this problem using only a few multi-view portrait images as input. Previous multi-view stereo methods that have been based, either on optimization strategies or deep learning techniques, suffer from low-frequency geometric structures such as unclear head structures and inaccurate reconstruction in hair regions. To tackle this problem, we propose a prior-guided implicit neural rendering network. Specifically, we model the head geometry with a learnable signed distance field (SDF) and optimize it via an implicit differentiable renderer with the guidance of some human head priors, including the facial prior knowledge, head semantic segmentation information and 2D hair orientation maps. The utilization of these priors can improve the reconstruction accuracy and robustness, leading to a high-quality integrated 3D head model. Extensive ablation studies and comparisons with state-of-the-art methods demonstrate that our method can generate high-fidelity 3D head geometries with the guidance of these priors.
Computational Complexity of Computing a Quasi-Proper Equilibrium
Venue: arXiv cs.GT 2021
Year: 2021

We study the computational complexity of computing or approximating a quasi-proper equilibrium for a given finite extensive form game of perfect recall. We show that the task of computing a symbolic quasi-proper equilibrium is $\mathrm{PPAD}$-complete for two-player games. For the case of zero-sum games we obtain a polynomial time algorithm based on Linear Programming. For general $n$-player games we show that computing an approximation of a quasi-proper equilibrium is $\mathrm{FIXP}_a$-complete.