OpenRaiser/Intern-Atlas huggingface dataset:
Smaller ACC0 Circuits for Symmetric Functions
Venue: arXiv cs.CC 2021
Year: 2021

What is the power of constant-depth circuits with $MOD_m$ gates, that can count modulo $m$? Can they efficiently compute MAJORITY and other symmetric functions? When $m$ is a constant prime power, the answer is well understood: Razborov and Smolensky proved in the 1980s that MAJORITY and $MOD_m$ require super-polynomial-size $MOD_q$ circuits, where $q$ is any prime power not dividing $m$. However, relatively little is known about the power of $MOD_m$ circuits for non-prime-power $m$. For example, it is still open whether every problem in $EXP$ can be computed by depth-$3$ circuits of polynomial size and only $MOD_6$ gates. We shed some light on the difficulty of proving lower bounds for $MOD_m$ circuits, by giving new upper bounds. We construct $MOD_m$ circuits computing symmetric functions with non-prime power $m$, with size-depth tradeoffs that beat the longstanding lower bounds for $AC^0[m]$ circuits for prime power $m$. Our size-depth tradeoff circuits have essentially optimal dependence on $m$ and $d$ in the exponent, under a natural circuit complexity hypothesis. For example, we show for every $\varepsilon > 0$ that every symmetric function can be computed with depth-3 $MOD_m$ circuits of $\exp(O(n^{\varepsilon}))$ size, for a constant $m$ depending only on $\varepsilon > 0$. That is, depth-$3$ $CC^0$ circuits can compute any symmetric function in \emph{subexponential} size. This demonstrates a significant difference in the power of depth-$3$ $CC^0$ circuits, compared to other models: for certain symmetric functions, depth-$3$ $AC^0$ circuits require $2^{Ω(\sqrt{n})}$ size [Håstad 1986], and depth-$3$ $AC^0[p^k]$ circuits (for fixed prime power $p^k$) require $2^{Ω(n^{1/6})}$ size [Smolensky 1987]. Even for depth-two $MOD_p \circ MOD_m$ circuits, $2^{Ω(n)}$ lower bounds were known [Barrington Straubing Thérien 1990].
A Topological-Framework to Improve Analysis of Machine Learning Model Performance
Venue: arXiv cs.LG 2021
Year: 2021

As both machine learning models and the datasets on which they are evaluated have grown in size and complexity, the practice of using a few summary statistics to understand model performance has become increasingly problematic. This is particularly true in real-world scenarios where understanding model failure on certain subpopulations of the data is of critical importance. In this paper we propose a topological framework for evaluating machine learning models in which a dataset is treated as a "space" on which a model operates. This provides us with a principled way to organize information about model performance at both the global level (over the entire test set) and also the local level (on specific subpopulations). Finally, we describe a topological data structure, presheaves, which offer a convenient way to store and analyze model performance between different subpopulations.
An Empirical Study of Data Constraint Implementations in Java
Venue: arXiv cs.SE 2021
Year: 2021

Software systems are designed according to guidelines and constraints defined by business rules. Some of these constraints define the allowable or required values for data handled by the systems. These data constraints usually originate from the problem domain (e.g., regulations), and developers must write code that enforces them. Understanding how data constraints are implemented is essential for testing, debugging, and software change. Unfortunately, there are no widely-accepted guidelines or best practices on how to implement data constraints. This paper presents an empirical study that investigates how data constraints are implemented in Java. We study the implementation of 187 data constraints extracted from the documentation of eight real-world Java software systems. First, we perform a qualitative analysis of the textual description of data constraints and identify four data constraint types. Second, we manually identify the implementations of these data constraints and reveal that they can be grouped into 30 implementation patterns. The analysis of these implementation patterns indicates that developers prefer a handful of patterns when implementing data constraints and deviations from these patterns are associated with unusual implementation decisions or code smells. Third, we develop a tool-assisted protocol that allows us to identify 256 additional trace links for the data constraints implemented using the 13 most common patterns. We find that almost half of these data constraints have multiple enforcing statements, which are code clones of different types.
Local-to-Global Self-Attention in Vision Transformers
Venue: arXiv cs.CV 2021
Year: 2021

Transformers have demonstrated great potential in computer vision tasks. To avoid dense computations of self-attentions in high-resolution visual data, some recent Transformer models adopt a hierarchical design, where self-attentions are only computed within local windows. This design significantly improves the efficiency but lacks global feature reasoning in early stages. In this work, we design a multi-path structure of the Transformer, which enables local-to-global reasoning at multiple granularities in each stage. The proposed framework is computationally efficient and highly effective. With a marginal increasement in computational overhead, our model achieves notable improvements in both image classification and semantic segmentation. Code is available at https://github.com/ljpadam/LG-Transformer
Anomaly Detection in Residential Video Surveillance on Edge Devices in IoT Framework
Venue: arXiv cs.CV 2021
Year: 2021

Intelligent resident surveillance is one of the most essential smart community services. The increasing demand for security needs surveillance systems to be able to detect anomalies in surveillance scenes. Employing high-capacity computational devices for intelligent surveillance in residential societies is costly and not feasible. Therefore, we propose anomaly detection for intelligent surveillance using CPU-only edge devices. A modular framework to capture object-level inferences and tracking is developed. To cope with partial occlusions, posture deformations, and complex scenes, we employed feature encoding and trajectory association governed by two metrices complementing to each other. The elements of an anomaly detection framework are optimized to run on CPU-only edge devices with sufficient frames per second (FPS). The experimental results indicate the proposed method is feasible and achieves satisfactory results in real-life scenarios.
Dirichlet polynomials and entropy
Venue: arXiv cs.IT 2021
Year: 2021

A Dirichlet polynomial $d$ in one variable ${\mathcal{y}}$ is a function of the form $d({\mathcal{y}})=a_n n^{\mathcal{y}}+\cdots+a_22^{\mathcal{y}}+a_11^{\mathcal{y}}+a_00^{\mathcal{y}}$ for some $n,a_0,\ldots,a_n\in\mathbb{N}$. We will show how to think of a Dirichlet polynomial as a set-theoretic bundle, and thus as an empirical distribution. We can then consider the Shannon entropy $H(d)$ of the corresponding probability distribution, and we define its length (or, classically, its perplexity) by $L(d)=2^{H(d)}$. On the other hand, we will define a rig homomorphism $h\colon\mathsf{Dir}\to\mathsf{Rect}$ from the rig of Dirichlet polynomials to the so-called rectangle rig, whose underlying set is $\mathbb{R}_{\geq0}\times\mathbb{R}_{\geq0}$ and whose additive structure involves the weighted geometric mean; we write $h(d)=(A(d),W(d))$, and call the two components area and width (respectively). The main result of this paper is the following: the rectangle-area formula $A(d)=L(d)W(d)$ holds for any Dirichlet polynomial $d$. In other words, the entropy of an empirical distribution can be calculated entirely in terms of the homomorphism $h$ applied to its corresponding Dirichlet polynomial. We also show that similar results hold for the cross entropy.
SynPick: A Dataset for Dynamic Bin Picking Scene Understanding
Venue: arXiv cs.RO 2021
Year: 2021

We present SynPick, a synthetic dataset for dynamic scene understanding in bin-picking scenarios. In contrast to existing datasets, our dataset is both situated in a realistic industrial application domain -- inspired by the well-known Amazon Robotics Challenge (ARC) -- and features dynamic scenes with authentic picking actions as chosen by our picking heuristic developed for the ARC 2017. The dataset is compatible with the popular BOP dataset format. We describe the dataset generation process in detail, including object arrangement generation and manipulation simulation using the NVIDIA PhysX physics engine. To cover a large action space, we perform untargeted and targeted picking actions, as well as random moving actions. To establish a baseline for object perception, a state-of-the-art pose estimation approach is evaluated on the dataset. We demonstrate the usefulness of tracking poses during manipulation instead of single-shot estimation even with a naive filtering approach. The generator source code and dataset are publicly available.
Inference of Shape Expression Schemas Typed RDF Graphs
Venue: arXiv cs.DB 2021
Year: 2021

We consider the problem of constructing a Shape Expression Schema (ShEx) that describes the structure of a given input RDF graph. We employ the framework of grammatical inference, where the objective is to find an inference algorithm that is both sound i.e., always producing a schema that validates the input RDF graph, and complete i.e., able to produce any schema, within a given class of schemas, provided that a sufficiently informative input graph is presented. We study the case where the input graph is typed i.e., every node is given with its types. We limit our attention to a practical fragment ShEx0 of Shape Expressions Schemas that has an equivalent graphical representation in the form of shape graphs. We investigate the problem of constructing a canonical representative of a given shape graph. Finally, we present a sound and complete algorithm for shape graphs thus showing that ShEx0 is learnable from typed graphs.
Anatomy of Domain Shift Impact on U-Net Layers in MRI Segmentation
Venue: arXiv cs.CV 2021
Year: 2021

Domain Adaptation (DA) methods are widely used in medical image segmentation tasks to tackle the problem of differently distributed train (source) and test (target) data. We consider the supervised DA task with a limited number of annotated samples from the target domain. It corresponds to one of the most relevant clinical setups: building a sufficiently accurate model on the minimum possible amount of annotated data. Existing methods mostly fine-tune specific layers of the pretrained Convolutional Neural Network (CNN). However, there is no consensus on which layers are better to fine-tune, e.g. the first layers for images with low-level domain shift or the deeper layers for images with high-level domain shift. To this end, we propose SpotTUnet - a CNN architecture that automatically chooses the layers which should be optimally fine-tuned. More specifically, on the target domain, our method additionally learns the policy that indicates whether a specific layer should be fine-tuned or reused from the pretrained network. We show that our method performs at the same level as the best of the nonflexible fine-tuning methods even under the extreme scarcity of annotated data. Secondly, we show that SpotTUnet policy provides a layer-wise visualization of the domain shift impact on the network, which could be further used to develop robust domain generalization methods. In order to extensively evaluate SpotTUnet performance, we use a publicly available dataset of brain MR images (CC359), characterized by explicit domain shift. We release a reproducible experimental pipeline.
Analysis of Smooth Heaps and Slim Heaps
Venue: arXiv cs.DS 2021
Year: 2021

The smooth heap is a recently introduced self-adjusting heap [Kozma, Saranurak, 2018] similar to the pairing heap [Fredman, Sedgewick, Sleator, Tarjan, 1986]. The smooth heap was obtained as a heap-counterpart of Greedy BST, a binary search tree updating strategy conjectured to be \emph{instance-optimal} [Lucas, 1988], [Munro, 2000]. Several adaptive properties of smooth heaps follow from this connection; moreover, the smooth heap itself has been conjectured to be instance-optimal within a certain class of heaps. Nevertheless, no general analysis of smooth heaps has existed until now, the only previous analysis showing that, when used in \emph{sorting mode} ($n$ insertions followed by $n$ delete-min operations), smooth heaps sort $n$ numbers in $O(n\lg n)$ time. In this paper we describe a simpler variant of the smooth heap we call the \emph{slim heap}. We give a new, self-contained analysis of smooth heaps and slim heaps in unrestricted operation, obtaining amortized bounds that match the best bounds known for self-adjusting heaps. Previous experimental work has found the pairing heap to dominate other data structures in this class in various settings. Our tests show that smooth heaps and slim heaps are competitive with pairing heaps, outperforming them in some cases, while being comparably easy to implement.
Deep Fiber Clustering: Anatomically Informed Unsupervised Deep Learning for Fast and Effective White Matter Parcellation
Venue: arXiv cs.CV 2021
Year: 2021

White matter fiber clustering (WMFC) enables parcellation of white matter tractography for applications such as disease classification and anatomical tract segmentation. However, the lack of ground truth and the ambiguity of fiber data (the points along a fiber can equivalently be represented in forward or reverse order) pose challenges to this task. We propose a novel WMFC framework based on unsupervised deep learning. We solve the unsupervised clustering problem as a self-supervised learning task. Specifically, we use a convolutional neural network to learn embeddings of input fibers, using pairwise fiber distances as pseudo annotations. This enables WMFC that is insensitive to fiber point ordering. In addition, anatomical coherence of fiber clusters is improved by incorporating brain anatomical segmentation data. The proposed framework enables outlier removal in a natural way by rejecting fibers with low cluster assignment probability. We train and evaluate our method using 200 datasets from the Human Connectome Project. Results demonstrate superior performance and efficiency of the proposed approach.
On the Performance of Pipelined HotStuff
Venue: arXiv cs.DC 2021
Year: 2021

HotStuff is a state-of-the-art Byzantine fault-tolerant consensus protocol. It can be pipelined to build large-scale blockchains. One of its variants called LibraBFT is adopted in Facebook's Libra blockchain. Although it is well known that pipelined HotStuff is secure against up to $1/3$ of Byzantine nodes, its performance in terms of throughput and delay is still under-explored. In this paper, we develop a multi-metric evaluation framework to quantitatively analyze pipelined \mbox{HotStuff's performance} with respect to its chain growth rate, chain quality, and latency. We then propose two attack strategies and evaluate their effects on the performance of pipelined HotStuff. Our analysis shows that the chain growth rate (resp, chain quality) of pipelined HotStuff under our attacks can drop to as low as 4/9 (resp, 12/17) of that without attacks when $1/3$ nodes are Byzantine. As another application, we use our framework to evaluate certain engineering optimizations adopted by LibraBFT. We find that these optimizations make the system more vulnerable to our attacks than the original pipelined HotStuff. Finally, we provide two countermeasures to thwart these attacks. We hope that our studies can shed light on the rigorous understanding of the state-of-the-art pipelined HotStuff protocol as well as its variants.
Designing Recommender Systems to Depolarize
Venue: arXiv cs.IR 2021
Year: 2021

Polarization is implicated in the erosion of democracy and the progression to violence, which makes the polarization properties of large algorithmic content selection systems (recommender systems) a matter of concern for peace and security. While algorithm-driven social media does not seem to be a primary driver of polarization at the country level, it could be a useful intervention point in polarized societies. This paper examines algorithmic depolarization interventions with the goal of conflict transformation: not suppressing or eliminating conflict but moving towards more constructive conflict. Algorithmic intervention is considered at three stages: which content is available (moderation), how content is selected and personalized (ranking), and content presentation and controls (user interface). Empirical studies of online conflict suggest that the exposure diversity intervention proposed as an antidote to "filter bubbles" can be improved and can even worsen polarization under some conditions. Using civility metrics in conjunction with diversity in content selection may be more effective. However, diversity-based interventions have not been tested at scale and may not work in the diverse and dynamic contexts of real platforms. Instead, intervening in platform polarization dynamics will likely require continuous monitoring of polarization metrics, such as the widely used "feeling thermometer." These metrics can be used to evaluate product features, and potentially engineered as algorithmic objectives. It may further prove necessary to include polarization measures in the objective functions of recommender algorithms to prevent optimization processes from creating conflict as a side effect.
STR-GODEs: Spatial-Temporal-Ridership Graph ODEs for Metro Ridership Prediction
Venue: arXiv cs.LG 2021
Year: 2021

The metro ridership prediction has always received extensive attention from governments and researchers. Recent works focus on designing complicated graph convolutional recurrent network architectures to capture spatial and temporal patterns. These works extract the information of spatial dimension well, but the limitation of temporal dimension still exists. We extended Neural ODE algorithms to the graph network and proposed the STR-GODEs network, which can effectively learn spatial, temporal, and ridership correlations without the limitation of dividing data into equal-sized intervals on the timeline. While learning the spatial relations and the temporal correlations, we modify the GODE-RNN cell to obtain the ridership feature and hidden states. Ridership information and its hidden states are added to the GODESolve to reduce the error accumulation caused by long time series in prediction. Extensive experiments on two large-scale datasets demonstrate the efficacy and robustness of our model.
Some Properties of Length Rate Quotient Shapers
Venue: arXiv cs.PF 2021
Year: 2021

Length Rate Quotient (LRQ) is the first algorithm of interleaved shaping -- a novel concept proposed to provide per-flow shaping for a flow aggregate without per-flow queuing. This concept has been adopted by Time-Sensitive Networking (TSN) and Deterministic Networking (DetNet). An appealing property of interleaved shaping is that, when an interleaved shaper is appended to a FIFO system, it does not increase the worst-case delay of the system. Based on this "shaping-for-free" property, an approach has been introduced to deliver bounded end-to-end latency. Specifically, at each output link of a node, class-based aggregate scheduling is used together with one interleaved shaper per-input link and per-class, and the interleaved shaper re-shapes every flow to its initial traffic constraint. In this paper, we investigate other properties of interleaved LRQ shapers, particularly as stand-alone elements. In addition, under per-flow setting, we also investigate per-flow LRQ based flow aggregation and derive its properties. The analysis focuses directly on the timing of operations, such as shaping and scheduling, in the network. This timing based method can be found in the Guaranteed Rate (GR) server model and more generally the max-plus branch of network calculus. With the derived properties, we not only show that an improved end-to-end latency bound can be obtained for the current approach, but also demonstrate with two examples that new approaches may be devised. End-to-end delay bounds for the three approaches are derived and compared. As a highlight, the two new approaches do not require different node architectures in allocating (shaping / scheduling) queues, which implies that they can be readily adapted for use in TSN and DetNet. This together with the derived properties of LRQ shed new insights on providing the TSN / DetNet qualities of service.
Similarity Guided Deep Face Image Retrieval
Venue: arXiv cs.CV 2021
Year: 2021

Face image retrieval, which searches for images of the same identity from the query input face image, is drawing more attention as the size of the image database increases rapidly. In order to conduct fast and accurate retrieval, a compact hash code-based methods have been proposed, and recently, deep face image hashing methods with supervised classification training have shown outstanding performance. However, classification-based scheme has a disadvantage in that it cannot reveal complex similarities between face images into the hash code learning. In this paper, we attempt to improve the face image retrieval quality by proposing a Similarity Guided Hashing (SGH) method, which gently considers self and pairwise-similarity simultaneously. SGH employs various data augmentations designed to explore elaborate similarities between face images, solving both intra and inter identity-wise difficulties. Extensive experimental results on the protocols with existing benchmarks and an additionally proposed large scale higher resolution face image dataset demonstrate that our SGH delivers state-of-the-art retrieval performance.
Blending Pruning Criteria for Convolutional Neural Networks
Venue: arXiv cs.CV 2021
Year: 2021

The advancement of convolutional neural networks (CNNs) on various vision applications has attracted lots of attention. Yet the majority of CNNs are unable to satisfy the strict requirement for real-world deployment. To overcome this, the recent popular network pruning is an effective method to reduce the redundancy of the models. However, the ranking of filters according to their "importance" on different pruning criteria may be inconsistent. One filter could be important according to a certain criterion, while it is unnecessary according to another one, which indicates that each criterion is only a partial view of the comprehensive "importance". From this motivation, we propose a novel framework to integrate the existing filter pruning criteria by exploring the criteria diversity. The proposed framework contains two stages: Criteria Clustering and Filters Importance Calibration. First, we condense the pruning criteria via layerwise clustering based on the rank of "importance" score. Second, within each cluster, we propose a calibration factor to adjust their significance for each selected blending candidates and search for the optimal blending criterion via Evolutionary Algorithm. Quantitative results on the CIFAR-100 and ImageNet benchmarks show that our framework outperforms the state-of-the-art baselines, regrading to the compact model performance after pruning.