OpenRaiser/Intern-Atlas huggingface dataset:
Single-Training Collaborative Object Detectors Adaptive to Bandwidth and Computation
Venue: arXiv cs.CV 2021
Year: 2021

In the past few years, mobile deep-learning deployment progressed by leaps and bounds, but solutions still struggle to accommodate its severe and fluctuating operational restrictions, which include bandwidth, latency, computation, and energy. In this work, we help to bridge that gap, introducing the first configurable solution for object detection that manages the triple communication-computation-accuracy trade-off with a single set of weights. Our solution shows state-of-the-art results on COCO-2017, adding only a minor penalty on the base EfficientDet-D2 architecture. Our design is robust to the choice of base architecture and compressor and should adapt well for future architectures.
Model Counting meets F0 Estimation
Venue: arXiv cs.DS 2021
Year: 2021

Constraint satisfaction problems (CSP's) and data stream models are two powerful abstractions to capture a wide variety of problems arising in different domains of computer science. Developments in the two communities have mostly occurred independently and with little interaction between them. In this work, we seek to investigate whether bridging the seeming communication gap between the two communities may pave the way to richer fundamental insights. To this end, we focus on two foundational problems: model counting for CSP's and computation of zeroth frequency moments ($F_0$) for data streams. Our investigations lead us to observe striking similarity in the core techniques employed in the algorithmic frameworks that have evolved separately for model counting and $F_0$ computation. We design a recipe for translation of algorithms developed for $F_0$ estimation to that of model counting, resulting in new algorithms for model counting. We then observe that algorithms in the context of distributed streaming can be transformed to distributed algorithms for model counting. We next turn our attention to viewing streaming from the lens of counting and show that framing $F_0$ estimation as a special case of #DNF counting allows us to obtain a general recipe for a rich class of streaming problems, which had been subjected to case-specific analysis in prior works. In particular, our view yields a state-of-the art algorithm for multidimensional range efficient $F_0$ estimation with a simpler analysis.
An Algorithm for Recommending Groceries Based on an Item Ranking Method
Venue: arXiv cs.IR 2021
Year: 2021

This research proposes a new recommender system algorithm for online grocery shopping. The algorithm is based on the perspective that, since the grocery items are usually bought in bulk, a grocery recommender system should be capable of recommending the items in bulk. The algorithm figures out the possible dishes a user may cook based on the items added to the basket and recommends the ingredients accordingly. Our algorithm does not depend on the user ratings. Customers usually do not have the patience to rate the groceries they purchase. Therefore, algorithms that are not dependent on user ratings need to be designed. Instead of using a brute force search, this algorithm limits the search space to a set of only a few probably food categories. Each food category consists of several food subcategories. For example, "fried rice" and "biryani" are food subcategories that belong to the food category "rice". For each food category, items are ranked according to how well they can differentiate a food subcategory. To each food subcategory in the activated search space, this algorithm attaches a score. The score is calculated based on the rank of the items added to the basket. Once the score exceeds a threshold value, its corresponding subcategory gets activated. The algorithm then uses a basket-to-recipe similarity measure to identify the best recipe matches within the activated subcategories only. This reduces the search space to a great extent. We may argue that this algorithm is similar to the content-based recommender system in some sense, but it does not suffer from the limitations like limited content, over-specialization, or the new user problem.
Unsupervised Document Expansion for Information Retrieval with Stochastic Text Generation
Venue: arXiv cs.IR 2021
Year: 2021

One of the challenges in information retrieval (IR) is the vocabulary mismatch problem, which happens when the terms between queries and documents are lexically different but semantically similar. While recent work has proposed to expand the queries or documents by enriching their representations with additional relevant terms to address this challenge, they usually require a large volume of query-document pairs to train an expansion model. In this paper, we propose an Unsupervised Document Expansion with Generation (UDEG) framework with a pre-trained language model, which generates diverse supplementary sentences for the original document without using labels on query-document pairs for training. For generating sentences, we further stochastically perturb their embeddings to generate more diverse sentences for document expansion. We validate our framework on two standard IR benchmark datasets. The results show that our framework significantly outperforms relevant expansion baselines for IR.
Learning by Design: Structuring and Documenting the Human Choices in Machine Learning Development
Venue: arXiv cs.LG 2021
Year: 2021

The influence of machine learning (ML) is quickly spreading, and a number of recent technological innovations have applied ML as a central technology. However, ML development still requires a substantial amount of human expertise to be successful. The deliberation and expert judgment applied during ML development cannot be revisited or scrutinized if not properly documented, and this hinders the further adoption of ML technologies--especially in safety critical situations. In this paper, we present a method consisting of eight design questions, that outline the deliberation and normative choices going into creating a ML model. Our method affords several benefits, such as supporting critical assessment through methodological transparency, aiding in model debugging, and anchoring model explanations by committing to a pre hoc expectation of the model's behavior. We believe that our method can help ML practitioners structure and justify their choices and assumptions when developing ML models, and that it can help bridge a gap between those inside and outside the ML field in understanding how and why ML models are designed and developed the way they are.
Spectral Machine Learning for Pancreatic Mass Imaging Classification
Venue: arXiv cs.CV 2021
Year: 2021

We present a novel spectral machine learning (SML) method in screening for pancreatic mass using CT imaging. Our algorithm is trained with approximately 30,000 images from 250 patients (50 patients with normal pancreas and 200 patients with abnormal pancreas findings) based on public data sources. A test accuracy of 94.6 percents was achieved in the out-of-sample diagnosis classification based on a total of approximately 15,000 images from 113 patients, whereby 26 out of 32 patients with normal pancreas and all 81 patients with abnormal pancreas findings were correctly diagnosed. SML is able to automatically choose fundamental images (on average 5 or 9 images for each patient) in the diagnosis classification and achieve the above mentioned accuracy. The computational time is 75 seconds for diagnosing 113 patients in a laptop with standard CPU running environment. Factors that influenced high performance of a well-designed integration of spectral learning and machine learning included: 1) use of eigenvectors corresponding to several of the largest eigenvalues of sample covariance matrix (spike eigenvectors) to choose input attributes in classification training, taking into account only the fundamental information of the raw images with less noise; 2) removal of irrelevant pixels based on mean-level spectral test to lower the challenges of memory capacity and enhance computational efficiency while maintaining superior classification accuracy; 3) adoption of state-of-the-art machine learning classification, gradient boosting and random forest. Our methodology showcases practical utility and improved accuracy of image diagnosis in pancreatic mass screening in the era of AI.
On the Complexity of Fair Coin Flipping
Venue: arXiv cs.CR 2021
Year: 2021

A two-party coin-flipping protocol is $ε$-fair if no efficient adversary can bias the output of the honest party (who always outputs a bit, even if the other party aborts) by more than $ε$. Cleve [STOC '86] showed that $r$-round $o(1/r)$-fair coin-flipping protocols do not exist. Awerbuch, Blum, Chor, Goldwasser, and Micali[Manuscript '85] constructed a $Θ(1/\sqrt{r})$-fair coin-flipping protocol, assuming the existence of one-way functions. Moran, Naor, and Segev [Journal of Cryptology '16] constructed an $r$-round coin-flipping protocol that is $Θ(1/r)$-fair (thus matching the aforementioned lower bound of Cleve [STOC '86]), assuming the existence of oblivious transfer. The above gives rise to the intriguing question of whether oblivious transfer, or more generally ``public-key primitives,'' is required for an $o(1/\sqrt r)$-fair coin flipping protocol. We make a different progress towards answering the question by showing that, for any constant $r\in \N$, the existence of an $1/(c\cdot \sqrt{r})$-fair, $r$-round coin-flipping protocol implies the existence of an infinitely-often key-agreement protocol, where $c$ denotes some universal constant (independent of $r$). Our reduction is \emph{non} black-box and makes a novel use of the recent dichotomy for two-party protocols of Haitner, Nissim, Omri, Shaltiel, and Silbak [FOCS '18] to facilitate a two-party variant of the recent attack of Beimel, Haitner, Makriyannis, and Omri [FOCS '18] on multi-party coin-flipping protocols.
Hardware Implementation of an OPC UA Server for Industrial Field Devices
Venue: arXiv cs.AR 2021
Year: 2021

Industrial plants suffer from a high degree of complexity and incompatibility in their communication infrastructure, caused by a wild mix of proprietary technologies. This prevents transformation towards Industry 4.0 and the Industrial Internet of Things. Open Platform Communications Unified Architecture (OPC UA) is a standardized protocol that addresses these problems with uniform and semantic communication across all levels of the hierarchy. However, its adoption in embedded field devices, such as sensors and actors, is still lacking due to prohibitive memory and power requirements of software implementations. We have developed a dedicated hardware engine that offloads processing of the OPC UA protocol and enables realization of compact and low-power field devices with OPC UA support. As part of a proof-of-concept embedded system we have implemented this engine in a 22 nm FDSOI technology. We measured performance, power consumption, and memory footprint of our test chip and compared it with a software implementation based on open62541 and a Raspberry Pi 2B. Our OPC UA hardware engine is 50 times more energy efficient and only requires 36 KiB of memory. The complete chip consumes only 24 mW under full load, making it suitable for low-power embedded applications.
DEUX: An Attribute-Guided Framework for Sociable Recommendation Dialog Systems
Venue: arXiv cs.CL 2021
Year: 2021

It is important for sociable recommendation dialog systems to perform as both on-task content and social content to engage users and gain their favor. In addition to understand the user preferences and provide a satisfying recommendation, such systems must be able to generate coherent and natural social conversations to the user. Traditional dialog state tracking cannot be applied to such systems because it does not track the attributes in the social content. To address this challenge, we propose DEUX, a novel attribute-guided framework to create better user experiences while accomplishing a movie recommendation task. DEUX has a module that keeps track of the movie attributes (e.g., favorite genres, actors,etc.) in both user utterances and system responses. This allows the system to introduce new movie attributes in its social content. Then, DEUX has multiple values for the same attribute type which suits the recommendation task since a user may like multiple genres, for instance. Experiments suggest that DEUX outperforms all the baselines on being more consistent, fitting the user preferences better, and providing a more engaging chat experience. Our approach can be used for any similar problems of sociable task-oriented dialog system.
Elo Ratings for Large Tournaments of Software Agents in Asymmetric Games
Venue: arXiv cs.AI 2021
Year: 2021

The Elo rating system has been used world wide for individual sports and team sports, as exemplified by the European Go Federation (EGF), International Chess Federation (FIDE), International Federation of Association Football (FIFA), and many others. To evaluate the performance of artificial intelligence agents, it is natural to evaluate them on the same Elo scale as humans, such as the rating of 5185 attributed to AlphaGo Zero. There are several fundamental differences between humans and AI that suggest modifications to the system, which in turn require revisiting Elo's fundamental rationale. AI is typically trained on many more games than humans play, and we have little a-priori information on newly created AI agents. Further, AI is being extended into games which are asymmetric between the players, and which could even have large complex boards with different setup in every game, such as commercial paper strategy games. We present a revised rating system, and guidelines for tournaments, to reflect these differences.
Performance and Energy-Aware Bi-objective Tasks Scheduling for Cloud Data Centers
Venue: arXiv cs.DC 2021
Year: 2021

Cloud computing enables remote execution of users tasks. The pervasive adoption of cloud computing in smart cities services and applications requires timely execution of tasks adhering to Quality of Services (QoS). However, the increasing use of computing servers exacerbates the issues of high energy consumption, operating costs, and environmental pollution. Maximizing the performance and minimizing the energy in a cloud data center is challenging. In this paper, we propose a performance and energy optimization bi-objective algorithm to tradeoff the contradicting performance and energy objectives. An evolutionary algorithm-based multi-objective optimization is for the first time proposed using system performance counters. The performance of the proposed model is evaluated using a realistic cloud dataset in a cloud computing environment. Our experimental results achieve higher performance and lower energy consumption compared to a state of the art algorithm.
GoHammer Blockchain Performance Test Tool
Venue: arXiv cs.DC 2021
Year: 2021

Decentralized services are increasingly being developed and their Decentralized applications are increasingly developed but their performance metrics are not tested enough. The total number of transactions that can be supported by the blockchain network and the performance effects of selecting different consensus protocols, using different block intervals and block size should be tested. There are some blockchain performance tools but most are built for specific blockchain frameworks and require complex configuration. The GoHammer tool is developed to provide an easy to use, flexible test tool for the Ethereum/Quorum blockchain frameworks. Transaction per second (TPS) values and several performance metrics will be tested. This tool is also a part of the series of tools that can be integrated with Tubu-io. This tool will help in developing more efficient decentralized systems and will affect decreasing the costs of developing decentralized application projects.
Ferroelectric based FETs and synaptic devices for highly energy efficient computational technologies
Venue: arXiv cs.ET 2021
Year: 2021

The technological exploitation of ferroelectricity in CMOS electron devices offers new design opportunities, but also significant challenges from an integration, optimization and modelling perspective. We here revisit the working principle and the modelling of some novel ferroelectric based devices, with an emphasis on energy efficiency and on applications to new computational paradigms.
General Knapsack Problems in a Dynamic Setting
Venue: arXiv cs.DS 2021
Year: 2021

The world is dynamic and changes over time, thus any optimization problem used to model real life problems must address this dynamic nature, taking into account the cost of changes to a solution over time. The multistage model was introduced with this goal in mind. In this model we are given a series of instances of an optimization problem, corresponding to different times, and a solution is provided for each instance. The strive for obtaining near-optimal solutions for each instance on one hand, while maintaining similar solutions for consecutive time units on the other hand, is quantified and integrated into the objective function. In this paper we consider the Generalized Multistage $d$-Knapsack problem, a generalization of the multistage variants of the Multiple Knapsack problem, as well as the $d$-Dimensional Knapsack problem. We present a PTAS for Generalized Multistage $d$-Knapsack.
Universal Weakly Supervised Segmentation by Pixel-to-Segment Contrastive Learning
Venue: arXiv cs.CV 2021
Year: 2021

Weakly supervised segmentation requires assigning a label to every pixel based on training instances with partial annotations such as image-level tags, object bounding boxes, labeled points and scribbles. This task is challenging, as coarse annotations (tags, boxes) lack precise pixel localization whereas sparse annotations (points, scribbles) lack broad region coverage. Existing methods tackle these two types of weak supervision differently: Class activation maps are used to localize coarse labels and iteratively refine the segmentation model, whereas conditional random fields are used to propagate sparse labels to the entire image. We formulate weakly supervised segmentation as a semi-supervised metric learning problem, where pixels of the same (different) semantics need to be mapped to the same (distinctive) features. We propose 4 types of contrastive relationships between pixels and segments in the feature space, capturing low-level image similarity, semantic annotation, co-occurrence, and feature affinity They act as priors; the pixel-wise feature can be learned from training images with any partial annotations in a data-driven fashion. In particular, unlabeled pixels in training images participate not only in data-driven grouping within each image, but also in discriminative feature learning within and across images. We deliver a universal weakly supervised segmenter with significant gains on Pascal VOC and DensePose. Our code is publicly available at https://github.com/twke18/SPML.
From Fairness to Full Security in Multiparty Computation
Venue: arXiv cs.CR 2021
Year: 2021

In the setting of secure multiparty computation (MPC), a set of mutually distrusting parties wish to jointly compute a function, while guaranteeing the privacy of their inputs and the correctness of the output. An MPC protocol is called \emph{fully secure} if no adversary can prevent the honest parties from obtaining their outputs. A protocol is called \emph{fair} if an adversary can prematurely abort the computation, however, only before learning any new information. We present highly efficient transformations from fair computations to fully secure computations, assuming the fraction of honest parties is constant (e.g., $1\%$ of the parties are honest). Compared to previous transformations that require linear invocations (in the number of parties) of the fair computation, our transformations require super-logarithmic, and sometimes even super-constant, such invocations. The main idea is to delegate the computation to chosen random committees that invoke the fair computation. Apart from the benefit of uplifting security, the reduction in the number of parties is also useful, since only committee members are required to work, whereas the remaining parties simply "listen" to the computation over a broadcast channel.
Analyzing scientific data sharing patterns for in-network data caching
Venue: arXiv cs.NI 2021
Year: 2021

The volume of data moving through a network increases with new scientific experiments and simulations. Network bandwidth requirements also increase proportionally to deliver data within a certain time frame. We observe that a significant portion of the popular dataset is transferred multiple times to different users as well as to the same user for various reasons. In-network data caching for the shared data has shown to reduce the redundant data transfers and consequently save network traffic volume. In addition, overall application performance is expected to improve with in-network caching because access to the locally cached data results in lower latency. This paper shows how much data was shared over the study period, how much network traffic volume was consequently saved, and how much the temporary in-network caching increased the scientific application performance. It also analyzes data access patterns in applications and the impacts of caching nodes on the regional data repository. From the results, we observed that the network bandwidth demand was reduced by nearly a factor of 3 over the study period.
Algorithms are not neutral: Bias in collaborative filtering
Venue: arXiv cs.CY 2021
Year: 2021

Discussions of algorithmic bias tend to focus on examples where either the data or the people building the algorithms are biased. This gives the impression that clean data and good intentions could eliminate bias. The neutrality of the algorithms themselves is defended by prominent Artificial Intelligence researchers. However, algorithms are not neutral. In addition to biased data and biased algorithm makers, AI algorithms themselves can be biased. This is illustrated with the example of collaborative filtering, which is known to suffer from popularity, and homogenizing biases. Iterative information filtering algorithms in general create a selection bias in the course of learning from user responses to documents that the algorithm recommended. These are not merely biases in the statistical sense; these statistical biases can cause discriminatory outcomes. Data points on the margins of distributions of human data tend to correspond to marginalized people. Popularity and homogenizing biases have the effect of further marginalizing the already marginal. This source of bias warrants serious attention given the ubiquity of algorithmic decision-making.