| paper | d4-conf-ijcai-2015-0004 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\), even with one worker type and fixed positive regularization and accuracy parameters. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given \(N\) concepts, worker response types \(r\) with rational population masses \(\mu_r\), and per-type answer frequencies \(v_{r,q,a}\) for path query \(q\) and answer \(a\), form \(Q_\mu(T)\propto \pi_0(T)\exp(\sum_{r,q,a}\mu_r v_{r,q,a}\log f_r(a\mid T,q))\) over rooted hierarchies \(T\). For \(P_\Lambda(T)=\exp(\sum_{e\in T}\lambda_e)/Z(\Lambda)\), find \(\Lambda\) within \(\epsilon\) of the minimum of \(\mathbb{E}_{T\sim Q_\mu}[-\log P_\Lambda(T)]+\beta\sum_e|\lambda_e|\); determine the convergence and finite-precision complexity in \(N\), support size \(\tau\), input bit length \(L\), and \(\epsilon^{-1}\).
A Bayesian posterior over hierarchies whose answer log-likelihoods are weighted by worker-type population masses, followed by the paper's regularized fit of an edge-factorized tree distribution.
The mirror covers posterior fitting after crowd answers are collected; it leaves active query selection, the cost of obtaining posterior samples or marginals, new-node insertion, and the end-to-end pipeline open.
The paper has no named theorem asserting that a problem is in P, NP-hard, FPT, or another standard complexity class. The closest useful anchor is Theorem 1 in §3.3, proved in the paper’s appendix (where the proof heading calls it Theorem 3). It says that for \(\beta>0\), Algorithm 1 generates a sequence \(\Lambda^{(1)},\Lambda^{(2)},\ldots\) whose regularized negative log-likelihood converges to its global minimum: \(\lim_{\ell\to\infty} L^\beta_{\tilde\pi}(\Lambda^{(\ell)})=\min_\Lambda L^\beta_{\tilde\pi}(\Lambda)\), where \(\tilde\pi\) is the empirical distribution of sampled trees. This is a convergence result, not a polynomial-time bound. If the required anchor must assert a complexity class, then there is no compliant positive case; what follows is the strongest narrower case I can make from a named computational result.
A plausible high-multiplicity setting is a large annotation workforce in which many workers fall into a small number \(\tau\) of calibrated response types. A type records a worker’s response behavior across the path questions, including their error tendencies. The society is the distribution \(\mu\) over those types: many workers, but relatively few distinct response profiles. This fits the paper’s use of crowdsourcing and its goal of representing disagreement, though the paper itself does not study a workforce at that scale.
The resulting question is Mass-Fit Hierarchy Inference, a mirror of the paper’s posterior-fitting step. An instance has a concept set of size \(N\), worker types with rational masses \(\mu_r\), and, for each type, the edge marginals \(\rho_{r,e}\) of the hierarchy distribution induced by its accumulated answers. The population’s aggregate edge statistics are \(\rho_e=\sum_r\mu_r\rho_{r,e}\). For rooted trees \(T\) and parameters \(\Lambda=(\lambda_e)\), define \(P_\Lambda(T)=\exp(\sum_{e\in T}\lambda_e)/Z(\Lambda)\). Given \(\beta>0\) and \(\epsilon>0\), find \(\Lambda\) whose value is within \(\epsilon\) of the minimum of \(F(\Lambda)=\log Z(\Lambda)-\sum_e\rho_e\lambda_e+\beta\sum_e|\lambda_e|\). The output is an edge-factorized distribution over hierarchies that fits the crowd’s mass-weighted evidence.
I expect this fitting problem to be tractable—Class A—when the edge marginals are available: it is a convex objective in \(O(N^2)\) variables, and the matrix-tree theorem supplies the partition function and its marginals. Theorem 1 supports this direction by proving convergence of the paper’s update procedure for sampled evidence; it does not establish a polynomial-time algorithm for the mass-input version. Further questions are whether the \(\rho_{r,e}\) can be computed efficiently from raw answer masses, whether active query selection remains tractable with type-level outcomes, and how the model behaves when worker types must be inferred.
This mirror covers hierarchy-distribution fitting after answers have been collected. It does not claim a continuous version of the paper’s active query-selection results or its new-node procedure. I would not use Theorem 2 as another anchor: its sample count \(m\) is a count of sampled trees used in Monte Carlo estimation, not a count of crowd workers.
The weakest point is that the mirror’s tractable input consists of edge marginals already distilled from the crowd evidence. Computing those statistics from the full type-level answer record may be the hard part, and the paper’s theorem does not resolve it. The worker-type model is also an added assumption, not one established in the paper. So the positive case is credible for the fitting subproblem, but it does not support a claim that the paper’s full crowdsourcing pipeline becomes tractable through population continuization.
The claimed anchor is thinner than the paper’s computational content suggests. Theorem 1 proves convergence of Algorithm 1’s parameter updates to the minimum of \(L^\beta_{\tilde\pi}\), for an empirical distribution \(\tilde\pi\) of sampled trees. Its iteration index \(\ell\) counts optimization steps; the sample count \(m\) counts trees. Neither is a count of workers. The paper states no complexity result for a problem whose population size might be continuized.
The proposed Mass-Fit problem also does not pool crowd evidence in the Bayesian sense. Averaging each worker type’s posterior edge marginals describes the posterior of a randomly selected type, then fits that average. Joint evidence instead multiplies the types’ likelihoods: with masses, its log-likelihood is proportional to \(\sum_{r,q,a}\mu_{r,q,a}\log f(a\mid T)\). Those two constructions generally differ. So the stated \(\rho_e\) objective is a legitimate fitting problem, but it is not the paper’s update applied to a continuous crowd.
A stronger repair would use masses of response types and their answers to each query, then fit to the pooled weighted likelihood. That gives a coherent population model. But the population masses enter as coefficients on observations; the hard structure remains the tree space, path-question likelihoods, and active query choice. The paper’s challenge is already to handle those structures. Replacing integer answer counts with proportions creates no evident multiplicity bottleneck to relax and no complexity landscape corresponding to Theorem 1. It would be a new continuous crowdsourcing inference problem, not a high-multiplicity mirror of the result the proponent selected.
The negative case is still weak against the user’s universal standard. A large workforce with a small number of shared response laws is plausible, and a continuous model of how its answer mass informs hierarchy inference could be worth studying. I can reject the proposed anchor as a strong case for this programme, but I cannot honestly rule out every worthwhile population-continuous formulation.
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.