skip to main content

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Friday, December 13 until 2:00 AM ET on Saturday, December 14 due to maintenance. We apologize for the inconvenience.


Title: Card guessing with partial feedback
Abstract Consider the following experiment: a deck with m copies of n different card types is randomly shuffled, and a guesser attempts to guess the cards sequentially as they are drawn. Each time a guess is made, some amount of ‘feedback’ is given. For example, one could tell the guesser the true identity of the card they just guessed (the complete feedback model) or they could be told nothing at all (the no feedback model). In this paper we explore a partial feedback model, where upon guessing a card, the guesser is only told whether or not their guess was correct. We show in this setting that, uniformly in n , at most $m+O(m^{3/4}\log m)$ cards can be guessed correctly in expectation. This resolves a question of Diaconis and Graham from 1981, where even the $m=2$ case was open.  more » « less
Award ID(s):
1954042
PAR ID:
10339301
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
Combinatorics, Probability and Computing
Volume:
31
Issue:
1
ISSN:
0963-5483
Page Range / eLocation ID:
1 to 20
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We examine the use of computer-based learning in the classroom and the effect of immediate feedback on student performance. Since it is well known in educational research that it is possible to observe a “Matthew Effect” in which the rich get richer, we wanted to see if feedback was useful for low prior knowledge students, as defined by students whose pretest score was at or below the median. In this counterbalanced randomized controlled trial, 243 tenth and eleventh grade mathematics students were exposed to one of two conditions, as we measured their learning from: 1) immediate feedback (where the computer told them correctness and they could also ask for hints) or 2) practice only (where they received feedback only after taking a posttest). Results suggest that immediate feedback from computer-based learning tasks benefit both high and low prior knowledge students, with low prior knowledge students exhibiting greater gains. The implications of these findings support further investigation into the use of computer-based learning tasks that provide immediate feedback. 
    more » « less
  2. We examine the use of computer-based learning in the classroom and the effect of immediate feedback on student performance. Since it is well known in educational research that it is possible to observe a “Matthew Effect” in which the rich get richer, we wanted to see if feedback was useful for low prior knowledge students, as defined by students whose pretest score was at or below the median. In this counterbalanced randomized controlled trial, 243 tenth and eleventh grade mathematics students were exposed to one of two conditions, as we measured their learning from: 1) immediate feedback (where the computer told them correctness and they could also ask for hints) or 2) practice only (where they received feedback only after taking a posttest). Results suggest that immediate feedback from computer-based learning tasks benefit both high and low prior knowledge students, with low prior knowledge students exhibiting greater gains. The implications of these findings support further investigation into the use of computer-based learning tasks that provide immediate feedback. 
    more » « less
  3. By design, large language models (LLMs) are static general-purpose models, expensive to retrain or update frequently. As they are increasingly adopted for knowledge-intensive tasks, it becomes evident that these design choices lead to failures to generate factual, relevant, and up-to-date knowledge. To this end, we propose Knowledge Card, a modular framework to plug in new factual and relevant knowledge into general-purpose LLMs. We first introduce knowledge cards---specialized language models trained on corpora from specific domains and sources. Knowledge cards serve as parametric repositories that are selected at inference time to generate background knowledge for the base LLM. We then propose three content selectors to dynamically select and retain information in documents generated by knowledge cards, specifically controlling for relevance, brevity, and factuality of outputs. Finally, we propose two complementary integration approaches to augment the base LLM with the (relevant, factual) knowledge curated from the specialized LMs. Through extensive experiments, we demonstrate that Knowledge Card achieves state-of-the-art performance on six benchmark datasets. Ultimately, Knowledge Card framework enables dynamic synthesis and updates of knowledge from diverse domains. Its modularity will ensure that relevant knowledge can be continuously updated through the collective efforts of the research community. 
    more » « less
  4. U.S. elections rely heavily on computers such as voter registration databases, electronic pollbooks, voting machines, scanners, tabulators, and results reporting websites. These introduce digital threats to election outcomes. Risk-limiting audits (RLAs) mitigate threats to some of these systems by manually inspecting random samples of ballot cards. RLAs have a large chance of correcting wrong outcomes (by conducting a full manual tabulation of a trustworthy record of the votes), but can save labor when reported outcomes are correct. This efficiency is eroded when sampling cannot be targeted to ballot cards that contain the contest(s) under audit. If the sample is drawn from all cast cards, then RLA sample sizes scale like the reciprocal of the fraction of ballot cards that contain the contest(s) under audit. That fraction shrinks as the number of cards per ballot grows (i.e., when elections contain more contests) and as the fraction of ballots that contain the contest decreases (i.e., when a smaller percentage of voters are eligible to vote in the contest). States that conduct RLAs of contests on multi-card ballots or RLAs of small contests can dramatically reduce sample sizes by using information about which ballot cards contain which contests—by keeping track of card-style data (CSD). For instance, CSD reduce the expected number of draws needed to audit a single countywide contest on a 4-card ballot by 75%. Similarly, CSD reduce the expected number of draws by 95% or more for an audit of two contests with the same margin on a 4-card ballot if one contest is on every ballot and the other is on 10% of ballots. In realistic examples, the savings can be several orders of magnitude. 
    more » « less
  5. Are underperforming women given less truthful, but kinder performance feedback (“white lies”) compared with equally underperforming men? We test this hypothesis by using a “benchmark” of truthful (objective) evaluation of performance and then either manipulating (Study 1) or measuring (Study 2) the extent to which the feedback given to women is upwardly distorted. In Study 1, participants were asked to guess the gender of an underperforming employee who had been given more or less truthful feedback. Participants overwhelmingly assumed that employees who had been told “white lies” were more likely to be women. In Study 2, in a naturalistic feedback paradigm, participants gave both quantitative and qualitative feedback to a male and a female writer directly. Participants upwardly distorted their original, gender-blind, quantitative evaluations of women’s work and gave more positive comments to women. The findings suggest that women may not receive the same quality of feedback as men.

     
    more » « less