Search

The papers in this special section focuses on signal processing advances in wireless transmission of power and information. Wireless power transfer (WPT) and wireless information and power transfer (WIPT) have received growing attention in the research community in the past few years. In this special issue, a total of fourteen papers present state-of-the-art results in the broad area of wireless transmission of information and power with a special emphasis on signal processing advances. The special issue starts with a guest editor-authored tutorial overview paper that reviews the signal processing, machine learning, sensing, and computing techniques, challenges and opportunities in future networks based on WPT and WIPT.

Neurobiological systems operate at power levels that are unattainable by modern electronic systems while exhibiting broader information processing capabilities for a number of important tasks. A variety of engineered systems designed for energy efficiency or hardware simplicity use time-based signal representations, which share similar mathematical principles with those that arise naturally in biology. In general, time-based signal representations refer to embedding information into the timing, density, or duration of a predetermined, and often bipolar, waveform. In mammalian nervous systems, it is generally accepted that neurons embed information into the timing and firing density of the sudden changes in their membrane potential, or spikes. Similarly, many low-power electronic systems use signal representations that embed information in the timing, repetition frequency, or duration of simple pulse waveforms. Despite their apparent similarities, such signal representations are often studied in different contexts.

In a recent essay on the role of modern information technologies in democratic processes, Zeynep Tufekci described the actions of Egyptian leader Hosni Mubarak in cutting off Internet and cellular service during the 2011 Tahrir uprising as follows: "The move backfired: it restricted the flow of information coming out of Tahrir Square but caused international attention on Egypt to spike. He hadn't understood that in the 21st century it is the flow of attention, not information (which we already have too much of), that matters."

Blockchain systems store transaction data in the form of a distributed ledger where each peer is to maintain an identical copy. Blockchain systems resemble repetition codes, incurring high storage cost. Recently, distributed storage blockchain (DSB) systems have been proposed to improve storage efficiency by incorporating secret sharing, private key encryption, and information dispersal algorithms. However, the DSB results in significant communication cost when peer failures occur due to denial of service attacks. In this letter, we propose a new DSB approach based on a local secret sharing (LSS) scheme with a hierarchical secret structure of one global secret and several local secrets. The proposed DSB approach with LSS improves the storage and recovery communication costs.

BackgroundSocial distancing policies were enacted during March 2020 to limit the spread of COVID-19. Lockdowns and movement restrictions increased the potential of negative impact on population mental health, in which depression and anxiety symptoms were frequently reported by different population groups during COVID-19 lockdown. However, the causal relationship of mitigation policies on national-wide mental health resource usage is lacking.ObjectiveThis study investigates the effect of COVID-19 mitigation measures on mental health across the United States, on county and state levels. It examines the effect on mental health facility usage and the prevalence of mental illnesses on the total population, different age and gender groups, and patients of selected mental health diagnoses.MethodsWe used large-scale medical claims data for mental health patients dated from September 1, 2019 to December 31, 2020, with publicly available state- and county-specific COVID-19 cases from first case in January to December 31, 2020, and used publicly available lockdown dates for states and counties. We designed a difference-in-differences (DID) model, which infers the causal effect of a policy intervention by comparing pre-policy and post-policy periods in different regions. We mainly focused on two types of social distancing policies, stay-at-home and school closure orders.ResultsBased on common pre-treatment trend assumption of regions, we find that lockdown has significantly and causally increased the usage of mental health in regions with lockdowns in comparison to regions without. In regions with lockdown orders the resource usage increased by 18% compared to 1% decline in regions without a lockdown. Also, female populations have been exposed to a larger lockdown effect on their mental health with 24% increase in regions with lockdowns compared to 3% increase in regions without. While male mental health patients decreased by 5% in regions without lockdowns. Patients diagnosed with panic disorders and reaction to severe stress both were significantly exposed to a significant large effect of lockdowns. Also, life management difficulty patients doubled in regions with stay-at-home orders but increased less with school closures. Contrarily, attention-deficit hyperactivity patients declined in regions without stay-at-home orders. Patients older than 80 used mental health resources less in regions with lockdowns. Adults between (21 – 40) years old were exposed to the greatest lockdown effect with increase between 20% to 30% in regions with lockdown.ConclusionAlthough non-pharmaceutical intervention policies were effective in containing the spread of COVID-19, our results show that mitigation policies led to population-wide increase in mental health patients. Our results suggest the need for greater mental health treatment resources in the face of lockdown policies.

Conventional wireless techniques are becoming inadequate for beyond fifth-generation (5G) networks due to latency and bandwidth considerations. To improve the error performance and throughput of wireless communication systems, we propose physical layer network coding (PNC) in an intelligent reflecting surface (IRS)-assisted environment. We consider an IRS-aided butterfly network, where we propose an algorithm for obtaining the optimal IRS phases. Also, analytic expressions for the bit error rate (BER) are derived. The numerical results demonstrate that the proposed scheme significantly improves the BER performance. For instance, the BER at the relay in the presence of a 32-element IRS is three orders of magnitudes less than that without an IRS.

Advances in predictive algorithms are revolutionizing how we understand and design effective decision support systems in many sectors. The expanding role of predictive algorithms is part of a broader movement toward using data-driven machine learning (ML) for modalities including images, natural language, speech. This article reviews whether and to what extent predictive algorithms can assist decision-making in forest conservation and management. Although state-of-the-art ML algorithms provide new opportunities, adoption has been slow in forest decision-making. This review shows how domain-specific characteristics, such as system complexity, impose limits on using predictive algorithms in forest conservation and management. We conclude with possible directions for developing new predictive tools and approaches to support meaningful forest decisions through easily interpretable and explainable recommendations.

Wireless power transfer (WPT) is an emerging paradigm that will enable using wireless to its full potential in future networks, not only to convey information but also to deliver energy. Such networks will enable trillions of future low-power devices to sense, compute, connect, and energize anywhere, anytime, and on the move. The design of such future networks brings new challenges and opportunities for signal processing, machine learning, sensing, and computing so as to make the best use of the RF radiations, spectrum, and network infrastructure in providing cost-effective and real-time power supplies to wireless devices and enable wireless-powered applications. In this paper, we first review recent signal processing techniques to make WPT and wireless information and power transfer as efficient as possible. Topics include power amplifier and energy harvester nonlinearities, active and passive beamforming, intelligent reflecting surfaces, receive combining with multi-antenna harvester, modulation, coding, waveform, massive MIMO, channel acquisition, transmit diversity, multi-user power region characterization, coordinated multipoint, and distributed antenna systems. Then, we overview two different design methodologies: the model and optimize approach relying on analytical system models, modern convex optimization, and communication theory, and the learning approach based on data-driven end-to-end learning and physics-based learning. We discuss the pros and cons of each approach, especially when accounting for various nonlinearities in wireless-powered networks, and identify interesting emerging opportunities for the approaches to complement each other. Finally, we identify new emerging wireless technologies where WPT may play a key role -- wireless-powered mobile edge computing and wireless-powered sensing -- arguing WPT, communication, computation, and sensing must be jointly designed., Comment: Overview paper submitted for publication

We present a principled framework to address resource allocation for realizing boosting algorithms on substrates with communication noise. Boosting classifiers (e.g., AdaBoost) make a final decision via a weighted vote from local decisions of many base classifiers (weak classifiers). Suppose the base classifiers' outputs are communicated over noisy channels; these noisy outputs will degrade the final classification accuracy. We show this degradation can be effectively reduced by allocating more system resources for more important base classifiers. We formulate resource optimization problems in terms of importance metrics for boosting. Moreover, we show that the optimized noisy boosting classifiers can be more robust than bagging for noise during inference (test stage). We provide numerical evidence to demonstrate the benefits of our approach.

We consider the problem of universal joint clustering and registration of images. Image clustering focuses on grouping similar images, while image registration refers to the task of aligning copies of an image that have been subject to rigid-body transformations, such as rotations and translations. We first study registering two images using maximum mutual information and prove its asymptotic optimality. We then show the shortcomings of pairwise registration in multi-image registration, and design an asymptotically optimal algorithm based on multi-information. Further, we define a novel multivariate information functional to perform joint clustering and registration of images, and prove consistency of the algorithm. Finally, we consider registration and clustering of numerous limited-resolution images, defining algorithms that are order-optimal in scaling of number of pixels in each image with the number of images.

With the advent of the Internet of Things (IoT) and a rapid deployment of smart devices and wireless sensor networks (WSNs), humans interact extensively with machine data. These human decision makers use sensors that provide information through a sociotechnical network. The sensors can be other human users or they can be IoT devices. The decision makers themselves are also part of the network, and there is a need to understand how they will behave. In this paper, the decision fusion behavior of humans is analyzed on the basis of behavioral experiments. The data collected from these experiments demonstrate that people perform decision fusion in a stochastic manner dependent on various factors, unlike machines that perform this task in a deterministic manner. A Bayesian hierarchical model is developed to characterize the observed stochastic human behavior. This hierarchical model captures the differences observed in people at individual, crowd, and population levels. The implications of such a model on designing large-scale inference systems are presented by developing optimal decision fusion trees with both human and machine agents.

Crowdsourcing of jobs to online freelance platforms is rapidly gaining popularity. Most crowdsourcing platforms are uncontrolled and offer freedom to customers and freelancers to choose each other. This works well for unskilled jobs (e.g., image classification) with no specific quality requirement since freelancers are functionally identical. For skilled jobs (e.g., software development) with specific quality requirements, however, this does not ensure that the maximum number of job requests is satisfied. In this paper, we determine the capacity of regulated freelance systems, in terms of maximum satisfied job requests, and propose centralized schemes that achieve capacity. To ensure decentralized operation and freedom for customers and freelancers, we propose simple schemes compatible with the operation of current crowdsourcing platforms that approximately achieve capacity. Furthermore, for settings where the number of job requests exceeds capacity, we propose a scheme that is agnostic of that information, but is optimal and fair in declining jobs without wait.

Racial discrimination in decision-making scenarios such as police arrests appears to be a violation of expected utility theory. Drawing on results from the science of information, we discuss an information-based model of signal detection over a population that generates such behavior as an alternative explanation to taste-based discrimination by the decision maker or differences among the racial populations. This model uses the decision rule that maximizes expected utility-the likelihood ratio test-but constrains the precision of the threshold to a small discrete set. The precision constraint follows from both bounded rationality in human recollection and finite training data for estimating priors. When combined with social aspects of human decision making and precautionary cost settings, the model predicts the own-race bias that has been observed in several econometric studies.

We study a setting in which a principal selects an agent to execute a collection of tasks according to a specified priority sequence. Agents, however, have their own individual priority sequences according to which they wish to execute the tasks. There is information asymmetry since each priority sequence is private knowledge for the individual agent. We design a mechanism for selecting the agent and incentivizing the selected agent to realize a priority sequence for executing the tasks that achieves socially optimal performance. Our proposed mechanism consists of two parts. First, the principal runs an auction to select an agent to allocate tasks to with minimum declared priority sequence misalignment. Then, the principal rewards the agent according to the realized priority sequence with which the tasks were performed. We show that the proposed mechanism is individually rational and incentive compatible. Further, it is also socially optimal for the case of linear cost of priority sequence modification for the agents., arXiv admin note: substantial text overlap with arXiv:1902.00138 This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

Interests in the automatic generation of cooking recipes have been growing steadily over the past few years thanks to a large amount of online cooking recipes. We present RecipeGPT, a novel online recipe generation and evaluation system. The system provides two modes of text generations: (1) instruction generation from given recipe title and ingredients; and (2) ingredient generation from recipe title and cooking instructions. Its back-end text generation module comprises a generative pre-trained language model GPT-2 fine-tuned on a large cooking recipe dataset. Moreover, the recipe evaluation module allows the users to conveniently inspect the quality of the generated recipe contents and store the results for future reference. RecipeGPT can be accessed online at https://recipegpt.org/., Comment: Accepted to WWW 2020. Demo track paper

Consumption of diets with low glycemic impact is highly recommended for diabetics and pre-diabetics as it helps maintain their blood glucose levels. However, laboratory analysis of dietary glycemic potency is time-consuming and expensive. In this paper, we explore a data-driven approach utilizing online crowdsourcing and machine learning to estimate the glycemic impact of cooking recipes. We show that a commonly used healthiness metric may not always be effective in determining recipes suitable for diabetics, thus emphasizing the importance of the glycemic-impact estimation task. Our best classification model, trained on nutritional and crowdsourced data obtained from Amazon Mechanical Turk (AMT), can accurately identify recipes which are unhealthful for diabetics., To appear in the Proceedings of Digital Public Health 2019 as short paper

Communication systems for multicasting information and energy simultaneously to more than one user are investigated. In the system under study, a transmitter sends the same message and signal to multiple receivers over distinct and independent channels. The fundamental communication limit under a received energy constraint, called the multicast capacity-energy function, is studied and a single-letter expression is derived. This is based on coding theorems for compound channels. The problem of receiver segmentation, where receivers are divided into related groups, is also considered., Comment: 6 pages, 5 figures, parts of results have submitted to 2019 IEEE International Symposium on Information Theory

International audience; Recursive estimation is a basic operation in statistical inference that may be implemented and deployed on faulty hardware with error rates governed by energy consumption. We analyze the loss in estimation performance due to noise in recursive probability computation for the binary case, and develop an optimal energy allocation strategy. Simulations show the validity of analytical bounds.

Odorous compound emissions and odor complaints from the public are rising concerns for agricultural, industrial, and water resource recovery facilities (WRRFs) near urban areas. Many facilities are deploying sensors that measure malodorous compounds and other factors related to odor creation and dispersion. Focusing on the Metropolitan Water Reclamation District of Greater Chicago's (MWRDGCs) Thornton Composite Reservoir (7.9 billion gallon capacity), we used meteorological, operational, and H2S sensor data to train a 3-day advance-warning predictor of local odor complaints, so as to implement targeted odor prevention measures. Using a machine learning approach, we bypassed difficulties in modeling both physical dispersion and human perception of odors. Utilizing random forest algorithms with varied settings and input attributes, we find that a small network of H2S sensors, meteorological data, and operational data are able to predict odor complaints three days in advance with greater than 60% accuracy and less than 25% false-positive rates, exceeding MWRDGC's standards required for full-scale deployment. PRACTITIONER POINTS: A random forest algorithm trained on H2 S, weather, and operations data successfully predicted odor complaints surrounding a large composite reservoir. Thirty-two data attribute combinations were tested. It was found that H2 S sensor data alone are insufficient for predicting odor complaints. The best predictor was a Random Forest Classifier trained on weather, operational, and H2 S readings from the reservoir corner locations. This study demonstrates odor complaint prediction capability utilizing a limited set of data sources and open-source machine learning techniques. Given a small network of H2 S sensors and organized data management, WRRFs and similar facilities can conduct advance-warning odor complaint prediction.

Carsharing systems are adopting electric vehicles into their fleets and may therefore be able to provide not only transportation services to drivers/passengers but also energy services to the power grid through appropriate participation in electricity markets. This paper develops a queuing model of such carsharing platforms where cars may be deployed for transportation services at a given price, but also for grid services during transportation-idle periods through energy price arbitrage. The model provides a characterization of revenue from each of these two streams. The paper further finds optimal pricing and battery splitting to maximize revenue for the carsharing platform, via an analysis of the reward structure and an optimization algorithm. Platform revenue is assessed for various system parameters under optimal operation.

In software-as-a-service applications provisioned through cloud computing, locally cached data are often modified with updates from new versions. In some cases, with each edit, one may want to preserve both the original and new versions. In this paper, we focus on cases in which only the latest version must be preserved. Furthermore, it is desirable for the data to not only be compressed but to also be easily modified during updates, since representing information and modifying the representation both incur cost. We examine whether it is possible to have both compression efficiency and ease of alteration, in order to promote codeword reuse. In other words, we study the feasibility of a malleable and efficient coding scheme. The tradeoff between compression efficiency and malleability cost—the difficulty of synchronizing compressed versions—is measured as the length of a reused prefix portion. The region of achievable rates and malleability is found. Drawing from prior work on common information problems, we show that efficient data compression may not be the best engineering design principle when storing software-as-a-service data. In the general case, goals of efficiency and malleability are fundamentally in conflict.

Image-based transcriptomics involves determining spatial patterns in gene expression across cells and tissues. Image registration is a necessary component of data analysis pipelines that study gene expression levels across different cells and intracellular structures. We consider images from multiplexed single molecule fluorescent in situ hybridization (smFISH) and multiplexed in situ sequencing (ISS) datasets from the Human Cell Atlas project and demonstrate a novel approach to groupwise image registration using a parametric representation of images based on finite rate of innovation sampling, together with practical optimization of empirical multivariate information measures.

Blockchain uses the idea of storing transaction data in the form of a distributed ledger wherein each node in the network stores a current copy of the sequence of transactions (ledger) in the form of a hash chain. Storing the entire ledger incurs a high storage cost that grows undesirably large for high transaction rates and large networks. In this work we use secret key sharing, private key encryption, and distributed storage to design a coding scheme such that each node stores only a part of each transaction thereby reducing storage cost to a fraction of the original. When further using dynamic zone allocation, we show the coding scheme can also improve the data integrity. A full version of this paper is accessible at: [1]

Crowdsourcing contests are used widely by organizations as a means of accomplishing tasks. These organizations would like to maximize the utility obtained through worker submissions to the contest. If this utility is greater than that obtained through alternative means of completing the task (e.g. hiring someone), the task should be crowdsourced. We analyze the utility generated for different types of tasks and provide a rule-of-thumb crowdsourcing contest design. Knowledge about the relative strengths of the workers participating in the contest is an important factor in contest design. When the contest organizer is unsure about the strength of the workers, crowdsourcing contests deliver higher utility than would hiring or assignment. Disseminating worker strength information acts as a lever to influence participation and increase utility in the contest. Finally, while crowdsourcing is a good option for generic tasks, it might perform poorly for highly specialized tasks.

In most information-theoretic studies of communication, it is assumed that the channel is always available. However communication between two parties may cease due to damage to transmitter/receiver devices, wire lines being cut, loss of attention at the terminals, or other such reasons. To model a setting where attention must be maintained, here we consider a channel model — a boring channel — with a reserve of attention that degrades when the channel is being used but is replenished when a codeword containing a certain amount of Bayesian surprise is received. Limits of communication over the boring channel are characterized and numerical results are found. Optimal communication strategies may be useful for various cognitive systems, and coincide with the segmenting principle that states that students learn better from a multimedia lesson when it is presented in user-paced segments rather than as a continuous unit. An application to designing the interaction between people and artificial agents is also discussed.

Blockchain systems establish a cryptographically secure data structure for storing data in the form of a hash chain. We use a novel combination of distributed storage, private key encryption, and Shamirs secret sharing scheme to distribute transaction data, without significant loss in data integrity. Additionally, using Shamirs secret sharing scheme on the hash values and dynamic zone allocation, we further enhance the integrity. We highlight the tradeoff in storage cost and data loss probability with varying zone size choices. We also study the tradeoff between recovery cost and security from adversarial corruption with varying recovery mechanisms. Then, we formulate code design, given a probability of data recovery and targeted corruption, as an integer program. Using the coding scheme we establish a mechanism to insure data, for instance in blockchain-based cloud storage systems, based on the value of the data, by understanding the costs involved for the service provider.

Due to the unprecedented success of deep neural networks in inference tasks like speech and image recognition, there has been increasing interest in using them in mobile and in-sensor applications. As most current deep neural networks are very large in size, a major challenge lies in storing the network in devices with limited memory. Consequently there is growing interest in compressing deep networks by quantizing synaptic weights, but most prior work is heuristic and lacking theoretical foundations. Here we develop an approach to quantizing deep networks using functional high-rate quantization theory. Under certain technical conditions, this approach leads to an optimal quantizer that is computed using the celebrated backpropagation algorithm. In all other cases, a heuristic quantizer with certain regularization guarantees can be computed.

Social media platforms provide rich signal sets to understand the nature of social life, and sentiment analysis techniques have been developed to understand the emotional content of text from sites like Twitter and Facebook. Beyond text however, most social media platforms have images at their core, and communication of images may require quantization. Here, we develop methods and present results on understanding the association between the visual content features of images on the popular social media platform Instagram and the psycholinguistic sentiment of their hashtag descriptors. In particular, we collect several thousand images and analyze several aspects of color to predict image sentiment. These results affirm and clarify several psychological theories on the relationship between color and mood/emotion, such as colorfulness being associated with happiness. The data-driven psychovisual insights into sentiment developed herein can be used to define novel fidelity criteria for designing color quantization schemes.

This paper defines and studies the problem of universal clustering using responses of crowd workers, without knowledge of worker reliability or task difficulty. We model stochastic worker response distributions by incorporating traits of memory for similar objects and traits of distance among differing objects. We are particularly interested in two limiting worker types — temporary and long-term workers, without and with memory respectively. We first define clustering algorithms for these limiting cases and then integrate them into an algorithm for the unified worker model. We prove asymptotic consistency of the algorithms and establish sufficient conditions on the sample complexity of the algorithm. Converse arguments establish necessary conditions on sample complexity, proving that the defined algorithms are asymptotically order-optimal in cost.

Deep neural networks have shown incredible performance for inference tasks in a variety of domains. Unfortunately, most current deep networks are enormous cloud-based structures that require significant storage space, which limits scaling of deep learning as a service (DLaaS). This paper is concerned with finding universal lossless compressed representations of deep feedforward networkswith synaptic weights drawn from discrete sets. The basic insight that allows much less rate than naive approaches is the recognition that the bipartite graph layers of feedforward networks have a kind of permutation invariance to the labeling of nodes, in terms of inferential operation. We provide efficient algorithms to dissipate this irrelevant uncertainty and then use arithmetic coding to nearly achieve the entropy bound in a universal manner.

New device technologies such as spintronics, carbon nanotubes, and nanoscale CMOS incur random transient failures, where the failure probability is governed by the energy consumption through energy-failure functions. At the same time, there is growing use of deep neural networks for many inference applications, and specialized hardware is being developed with these nanotechnologies as physical substrates. It is important to understand the basic energy-reliability limits. Using Pippenger's mutual information propagation technique (extended to directed acyclic graphs), together with optimization, we obtain a lower bound on energy consumption in multilayer binary neural networks for a given reliability. We also obtain a simple energy allocation rule for neurons in the different layers of the neural network. The mathematical results also provide insight into mammalian neuroenergetics of brain regions involved in sensory processing.

Recent advances in associative memory design through structured pattern sets and graph-based inference algorithms have allowed reliable learning and recall of an exponential number of patterns. Although these designs correct external errors in recall, they assume neurons that compute noiselessly, in contrast to the highly variable neurons in brain regions thought to operate associatively such as hippocampus and olfactory cortex. Here we consider associative memories with noisy internal computations and analytically characterize performance. As long as the internal noise level is below a specified threshold, the error probability in the recall phase can be made exceedingly small. More surprisingly, we show that internal noise actually improves the performance of the recall phase while the pattern retrieval capacity remains intact, i.e., the number of stored patterns does not reduce with noise (up to a threshold). Computational experiments lend additional support to our theoretical analysis. This work suggests a functional benefit to noisy neurons in biological neuronal networks., Comment: arXiv admin note: text overlap with arXiv:1301.6265

We consider the problem of universal joint clustering and registration of images and define algorithms using multivariate information functionals. We first study registering two images using maximum mutual information and prove its asymptotic optimality. We then show the shortcomings of pairwise registration in multi-image registration, and design an asymptotically optimal algorithm based on multiinformation. Further, we define a novel multivariate information functional to perform joint clustering and registration of images, and prove consistency of the algorithm. Finally, we consider registration and clustering of numerous limited-resolution images, defining algorithms that are order-optimal in scaling of number of pixels in each image with the number of images., Comment: 22 pages, 4 figures

We propose a novel system which can transform a recipe into any selected regional style (e.g., Japanese, Mediterranean, or Italian). This system has two characteristics. First the system can identify the degree of regional cuisine style mixture of any selected recipe and visualize such regional cuisine style mixtures using barycentric Newton diagrams. Second, the system can suggest ingredient substitutions through an extended word2vec model, such that a recipe becomes more authentic for any selected regional cuisine style. Drawing on a large number of recipes from Yummly, an example shows how the proposed system can transform a traditional Japanese recipe, Sukiyaki, into French style.

Circuits and systems to simultaneously transmit energy and information using orthogonal frequency-division multiplexing (OFDM) that obtain receiver energy self-sufficiency have recently been proposed. To obtain smooth, rather than bursty energy delivery which may lead to energy outage, this paper develops a new architecture for self-sustainable OFDM that reduces the peak-to-average power ratio (PAPR) in the cyclic prefix through a novel frame-theoretic operation, similar to the erasure pattern selection technique. Numerical results demonstrate that this new approach outperforms prior self-sustainable OFDM techniques in terms of PAPR while maintaining nearly the same self-sustainability.

Many companies now use crowdsourcing to leverage external (as well as internal) crowds to perform specialized work, and so methods of improving efficiency are critical. Tasks in crowdsourcing systems with specialized work have multiple steps and each step requires multiple skills. Steps may have different flexibilities in terms of obtaining service from one or multiple agents, due to varying levels of dependency among parts of steps. Steps of a task may have precedence constraints among them. Moreover, there are variations in loads of different types of tasks requiring different skill-sets and availabilities of different types of agents with different skill-sets. Considering these constraints together necessitates the design of novel schemes to allocate steps to agents. In addition, large crowdsourcing systems require allocation schemes that are simple, fast, decentralized and offer customers (task requesters) the freedom to choose agents. In this work we study the performance limits of such crowdsourcing systems and propose efficient allocation schemes that provably meet the performance limits under these additional requirements. We demonstrate our algorithms on data from a crowdsourcing platform run by a non-profit company and show significant improvements over current practice.

With developments in experimental connectomics producing wiring diagrams of many neuronal networks, there is emerging interest in theories to understand the relationship between structure and function. Efficiency of information flow in networks has been proposed as a key functional in characterizing cognition, and we have previously shown that information-theoretic limits on information flow are predictive of behavioral speed in the nematode Caenorhabditis elegans. In particular, we defined and computed a notion called effective bottleneck capacity that emerged from a pipelining model of information flow. It was unclear, however, whether the particular C. elegans connectome had unique capacity properties or whether similar properties would hold for random networks. Here, we determine the effective bottleneck capacity for several random graph ensembles to understand the range of possible variation and compare to the C. elegans network.

Consider a distributed estimation problem to be carried out by paid crowdworkers, where results are to be returned quickly and accurately. Estimation accuracy is a function of the number of workers completing the job and of the quality of the workers, both of which may be influenced by the payment offered. With limited budget, payment allocation should consider both effects to obtain best results. Since people are not deterministic, payment offers will lead to a random number of variable-quality workers, as governed by choice models. We consider average performance and focus on estimating a parameter from measurements through uniform noise. Since we have shown the optimality of the midrange estimator in specific settings of the general problem, we focus on the best linear unbiased estimator based on order statistics (BLUE-OS) under the mean-squared error (MSE) criterion. Best payment allocations are determined for single crowd platforms, joint population models and separated platform models. Illustrative numerical examples are provided.

In the Big Data era, informational systems involving humans and machines are being deployed in multifarious societal settings. Many use data analytics as subcomponents for descriptive, predictive, and prescriptive tasks, often trained using machine learning. Yet when analytics components are placed in large-scale sociotechnical systems, it is often difficult to characterize how well the systems will act, measured with criteria relevant in the world. Here, we propose a system modeling technique that treats data analytics components as “noisy black boxes” or stochastic kernels, which together with elementary stochastic analysis provides insight into fundamental performance limits. An example application is helping prioritize people’s limited attention, where learning algorithms rank tasks using noisy features and people sequentially select from the ranked list. This paper demonstrates the general technique by developing a stochastic model of analytics-enabled sequential selection, derives fundamental limits using concomitants of order statistics, and assesses limits in terms of system-wide performance metrics, such as screening cost and value of objects selected. Connections to sample complexity for bipartite ranking are also made.

Consider designing an effective crowdsourcing system for an $M$-ary classification task. Crowd workers complete simple binary microtasks whose results are aggregated to give the final result. We consider the novel scenario where workers have a reject option so they may skip microtasks when they are unable or choose not to respond. For example, in mismatched speech transcription, workers who do not know the language may not be able to respond to microtasks focused on phonological dimensions outside their categorical perception. We present an aggregation approach using a weighted majority voting rule, where each worker's response is assigned an optimized weight to maximize the crowd's classification performance. We evaluate system performance in both exact and asymptotic forms. Further, we consider the setting where there may be a set of greedy workers that complete microtasks even when they are unable to perform it reliably. We consider an oblivious and an expurgation strategy to deal with greedy workers, developing an algorithm to adaptively switch between the two based on the estimated fraction of greedy workers in the anonymous crowd. Simulation results show improved performance compared with conventional majority voting., two column, 15 pages, 8 figures, submitted to IEEE Trans. Signal Process

It is often said that successive generations of researchers face an increasing educational burden due to knowledge accumulation. On the other hand, technological advancement over time can improve the productivity of researchers and even change their cognitive processes. This paper presents a longitudinal study (2004–2011) of citation behavior in doctoral theses at the Massachusetts Institute of Technology’s Department of Electrical Engineering and Computer Science. It is found that the number of references cited has increased over the years. At the same time, there has been a decrease in the length of time in the doctoral program and a relative constancy in the culture of the department. This suggests that students are more productive in facing an increased knowledge burden, and indeed seem to encode prior literature as transactive memory to a greater extent, as evidenced by the greater use of older literature.

Computational creativity is an emerging branch of artificial intelligence that places computers in the center of the creative process. Broadly, creativity involves a generative step to produce many ideas and a selective step to determine the ones that are the best. Many previous attempts at computational creativity, however, have not been able to achieve a valid selective step. This paper shows how bringing data sources from the creative domain and from hedonic psychophysics together with machine learning and data analytics techniques can overcome this shortcoming to yield a system that can produce novel and high-quality creative artifacts. To demonstrate our data-driven approach, we developed and deployed a computational creativity system for culinary recipes and menus, Chef Watson, which can operate either autonomously or semiautonomously with human interaction. We present the basic system architecture, data engineering, and algorithms that are involved. Experimental results demonstrate the system passes the test for creativity based on the consensual assessment technique, producing a novel and flavorful recipe. Large-scale deployments are also discussed.

We study the information-theoretic limit of reliable information processing by a server with queue-length dependent quality of service. We define the capacity for such a system as the number of bits reliably processed per unit time, and characterize it in terms of queuing system parameters. We also characterize the distributions of the arrival and service processes that maximize and minimize the capacity of such systems in a discrete-time setting. For arrival processes with at most one arrival per time slot, we observed a minimum around the memoryless distribution. We also studied the case of multiple arrivals per time slot, and observed that burstiness in arrival has adverse effects on the system. The problem is theoretically motivated by an effort to incorporate the notion of reliability in queueing systems, and is applicable in the contexts of crowdsourcing, multimedia communication, and stream computing.

Developing automatic speech recognition technologies requires transcribed speech so as to learn the mapping from sound to text. It is traditionally assumed that transcribers need to be native speakers of the language being transcribed. Mismatched crowdsourcing is the transcription of speech by crowd workers who do not speak the language. Given there are phonological similarities among different human languages, mismatched crowdsourcing does provide noisy data that can be aggregated to yield reliable labels. Here we discuss phonological properties of different languages in a coding-theoretic framework, and how nonnative phoneme misperception can be modeled as a noisy communication channel. We show the results of experiments demonstrating the efficacy of this information theory inspired modeling approach, having native English speakers and native Mandarin speakers transcribe Cantonese speech. Finally we discuss how crowd workers whose native language background give them the highest probability of faithful transcription can be found by solving a weighted set cover problem.

People and machines perform tasks differently. Building optimal systems that include people and machines, requires understanding their respective behavioral properties. The task of decision fusion is considered and the performance of people is compared to the optimal fusion rule. Our behavioral experiments demonstrate that people perform decision fusion in a stochastic manner dependent on various factors, whereas optimal rule is deterministic. A Bayesian hierarchical model is developed to characterize the observed human behavior. This model captures the differences observed in people at individual level, crowd level, and population level. The implications of such a model on developing large-scale human-machine systems are presented by developing optimal decision fusion trees with both human and machine agents.

Transcribers make mistakes. Workers recruited in a crowdsourcing marketplace, because of their varying levels of commitment and education, make more mistakes than workers in a controlled laboratory setting. Methods for compensating transcriber mistakes are desirable because, with such methods available, crowdsourcing has the potential to significantly increase the scale of experiments in laboratory phonology. This paper provides a brief tutorial on statistical learning theory, introducing the relationship between dataset size and estimation error, then presents a theoretical description and preliminary results for two new methods that control labeler error in laboratory phonology experiments. First, we discuss the method of crowdsourcing over error-correcting codes. In the error-correcting-code method, each difficult labeling task is first factored, by the experimenter, into the product of several easy labeling tasks (typically binary). Factoring increases the total number of tasks, nevertheless it results in faster completion and higher accuracy, because workers unable to perform the difficult task may be able to meaningfully contribute to the solution of each easy task. Second, we discuss the use of explicit mathematical models of the errors made by a worker in the crowd. In particular, we introduce the method of mismatched crowdsourcing, in which workers transcribe a language they do not understand, and an explicit mathematical model of second-language phoneme perception is used to learn and then compensate their transcription errors. Though introduced as technologies that increase the scale of phonology experiments, both methods have implications beyond increased scale. The method of easy questions permits us to probe the perception, by untrained listeners, of complicated phonological models; examples are provided from the prosody of English and Hindi. The method of mismatched crowdsourcing permits us to probe, in more detail than ever before, the perception of phonetic categories by listeners with a different phonological system.

Crowdsourcing of jobs to online freelance markets is rapidly gaining popularity. Most crowdsourcing platforms are uncontrolled and offer freedom to customers and freelancers to choose each other. This works well for unskilled jobs (e.g., image classification) with no specific quality requirement since freelancers are functionally identical. For skilled jobs (e.g., software development) with specific quality requirements, however, this does not ensure that the maximum number of job requests is satisfied. In this work we determine the capacity of freelance markets, in terms of maximum satisfied job requests, and propose centralized schemes that achieve capacity. To ensure decentralized operation and freedom of choice for customers and freelancers, we propose simple schemes compatible with the operation of current crowdsourcing platforms that approximately achieve capacity. Further, for settings where the number of job requests exceeds capacity, we propose a scheme that is agnostic of that information, but is optimal and fair in declining jobs without wait.

It is well known that uncoded transmission of a memoryless Gaussian source over a memoryless additive white Gaussian noise channel results in optimal performance theoretically attainable. When there is additional interference in the channel, uncoded transmission is robust. It achieves the same sensitivity performance as optimal performance, measured using sensitivity results of Pinsker, Prelov, and Verdu.

Compared to artifacts in expressive or performance domains, work products resulting from scientific creativity (including culinary recipes) seem much more conducive to data-driven assessment. If such products are viewed as an assembly of constituents that follow certain association principles, one could apply computationally intensive techniques to generate many possible combinations and use automated assessors to evaluate each of them. Assembly work plans for the selected novel products could subsequently be inferred from existing records. In this chapter, we report on our efforts to build a computational creativity system for culinary recipes. After gathering data and creating a knowledge base of recipes and ingredients, the system generates ingredient combinations that satisfy user inputs such as the choice of key ingredient, desired dish, and cuisine. Once a combination has been selected with the help of novelty and quality evaluators, the system further recommends ingredient proportions using a distributional conformance method and generates recipe steps using a subgraph composition algorithm. The time durations or efforts of atomic steps are estimated by solving an inverse problem from data on complete recipes. The example of culinary recipes could be generalized and applied to other scientific domains; manufacturing products and business processes could potentially follow a similar recipe for success.