| paper | Learning Conditional Preference Networks: An Approach Based on the Minimum Description Length Principle |
| authors | Pierre-François Gimenez, Jérôme Mengin |
| venue | IJCAI 2024 |
| filed under | voting · combinatorial |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Proposition 2
statement extracted from the paper’s text layer
Given attributes \(X\) with finite domains, a rational distribution \(\mu\) over configurations \(o\in\mathcal{X}=\prod_{A\in X}A\), and a rational threshold \(q\), find an acyclic CP-net \(\phi\) minimizing \(\operatorname{NMCL}_{\mu}(\phi)=\frac{1}{n}\sum_{o\in\operatorname{supp}(\mu)}\mu_o\lvert\operatorname{code}(o,\phi)\rvert\), or decide whether the minimum is at most \(q\), using the paper's minimal-code definition.
A high-multiplicity population-risk CP-net learning problem: each agent's complete observable type is a purchased configuration \(o\), \(\mu_o\) is its population mass, the decision variable is an acyclic CP-net \(\phi\), and the objective is expected normalized code length.
The mirror treats repeated observed configurations as population types, although the paper's motivating users have latent preferences and noisy choice channels, so it may not model a population of customers in the semantic sense.
fatal: False
Covers Proposition 2 and the NMCL surrogate's exact empirical optimizer; it leaves Proposition 1's sample-complexity result, the full MDL objective \(L(\phi)+L(D\mid\phi)\), the heuristic algorithm, and the experiments outside the mirror.
The paper admits a strong, direct continuous mirror, although the result on that mirror is likely Class B rather than tractable. My lead anchor is Proposition 2:
“Let \(D\) be a dataset. The problem of finding the minimal acyclic CP-net that minimizes the empirical normalized mean code length over \(D\) is NP-complete.”
This proposition is proved in the paper, not merely cited; the paper gives a proof sketch and points to the full proof in its repository. The reduction is from Minimum Feedback Arc Set.
A plausible regime is a large product-configurator or fleet-order market. The agents are customers or sales events, \(N\) is the number of completed orders, and \(\tau\) is the number of recurring configurations. A type is a complete configuration \(o\in\mathcal X\), including every attribute used by the learning problem. Two customers are the same type precisely when they contribute the same observable configuration to the dataset; if the model used region, customer segment, price, or other covariates, those would have to be included in the type as well. In a mass-market or fleet setting, \(N\gg\tau\) is entirely credible: many orders may use the same option bundle even though the full configuration space is exponential.
The mass \(\mu_o\) is the fraction of sales events producing configuration \(o\). The continuous object is therefore a rational distribution \(\mu\) over discrete configurations, not a fractional product or a probabilistic CP-net. The learner chooses an acyclic CP-net \(\phi=(\mathcal X,\mathrm{Pa},\mathrm{CPT})\). For each configuration \(o\), let \(\operatorname{code}(o,\phi)\) be the paper’s minimal partial instantiation whose optimal completion under \(\phi\) is \(o\). The continuous objective is
\[ \operatorname{NMCL}_{\mu}(\phi) = \frac{1}{n}\sum_{o\in T}\mu_o \left|\operatorname{code}(o,\phi)\right|, \]
where \(T\) is the support of \(\mu\) and \(n\) is the number of attributes.
I would call the resulting problem Population-NMCL Acyclic CP-net Learning:
This is a direct high-multiplicity relaxation. Given a finite sales history \(D\), set
\[ \mu_o=\frac{\#_D(o)}{|D|}. \]
Then the empirical NMCL of \(D\) is exactly \(\operatorname{NMCL}_{\mu}(\phi)\) for every \(\phi\). Conversely, clearing the denominators of a rational \(\mu\) reconstructs a finite multiset of sales events with those proportions. Ties, codes, feasible CP-nets, and objective comparisons are unchanged.
The NP-hardness also transfers transparently. In the paper’s reduction from a graph \(G=(V,E)\), the dataset contains \(3|E|+1\) copies of the all-\(K\) configuration and one copy of each of three edge-specific configurations for every edge. Replace that multiset by a distribution giving the all-\(K\) configuration mass
\[ \frac{3|E|+1}{6|E|+1} \]
and each edge-specific configuration mass
\[ \frac{1}{6|E|+1}. \]
Every CP-net has exactly the same objective value as it had on the constructed dataset. Thus an exact optimizer for Population-NMCL Acyclic CP-net Learning would solve the paper’s FAS instance. The expected classification is therefore Class B: the hardness survives because the combinatorics live in the attribute-dependency DAG and its acyclicity constraint, not in the number of customers. Continuization compresses repeated sales, but it does not dissolve the source of hardness.
The authors should recognize this as their problem. Their input is already a multiset of purchased configurations, their objective is already an average code length, and their recommendation model is already a CP-net selected from those frequencies. The mirror merely promotes normalized frequencies from a derived empirical object to the explicit population input. It preserves the central question: which acyclic conditional-preference structure best explains and guides a population of observed choices?
The scope is deliberately narrow. This mirrors Proposition 2 and its NMCL surrogate, not the full MDL objective \(L(\phi)+L(D\mid\phi)\). A full continuous MDL version would need an additional population-scale parameter, since after normalization the model-description term becomes something like \(L(\phi)/|D|\). I would not claim that result here. I also would not use Proposition 1 as a second anchor: it is a named sample-complexity result, but not itself a computational optimization classification. It does, however, suggest a natural follow-up: unknown-\(\mu\) learning from sampled customers, with guarantees of the form
\[ \operatorname{NMCL}_{\mu}(\widehat{\phi}) - \operatorname{NMCL}_{\mu}(\bar{\phi}) \leq \varepsilon. \]
For fixed domain size and parent bound, Proposition 1 already points toward polynomial sample complexity, while Proposition 2 warns that finding the exact empirical optimizer may remain NP-hard.
The weakest point is the information model. Giving \(\mu\) exactly makes this a population model-selection problem rather than the paper’s finite-sample learning process, and a repeated configuration does not necessarily imply identical latent customer preferences. That objection is real. But it does not undermine the Proposition 2 mirror: the proposition itself uses only the observed multiset of configurations, not hidden preferences or customer identities. The honest claim is therefore not that every aspect of the paper has been continuized, but that its central NP-complete structural-learning problem has a faithful rational-mass formulation, with hardness surviving the passage to a continuous population.
The proponent is right about one important point: Proposition 2 is a genuine named computational result, and the rational-weight calculation is correct. If \(D\) is replaced by \(\mu_o=\#_D(o)/|D|\), then
\[ \operatorname{NMCL}_{D}(\phi) = \frac{1}{n}\sum_o \mu_o\lvert \operatorname{code}(o,\phi)\rvert . \]
Clearing denominators recovers the finite instance exactly, so the NP-hardness transfer is valid. The negative case therefore cannot rest on denying the proposition or on saying that inherited hardness is uninteresting.
The problem is what is being cloned. The paper’s agents are users with latent preference relations. A purchased configuration \(o\) is only an observation of a user, not a complete user type. The paper explicitly allows advertisements, special offers, unavailability, and other influences to make a user choose something other than her most preferred product. Thus two users who purchase the same \(o\) may have entirely different preferences, and two users with the same preference may purchase different configurations. The proponent’s \(\mu_o\) is consequently a distribution over observed outcomes, not a distribution over indistinguishable agents.
That distinction creates a dilemma. If the formal problem is taken literally, the latent preferences are absent and \(D\) is merely a multiset of data rows. Then \(\mu\) is just a histogram representation of the training sample. The paper has effectively already introduced the corresponding population quantity as \(p\) in its definition of normalized mean code length. Promoting that \(p\) to an explicit input does not continuize a society; it replaces a list of observations by their empirical distribution. Every learning problem with an additive empirical loss could receive the same treatment.
If instead one uses the paper’s motivating user semantics, a type must include at least the user’s preference relation and whatever context governs the observed purchase. The appropriate population objective would require an observation channel, for example
\[ \mathbb E_{\theta\sim\mu} \mathbb E_{o\sim K(\cdot\mid\theta)} \left[ \frac{1}{n}\lvert\operatorname{code}(o,\phi)\rvert \right]. \]
Neither the latent type \(\theta\) nor the choice kernel \(K\) is specified by the paper. Supplying them is not a harmless change of notation: it changes the learning problem. If \(\mu\) and \(K\) are given exactly, the statistical learning problem has been replaced by population-risk minimization. If only sales samples are available, one has returned to the paper’s original finite-sample setting.
The proposed fleet or mass-market scenario does not cure this. Repeated configurations may be common, but repetition of an observed product does not establish repeated preference types. One can stipulate that every customer choosing a given configuration is genuinely identical, but then one has deliberately removed the paper’s latent-preference and noisy-choice interpretation. The result becomes a weighted model-fitting problem over product configurations, recognizable as an extension but not a faithful population mirror of the stated learning task.
There is also no population operation in Proposition 2: no mass is transferred, agents are not altered, and collective behavior is not computed. The only role of \(\mu\) is to weight the loss used to select a single CP-net. The resulting Class B hardness is mathematically legitimate, but it is inherited by denominator clearing from the finite optimization and says nothing specifically about computation over a continuous society.
Thus the strongest negative case is not that the proponent’s formulation is ill-defined. It is well-defined and exactly equivalent to weighted empirical NMCL minimization. The case against it is that the formulation either loses the paper’s agents and becomes a routine weighted-data restatement, or restores them only by adding an unspecified observation model and thereby changing the problem. That is a substantial obstruction to calling it a worthwhile continuous-social-choice mirror. The universal negative is not airtight, however: under a permissive interpretation in which distributions over observed configurations count as populations, Proposition 2 does survive as a narrow direct high-multiplicity reformulation.
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.