Trust-weighted histograms

Dan’s proposal for trust-weighted histograms

This is my (@efrias) interpretation of an algorithm Dan proposed after the July 24th meeting. It behaves differently from previous algorithms:

the output of this algorithm is a histogram that could be presented to the user as-is
previous algorithms used the trust factor to pull stronger opinions towards the center. In other words, previous algorithms would treat a source who had 50% confident in their own opinion (personal opinion of 25% or 75%) but whom we trusted at 50% entirely equal to a source who was 25% confident in their own opinion but whom we trusted at 100% – both would be weighted at 37.5% or 62.5%). This algorithm preserves the individual sources’ “confidence” in the final result – if every source in your graph has a 100% confidence in one outcome or the other, the resulting histogram will only have nonzero values for the bins containing the extreme values of 0% and 100%.

setup

Assume a simple “a or b” predicate, and any node that has a personal opinion expresses it as a probability from 0% to 100%. If a personal opinion is 0%, it means they are completely confident that the answer is “a”. If their personal opinion is 100%, it means that they are completely confident that the answer is “b”. If it’s 50%, they have no idea and probably shouldn’t be wasting your time by answering.

Instead of reporting a single answer for their computed opinion, each node will report a histogram

algorithm

We decide on a number of “bins”, let’s assume we choose 10, defined the obvious way:

bin 1: ${\textstyle [0\%,10\%)}$
bin 2: ${\textstyle [10\%,20\%)}$
etc.

To generate a computed answer, each node will generate a trust-weighted histogram as follows:

start with a computed opinion of ten zeros
if they have a personal opinion, set the bin containing their personal answer to ${\textstyle 1.0}$ (the node trusts itself completely)
iterate through the sources the node trusts. Each of those nodes will be providing their own trust-weighted histogram. For each source:
- for each bin:
  - multiply the source’s value for that bin by your trust factor for that source. Add it to the bin
normalize the histogram by dividing all bins by the highest value in any bin. if the highest value is zero, you may want to skip this step. Note: this “normalize to make the highest value = 1” was my initial assumption, but we should investigate alternatives, like “normalize to make the area under the histogram = 1”

example

Let’s work Pete’s example:

HTTP-Response: 
Error 400: Internal Server Error

Diagram-Code:
digraph G {
    fontname="Helvetica,Arial,sans-serif"
    node [fontname="Helvetica,Arial,sans-serif"]
    edge [fontname="Helvetica,Arial,sans-serif"]
    layout=dot
    1 [label="1, P=20%"]
    2 [label="2, P=30%"]
    3 [label="3, P=40%"]
    4 [label="4, P=45%"]
    5 [label="5, P=60%"]
    6 [label="6, P=90%"]
    7 [label="7, P=55%"]
    8 [label="8, P=65%"]
    9 [label="9, P=70%"]
    10 [label="10, P=80%"]
    1 -> 2 [label="T=0.9"];
    1 -> 3 [label="T=0.9"];
    1 -> 4 [label="T=0.9"];
    2 -> 5 [label="T=0.9"];
    2 -> 6 [label="T=0.9"];
    3 -> 7 [label="T=0.9"];
    3 -> 8 [label="T=0.9"];
    4 -> 9 [label="T=0.9"];
    4 -> 10 [label="T=0.9"];
    }

Starting at the leaf nodes, the nodes will just return a histogram containing ${\textstyle 1.0}$ in the bin with their personal opinion, ${\textstyle 0}$ elsewhere:

${\textstyle H_{5}=[0,0,0,0,0,0,1,0,0,0]}$

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle H_6 = [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle H_7 = [0, 0, 0, 0, 0, 1, 0, 0, 0, 0]}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle H_8 = [0, 0, 0, 0, 0, 0, 1, 0, 0, 0]}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle H_9 = [0, 0, 0, 0, 0, 0, 0, 1, 0, 0]}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle H_{10} = [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]}

On the middle layer of the graph, it gets more interesting:

Node 2 starts with its own personal opinion, in the form of a histogram: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle [0, 0, 0, 1, 0, 0, 0, 0, 0, 0]} . Then it takes the opinion of node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 5} , scales it by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 0.9} to get Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle [0, 0, 0, 0, 0, 0, 0.9, 0, 0, 0]} , and adds it to its personal opinion to get: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle [0, 0, 0, 1, 0, 0, 0.9, 0, 0, 0]} . It repeats the process with node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 6} , scaling Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 6} ’s histogram down to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle [0, 0, 0, 0, 0, 0, 0, 0, 0, 0.9]} and adding it to the running total to get Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle [0, 0, 0, 1, 0, 0, 0.9, 0, 0, 0.9]} . Finally, it would scale the histogram, but the highest value is already Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 1.0} so no scaling is necessary, so the final result is:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle H_2 = [0, 0, 0, 1, 0, 0, 0.9, 0, 0, 0.9]}

Node 3 and 4 repeat the same process to get:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle H_3 = [0, 0, 0, 0, 1, 0.9, 0.9, 0, 0, 0]}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle H_4 = [0, 0, 0, 0, 1, 0, 0, 0.9, 0.9, 0]}

Finally, node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 1} gets their say. They start with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle [0, 0, 1, 0, 0, 0, 0, 0, 0, 0]} . Then they scale node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 2} ’s computed opinion by the trust factor to get: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle [0, 0, 0, 0.9, 0, 0, 0.81, 0, 0, 0.81]} , and add it to their personal opinion to get Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle [0, 0, 1, 0.9, 0, 0, 0.81, 0, 0, 0.81]} . They do the same with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 3} ’s computed opinion, scaled to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle [0, 0, 0, 0, 0.9, 0.81, 0.81, 0, 0, 0]} , and accumulating it to get Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle [0, 0, 1, 0.9, 0.9, 0.81, 1.62, 0, 0, 0.81]} . Scaling Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 4} ’s yields Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle [0, 0, 0, 0, 0.9, 0, 0, 0.81, 0.81, 0]} , and adding it gives: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle [0, 0, 1, 0.9, 1.8, 0.81, 1.62, 0.81, 0.81, 0.81]} . Finally, they scale their answer back down, dividing by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 1.8} to get the final answer of:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle H_1 = [0, 0, 0.56, 0.5, 1, 0.45, 0.9, 0.45, 0.45, 0.45]}

{
  "$schema": "https://vega.github.io/schema/vega-lite/v5.json",
  "description": "Final Normalized Result",
  "width": 640,
  "data": {
    "values": [
      {"bin": "0%", "weight": 0}, {"bin": "10%", "weight": 0}, {"bin": "20%", "weight": 0.56},
      {"bin": "30%", "weight": 0.5}, {"bin": "40%", "weight": 1}, {"bin": "50%", "weight": 0.45},
      {"bin": "60%", "weight": 0.9}, {"bin": "70%", "weight": 0.45}, {"bin": "80%", "weight": 0.45}, {"bin": "90%", "weight": 0.45}
    ]
  },
  "mark": "bar",
  "encoding": {
    "x": {"field": "bin", "type": "nominal", "axis": {"labelAngle": 0}},
    "y": {"field": "weight", "type": "quantitative"}
  }
}

This shows a slight preference for the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle [40\%, 50\%)} interval, because two sources favored it. Two sources also favored the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle [60\%, 70\%)} interval, but those sources were more distant so their effect was watered down.