| paper | d4-conf-ijcai-2009-0336 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Every cohort's minimal representation is identifiable with total queries and learner running time polynomial in \(n,\tau,S,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given \(n\) Boolean attributes and \(\tau\) addressable preference-homogeneous cohorts with known rational masses \(\mu_g>0\) summing to \(1\), each with its own unknown acyclic CP-net, can a learner identify every cohort's minimal representation using cohort-specific equivalence queries and swap membership queries, with total query and running-time bounds polynomial in \(n\), \(\tau\), the total representation size, and the mass bit length \(L\)?
The society is a distribution \(\mu\) over \(\tau\) cohorts, each sharing one hidden acyclic CP-net over the same \(n\) Boolean attributes. The decision variables are the cohort hypotheses \(N_g\); the learner has a swap membership oracle and an equivalence oracle for each cohort, and must identify every \(N_g\). Repeated application of Theorem 2 gives at most \(\sum_g (|N_g^*|+1)\) equivalence queries and \(\sum_g e_g\lceil\log n\rceil\) membership queries, where \(N_g^*\) is cohort \(g\)'s minimal representation and \(e_g\) its number of edges.
The masses do not change the query strategy, and the learner needs a separate oracle for each named cohort, so the computation is a batch of target-learning tasks rather than learning from aggregate population responses.
fatal: False
The mirror covers Theorem 2's exact learning of acyclic CP-nets from swap examples. It leaves the equivalence-query-only lower bound, the tree-CP-net results, and the earlier passive-learning hardness cited in the discussion outside its scope.
I would lead with Theorem 2, proved in this paper. It says that acyclic CP-net concepts are attribute-efficiently learnable using equivalence and membership queries restricted to swaps: a target with minimal representation \(N^*\) can be identified in polynomial time with at most \(|N^*|+1\) equivalence queries and \(e\lceil\log n\rceil\) membership queries, where \(e\) is the number of edges in \(N^*\). The paper’s other formal learning results are also relevant, but this is its clearest constructive anchor. The NP-hardness of passive learning mentioned in the discussion is attributed to earlier work; it is not a numbered result proved here.
A continuous version I find plausible is Mass-Weighted Cohort CP-net Elicitation. The society consists of \(\tau\) addressable cohorts with known masses \(\mu_g\in\mathbb{Q}_{>0}\), summing to \(1\). Members of a cohort share the same binary attributes and the same, initially unknown, acyclic CP-net preference model. A cohort query asks about its shared preferences: a membership query supplies a swap \((o,o')\) and returns whether \(o\succ_g o'\); an equivalence query supplies a CP-net hypothesis and returns either confirmation or a swap counterexample. The task is to output, for every cohort \(g\), a CP-net \(N_g\) representing its dominance relation exactly. The decision variable is the set of cohort-specific hypotheses; the computational objective is to identify them with bounded query and running-time resources.
The regime is a large recommender or product-design population: perhaps millions of users but a relatively small number \(\tau\) of stable, preference-homogeneous segments. A type here is a complete preference description for this task: members of the same cohort agree on the attributes and all conditional preferences represented by their CP-net. The masses record what fraction of the population each learned model represents. A finite population with cohort counts \(n_g\) gives \(\mu_g=n_g/N\); the continuous version allows arbitrary binary-rational proportions. The cohort identifiers must be available so the learner can direct a query to a representative. That makes mass, rather than a count of individually addressable users, the natural description of the society.
This mirror is tractable directly by running the paper’s algorithm once per cohort. If \(N_g^*\) is the minimal representation for cohort \(g\) and \(e_g\) its number of edges, the total query bounds are \(\sum_g(|N_g^*|+1)\) equivalence queries and \(\sum_g e_g\lceil\log n\rceil\) membership queries. The resulting running time is polynomial in \(n\), \(\tau\), the bit length \(L\) of the masses, and the total description size of the cohort models. Thus the expected direction is tractable. This is a multi-cohort continuation of the paper’s elicitation problem, not a claim that the theorem already solves learning a hidden mixture from population-level averages.
The scope is deliberately limited to Theorem 2’s acyclic-CP-net learning result, with swap examples. It does not claim a mirror for the paper’s equivalence-query-only lower bound or its tree-CP-net results with arbitrary examples.
The weakest point is that the masses do little computational work: the algorithm learns each cohort’s model separately, and its query bounds do not improve when one cohort is especially large. A referee could reasonably call this batch elicitation over homogeneous segments, rather than a new continuous-learning phenomenon. I think it is still a sensible mirror because the population is represented by its segment masses, no individual-level targeting is needed within a segment, and the paper itself motivates preference elicitation in applications including group decision-making. It would not support a stronger claim about learning from an undifferentiated population. That leads to a distinct follow-up question: if queries can only ask what *fraction* of the whole society prefers a swap, can the learner recover the population’s aggregate preference behavior, or do different mixtures of CP-nets become indistinguishable?
Theorem 2 is a genuine computational result, so the case against cannot rest on a lack of an algorithmic anchor. Its target, though, is one unknown dominance relation \(\succ\), accessed through membership and equivalence queries that all refer to that same relation.
The cohort construction replaces that target with \(\tau\) separate relations, \(\succ_1,\ldots,\succ_\tau\), and runs the learning algorithm once for each. The masses \(\mu_g\) do not affect the queries or the learned models: a cohort with tiny positive mass costs as many queries as one containing most of the population. To answer queries, the learner also needs access to a representative of each named cohort. The resulting task is coherent, and could be useful for learning preference segments, but its computation is a batch of single-target learning problems. The continuous society supplies weights to the output without changing what the algorithm must learn.
The strongest population-level repair would make a query return the fraction of society for whom \(o\succ o'\). That makes mass operational, but it changes the paper’s oracle and target. Answers are now numbers, not membership labels for one strict partial order; an equivalence-query counterexample to a mixture of CP-nets also needs a new definition. Recovering the mixture may be impossible from pairwise responses when different mixtures induce the same aggregate answers. Learning only those aggregate answers is a different objective from identifying a CP-net, and would need its own model and guarantees.
A weighted objective, such as learning models for all but an \(\varepsilon\) fraction of the population, is another plausible direction. It changes exact identification into approximate population learning and adds choices about query access and coverage. That may be worth studying, but it is not a continuous version of Theorem 2’s exact-learning problem.
So the strongest negative case is that this paper’s central computation is driven by oracle access to individual preference relations, while its proposed population masses have no role in that computation. I cannot make that case airtight: learning a small set of preference models for large user segments is a sensible application, and the paper’s elicitation setting could motivate a new aggregate-learning problem. I would treat those as adjacent research directions, rather than a strong ChoCo mirror of the named result.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.