OpenRaiser/Intern-Atlas huggingface dataset:
Tight Approximation Algorithms for Geometric Bin Packing with Skewed Items
Venue: arXiv cs.CG 2021
Year: 2021

In the Two-dimensional Bin Packing (2BP) problem, we are given a set of rectangles of height and width at most one and our goal is to find an axis-aligned nonoverlapping packing of these rectangles into the minimum number of unit square bins. The problem admits no APTAS and the current best approximation ratio is $1.406$ by Bansal and Khan [SODA'14]. A well-studied variant of the problem is Guillotine Two-dimensional Bin Packing (G2BP), where all rectangles must be packed in such a way that every rectangle in the packing can be obtained by recursively applying a sequence of end-to-end axis-parallel cuts, also called guillotine cuts. Bansal, Lodi, and Sviridenko [FOCS'05] obtained an APTAS for this problem. Let $λ$ be the smallest constant such that for every set $I$ of items, the number of bins in the optimal solution to G2BP for $I$ is upper bounded by $λ\operatorname{opt}(I) + c$, where $\operatorname{opt}(I)$ is the number of bins in the optimal solution to 2BP for $I$ and $c$ is a constant. It is known that $4/3 \le λ\le 1.692$. Bansal and Khan [SODA'14] conjectured that $λ= 4/3$. The conjecture, if true, will imply a $(4/3+\varepsilon)$-approximation algorithm for 2BP. According to convention, for a given constant $δ>0$, a rectangle is large if both its height and width are at least $δ$, and otherwise it is called skewed. We make progress towards the conjecture by showing $λ= 4/3$ for skewed instance, i.e., when all input rectangles are skewed. Even for this case, the previous best upper bound on $λ$ was roughly 1.692. We also give an APTAS for 2BP for skewed instance, though general 2BP does not admit an APTAS.
Stylistic Analysis of the French Presidential Speeches: Is Macron really different?
Venue: arXiv cs.CL 2021
Year: 2021

Presidential speeches indicate the government's intentions and justifications supported by a dedicated style and rhetoric oscillating between explanation and controversy. Over a period of sixty years, can we observe stylistic variations by the different French presidents of the Fifth Republic (1958-2018)? Based on official transcripts of all their allocution, this paper illustrates the stylistic evolution and presents the underlying main trends. This study shows that de Gaulle's rhetoric is not mainly dedicated to his own person, or that the two terms of J. Chirac are not fully similar. According to several overall stylistic indicators, Macron's style does not appear as complex compared to his predecessors (F. Hollande or N. Sarkozy) but a more careful analysis clearly demonstrates his noticeable new style. Compared to the recent US presidents, the French ones present some similarities (e.g., similar mean sentence length) and dissimilarities (more I-words, less we-words). In this comparative analysis, Macron's style is also clearly distinctive from both the US and former French presidents. Opting for a more abstract discourse, less anchored in space, using less numbers, E. Macron tends to use long sentences. These various stylistic and rhetorical features could explain his being misunderstood by the French people and his recurrent low approval ratings.
A Metamodel Structure For Regression Analysis: Application To Prediction Of Autism Spectrum Disorder Severity
Venue: arXiv cs.LG 2021
Year: 2021

Traditional regression models do not generalize well when learning from small and noisy datasets. Here we propose a novel metamodel structure to improve the regression result. The metamodel is composed of multiple classification base models and a regression model built upon the base models. We test this structure on the prediction of autism spectrum disorder (ASD) severity as measured by the ADOS communication (ADOS COMM) score from resting-state fMRI data, using a variety of base models. The metamodel outperforms traditional regression models as measured by the Pearson correlation coefficient between true and predicted scores and stability. In addition, we found that the metamodel is more flexible and more generalizable.
Users' Perception of Search Engine Biases and Satisfaction
Venue: arXiv cs.IR 2021
Year: 2021

Search engines could consistently favor certain values over the others, which is considered as biased due to the built-in infrastructures. Many studies have been dedicated to detect, control, and mitigate the impacts of the biases from the perspectives of search engines themselves. In our study, we take the perspective from end-users to analyze their perceptions of search engine biases and their satisfaction when the biases are regulated. In the study, we paired a real search page from search engine Bing with a synthesized page that has more diversities in the results (i.e. less biased). Both pages show the top-10 search items given search queries and we asked participants which one do they prefer and why do they prefer the one selected. Statistical analyses revealed that overall, participants prefer the original Bing pages and the locations where the diversities are introduced are also associated with users' preferences. We found out that users prefer results that are more consistent and relevant to the search queries. Introducing diversities undermines the relevance of the search results and impairs users' satisfaction to some degree. Additionally, we confirmed that users tend to pay more attention to the top portion of the results than the bottom ones.
Computing the $4$-Edge-Connected Components of a Graph in Linear Time
Venue: arXiv cs.DS 2021
Year: 2021

We present the first linear-time algorithm that computes the $4$-edge-connected components of an undirected graph. Hence, we also obtain the first linear-time algorithm for testing $4$-edge connectivity. Our results are based on a linear-time algorithm that computes the $3$-edge cuts of a $3$-edge-connected graph $G$, and a linear-time procedure that, given the collection of all $3$-edge cuts, partitions the vertices of $G$ into the $4$-edge-connected components.
Securing Parallel-chain Protocols under Variable Mining Power
Venue: arXiv cs.CR 2021
Year: 2021

Several emerging PoW blockchain protocols rely on a "parallel-chain" architecture for scaling, where instead of a single chain, multiple chains are run in parallel and aggregated. A key requirement of practical PoW blockchains is to adapt to mining power variations over time. In this paper, we consider the design of provably secure parallel-chain protocols which can adapt to such mining power variations. The Bitcoin difficulty adjustment rule adjusts the difficulty target of block mining periodically to get a constant mean inter-block time. While superficially simple, the rule has proved itself to be sophisticated and successfully secure, both in practice and in theory. We show that natural adaptations of the Bitcoin adjustment rule to the parallel-chain case open the door to subtle, but catastrophic safety and liveness breaches. We uncover a meta-design principle that allow us to design variable mining difficulty protocols for three popular PoW blockchain proposals (Prism, OHIE, and Fruitchains) inside a common rubric. The principle has three components:(M1) a pivot chain, based on which blocks in all chains choose difficulty, (M2) a monotonicity condition for referencing pivot chain blocks and (M3) translating additional protocol aspects from using levels (depth) to using "difficulty levels". We show that protocols employing a subset of these principles may have catastrophic failures. The security of the designs is also proved using a common rubric - the key technical challenge involves analyzing the interaction between the pivot chain and the other chains, as well as bounding the sudden changes in difficulty target experienced in non-pivot chains. We empirically investigate the responsivity of the new mining difficulty rule via simulations based on historical Bitcoin data, and find that the protocol very effectively controls the forking rate across all the chains.
Profiling the Cybercriminal: A Systematic Review of Research
Venue: arXiv cs.CY 2021
Year: 2021

As cybercrime becomes one of the most significant threats facing society today, it is of utmost importance to better understand the perpetrators behind such attacks. In this article, we seek to advance research and practitioner understanding of the cybercriminal (cyber-offender) profiling domain by conducting a rigorous systematic review. This work investigates the aforementioned domain to answer the question: what is the state-of-the-art in the academic field of understanding, characterising and profiling cybercriminals. Through the application of the PRISMA systematic literature review technique, we identify 39 works from the last 14 years (2006-2020). Our findings demonstrate that overall, there is lack of a common definition of profiling for cyber-offenders. The review found that one of the primary types of cybercriminals that studies have focused on is hackers and the majority of papers used the deductive approach as a preferred one. This article produces an up-to-date characterisation of the field and also defines open issues deserving of further attention such as the role of security professionals and law enforcement in supporting such research, as well as factors including personality traits which must be further researched whilst exploring online criminal behaviour. By understanding online offenders and their pathways towards malevolent behaviours, we can better identify steps that need to be taken to prevent such criminal activities.
Text similarity analysis for evaluation of descriptive answers
Venue: arXiv cs.LG 2021
Year: 2021

Keeping in mind the necessity of intelligent system in educational sector, this paper proposes a text analysis based automated approach for automatic evaluation of the descriptive answers in an examination. In particular, the research focuses on the use of intelligent concepts of Natural Language Processing and Data Mining for computer aided examination evaluation system. The paper present an architecture for fair evaluation of answer sheet. In this architecture, the examiner creates a sample answer sheet for given sets of question. By using the concept of text summarization, text semantics and keywords summarization, the final score for each answer is calculated. The text similarity model is based on Siamese Manhattan LSTM (MaLSTM). The results of this research were compared to manually graded assignments and other existing system. This approach was found to be very efficient in order to be implemented in an institution or in an university.
A DLT-based Smart Contract Architecture for Atomic and Scalable Trading
Venue: arXiv cs.CR 2021
Year: 2021

Distributed Ledger Technology (DLT) has an enormous potential but also downsides. One downside of many DLT systems, such as blockchain, is their limited transaction throughput that hinders their adoption in many use cases (e.g., real-time payments). State channels have emerged as a potential solution to enhance throughput by allowing transactions to process off-chain. While current proposals can increase scalability, they require high collateral and lack support for dynamic systems that require asynchronous state transitions. Additionally, the latency of channel initialisations can cause issues especially if fast interactions are required. In this paper, we propose an atomic, scalable and privacy-preserving protocol that enables secure and dynamic updates. We develop a smart contract-based Credit-Note System (CNS) that allows participants to lock funds before a state channel initialisation, which enhances flexibility and efficiency. We formalise our model using the Universal Composability (UC) framework and demonstrate that it achieves the stated design goals of privacy, scalability, and atomicity. Moreover, we implement a dispute process in the state channel to counter availability attacks. Finally, we analyse the protocol in the context of an asynchronous smart grid-based marketplace.
Object detection for crabs in top-view seabed imagery
Venue: arXiv cs.CV 2021
Year: 2021

This report presents the application of object detection on a database of underwater images of different species of crabs, as well as aerial images of sea lions and finally the Pascal VOC dataset. The model is an end-to-end object detection neural network based on a convolutional network base and a Long Short-Term Memory detector.
A Review on Serious Games for ADHD
Venue: arXiv cs.HC 2021
Year: 2021

Attention deficit and hyperactivity disorder (ADHD) have two main characteristics: inattention and impulsivity.It has many obstacles to the normal development of children and is very common among children.As an intervention, Serious games for ADHD(SGADs) have shown great potential and are very effective for these ADHD patients.Although many serious games have been developed for ADHD patients, but a review paper that summarizes and generalizes the topic of video games has not yet appeared.In this article, we first classified serious games about ADHD according to different platforms developed by video games, and then we conducted a systematic review of video games that can help children with ADHD diagnose and treat. Finally, we discussed and made suggestions based on the current development of SGADs.
Utilizing Skipped Frames in Action Repeats via Pseudo-Actions
Venue: arXiv cs.LG 2021
Year: 2021

In many deep reinforcement learning settings, when an agent takes an action, it repeats the same action a predefined number of times without observing the states until the next action-decision point. This technique of action repetition has several merits in training the agent, but the data between action-decision points (i.e., intermediate frames) are, in effect, discarded. Since the amount of training data is inversely proportional to the interval of action repeats, they can have a negative impact on the sample efficiency of training. In this paper, we propose a simple but effective approach to alleviate to this problem by introducing the concept of pseudo-actions. The key idea of our method is making the transition between action-decision points usable as training data by considering pseudo-actions. Pseudo-actions for continuous control tasks are obtained as the average of the action sequence straddling an action-decision point. For discrete control tasks, pseudo-actions are computed from learned action embeddings. This method can be combined with any model-free reinforcement learning algorithm that involves the learning of Q-functions. We demonstrate the effectiveness of our approach on both continuous and discrete control tasks in OpenAI Gym.
GANTL: Towards Practical and Real-Time Topology Optimization with Conditional GANs and Transfer Learning
Venue: arXiv cs.LG 2021
Year: 2021

Many machine learning methods have been recently developed to circumvent the high computational cost of the gradient-based topology optimization. These methods typically require extensive and costly datasets for training, have a difficult time generalizing to unseen boundary and loading conditions and to new domains, and do not take into consideration topological constraints of the predictions, which produces predictions with inconsistent topologies. We present a deep learning method based on generative adversarial networks for generative design exploration. The proposed method combines the generative power of conditional GANs with the knowledge transfer capabilities of transfer learning methods to predict optimal topologies for unseen boundary conditions. We also show that the knowledge transfer capabilities embedded in the design of the proposed algorithm significantly reduces the size of the training dataset compared to the traditional deep learning neural or adversarial networks. Moreover, we formulate a topological loss function based on the bottleneck distance obtained from the persistent diagram of the structures and demonstrate a significant improvement in the topological connectivity of the predicted structures. We use numerous examples to explore the efficiency and accuracy of the proposed approach for both seen and unseen boundary conditions in 2D.
Faster and Simpler Siamese Network for Single Object Tracking
Venue: arXiv cs.CV 2021
Year: 2021

Single object tracking (SOT) is currently one of the most important tasks in computer vision. With the development of the deep network and the release for a series of large scale datasets for single object tracking, siamese networks have been proposed and perform better than most of the traditional methods. However, recent siamese networks get deeper and slower to obtain better performance. Most of these methods could only meet the needs of real-time object tracking in ideal environments. In order to achieve a better balance between efficiency and accuracy, we propose a simpler siamese network for single object tracking, which runs fast in poor hardware configurations while remaining an excellent accuracy. We use a more efficient regression method to compute the location of the tracked object in a shorter time without losing much precision. For improving the accuracy and speeding up the training progress, we introduce the Squeeze-and-excitation (SE) network into the feature extractor. In this paper, we compare the proposed method with some state-of-the-art trackers and analysis their performances. Using our method, a siamese network could be trained with shorter time and less data. The fast processing speed enables combining object tracking with object detection or other tasks in real time.
SpeechNet: A Universal Modularized Model for Speech Processing Tasks
Venue: arXiv cs.CL 2021
Year: 2021

There is a wide variety of speech processing tasks ranging from extracting content information from speech signals to generating speech signals. For different tasks, model networks are usually designed and tuned separately. If a universal model can perform multiple speech processing tasks, some tasks might be improved with the related abilities learned from other tasks. The multi-task learning of a wide variety of speech processing tasks with a universal model has not been studied. This paper proposes a universal modularized model, SpeechNet, which treats all speech processing tasks into a speech/text input and speech/text output format. We select five essential speech processing tasks for multi-task learning experiments with SpeechNet. We show that SpeechNet learns all of the above tasks, and we further analyze which tasks can be improved by other tasks. SpeechNet is modularized and flexible for incorporating more modules, tasks, or training approaches in the future. We release the code and experimental settings to facilitate the research of modularized universal models and multi-task learning of speech processing tasks.
Toward Interactive Modulation for Photo-Realistic Image Restoration
Venue: arXiv cs.CV 2021
Year: 2021

Modulating image restoration level aims to generate a restored image by altering a factor that represents the restoration strength. Previous works mainly focused on optimizing the mean squared reconstruction error, which brings high reconstruction accuracy but lacks finer texture details. This paper presents a Controllable Unet Generative Adversarial Network (CUGAN) to generate high-frequency textures in the modulation tasks. CUGAN consists of two modules -- base networks and condition networks. The base networks comprise a generator and a discriminator. In the generator, we realize the interactive control of restoration levels by tuning the weights of different features from different scales in the Unet architecture. Moreover, we adaptively modulate the intermediate features in the discriminator according to the severity of degradations. The condition networks accept the condition vector (encoded degradation information) as input, then generate modulation parameters for both the generator and the discriminator. During testing, users can control the output effects by tweaking the condition vector. We also provide a smooth transition between GAN and MSE effects by a simple transition method. Extensive experiments demonstrate that the proposed CUGAN achieves excellent performance on image restoration modulation tasks.
Learning Shared Semantic Space for Speech-to-Text Translation
Venue: arXiv cs.CL 2021
Year: 2021

Having numerous potential applications and great impact, end-to-end speech translation (ST) has long been treated as an independent task, failing to fully draw strength from the rapid advances of its sibling - text machine translation (MT). With text and audio inputs represented differently, the modality gap has rendered MT data and its end-to-end models incompatible with their ST counterparts. In observation of this obstacle, we propose to bridge this representation gap with Chimera. By projecting audio and text features to a common semantic representation, Chimera unifies MT and ST tasks and boosts the performance on ST benchmarks, MuST-C and Augmented Librispeech, to a new state-of-the-art. Specifically, Chimera obtains 27.1 BLEU on MuST-C EN-DE, improving the SOTA by a +1.9 BLEU margin. Further experimental analyses demonstrate that the shared semantic space indeed conveys common knowledge between these two tasks and thus paves a new way for augmenting training resources across modalities. Code, data, and resources are available at https://github.com/Glaciohound/Chimera-ST.
Contrastive Learning for Unsupervised Image-to-Image Translation
Venue: arXiv cs.CV 2021
Year: 2021

Image-to-image translation aims to learn a mapping between different groups of visually distinguishable images. While recent methods have shown impressive ability to change even intricate appearance of images, they still rely on domain labels in training a model to distinguish between distinct visual features. Such dependency on labels often significantly limits the scope of applications since consistent and high-quality labels are expensive. Instead, we wish to capture visual features from images themselves and apply them to enable realistic translation without human-generated labels. To this end, we propose an unsupervised image-to-image translation method based on contrastive learning. The key idea is to learn a discriminator that differentiates between distinctive styles and let the discriminator supervise a generator to transfer those styles across images. During training, we randomly sample a pair of images and train the generator to change the appearance of one towards another while keeping the original structure. Experimental results show that our method outperforms the leading unsupervised baselines in terms of visual quality and translation accuracy.
An Intelligent Passive Food Intake Assessment System with Egocentric Cameras
Venue: arXiv cs.CV 2021
Year: 2021

Malnutrition is a major public health concern in low-and-middle-income countries (LMICs). Understanding food and nutrient intake across communities, households and individuals is critical to the development of health policies and interventions. To ease the procedure in conducting large-scale dietary assessments, we propose to implement an intelligent passive food intake assessment system via egocentric cameras particular for households in Ghana and Uganda. Algorithms are first designed to remove redundant images for minimising the storage memory. At run time, deep learning-based semantic segmentation is applied to recognise multi-food types and newly-designed handcrafted features are extracted for further consumed food weight monitoring. Comprehensive experiments are conducted to validate our methods on an in-the-wild dataset captured under the settings which simulate the unique LMIC conditions with participants of Ghanaian and Kenyan origin eating common Ghanaian/Kenyan dishes. To demonstrate the efficacy, experienced dietitians are involved in this research to perform the visual portion size estimation, and their predictions are compared to our proposed method. The promising results have shown that our method is able to reliably monitor food intake and give feedback on users' eating behaviour which provides guidance for dietitians in regular dietary assessment.