advanced extraction-knowledge-graphs 40 min read

Capstone: An Earnings-Call NLP Pipeline

Four published stages read earnings calls into a knowledge graph. Which stage costs what is a question about a lattice of oracle swaps, what one stage should hand the next is a question about garbling, and when the knowledge base can repair its own output is a question about total unimodularity.

Overview & Motivation

Twenty-eight topics built models one at a time. This one runs four of them in sequence on earnings calls and asks what the composition does that no single model does.

Take one synthetic call, the Marrow Freight quarterly results call from the seen-roster test run. Its first sentence is “Thank you for joining the Marrow Freight quarterly results call.” Topic 22’s tagger misses “Marrow Freight” there, so the pipeline never learns whose call it is. It misses the name again in “Marrow Freight operates in the industrials sector,” so the relation reader never sees the pair, and the sector fact is lost. It tags only “Fenwick” in “Fenwick Logistics is headquartered in Houston, Texas,” and the linker cannot place a bare “Fenwick,” so the headquarters fact is lost too. The relation reader gets the three facts whose arguments survive. Topic 17’s logistic regression calls the call positive; the generator made it neutral, and Topic 19’s aspect reader agrees with the generator. Every error is local, but they all land in one place: the call graph, the facts the calls state plus each call’s subject, tone, and aspect polarities. The lab’s Trace a call tab shows this call sentence by sentence.

Three questions follow, and each has a precise answer.

  1. Who gets the blame? Fix one stage at a time by giving it the gold answer, and see how much the graph improves. The answer depends on the order in which we fix them, and the Shapley value removes that dependence (Theorem 1). On 126 calls, tone takes the largest share, aspects exactly none (Corollary 1), and the only sizable interaction is that entities and relations are complements.
  2. What should one stage hand the next? A posterior instead of an argmax can only help a successor that acts optimally on it (Theorem 2(a)), and it can hurt one that does not (Theorem 2(b)). On the calls, span marginals raise fact AP from 0.7440.744 to 0.8510.851 and lower F1 at the hard pipeline’s threshold.
  3. Can the knowledge base repair the output? Constraints such as “one headquarters city per company” turn fact selection into an integer program. With inverse and symmetric facts merged, its LP relaxation is exact (Theorem 3), and adding composition rules breaks that (Proposition 3).

formalRAG’s capstone proved the product law for a retrieval cascade. That law reappears in Proposition 1, and the three results above are what a pipeline of different stages adds to it.


The pipeline and its oracles

The test documents are the entity-recognition topic’s two test runs of the synthetic finance corpus, one on the training roster (“seen”) and one on six held-out companies (“unseen”). The pipeline reads their earnings calls, 66 and 60 of them, covering 16 and 6 companies.

stagemodelfrom
E, entitiesCRF tagger on encoder states, then exact string linkingTopics 22, 23
R, relationsmultiple-instance reader, facts by noisy-ORTopic 23
T, tonedictionary net tone, unigram LR, or aspects through the Bayes ruleTopics 18, 17, 19
A, aspectsa term matcher, then the bigram attention readerTopic 19

Definition 1 (Call graph and oracle).

The pipeline’s output on a set of calls is the call graph G\mathcal{G}, a set of triples: every fact (h,r,t)(h, r, t) that a call states between linked entities, and for each call cc the triples (c,ABOUT,s)(c, \text{ABOUT}, s) with ss its subject, (c,TONE,τ)(c, \text{TONE}, \tau) with τ∈{−1,0,1}\tau \in \lbrace -1, 0, 1 \rbrace, and (c,ASPECT:a,±1)(c, \text{ASPECT:}a, \pm 1) for each aspect category aa whose polar mentions do not cancel. The oracle of stage ii replaces its output by the gold one, and later stages read the replacement. With predicted entities, the relation oracle returns the facts stated between the mentions the entity stage found, typed, and linked. The gold graph has every oracle in place.

The gold graph of the two runs has 478 and 356 triples, 115 and 45 of them facts. Every oracle reproduces its prerequisite’s own gold reading: the aspect triples are the overlap-metrics topic’s doc_facts, and the tone-bearing sentences are the aspect topic’s tone_sentences. A call’s subject is its first linked organization mention, which is the covered company on every call when the mentions are gold.


How errors compound

A fact reaches the graph only if both stages succeed on it. For a gold fact ff, let AfA_f be the event that both of its arguments are found and linked, and BfB_f the event that the relation reader recovers ff from gold mentions. Write rEr_E for the share of gold facts in AA and rRr_R for the share in BB.

Proposition 1 (Two-sided bounds and modularity).

max⁡(0, rE+rR−1)≤P(A∩B)≤min⁡(rE,rR)\max(0,\ r_E + r_R - 1) \le P(A \cap B) \le \min(r_E, r_R). If AA and BB are independent, P(A∩B)=rErRP(A \cap B) = r_E r_R, and if they are positively associated, P(A∩B)≥rErRP(A \cap B) \ge r_E r_R. If the pipeline is modular, meaning the reader recovers ff from predicted mentions exactly when Af∩BfA_f \cap B_f holds, then end-to-end recall equals P(A∩B)P(A \cap B).

Proof.

P(A∩B)=1−P(Ac∪Bc)≥1−P(Ac)−P(Bc)=rE+rR−1P(A \cap B) = 1 - P(A^c \cup B^c) \ge 1 - P(A^c) - P(B^c) = r_E + r_R - 1 by Bonferroni’s inequality (formalCalculus, Probability and the Union Bound, Corollary 1), and P(A∩B)≥0P(A \cap B) \ge 0. Since A∩B⊆AA \cap B \subseteq A and A∩B⊆BA \cap B \subseteq B, P(A∩B)≤min⁡(rE,rR)P(A \cap B) \le \min(r_E, r_R). Independence is the definition P(A∩B)=P(A)P(B)P(A \cap B) = P(A)P(B); the positively associated case is formalRAG’s Proposition 1 (Harris and FKG). Under modularity, a fact succeeds end to end exactly on A∩BA \cap B, so the two recalls coincide.

∎

The product law in the middle is formalRAG’s Theorem 1. On the calls:

callsrEr_ErRr_RBonferroniproductP(A∩B)P(A \cap B)end to end
seen0.8430.8430.8170.8170.6610.6610.6890.6890.7390.7390.6960.696
unseen0.9560.9560.8670.8670.8220.8220.8280.8280.8670.8670.8670.867

P(A∩B)P(A \cap B) exceeds the product on both runs, so success at the two stages is positively associated. Both kinds of error cluster on the same rarely covered companies. On the unseen calls the pipeline is modular: end-to-end recall is exactly P(A∩B)P(A \cap B). On the seen calls it is not, and end-to-end recall falls 0.0430.043 below P(A∩B)P(A \cap B). When the tagger mis-tags a neighbor, the string between the two arguments changes, and the reader, which reads that string, can miss a fact whose arguments it was given correctly. Every end-to-end success still lies inside A∩BA \cap B, so the upper bound holds. Bounds like these presume that a stage behaves the same on predicted input as on gold input, and that presumption can be checked.


Who gets the blame

Fixing stages one at a time is called a ceiling analysis: give the first stage the gold answer and record the gain, then the second, and so on. With four stages there are 24=162^4 = 16 sets of oracles, a Boolean lattice ordered by inclusion, and one ceiling analysis is one path from the bottom (no oracles) to the top (all of them). There are 4!=244! = 24 such paths, and they need not agree.

Definition 2 (Oracle game, dividends, sequential shares).

Let N={E,R,T,A}N = \lbrace E, R, T, A \rbrace. The oracle game is v(S)=F1(GS)−F1(G∅)v(S) = F_1(\mathcal{G}_S) - F_1(\mathcal{G}_\varnothing), where GS\mathcal{G}_S is the call graph with the stages in SS replaced by their oracles and F1F_1 is micro F1 against the gold graph. The error game is verr(S)=err(∅)−err(S)v_{\text{err}}(S) = \text{err}(\varnothing) - \text{err}(S), with err the number of false and missing triples. The Harsanyi dividends are

d(T)=∑S⊆T(−1)∣T∣−∣S∣ v(S),so thatv(S)=∑T⊆Sd(T).d(T) = \sum_{S \subseteq T} (-1)^{|T| - |S|}\, v(S), \qquad \text{so that} \qquad v(S) = \sum_{T \subseteq S} d(T).

In an order π\pi of NN, the sequential share of stage ii is v(Pπ(i)∪{i})−v(Pπ(i))v(P_\pi(i) \cup \lbrace i \rbrace) - v(P_\pi(i)), where Pπ(i)P_\pi(i) is the set of stages before ii.

The two formulas for dd and vv are Möbius inversion on the lattice. A dividend measures what a coalition achieves beyond what its sub-coalitions already explain: d({i})d(\lbrace i \rbrace) is the gain of stage ii alone, and d({E,R})=v({E,R})−v({E})−v({R})d(\lbrace E, R \rbrace) = v(\lbrace E, R \rbrace) - v(\lbrace E \rbrace) - v(\lbrace R \rbrace) is what entities and relations do together beyond each alone.

Theorem 1 (Ceiling analysis and the Shapley value).

(a) In order π\pi, the sequential share of stage ii is ∑d(T)\sum d(T) over the coalitions TT whose last member under π\pi is ii.

(b) Every order gives every stage the same share if and only if d(T)=0d(T) = 0 for every TT with ∣T∣≥2|T| \ge 2.

(c) The average share over all ∣N∣!|N|! orders is

ϕi=∑T∋id(T)∣T∣=∑S⊆N∖{i}∣S∣! (∣N∣−∣S∣−1)!∣N∣!(v(S∪{i})−v(S)),\phi_i = \sum_{T \ni i} \frac{d(T)}{|T|} = \sum_{S \subseteq N \setminus \lbrace i \rbrace} \frac{|S|!\,(|N| - |S| - 1)!}{|N|!} \big(v(S \cup \lbrace i \rbrace) - v(S)\big),

the Shapley value, and it is the only map from games to attributions that is efficient (∑iϕi=v(N)\sum_i \phi_i = v(N)), symmetric (interchangeable stages get equal shares), null on null players, and additive.

Proof.

(a) With P=Pπ(i)P = P_\pi(i), v(P∪{i})−v(P)=∑T⊆P∪{i}d(T)−∑T⊆Pd(T)=∑d(T)v(P \cup \lbrace i \rbrace) - v(P) = \sum_{T \subseteq P \cup \lbrace i \rbrace} d(T) - \sum_{T \subseteq P} d(T) = \sum d(T) over T⊆P∪{i}T \subseteq P \cup \lbrace i \rbrace with i∈Ti \in T. These are exactly the coalitions all of whose other members come before ii, so ii is last among them.

(b) If every dividend of two or more stages is 00, (a) gives ii the share d({i})d(\lbrace i \rbrace) in every order. Conversely, suppose all orders agree, and take T∋iT \ni i with ∣T∣≥2|T| \ge 2. Compare an order that lists T∖{i}T \setminus \lbrace i \rbrace first and then ii with an order that starts with ii. By (a) the first gives ii the dividends of all T′⊆TT' \subseteq T containing ii, and the second only d({i})d(\lbrace i \rbrace), so ∑T′⊆T, T′∋i, ∣T′∣≥2d(T′)=0\sum_{T' \subseteq T,\ T' \ni i,\ |T'| \ge 2} d(T') = 0. Induct on ∣T∣|T|: for ∣T∣=2|T| = 2 the sum is d(T)d(T) itself, and for larger TT every smaller T′T' in the sum has d(T′)=0d(T') = 0 already, so d(T)=0d(T) = 0.

(c) Under a uniformly random order, each member of TT is equally likely to come last, so by (a) the expected share of ii is ∑T∋id(T)/∣T∣\sum_{T \ni i} d(T)/|T|. The probability that the set of stages before ii is exactly SS is ∣S∣! (∣N∣−∣S∣−1)!/∣N∣!|S|!\,(|N| - |S| - 1)!/|N|!, which gives the second formula. The Shapley value satisfies the four properties: efficiency because ∑i∑T∋id(T)/∣T∣=∑Td(T)=v(N)\sum_i \sum_{T \ni i} d(T)/|T| = \sum_T d(T) = v(N); symmetry and null players from the formula; additivity because it is linear in vv. For uniqueness, write v=∑T≠∅d(T) uTv = \sum_{T \ne \varnothing} d(T)\, u_T with the unanimity games uT(S)=1[T⊆S]u_T(S) = 1[T \subseteq S]. For any real cc, every stage outside TT is a null player in c uTc\,u_T; the members of TT are interchangeable; and the total is cc. So any map with the four properties gives c uTc\,u_T the attribution c/∣T∣c/|T| on TT and 00 off it, and additivity over the 2∣N∣−12^{|N|} - 1 terms fixes it on vv.

∎

Shapley (1953) proved the uniqueness; Harsanyi (1963) read the value as dividends split equally. Part (b) is the practical content: a ceiling analysis is safe to report in one order exactly when no two stages interact. When they do, the dividend goes to whichever stage arrives last.

Corollary 1 (Null players).

If v(S∪{i})=v(S)v(S \cup \lbrace i \rbrace) = v(S) for every SS, then every dividend containing ii is 00, and the share of stage ii is 00 in every order and under the Shapley value.

Proof.

For T∋iT \ni i, pair each S⊆T∖{i}S \subseteq T \setminus \lbrace i \rbrace with S∪{i}S \cup \lbrace i \rbrace in the sum defining d(T)d(T). The two terms carry opposite signs and equal values, so they cancel, and d(T)=0d(T) = 0. Then (a) and (c) of Theorem 1 give 00.

∎

The aspect stage is such a player. The term matcher finds exactly the gold aspect spans, because the corpus’s aspect vocabulary is closed and every mention of a term is annotated, and Topic 19’s bigram reader reads all 1,209 of them correctly. Its oracle changes nothing, in either game, for every tone reader.

Whether two stages interact depends on the metric as well as on the stages.

Proposition 2 (Counts add, ratios couple).

If the correctness of each triple xx depends on SS only through S∩WxS \cap W_x, where WxW_x is the set of stages whose output determines xx, then verr(S)=∑xgx(S∩Wx)v_{\text{err}}(S) = \sum_x g_x(S \cap W_x), and derr(T)≠0d_{\text{err}}(T) \ne 0 only if T⊆WxT \subseteq W_x for some triple xx. Micro F1 is a ratio of sums of the same indicators, and its dividends are not confined in this way.

Proof.

The error count is a sum over triples of an indicator that depends only on S∩WxS \cap W_x, and the map from vv to its dividends is linear. A function of S∩WS \cap W does not change when a stage i∉Wi \notin W joins, so by Corollary 1 its dividends vanish on every TT containing such an ii, that is, on every T⊈WT \not\subseteq W. F1 is 2 tp/(predicted+gold)2\,\text{tp}/(\text{predicted} + \text{gold}), and a stage that changes the number of predicted triples rescales the credit for every other stage’s true positives.

∎

Facts depend on {E,R}\lbrace E, R \rbrace, subjects on {E}\lbrace E \rbrace, tone triples on {T}\lbrace T \rbrace (for the document-level readers), and aspect triples on {A}\lbrace A \rbrace. So the error game can have exactly one dividend of two stages, d({E,R})d(\lbrace E, R \rbrace), and on all 126 calls it is 66 errors. That dividend is positive: entities and relations are complements, each oracle worth more once the other is in place, because a fact needs both its arguments and its relation. The aspect reader’s tone could depend on the entity stage, since a tone-bearing sentence names no company, but on these calls the entity stage’s errors never move a sentence in or out, so that game is additive too.

Shapley shares of F1, both runs, by tone reader:

tone readerentitiesrelationstoneaspectsd({E,R})d(\lbrace E, R \rbrace)
dictionary0.02180.02180.01530.01530.06350.0635000.00330.0033
LR0.02150.02150.01520.01520.04030.0403000.00320.0032
aspects0.02140.02140.01510.01510.02200.0220000.00320.0032

With the LR reader, a ceiling analysis that fixes entities first credits them 0.02030.0203, and one that fixes relations first credits them 0.02360.0236: the 0.00320.0032 dividend goes to whichever arrives second. The F1 game also has small negative dividends between tone and the other stages (−0.0008-0.0008 and −0.0005-0.0005), which Proposition 2 attributes to F1’s denominator rather than to any interaction among the stages. Error counts give the same picture without them: 3434, 2424, 6666, and 00 errors for entities, relations, tone, and aspects.

Two readings of the table matter more than its digits. Tone’s share is the largest, and most of it no reader could remove: the aspect reader outputs exactly the Bayes rule applied to the gold aspect polarities on every call, and the classification topic’s Bayes ceiling is 0.8900.890. So of LR’s 0.04030.0403, the 0.02200.0220 the aspect reader keeps is irreducible, and only the difference is fixable. An oracle’s gain is not the same as fixable error. And entities matter far more on the seen run than on the unseen one (0.03380.0338 against 0.00580.0058 with LR). The tagger reads the six held-out companies almost perfectly; the hard names are the training roster’s rarely covered companies and cities. The lab’s Oracle lattice tab draws the sixteen coalitions, highlights the path of any order you choose, and sets its shares beside Shapley’s.


What one stage should hand the next

A pipeline stage usually passes on its best guess: the Viterbi span set, the argmax label. It could pass on its uncertainty instead.

Definition 3 (Hard and soft handoffs).

A stage with posterior q(y∣x)q(y \mid x) makes a hard handoff when it passes y^=arg⁡max⁡yq(y∣x)\hat y = \arg\max_y q(y \mid x) and a soft handoff when it passes qq itself. For the entity stage, a marginal handoff passes every span with marginal probability q>10−3q \gt 10^{-3} (the entity topic’s Proposition 4) and scales each candidate pair’s relation probabilities by qhead qtailq_{\text{head}}\, q_{\text{tail}}. A sampled handoff draws K=64K = 64 span sets per sentence from the constrained chain by forward filtering, backward sampling (Carter and Kohn 1994), runs the relation stage on each, and averages the 64 noisy-OR fact scores.

Finkel, Manning, and Ng (2006) proposed the sampled handoff for linguistic pipelines, with a majority vote over last-stage samples; we keep the averaged scores so that the facts can be ranked.

Theorem 2 (The argmax is a garbling).

(a) For every loss and every downstream decision, a Bayes-optimal successor that receives qq has risk no larger than one that receives arg⁡max⁡q\arg\max q.

(b) A fixed successor can do worse with qq: there are a loss and a decision rule δ\delta with R(δ∘q)>R(δ∘arg⁡max⁡q)R(\delta \circ q) \gt R(\delta \circ \arg\max q).

Proof.

(a) The argmax is a function hh of qq, so every decision rule δ(h(q))\delta(h(q)) that uses the argmax is also a rule that uses qq. The Bayes risk minimizes over rules, and minimizing over a larger class cannot give a larger minimum.

(b) Let a mention’s span be right with probability q=0.6q = 0.6, and let the reader state a fact from the right span with probability p=0.8p = 0.8 and from a wrong one never, so the fact holds with probability qp=0.48qp = 0.48. A missed fact costs 33 and a false one 11, so the Bayes act asserts the fact whenever its probability exceeds 1/41/4. Let δ\delta be the hard pipeline’s rule: assert when the score exceeds 1/21/2. Hard, the span is kept (q>1/2q \gt 1/2) and the score is 0.80.8, so δ\delta asserts, which is the Bayes act, at expected cost 0.52⋅1=0.520.52 \cdot 1 = 0.52. Soft, the score is 0.480.48, so δ\delta withholds, at expected cost 0.48⋅3=1.440.48 \cdot 3 = 1.44. Refitting the threshold to 1/41/4 on the soft score restores 0.520.52.

∎

Part (a) is the easy direction of Blackwell’s comparison of experiments (1953): an experiment is more informative than its garblings in every decision problem. It is a decision-theoretic counterpart of formalML’s data processing inequality (Theorem 4 there), and of Rao–Blackwell (formalStatistics, Theorem 4). The harness checks (a) on 300 random finite worlds by exact enumeration; in 22 of them the inequality is strict. The proof of (b) shows what goes wrong: a soft score is closer to a probability than a hard one, and a threshold set for hard scores is set for the wrong quantity. The entity topic’s Theorem 3 gives the refit for F1: with calibrated scores, threshold at half the optimal F1 (Lipton, Elkan, and Naryanaswamy 2014, Corollary 1).

On the calls, fact precision is 1.0001.000 for every handoff at τ=0.5\tau = 0.5, and the differences are all in recall:

seen callsF1 at 0.50.5APF1 at F∗/2F^*/2F1, τ\tau tuned on filings
hard0.8210.8210.7440.7440.8380.8380.8380.838
marginal0.7570.7570.8510.8510.8080.8080.8800.880
sampled0.7630.7630.8380.8380.8080.8080.8800.880

The seen run is where entity errors are common, and there the soft handoffs carry real information: of the 92 gold spans the hard tagger misses on the calls, 61 keep marginal mass above 0.10.1, and average precision rises by more than 0.090.09. At the hard pipeline’s threshold they lose, as Theorem 2(b) predicts: scaling by qhead qtailq_{\text{head}}\, q_{\text{tail}} pushes true facts below 0.50.5. The F∗/2F^*/2 rule, computed from the soft scores alone, recovers part of the loss; noisy-OR scores built from scaled mention probabilities are underconfident, so the rule’s calibration assumption fails and it stays short. A threshold tuned on the same run’s filings, which never enter the graph, gives the soft handoffs the best F1 on the calls, 0.8800.880 against 0.8380.838. On the unseen run the tagger is nearly right, the marginals add little (AP 0.9180.918 against 0.9200.920), and the tuned soft handoffs tie the hard one or trail it by 0.0130.013. The lab’s Hard vs. soft tab moves the threshold.


Letting the knowledge base check itself

The extracted facts are scored one at a time, but the world they describe has structure: a company has one headquarters city and one CEO, and a subsidiary has one parent. Respecting that structure means choosing the facts jointly.

Definition 4 (Constrained fact selection).

Each scored fact ff gets an indicator xf∈{0,1}x_f \in \lbrace 0, 1 \rbrace and a weight wf=logit⁡sf−logit⁡τw_f = \operatorname{logit} s_f - \operatorname{logit} \tau, so that with no constraints, maximizing ∑fwfxf\sum_f w_f x_f keeps exactly the facts with sf>τs_f \gt \tau. A fact and its inverse (PARENT_OF(a,b)\text{PARENT\_OF}(a, b) and SUBSIDIARY_OF(b,a)\text{SUBSIDIARY\_OF}(b, a)), and a symmetric fact and its reverse (COMPETES_WITH\text{COMPETES\_WITH}), are one variable, scored by the noisy-OR 1−∏(1−s)1 - \prod (1 - s) over both directions. The functional rows are

∑tx(h,r,t)≤1  for each head slot (h,r),∑hx(h,r,t)≤1  for each tail slot (r,t),\sum_{t} x_{(h, r, t)} \le 1 \ \text{ for each head slot } (h, r), \qquad \sum_{h} x_{(h, r, t)} \le 1 \ \text{ for each tail slot } (r, t),

the first for the relations a head has at most one of (HQ_IN, IN_SECTOR, BASED_IN, LOCATED_IN, SUBSIDIARY_OF, CEO_OF, CFO_OF, ACQUIRED), the second for those a tail has at most one of (CEO_OF, CFO_OF, ACQUIRED). Both lists are read off the knowledge base’s own maximum degrees.

The merge is a modeling choice with consequences. Adding the two directions’ log-odds instead of combining them by noisy-OR lets a reader that states only one direction veto it: Brightwater Analytics PARENT_OF Larch Data, scored 0.6850.685, was dropped at τ=0.55\tau = 0.55 for its inverse, scored 0.3980.398, when the harness first added them. Every mention of either direction is evidence for the one fact, and noisy-OR treats it so.

Theorem 3 (Functional constraints are totally unimodular).

(a) After merging, the matrix of functional rows is totally unimodular, so the LP relaxation of Definition 4 (0≤x≤10 \le x \le 1) has an integral optimum, and it is the constrained MAP.

(b) If no tail-functional row binds, the MAP keeps each head slot’s highest-weight fact when that weight is positive, and every positive-weight fact outside the functional relations. When rows of both families bind, the MAP is a maximum-weight bipartite matching.

Proof.

(a) Each fact has one head slot and at most one tail slot, so every column has at most one 11 among the head-slot rows and at most one among the tail-slot rows. Let BB be a square submatrix; we show det⁡B∈{0,±1}\det B \in \lbrace 0, \pm 1 \rbrace by induction on its size. If a column of BB is zero, det⁡B=0\det B = 0. If a column has a single 11, expanding along it gives ±\pm the determinant of a smaller submatrix. Otherwise every column has exactly one 11 in each family, so the sum of the head-slot rows of BB minus the sum of its tail-slot rows is the zero vector, and det⁡B=0\det B = 0. This is Heller and Tompkins’ criterion (1956). Appending the identity rows for x≤1x \le 1 keeps total unimodularity, since a determinant expanded along an identity row is ±\pm a smaller one. With a totally unimodular matrix and an integral right-hand side, every vertex of the polytope is integral (Hoffman and Kruskal 1956), so the LP attains its optimum at an integral point, which is a feasible point of the integer program with the same value.

(b) Without binding tail rows, the head-slot rows partition the variables into disjoint slots, and the LP separates into one problem per slot, max⁡∑jwjxj\max \sum_j w_j x_j subject to ∑jxj≤1\sum_j x_j \le 1 and 0≤xj≤10 \le x_j \le 1. Its optimum puts weight 11 on the largest wjw_j if it is positive and nothing otherwise. With both families, the variables are the edges of a bipartite graph between head slots and tail slots, and the rows say each slot is used at most once.

∎

On the calls, the per-slot rule of (b) agrees with the MAP except at τ≤0.05\tau \le 0.05 on the unseen run, where a company has two plausible CEOs and the one-CEO-per-company rows bind. Composition rules are another matter. The knowledge base satisfies BASED_IN=HQ_IN∘LOCATED_IN\text{BASED\_IN} = \text{HQ\_IN} \circ \text{LOCATED\_IN}: a company is based in the region of its headquarters city. As linear constraints, xhq+xloc−xbased≤1x_{\text{hq}} + x_{\text{loc}} - x_{\text{based}} \le 1 and xhq+xbased−xloc≤1x_{\text{hq}} + x_{\text{based}} - x_{\text{loc}} \le 1.

Proposition 3 (Composition breaks total unimodularity).

Take one company with two candidate headquarters cities in one country, variables (xhq1,xhq2,xloc1,xloc2,xbased)(x_{\text{hq}_1}, x_{\text{hq}_2}, x_{\text{loc}_1}, x_{\text{loc}_2}, x_{\text{based}}), the row xhq1+xhq2≤1x_{\text{hq}_1} + x_{\text{hq}_2} \le 1, and the two rules for each city. The submatrix on the two rules of city 1 and the columns (hq1,loc1)(\text{hq}_1, \text{loc}_1) has determinant −2-2. With weights w=(1,1,−2,−2,1)w = (1, 1, -2, -2, 1) the LP optimum is x=(12,12,0,0,12)x = (\tfrac12, \tfrac12, 0, 0, \tfrac12), with value 32\tfrac32, while the best integer point is worth 11.

Proof.

The two rows restricted to those columns are (1,1)(1, 1) and (1,−1)(1, -1), with determinant −2-2. The point x=(12,12,0,0,12)x = (\tfrac12, \tfrac12, 0, 0, \tfrac12) satisfies 12+12≤1\tfrac12 + \tfrac12 \le 1, 12+0−12=0≤1\tfrac12 + 0 - \tfrac12 = 0 \le 1, and 12+12−0=1≤1\tfrac12 + \tfrac12 - 0 = 1 \le 1 for each city, and its value is 12+12+12=32\tfrac12 + \tfrac12 + \tfrac12 = \tfrac32. At an integer point, xhqi=1x_{\text{hq}_i} = 1 forces xbased=xlocix_{\text{based}} = x_{\text{loc}_i} by the two rules, and the pair is worth 1−2=−11 - 2 = -1 or 00. So the integer optimum is either a headquarters alone or BASED_IN alone, each worth 11. The LP gains by splitting the headquarters between two cities, which no real knowledge base allows.

∎

Roth and Yih (2004, §3.3) formulated entity and relation decisions as such a program and found that, although their matrix “is not unimodular,” the LP relaxation returned integer solutions in every one of thousands of cases. So does ours: at all 19 thresholds of the lab’s grid, on both runs, with gold or predicted mentions, with or without the rules, the LP is integral. Proposition 3 shows this is a property of the instances, not of the formulation.

What the constraints do to F1 (both runs, predicted mentions):

run, τ\tauthresholdmergedfunctionalwith rules
seen, 0.050.050.8060.8060.8060.8060.8260.8260.8080.808
seen, 0.50.50.8210.8210.8210.8210.8210.8210.8140.814
unseen, 0.050.050.8630.8630.8630.8630.9210.9210.9210.921
unseen, 0.50.50.9290.9290.9290.9290.9290.9290.9290.929

Merging the inverse and symmetric facts never lowers F1 at τ≥0.4\tau \ge 0.4, and at high thresholds it raises it (seen, τ=0.8\tau = 0.8: 0.5980.598 to 0.6310.631) by completing the direction a reader missed; at low τ\tau it also completes the inverses of weak false facts. The functional rows never lower F1 against the merged threshold, and at low τ\tau they raise it, and every fact they remove there is false: a second headquarters city, a region read as a city, a second CFO. The rules cut both ways. At τ=0.5\tau = 0.5 on the seen run they lower F1, by deleting true LOCATED_IN facts such as Chicago in Illinois and Denver in Colorado: no call states the BASED_IN fact that would complete the triangle, so its weight is strongly negative, and the rules let that unstated fact veto the stated one. This is the closed-world assumption the embedding topic found in training, now acting at inference: an unstated fact counts as false. The lab’s Joint KB tab lists which facts each step adds and removes at every threshold.


How sure are the shares

The shares above come from 22 companies, and calls of one company share a subject, a coverage rate, and its rare names. A share that cannot be separated from zero should not be reported as a ranking.

Proposition 4 (One bootstrap serves every share).

Charge each triple of the call graph to a company: a call triple to the call’s company, a fact to the company of the first call that mentions both of its entities. Let Cc(S)=(tp,predicted,gold)C_c(S) = (\text{tp}, \text{predicted}, \text{gold}) be the counts of company cc under coalition SS. Then ϕ=Mv\phi = M v, with MM the ∣N∣×2∣N∣|N| \times 2^{|N|} matrix of Theorem 1(c), and v(S)=F1(∑cCc(S))−F1(∑cCc(∅))v(S) = F_1\big(\sum_c C_c(S)\big) - F_1\big(\sum_c C_c(\varnothing)\big). Resampling companies with multiplicities WW gives every share’s bootstrap replicate at once: ϕ∗=M(F1(WC(S))−F1(WC(∅)))S\phi^* = M\big(F_1(W C(S)) - F_1(W C(\varnothing))\big)_S.

Proof.

Theorem 1(c) writes each ϕi\phi_i as a fixed linear combination of the 2∣N∣2^{|N|} values v(S)v(S), so ϕ=Mv\phi = Mv for every game, including the game computed on a resample. Each company’s triples are charged to it alone, so the pooled counts of a resample are WC(S)W C(S), and F1 is a function of pooled counts. F1 is homogeneous of degree 00 in them, so multiplicities and normalized weights give the same value, the form the significance topic resamples in (its Definition 1).

∎

Consistency is formalStatistics’ bootstrap Theorem 3 for each pooled mean, carried to F1 by the delta method; 22 clusters is a small sample for it. With 2,000 resamples, both runs, LR reader, the 90% intervals are [0.0097,0.0389][0.0097, 0.0389] for entities, [0.0096,0.0229][0.0096, 0.0229] for relations, and [0.0322,0.0500][0.0322, 0.0500] for tone. Tone’s share is separated from zero and from the others, and the aspect share is exactly zero in every replicate. Entities and relations cannot be ordered: entities’ replicate exceeds relations’ in 0.7440.744 of the resamples. On the unseen run alone, entities’ interval reaches zero. The lab’s Oracle lattice tab draws these intervals as whiskers.


Finance case study

One earnings call through every stage: Marrow Freight (seen roster test run, synth-0058)
call
spans
≠Thank you for joining the Marrow Freight quarterly results call
·Marrow Freight finance chief Ingrid Sato walked through results in ledgerwork
·The plan reallocates resources from microclinic and crediter toward nonbrand and swaper
≠Marrow Freight operates in the industrials sector chiefly in indexers underrebate
≠Fenwick Logistics is headquartered in Houston Texas
·Marrow Freight reported revenue of million for fiscal
≠Analysts who cover Marrow Freight also follow Larch Data
·Results reflected ledgerwork bondings equitylines postbrokers networking and contracts
·Marrow Freight keeps its corporate base in Illinois
·Marrow guided to percent growth in the third quarter
·Management highlighted brandings freight nonbrand and routeworks leverage as areas of focus
·[tone]Gross margin was in line with the prior period
·[tone]Sales held steady across prenetwork and underyields
·[tone]Pension liabilities climbed percent in receivableflows and tariffment postdeposit but margins climbed percent in pipepoint transswaps and freight which analysts viewed as favorable
·[tone]Cost of revenue was broadly unchanged in policyside and escrowwork
·[tone]Margins in marginment and loanline trailed expectations but operating costs fell percent in marketbook and brokerlines
·[tone]Volume held steady across shareside and cargobase
·[tone]Capital levels held steady across intermarkets and crosswells
·Estimates of volatility may change and the microcredit outlook remains tentative given variability in freighting
·Management expects demand for the Marrow logistics network to support overseats and rebatings
organizationpersonplacesectoraspect term (solid +, dotted −, dashed neutral)
sentences whose spans differ
4 of 20
subject found
none (opener missed)
gold tone
neutral
dictionary reader
neutral
LR reader
positive
aspects reader
neutral
aspect polarities (predicted)
costs +, liabilities −
Facts charged to this call
factscoreextractedgold
Fenwick Logistics HQ_IN Houston0.000noyes
Houston LOCATED_IN Texas0.918yesyes
Ingrid Sato CFO_OF Marrow Freight0.977yesyes
Marrow Freight BASED_IN Illinois0.998yesyes
Marrow Freight IN_SECTOR industrials0.002noyes

Bold rows are errors. A struck-through name is a span the tagger found but the linker could not place. Tone-bearing sentences, marked [tone], are the ones the aspect reader votes with.


Where this sits

Every earlier topic built one map from text to structure and studied it alone. Composing them raises three questions that no single topic raises. Blame is a cooperative game over a lattice of oracle swaps: a ceiling analysis is one path through it, paths disagree exactly when stages interact (Theorem 1), a stage whose oracle changes nothing gets nothing (Corollary 1), and whether stages interact depends on the metric (Proposition 2). Handoffs are a comparison of experiments: a posterior can only help a successor that acts on it optimally, and a fixed successor must be refit to benefit (Theorem 2). Repair is an integer program: functional constraints are totally unimodular, so the LP is exact (Theorem 3), and composition rules are not (Proposition 3). The cascade bounds (Proposition 1) and the bootstrap of shares (Proposition 4) say how much of this can be read from one test set.

The capstone closes the extraction and knowledge-graph track and the curriculum. Its cascade law comes from formalRAG’s capstone, and its one-stage special case is the recall pinch of formalRAG’s reranking topic.


Honest caveats


Implementation

The companion notebook (notebookPath) imports the topic’s Python module, which owns every number on this page. The module imports the relation-extraction topic’s module, and through it the entity and sequence-labeling topics, for the entity and relation stages; the aspect topic’s module, and through it the lexicon and classification topics, for the tone readers and the aspect reader; the topic-model, embedding, and significance topics’ modules for the topic stage, the completion ranks, and the reader tests. Its harness checks:

  • that every oracle reproduces its prerequisite’s gold reading;
  • Theorem 1 and Corollary 1 on random games and on the corpus, and Proposition 2’s dividends in both games;
  • Proposition 1’s bounds and the modularity gap;
  • Theorem 2(a) on 300 random finite worlds, the counterexample of Theorem 2(b), and forward filtering, backward sampling against brute-force path probabilities;
  • Theorem 3 by brute-force minors on random fragments and LP integrality on every corpus problem, and Proposition 3 by exhaustive enumeration;
  • Proposition 4’s linear map against the Shapley formula, and every finance number this page states.

The laboratory reads its data from a JSON file that one of the harness’s tests requires to equal the module’s viz_payload() exactly, so the figure cannot drift from the code.

Connections

  • Its headline tagger is this pipeline's entity stage; its span marginals and constrained chains are the soft handoffs of Theorem 2, and its F*/2 threshold is the refit that Theorem 2(b) calls for. named-entity-recognition
  • Its MIL reader and noisy-OR aggregation are the relation stage, and its Proposition 5, that a triple needs both of its arguments, is the event A of Proposition 1 here. relation-extraction-distant-supervision
  • Its bigram reader and its Bayes rule from aspects to tone are the aspect stage and the third tone reader; on these calls the reader is perfect and the stage is Corollary 1's null player. aspect-based-sentiment
  • Its unigram logistic regression is the learned tone reader, and its Bayes ceiling of 0.890 bounds every tone reader of this text, which is why tone's Shapley share is mostly irreducible. linear-text-classifiers
  • Its McNemar test and approximate randomization compare the three tone readers on the same calls, and its pooled-statistics resampling is what Proposition 4 applies to the Shapley shares. significance-testing-for-nlp

References & Further Reading

  • paper A Value for n-Person Games — Lloyd S. Shapley (1953) In Contributions to the Theory of Games II, Annals of Mathematics Studies 28, 307–17. The value as the unique map satisfying symmetry, efficiency, and additivity on games with carriers
  • paper A Simplified Bargaining Model for the n-Person Cooperative Game — John C. Harsanyi (1963) International Economic Review 4 (2): 194–220. The dividends of coalitions, split equally among their members, as a reading of the Shapley value
  • paper Integral Boundary Points of Convex Polyhedra — A. J. Hoffman and J. B. Kruskal (1956) In Linear Inequalities and Related Systems, Annals of Mathematics Studies 38, 223–46: a totally unimodular constraint matrix gives an integral polyhedron for every integral right-hand side (Crossref dates the digitized volume 1957)
  • paper An Extension of a Theorem of Dantzig's — I. Heller and C. B. Tompkins (1956) Same volume, 247–54: a matrix whose columns have at most two nonzero entries is totally unimodular when its rows split into two classes as in Theorem 3's proof
  • paper Equivalent Comparisons of Experiments — David Blackwell (1953) Annals of Mathematical Statistics 24 (2): 265–72. An experiment is more informative than another iff the other is a garbling of it iff it has lower Bayes risk in every decision problem; Theorem 2(a) is the easy direction
  • paper Solving the Problem of Cascading Errors: Approximate Bayesian Inference for Linguistic Annotation Pipelines — Jenny Rose Finkel, Christopher D. Manning, and Andrew Y. Ng (2006) Proceedings of EMNLP 2006, 618–26. Each stage samples conditioned on the earlier stages' samples, and a majority vote over last-stage samples decides; k-best lists as the prior practice
  • paper A Linear Programming Formulation for Global Inference in Natural Language Tasks — Dan Roth and Wen-tau Yih (2004) Proceedings of CoNLL 2004. Entities and relations decided jointly by an integer program; §3.3: the coefficient matrix is not unimodular, yet the LP relaxation returned integer solutions in all of their thousands of cases
  • paper On Gibbs Sampling for State Space Models — C. K. Carter and R. Kohn (1994) Biometrika 81 (3): 541–53. Forward filtering, backward sampling: exact joint draws from a chain's posterior
  • paper Optimal Thresholding of Classifiers to Maximize F1 Measure — Zachary C. Lipton, Charles Elkan, and Balakrishnan Naryanaswamy (2014) ECML PKDD 2014, LNCS 8725, 225–39. Corollary 1: with calibrated scores, the F1-optimal threshold is half the optimal F1