Search

Modern manipulators are acclaimed for their precision but often struggle to operate in confined spaces. This limitation has driven the development of hyper-redundant and continuum robots. While these present unique advantages, they face challenges in, for instance, weight, mechanical complexity, modeling and costs. The Minimally Actuated Serial Robot (MASR) has been proposed as a light-weight, low-cost and simpler alternative where passive joints are actuated with a Mobile Actuator (MA) moving along the arm. Yet, Inverse Kinematics (IK) and a general motion planning algorithm for the MASR have not be addressed. In this letter, we propose the MASR-RRT* motion planning algorithm specifically developed for the unique kinematics of MASR. The main component of the algorithm is a data-based model for solving the IK problem while considering minimal traverse of the MA. The model is trained solely using the forward kinematics of the MASR and does not require real data. With the model as a local-connection mechanism, MASR-RRT* minimizes a cost function expressing the action time. In a comprehensive analysis, we show that MASR-RRT* is superior in performance to the straight-forward implementation of the standard RRT*. Experiments on a real robot in different environments with obstacles validate the proposed algorithm.

In the interdependent values (IDV) model introduced by Milgrom and Weber [1982], agents have private signals that capture their information about different social alternatives, and the valuation of every agent is a function of all agent signals. While interdependence has been mainly studied for auctions, it is extremely relevant for a large variety of social choice settings, including the canonical setting of public projects. The IDV model is very challenging relative to standard independent private values, and welfare guarantees have been achieved through two alternative conditions known as {\em single-crossing} and {\em submodularity over signals (SOS)}. In either case, the existing theory falls short of solving the public projects setting. Our contribution is twofold: (i) We give a workable characterization of truthfulness for IDV public projects for the largest class of valuations for which such a characterization exists, and term this class \emph{decomposable valuations}; (ii) We provide possibility and impossibility results for welfare approximation in public projects with SOS valuations. Our main impossibility result is that, in contrast to auctions, no universally truthful mechanism performs better for public projects with SOS valuations than choosing a project at random. Our main positive result applies to {\em excludable} public projects with SOS, for which we establish a constant factor approximation similar to auctions. Our results suggest that exclusion may be a key tool for achieving welfare guarantees in the IDV model.

Representation knowledge distillation aims at transferring rich information from one model to another. Common approaches for representation distillation mainly focus on the direct minimization of distance metrics between the models' embedding vectors. Such direct methods may be limited in transferring high-order dependencies embedded in the representation vectors, or in handling the capacity gap between the teacher and student models. Moreover, in standard knowledge distillation, the teacher is trained without awareness of the student's characteristics and capacity. In this paper, we explore two mechanisms for enhancing representation distillation using classifier sharing between the teacher and student. We first investigate a simple scheme where the teacher's classifier is connected to the student backbone, acting as an additional classification head. Then, we propose a student-aware mechanism that asks to tailor the teacher model to a student with limited capacity by training the teacher with a temporary student's head. We analyze and compare these two mechanisms and show their effectiveness on various datasets and tasks, including image classification, fine-grained classification, and face verification. In particular, we achieve state-of-the-art results for face verification on the IJB-C dataset for a MobileFaceNet model: TAR@(FAR=1e-5)=93.7\%. Code is available at https://github.com/Alibaba-MIIL/HeadSharingKD.

In this paper, we introduce ML-Decoder, a new attention-based classification head. ML-Decoder predicts the existence of class labels via queries, and enables better utilization of spatial data compared to global average pooling. By redesigning the decoder architecture, and using a novel group-decoding scheme, ML-Decoder is highly efficient, and can scale well to thousands of classes. Compared to using a larger backbone, ML-Decoder consistently provides a better speed-accuracy trade-off. ML-Decoder is also versatile - it can be used as a drop-in replacement for various classification heads, and generalize to unseen classes when operated with word queries. Novel query augmentations further improve its generalization ability. Using ML-Decoder, we achieve state-of-the-art results on several classification tasks: on MS-COCO multi-label, we reach 91.4% mAP; on NUS-WIDE zero-shot, we reach 31.1% ZSL mAP; and on ImageNet single-label, we reach with vanilla ResNet50 backbone a new top score of 80.7%, without extra data or distillation. Public code is available at: https://github.com/Alibaba-MIIL/ML_Decoder

Large-scale multi-label classification datasets are commonly, and perhaps inevitably, partially annotated. That is, only a small subset of labels are annotated per sample. Different methods for handling the missing labels induce different properties on the model and impact its accuracy. In this work, we analyze the partial labeling problem, then propose a solution based on two key ideas. First, un-annotated labels should be treated selectively according to two probability quantities: the class distribution in the overall dataset and the specific label likelihood for a given data sample. We propose to estimate the class distribution using a dedicated temporary model, and we show its improved efficiency over a naive estimation computed using the dataset's partial annotations. Second, during the training of the target model, we emphasize the contribution of annotated labels over originally un-annotated labels by using a dedicated asymmetric loss. With our novel approach, we achieve state-of-the-art results on OpenImages dataset (e.g. reaching 87.3 mAP on V6). In addition, experiments conducted on LVIS and simulated-COCO demonstrate the effectiveness of our approach. Code is available at https://github.com/Alibaba-MIIL/PartialLabelingCSL.

We study the {\em Budgeted Dominating Set} (BDS) problem on uncertain graphs, namely, graphs with a probability distribution $p$ associated with the edges, such that an edge $e$ exists in the graph with probability $p(e)$. The input to the problem consists of a vertex-weighted uncertain graph $\G=(V, E, p, \omega)$ and an integer {\em budget} (or {\em solution size}) $k$, and the objective is to compute a vertex set $S$ of size $k$ that maximizes the expected total domination (or total weight) of vertices in the closed neighborhood of $S$. We refer to the problem as the {\em Probabilistic Budgeted Dominating Set}~(PBDS) problem and present the following results. \begin{enumerate} \dnsitem We show that the PBDS problem is NP-complete even when restricted to uncertain {\em trees} of diameter at most four. This is in sharp contrast with the well-known fact that the BDS problem is solvable in polynomial time in trees. We further show that PBDS is \wone-hard for the budget parameter $k$, and under the {\em Exponential time hypothesis} it cannot be solved in $n^{o(k)}$ time. \item We show that if one is willing to settle for $(1-\epsilon)$ approximation, then there exists a PTAS for PBDS on trees. Moreover, for the scenario of uniform edge-probabilities, the problem can be solved optimally in polynomial time. \item We consider the parameterized complexity of the PBDS problem, and show that Uni-PBDS (where all edge probabilities are identical) is \wone-hard for the parameter pathwidth. On the other hand, we show that it is FPT in the combined parameters of the budget $k$ and the treewidth. \item Finally, we extend some of our parameterized results to planar and apex-minor-free graphs. \end{enumerate}

Consider a seller that intends to auction some item. The seller can invest money and effort in advertising in different market segments in order to recruit $n$ bidders to the auction. Alternatively, the seller can have a much cheaper and focused marketing operation and recruit the same number of bidders from a single market segment. Which marketing operation should the seller choose? More formally, let $D=\{\mathcal D_1,\ldots, \mathcal D_n\}$ be a set of distributions. Our main result shows that there is always $\mathcal D_i\in D$ such that the revenue that can be extracted from $n$ bidders, where the value of each is independently drawn from $\mathcal D_i$, is at least $\frac 1 2 \cdot (1-\frac 1 e)$ of the revenue that can be obtained by any possible mix of bidders, where the value of each bidder is drawn from some (possibly different) distribution that belongs to $D$. We next consider situations in which the auctioneer cannot use the optimal auction and is required to use a second price auction. We show that there is always $\mathcal D_i\in D$ such that if the value of all bidders is independently drawn from $\mathcal D_i$ then running a second price auction guarantees a constant fraction of the revenue that can be obtained by a second-price auction by any possible mix of bidders. Finally, we show that for any $\varepsilon>0$ there exists a function $f$ that depends only on $\varepsilon$ (in particular, the function does not depend on $n$ or on the set $D$), such that recruiting $n$ bidders which have at most $f(\varepsilon)$ different distributions, all from $D$, guarantees $(1-\varepsilon)$-fraction of the revenue that can be obtained by a second-price auction by any possible mix of bidders.

Training a neural network model for recognizing multiple labels associated with an image, including identifying unseen labels, is challenging, especially for images that portray numerous semantically diverse labels. As challenging as this task is, it is an essential task to tackle since it represents many real-world cases, such as image retrieval of natural images. We argue that using a single embedding vector to represent an image, as commonly practiced, is not sufficient to rank both relevant seen and unseen labels accurately. This study introduces an end-to-end model training for multi-label zero-shot learning that supports semantic diversity of the images and labels. We propose to use an embedding matrix having principal embedding vectors trained using a tailored loss function. In addition, during training, we suggest up-weighting in the loss function image samples presenting higher semantic diversity to encourage the diversity of the embedding matrix. Extensive experiments show that our proposed method improves the zero-shot model's quality in tag-based image retrieval achieving SoTA results on several common datasets (NUS-Wide, COCO, Open Images).

The existence of EFX allocations is a major open problem in fair division, even for additive valuations. The current state of the art is that no setting where EFX allocations are impossible is known, and EFX is known to exist for ($i$) agents with identical valuations, ($ii$) 2 agents, ($iii$) 3 agents with additive valuations, ($iv$) agents with one of two additive valuations and ($v$) agents with two-valued instances. It is also known that EFX exists if one can leave $n-1$ items unallocated, where $n$ is the number of agents. We develop new techniques that allow us to push the boundaries of the enigmatic EFX problem beyond these known results, and, arguably, to simplify proofs of earlier results. Our main results are ($i$) every setting with 4 additive agents admits an EFX allocation that leaves at most a single item unallocated, ($ii$) every setting with $n$ additive valuations has an EFX allocation with at most $n-2$ unallocated items. Moreover, all of our results extend beyond additive valuations to all nice cancelable valuations (a new class, including additive, unit-demand, budget-additive and multiplicative valuations, among others). Furthermore, using our new techniques, we show that previous results for additive valuations extend to nice cancelable valuations.

Scalable training data generation is a critical problem in deep learning. We propose PennSyn2Real - a photo-realistic synthetic dataset consisting of more than 100,000 4K images of more than 20 types of micro aerial vehicles (MAVs). The dataset can be used to generate arbitrary numbers of training images for high-level computer vision tasks such as MAV detection and classification. Our data generation framework bootstraps chroma-keying, a mature cinematography technique with a motion tracking system, providing artifact-free and curated annotated images where object orientations and lighting are controlled. This framework is easy to set up and can be applied to a broad range of objects, reducing the gap between synthetic and real-world data. We show that synthetic data generated using this framework can be directly used to train CNN models for common object recognition tasks such as detection and segmentation. We demonstrate competitive performance in comparison with training using only real images. Furthermore, bootstrapping the generated synthetic data in few-shot learning can significantly improve the overall performance, reducing the number of required training data samples to achieve the desired accuracy., Comment: 7 pages, 9 figures, 3 tables. Submitted to R-AL and ICRA 2021

We study graph realization problems from a distributed perspective and we study it in the node capacitated clique (NCC) model of distributed computing, recently introduced for representing peer-to-peer networks. We focus on two central variants, degree-sequence realization and minimum threshold-connectivity realization both of which result in overlay network realizations. Overlay network realizations can be either explicit or implicit. Explicit realizations require both endpoints of any edge in the realized graph to be aware of the edge. In implicit realizations, on the other hand, at least one endpoint of each edge of the realized graph needs to be aware of the edge. The main realization algorithms we present are the following. 1. An $\tilde{O}(\min\{\sqrt{m},\Delta\})$ time algorithm for implicit realization of a degree sequence. Here, $\Delta = \max_v d(v)$ is the maximum degree and $m = (1/2) \sum_v d(v)$ is the number of edges in the final realization. An $\tilde{O}(\Delta)$ time algorithm for an explicit realization of a degree sequence. We first compute an implicit realization and then transform it into an explicit one in $\tilde{O}(\Delta)$ additional rounds. 2. An $\tilde{O}(\Delta)$ time algorithm for the threshold connectivity problem that obtains an explicit solution and an improved $\tilde{O}(1)$ algorithm for implicit realization when all nodes know each other's IDs. These algorithms are 2-approximations w.r.t. the number of edges. We complement our upper bounds with lower bounds to show that the above algorithms are tight up to factors of $\log n$. Additionally, we provide algorithms for realizing trees and an $\tilde{O}(1)$ round algorithm for approximate degree sequence realization., Comment: 22 pages, 4 figures. Short version to appear in IPDPS 2020

The task of person re-identification (ReID) has attracted growing attention in recent years leading to improved performance, albeit with little focus on real-world applications. Most SotA methods are based on heavy pre-trained models, e.g. ResNet50 (~25M parameters), which makes them less practical and more tedious to explore architecture modifications. In this study, we focus on a small-sized randomly initialized model that enables us to easily introduce architecture and training modifications suitable for person ReID. The outcomes of our study are a compact network and a fitting training regime. We show the robustness of the network by outperforming the SotA on both Market1501 and DukeMTMC. Furthermore, we show the representation power of our ReID network via SotA results on a different task of multi-object tracking.

The classical Hotelling game is played on a line segment whose points represent uniformly distributed clients. The $n$ players of the game are servers who need to place themselves on the line segment, and once this is done, each client gets served by the player closest to it. The goal of each player is to choose its location so as to maximize the number of clients it attracts. In this paper we study a variant of the Hotelling game where each client $v$ has a tolerance interval, randomly distributed according to some density function $f$, and $v$ gets served by the nearest among the players eligible for it, namely, those that fall within its interval. (If no such player exists, then $v$ abstains.) It turns out that this modification significantly changes the behavior of the game and its states of equilibria. In particular, it may serve to explain why players sometimes prefer to "spread out", rather than to cluster together as dictated by the classical Hotelling game. We consider two variants of the game: symmetric games, where clients have the same tolerance range to their left and right, and asymmetric games, where the left and right ranges of each client are determined independently of each other. We fully characterize the Nash equilibria of the 2-player game. For at least 3 players, we characterize a specific class of strategy profiles, referred to as canonical profiles, and show that these profiles are the only ones that may yield Nash equilibria in our game. Moreover, the canonical profile, if exists, is uniquely defined for every $n$ and $f$. In both the symmetric and asymmetric setting, we give necessary and sufficient conditions for the canonical profile to be a Nash equilibrium, and demonstrate their application for several distributions.

We present an automatic method for joint liver lesion segmentation and classification using a hierarchical fine-tuning framework. Our dataset is small, containing 332 2-D CT examinations with lesion annotated into 3 lesion types: cysts, hemangiomas, and metastases. Using a cascaded U-net that performs segmentation and classification simultaneously, we trained a strong lesion segmentation model on the dataset of MICCAI 2017 Liver Tumor Segmentation (LiTS) Challenge. We used the trained weights to fine-tune a slightly modified model to obtain improved lesion segmentation and classification, on the smaller dataset. Since pre-training was done with similar data on a related task, we were able to learn more representative features (especially higher-level features in the U-Net's encoder), and improve pixel-wise classification results. We show an improvement of over 10\% in Dice score and classification accuracy, compared to a baseline model. We further improve the classification performance by hierarchically freezing the encoder part of the network and achieve an improvement of over 15\% in Dice score and classification accuracy. We compare our results with an existing method and show an improvement of 14\% in the success rate and 12\% in the classification accuracy., Comment: Accepted to IEEE EMBC 2019

The Hotelling game consists of n servers each choosing a point on the line segment, so as to maximize the amount of clients it attracts. Clients are uniformly distributed along the line, and each client buys from the closest server. In this paper, we study a fault-prone version of the Hotelling game, where the line fails at multiple random locations. Each failure disconnects the line, blocking the passage of clients. We show that the game admits a Nash equilibrium if and only if the rate of faults exceeds a certain threshold, and calculate that threshold approximately. Moreover, when a Nash equilibrium exists we show it is unique and construct it explicitly. Hence, somewhat surprisingly, the potential occurrence of failures has a stabilizing effect on the game (provided there are enough of them). Additionally, we study the social cost of the game (measured in terms of the total transportation cost of the clients), which also seems to benefit in a certain sense from the potential presence of failures.

In this work, we report the set-up and results of the Liver Tumor Segmentation Benchmark (LiTS), which was organized in conjunction with the IEEE International Symposium on Biomedical Imaging (ISBI) 2017 and the International Conferences on Medical Image Computing and Computer-Assisted Intervention (MICCAI) 2017 and 2018. The image dataset is diverse and contains primary and secondary tumors with varied sizes and appearances with various lesion-to-background levels (hyper-/hypo-dense), created in collaboration with seven hospitals and research institutions. Seventy-five submitted liver and liver tumor segmentation algorithms were trained on a set of 131 computed tomography (CT) volumes and were tested on 70 unseen test images acquired from different patients. We found that not a single algorithm performed best for both liver and liver tumors in the three events. The best liver segmentation algorithm achieved a Dice score of 0.963, whereas, for tumor segmentation, the best algorithms achieved Dices scores of 0.674 (ISBI 2017), 0.702 (MICCAI 2017), and 0.739 (MICCAI 2018). Retrospectively, we performed additional analysis on liver tumor detection and revealed that not all top-performing segmentation algorithms worked well for tumor detection. The best liver tumor detection method achieved a lesion-wise recall of 0.458 (ISBI 2017), 0.515 (MICCAI 2017), and 0.554 (MICCAI 2018), indicating the need for further research. LiTS remains an active benchmark and resource for research, e.g., contributing the liver-related segmentation tasks in \url{http://medicaldecathlon.com/}. In addition, both data and online evaluation are accessible via \url{www.lits-challenge.com}., Comment: Patrick Bilic, Patrick Christ, Hongwei Bran Li, and Eugene Vorontsov made equal contributions to this work. Published in Medical Image Analysis

Training data is the key component in designing algorithms for medical image analysis and in many cases it is the main bottleneck in achieving good results. Recent progress in image generation has enabled the training of neural network based solutions using synthetic data. A key factor in the generation of new samples is controlling the important appearance features and potentially being able to generate a new sample of a specific class with different variants. In this work we suggest the synthesis of new data by mixing the class specified and unspecified representation of different factors in the training data. Our experiments on liver lesion classification in CT show an average improvement of 7.4% in accuracy over the baseline training scheme.

Accurate segmentation of anatomical structures in chest radiographs is essential for many computer-aided diagnosis tasks. In this paper we investigate the latest fully-convolutional architectures for the task of multi-class segmentation of the lungs field, heart and clavicles in a chest radiograph. In addition, we explore the influence of using different loss functions in the training process of a neural network for semantic segmentation. We evaluate all models on a common benchmark of 247 X-ray images from the JSRT database and ground-truth segmentation masks from the SCR dataset. Our best performing architecture, is a modified U-Net that benefits from pre-trained encoder weights. This model outperformed the current state-of-the-art methods tested on the same benchmark, with Jaccard overlap scores of 96.1% for lung fields, 90.6% for heart and 85.5% for clavicles., Comment: Presented at the First International Workshop on Thoracic Image Analysis (TIA), MICCAI 2018

In this work we present a novel system for generation of virtual PET images using CT scans. We combine a fully convolutional network (FCN) with a conditional generative adversarial network (GAN) to generate simulated PET data from given input CT data. The synthesized PET can be used for false-positive reduction in lesion detection solutions. Clinically, such solutions may enable lesion detection and drug treatment evaluation in a CT-only environment, thus reducing the need for the more expensive and radioactive PET/CT scan. Our dataset includes 60 PET/CT scans from Sheba Medical center. We used 23 scans for training and 37 for testing. Different schemes to achieve the synthesized output were qualitatively compared. Quantitative evaluation was conducted using an existing lesion detection software, combining the synthesized PET as a false positive reduction layer for the detection of malignant lesions in the liver. Current results look promising showing a 28% reduction in the average false positive per case from 2.9 to 2.1. The suggested solution is comprehensive and can be expanded to additional body organs, and different modalities., Comment: Preprint submitted to Engineering applications of artificial intelligence

The $n$-player Hotelling game calls for each player to choose a point on the line segment, so as to maximize the size of his Voronoi cell. This paper studies fault-tolerant versions of the Hotelling game. Two fault models are studied: line faults and player faults. The first model assumes that the environment is prone to failure: with some probability, a disconnection occurs at a random point on the line, splitting it into two separate segments and modifying each player's Voronoi cell accordingly. A complete characterization of the Nash equilibria of this variant is provided for every $n$. Additionally, a one to one correspondence is shown between equilibria of this variant and of the Hotelling game with no faults. The second fault model assumes the players are prone to failure: each player is removed from the game with i.i.d. probability, changing the payoffs of the remaining players accordingly. It is shown that for $n \geq 3$ this variant of the game has no Nash equilibria.

In this work we propose a method for anatomical data augmentation that is based on using slices of computed tomography (CT) examinations that are adjacent to labeled slices as another resource of labeled data for training the network. The extended labeled data is used to train a U-net network for a pixel-wise classification into different hepatic lesions and normal liver tissues. Our dataset contains CT examinations from 140 patients with 333 CT images annotated by an expert radiologist. We tested our approach and compared it to the conventional training process. Results indicate superiority of our method. Using the anatomical data augmentation we achieved an improvement of 3% in the success rate, 5% in the classification accuracy, and 4% in Dice., Comment: To be presented at IEEE ISBI 2018

In this work we present a novel system for PET estimation using CT scans. We explore the use of fully convolutional networks (FCN) and conditional generative adversarial networks (GAN) to export PET data from CT data. Our dataset includes 25 pairs of PET and CT scans where 17 were used for training and 8 for testing. The system was tested for detection of malignant tumors in the liver region. Initial results look promising showing high detection performance with a TPR of 92.3% and FPR of 0.25 per case. Future work entails expansion of the current system to the entire body using a much larger dataset. Such a system can be used for tumor detection and drug treatment evaluation in a CT-only environment instead of the expansive and radioactive PET-CT scan., Comment: To be presented at SASHIMI2017: Simulation and Synthesis in Medical Imaging, MICCAI 2017