OpenRaiser/Intern-Atlas huggingface dataset:
A robotic vision system to measure tree traits
Venue: arXiv cs.RO 2021
Year: 2021

The autonomous measurement of tree traits, such as branching structure, branch diameters, branch lengths, and branch angles, is required for tasks such as robotic pruning of trees as well as structural phenotyping. We propose a robotic vision system called the Robotic System for Tree Shape Estimation (RoTSE) to determine tree traits in field settings. The process is composed of the following stages: image acquisition with a mobile robot unit, segmentation, reconstruction, curve skeletonization, conversion to a graph representation, and then computation of traits. Quantitative and qualitative results on apple trees are shown in terms of accuracy, computation time, and robustness. Compared to ground truth measurements, the RoTSE produced the following estimates: branch diameter (root mean-squared error $2.97$ mm), branch length (root mean-squared error $136.92$ mm), and branch angle (mean-squared error $31.07$ degrees). The average run time was $8.47$ minutes when the voxel resolution was $3$ mm$^3$.
Non-Cooperative Rational Interactive Proofs
Venue: arXiv cs.GT 2021
Year: 2021

Interactive-proof games model the scenario where an honest party interacts with powerful but strategic provers, to elicit from them the correct answer to a computational question. Interactive proofs are increasingly used as a framework to design protocols for computation outsourcing. Existing interactive-proof games largely fall into two categories: either as games of cooperation such as multi-prover interactive proofs and cooperative rational proofs, where the provers work together as a team; or as games of conflict such as refereed games, where the provers directly compete with each other in a zero-sum game. Neither of these extremes truly capture the strategic nature of service providers in outsourcing applications. How to design and analyze non-cooperative interactive proofs is an important open problem. In this paper, we introduce a mechanism-design approach to define a multi-prover interactive-proof model in which the provers are rational and non-cooperative---they act to maximize their expected utility given others' strategies. We define a strong notion of backwards induction as our solution concept to analyze the resulting extensive-form game with imperfect information. Our protocols provide utility gap guarantees, which are analogous to soundness gap in classic interactive proofs. At a high level, a utility gap of u means that the protocol is robust against provers that may not care about a utility loss of 1/u. We fully characterize the complexity of our proof system under different utility gap guarantees. For example, we show that with a polynomial utility gap, the power of non-cooperative rational interactive proofs is exactly P^NEXP.
PSA: A novel optimization algorithm based on survival rules of porcellio scaber
Venue: arXiv cs.NE 2021
Year: 2021

Bio-inspired algorithms such as neural network algorithms and genetic algorithms have received a significant amount of attention in both academic and engineering societies. In this paper, based on the observation of two major survival rules of a species of woodlice, i.e., porcellio scaber, we present an algorithm called the porcellio scaber algorithm (PSA) for solving general unconstrained optimization problems, including differentiable and non-differential ones as well as the case with local optima. Numerical results based on benchmark problems are presented to validate the efficacy of PSA.
Improved Schemes for Asymptotically Optimal Repair of MDS Codes
Venue: arXiv cs.IT 2021
Year: 2021

We consider $(n,k,l)$ MDS codes of length $n$, dimension $k$, and subpacketization $l$ over a finite field $\mathbb{F}$. A codeword of such a code consists of $n$ column-vectors of length $l$ over $\mathbb{F}$, with the property that any $k$ of them suffice to recover the entire codeword. Each of these $n$ vectors may be stored on a separate node in a network. If one of the $n$ nodes fails, we can recover its content by downloading symbols from the surviving nodes, and the total number of symbols downloaded in the worst case is called the repair bandwidth of the code. By the cut-set bound, the repair bandwidth of an $(n,k,l)$ MDS code is at least $l(n{-}1)/(n{-}k)$. There are several constructions of MDS codes whose repair bandwidth meets or asymptotically meets the cut-set bound. For example, Ye and Barg constructed $(n,k,r^{n})$ Reed--Solomon codes that asymptotically meet the cut-set bound, where $r = n-k$. Ye and Barg also constructed optimal-bandwidth and optimal-update $(n,k,r^{n})$ MDS codes. Wang, Tamo, and Bruck constructed optimal-bandwidth $(n, k, r^{n/(r+1)})$ MDS codes, and these codes have the smallest known subpacketization for optimal-bandwidth MDS codes. A key idea in all these constructions is to represent certain integers in base $r$. We show how this technique can be refined to improve the subpacketization of the two MDS code constructions by Ye and Barg, while achieving asymptotically optimal repair bandwidth. Specifically, when $r=s^{m}$ for an integer $s$,we obtain an $(n,k,s^{m+n-1})$ Reed--Solomon code and an optimal-update $(n,k,s^{m+n-1})$ MDS code, both having asymptotically optimal repair bandwidth. We also present an extension of this idea to reduce the subpacketization of the Wang--Tamo--Bruck construction while achieving a repair-by-transfer scheme with asymptotically optimal repair bandwidth.
Toward Multidiversified Ensemble Clustering of High-Dimensional Data: From Subspaces to Metrics and Beyond
Venue: arXiv cs.LG 2021
Year: 2021

The rapid emergence of high-dimensional data in various areas has brought new challenges to current ensemble clustering research. To deal with the curse of dimensionality, recently considerable efforts in ensemble clustering have been made by means of different subspace-based techniques. However, besides the emphasis on subspaces, rather limited attention has been paid to the potential diversity in similarity/dissimilarity metrics. It remains a surprisingly open problem in ensemble clustering how to create and aggregate a large population of diversified metrics, and furthermore, how to jointly investigate the multi-level diversity in the large populations of metrics, subspaces, and clusters in a unified framework. To tackle this problem, this paper proposes a novel multidiversified ensemble clustering approach. In particular, we create a large number of diversified metrics by randomizing a scaled exponential similarity kernel, which are then coupled with random subspaces to form a large set of metric-subspace pairs. Based on the similarity matrices derived from these metric-subspace pairs, an ensemble of diversified base clusterings can thereby be constructed. Further, an entropy-based criterion is utilized to explore the cluster-wise diversity in ensembles, based on which three specific ensemble clustering algorithms are presented by incorporating three types of consensus functions. Extensive experiments are conducted on 30 high-dimensional datasets, including 18 cancer gene expression datasets and 12 image/speech datasets, which demonstrate the superiority of our algorithms over the state-of-the-art. The source code is available at https://github.com/huangdonghere/MDEC.
The complexity of general-valued CSPs seen from the other side
Venue: arXiv cs.CC 2021
Year: 2021

The constraint satisfaction problem (CSP) is concerned with homomorphisms between two structures. For CSPs with restricted left-hand side structures, the results of Dalmau, Kolaitis, and Vardi [CP'02], Grohe [FOCS'03/JACM'07], and Atserias, Bulatov, and Dalmau [ICALP'07] establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by bounded-consistency algorithms (unconditionally) as bounded treewidth modulo homomorphic equivalence. The general-valued constraint satisfaction problem (VCSP) is a generalisation of the CSP concerned with homomorphisms between two valued structures. For VCSPs with restricted left-hand side valued structures, we establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by the $k$-th level of the Sherali-Adams LP hierarchy (unconditionally). We also obtain results on related problems concerned with finding a solution and recognising the tractable cases; the latter has an application in database theory.
End-to-End Optimized Speech Coding with Deep Neural Networks
Venue: arXiv cs.SD 2021
Year: 2021

Modern compression algorithms are often the result of laborious domain-specific research; industry standards such as MP3, JPEG, and AMR-WB took years to develop and were largely hand-designed. We present a deep neural network model which optimizes all the steps of a wideband speech coding pipeline (compression, quantization, entropy coding, and decompression) end-to-end directly from raw speech data -- no manual feature engineering necessary, and it trains in hours. In testing, our DNN-based coder performs on par with the AMR-WB standard at a variety of bitrates (~9kbps up to ~24kbps). It also runs in realtime on a 3.8GhZ Intel CPU.
PriFi: Low-Latency Anonymity for Organizational Networks
Venue: arXiv cs.CR 2021
Year: 2021

Organizational networks are vulnerable to traffic-analysis attacks that enable adversaries to infer sensitive information from the network traffic - even if encryption is used. Typical anonymous communication networks are tailored to the Internet and are poorly suited for organizational networks. We present PriFi, an anonymous communication protocol for LANs, which protects users against eavesdroppers and provides high-performance traffic-analysis resistance. PriFi builds on Dining Cryptographers networks but reduces the high communication latency of prior work via a new client/relay/server architecture, in which a client's packets remain on their usual network path without additional hops, and in which a set of remote servers assist the anonymization process without adding latency. PriFi also solves the challenge of equivocation attacks, which are not addressed by related works, by encrypting the traffic based on the communication history. Our evaluation shows that PriFi introduces a small latency overhead (~100ms for 100 clients) and is compatible with delay-sensitive applications such as VoIP.
Dual-Path Convolutional Image-Text Embeddings with Instance Loss
Venue: arXiv cs.CV 2021
Year: 2021

Matching images and sentences demands a fine understanding of both modalities. In this paper, we propose a new system to discriminatively embed the image and text to a shared visual-textual space. In this field, most existing works apply the ranking loss to pull the positive image / text pairs close and push the negative pairs apart from each other. However, directly deploying the ranking loss is hard for network learning, since it starts from the two heterogeneous features to build inter-modal relationship. To address this problem, we propose the instance loss which explicitly considers the intra-modal data distribution. It is based on an unsupervised assumption that each image / text group can be viewed as a class. So the network can learn the fine granularity from every image/text group. The experiment shows that the instance loss offers better weight initialization for the ranking loss, so that more discriminative embeddings can be learned. Besides, existing works usually apply the off-the-shelf features, i.e., word2vec and fixed visual feature. So in a minor contribution, this paper constructs an end-to-end dual-path convolutional network to learn the image and text representations. End-to-end learning allows the system to directly learn from the data and fully utilize the supervision. On two generic retrieval datasets (Flickr30k and MSCOCO), experiments demonstrate that our method yields competitive accuracy compared to state-of-the-art methods. Moreover, in language based person retrieval, we improve the state of the art by a large margin. The code has been made publicly available.
Time-Limited Toeplitz Operators on Abelian Groups: Applications in Information Theory and Subspace Approximation
Venue: arXiv cs.IT 2021
Year: 2021

Toeplitz operators are fundamental and ubiquitous in signal processing and information theory as models for linear, time-invariant (LTI) systems. Due to the fact that any practical system can access only signals of finite duration, time-limited restrictions of Toeplitz operators are naturally of interest. To provide a unifying treatment of such systems working on different signal domains, we consider time-limited Toeplitz operators on locally compact abelian groups with the aid of the Fourier transform on these groups. In particular, we survey existing results concerning the relationship between the spectrum of a time-limited Toeplitz operator and the spectrum of the corresponding non-time-limited Toeplitz operator. We also develop new results specifically concerning the eigenvalues of time-frequency limiting operators on locally compact abelian groups. Applications of our unifying treatment are discussed in relation to channel capacity and in relation to representation and approximation of signals.
Fruit recognition from images using deep learning
Venue: arXiv cs.CV 2021
Year: 2021

In this paper we introduce a new, high-quality, dataset of images containing fruits. We also present the results of some numerical experiment for training a neural network to detect fruits. We discuss the reason why we chose to use fruits in this project by proposing a few applications that could use this kind of neural network.
Asymptotic Coupling and Its Applications in Information Theory
Venue: arXiv cs.IT 2021
Year: 2021

A coupling of two distributions $P_{X}$ and $P_{Y}$ is a joint distribution $P_{XY}$ with marginal distributions equal to $P_{X}$ and $P_{Y}$. Given marginals $P_{X}$ and $P_{Y}$ and a real-valued function $f$ of the joint distribution $P_{XY}$, what is its minimum over all couplings $P_{XY}$ of $P_{X}$ and $P_{Y}$? We study the asymptotics of such coupling problems with different $f$'s and with $X$ and $Y$ replaced by $X^{n}=(X_{1},\ldots,X_{n})$ and $Y^{n}=(Y_{1},\ldots,Y_{n})$ where $X_{i}$ and $Y_{i}$ are i.i.d.\ copies of random variables $X$ and $Y$ with distributions $P_{X}$ and $P_{Y}$ respectively. These include the maximal coupling, minimum distance coupling, maximal guessing coupling, and minimum entropy coupling problems. We characterize the limiting values of these coupling problems as $n$ tends to infinity. We show that they typically converge at least exponentially fast to their limits. Moreover, for the problems of maximal coupling and minimum excess-distance probability coupling, we also characterize (or bound) the optimal convergence rates (exponents). Furthermore, for the maximal guessing coupling problem we show that it is equivalent to the distribution approximation problem. Therefore, some existing results for the latter problem can be used to derive the asymptotics of the maximal guessing coupling problem. We also study the asymptotics of the maximal guessing coupling problem for two \emph{general} sources and a generalization of this problem, named the \emph{maximal guessing coupling through a channel problem}. We apply the preceding results to several new information-theoretic problems, including exact intrinsic randomness, exact resolvability, channel capacity with input distribution constraint, and perfect stealth and secrecy communication.
Community Detection in Partially Observable Social Networks
Venue: arXiv cs.SI 2021
Year: 2021

The discovery of community structures in social networks has gained significant attention since it is a fundamental problem in understanding the networks' topology and functions. However, most social network data are collected from partially observable networks with both missing nodes and edges. In this paper, we address a new problem of detecting overlapping community structures in the context of such an incomplete network, where communities in the network are allowed to overlap since nodes belong to multiple communities at once. To solve this problem, we introduce KroMFac, a new framework that conducts community detection via regularized nonnegative matrix factorization (NMF) based on the Kronecker graph model. Specifically, from an inferred Kronecker generative parameter matrix, we first estimate the missing part of the network. As our major contribution to the proposed framework, to improve community detection accuracy, we then characterize and select influential nodes (which tend to have high degrees) by ranking, and add them to the existing graph. Finally, we uncover the community structures by solving the regularized NMF-aided optimization problem in terms of maximizing the likelihood of the underlying graph. Furthermore, adopting normalized mutual information (NMI), we empirically show superiority of our KroMFac approach over two baseline schemes by using both synthetic and real-world networks.
How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
Venue: arXiv cs.LG 2021
Year: 2021

Stochastic gradient descent (SGD) gives an optimal convergence rate when minimizing convex stochastic objectives $f(x)$. However, in terms of making the gradients small, the original SGD does not give an optimal rate, even when $f(x)$ is convex. If $f(x)$ is convex, to find a point with gradient norm $\varepsilon$, we design an algorithm SGD3 with a near-optimal rate $\tilde{O}(\varepsilon^{-2})$, improving the best known rate $O(\varepsilon^{-8/3})$ of [18]. If $f(x)$ is nonconvex, to find its $\varepsilon$-approximate local minimum, we design an algorithm SGD5 with rate $\tilde{O}(\varepsilon^{-3.5})$, where previously SGD variants only achieve $\tilde{O}(\varepsilon^{-4})$ [6, 15, 33]. This is no slower than the best known stochastic version of Newton's method in all parameter regimes [30].
BUSIS: A Benchmark for Breast Ultrasound Image Segmentation
Venue: arXiv cs.CV 2021
Year: 2021

Breast ultrasound (BUS) image segmentation is challenging and critical for BUS Comput-er-Aided Diagnosis (CAD) systems. Many BUS segmentation approaches have been studied in the last two decades, but the performances of most approaches have been assessed using relatively small private datasets with different quantitative metrics, which results in a discrepancy in performance comparison. Therefore, there is a pressing need for building a benchmark to compare existing methods using a public dataset objectively, to determine the performance of the best breast tumor segmentation algorithm available today, and to investigate what segmentation strategies are valuable in clinical practice and theoretical study. In this work, a benchmark for B-mode breast ultrasound image segmentation is presented. In the benchmark, 1) we collected 562 breast ultrasound images, prepared a software tool, and involved four radiologists in obtaining accurate annotations through standardized procedures; 2) we extensively compared the performance of sixteen state-of-the-art segmentation methods and discussed their advantages and disadvantages; 3) we proposed a set of valuable quantitative metrics to evaluate both semi-automatic and fully automatic segmentation approaches; and 4) the successful segmentation strategies and possible future improvements are discussed in details.
MINE: Mutual Information Neural Estimation
Venue: arXiv cs.LG 2021
Year: 2021

We argue that the estimation of mutual information between high dimensional continuous random variables can be achieved by gradient descent over neural networks. We present a Mutual Information Neural Estimator (MINE) that is linearly scalable in dimensionality as well as in sample size, trainable through back-prop, and strongly consistent. We present a handful of applications on which MINE can be used to minimize or maximize mutual information. We apply MINE to improve adversarially trained generative models. We also use MINE to implement Information Bottleneck, applying it to supervised classification; our results demonstrate substantial improvement in flexibility and performance in these settings.
Robots as Powerful Allies for the Study of Embodied Cognition from the Bottom Up
Venue: arXiv cs.AI 2021
Year: 2021

A large body of compelling evidence has been accumulated demonstrating that embodiment - the agent's physical setup, including its shape, materials, sensors and actuators - is constitutive for any form of cognition and as a consequence, models of cognition need to be embodied. In contrast to methods from empirical sciences to study cognition, robots can be freely manipulated and virtually all key variables of their embodiment and control programs can be systematically varied. As such, they provide an extremely powerful tool of investigation. We present a robotic bottom-up or developmental approach, focusing on three stages: (a) low-level behaviors like walking and reflexes, (b) learning regularities in sensorimotor spaces, and (c) human-like cognition. We also show that robotic based research is not only a productive path to deepening our understanding of cognition, but that robots can strongly benefit from human-like cognition in order to become more autonomous, robust, resilient, and safe.
A Cyber Science Based Ontology for Artificial General Intelligence Containment
Venue: arXiv cs.AI 2021
Year: 2021

The development of artificial general intelligence is considered by many to be inevitable. What such intelligence does after becoming aware is not so certain. To that end, research suggests that the likelihood of artificial general intelligence becoming hostile to humans is significant enough to warrant inquiry into methods to limit such potential. Thus, containment of artificial general intelligence is a timely and meaningful research topic. While there is limited research exploring possible containment strategies, such work is bounded by the underlying field the strategies draw upon. Accordingly, we set out to construct an ontology to describe necessary elements in any future containment technology. Using existing academic literature, we developed a single domain ontology containing five levels, 32 codes, and 32 associated descriptors. Further, we constructed ontology diagrams to demonstrate intended relationships. We then identified humans, AGI, and the cyber world as novel agent objects necessary for future containment activities. Collectively, the work addresses three critical gaps: (a) identifying and arranging fundamental constructs; (b) situating AGI containment within cyber science; and (c) developing scientific rigor within the field.
CoCoS: Fast and Accurate Distributed Triangle Counting in Graph Streams
Venue: arXiv cs.DB 2021
Year: 2021

Given a graph stream, how can we estimate the number of triangles in it using multiple machines with limited storage? Specifically, how should edges be processed and sampled across the machines for rapid and accurate estimation? The count of triangles (i.e., cliques of size three) has proven useful in numerous applications, including anomaly detection, community detection, and link recommendation. For triangle counting in large and dynamic graphs, recent work has focused largely on streaming algorithms and distributed algorithms but little on their combinations for "the best of both worlds". In this work, we propose CoCoS, a fast and accurate distributed streaming algorithm for estimating the counts of global triangles (i.e., all triangles) and local triangles incident to each node. Making one pass over the input stream, COCOS carefully processes and stores the edges across multiple machines so that the redundant use of computational and storage resources is minimized. Compared to baselines, CoCoS is (a) Accurate: giving up to 39X smaller estimation error, (b) Fast: up to 10.4X faster, scaling linearly with the size of the input stream, and (c) Theoretically sound: yielding unbiased estimates.