Spaces:
Sleeping
Sleeping
File size: 4,014 Bytes
d822cf7 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 |
import streamlit as st
import plotly.graph_objects as go
import numpy as np
import scipy.integrate as integrate
def _false_positive_probability(threshold, b, r):
def _probability(s):
return 1 - (1 - s ** float(r)) ** float(b)
a, err = integrate.quad(_probability, 0.0, threshold)
return a
def _false_negative_probability(threshold, b, r):
def _probability(s):
return 1 - (1 - (1 - s ** float(r)) ** float(b))
a, err = integrate.quad(_probability, threshold, 1.0)
return a
def _optimal_param(threshold, num_perm, false_positive_weight, false_negative_weight):
"""
Compute the optimal `MinHashLSH` parameter that minimizes the weighted sum
of probabilities of false positive and false negative.
"""
min_error = float("inf")
opt = (0, 0)
for b in range(1, num_perm + 1):
max_r = int(num_perm / b)
for r in range(1, max_r + 1):
fp = _false_positive_probability(threshold, b, r)
fn = _false_negative_probability(threshold, b, r)
error = fp * false_positive_weight + fn * false_negative_weight
if error < min_error:
min_error = error
opt = (b, r)
return opt
col1, col2 = st.columns(2)
s = col1.slider("Select a Jaccard similarity", 0.0, 1.0, 0.1)
p = col2.slider("Select a number of permutations", 0, 1000, 10)
optimal_b, optimal_r = _optimal_param(s, p, 1, 1)
b = col1.slider("Select a number of bands", 1, 100, 1)
r = col2.slider("Select a number of rows per band", 1, 100, 1)
col1.metric(label="Optimal number of bands", value=optimal_b)
col2.metric(label="Optimal number of rows per band", value=optimal_r)
st.markdown("---")
st.markdown(f"Two documents that have a Jaccard similarity of $s={s}$ will have:")
st.markdown(f"1. ${s * 100:.2f}\%$ of their k-shingles will be the same")
st.markdown(f"2. ${s * 100:.2f}\%$ of their k-shingles' hashes will be the same")
st.markdown(f"4. ${s * 100:.2f}\%$ of the time, a particular hash will be the same for two documents")
st.markdown(
f"3. $s^r={100 * s ** r:.2f}\%$ of the time, they will have the same hashes for a particular band of $r={r}$ rows"
)
st.markdown(
f"5. $1 - s^r = {100 * (1 - s ** r):.2f}\%$ of the time, they will have at least one different hash for a particular band"
)
st.markdown(
f"6. $(1 - s^r)^b = {100 * (1 - s ** r)**b:.2f}\%$ of the time, they will have at least one different hash for all $b={b}$ bands"
)
st.markdown(
f"7. $1 - (1 - s^r)^b={100 * (1 - (1 - s ** r)**b):.2f}\%$ of the time, they will have at least one band with the same hashes"
)
t = st.slider("Select a Jaccard similarity threshold", 0.0, 1.0, 0.1)
x = np.linspace(0, 1, 1000)
y = 1 - (1 - x**r) ** b
fig = go.Figure(
data=go.Scatter(
x=x,
y=y,
showlegend=False,
)
)
fig = fig.add_shape(
type="line",
x0=t,
y0=0,
x1=t,
y1=1,
line=dict(
color="Red",
width=4,
),
)
false_positive_x = [d for d in x if d <= t] + [t]
false_positive_y = [d for i, d in enumerate(y) if x[i] <= t] + [0]
fig.add_trace(
go.Scatter(
x=false_positive_x,
y=false_positive_y,
fill="tozeroy",
fillcolor="rgba(255, 0, 0, 0.2)",
line_color="rgba(255, 0, 0, 0)",
showlegend=False,
)
)
false_negative_x = [d for d in x if d > t]
false_negative_y = [d for i, d in enumerate(y) if x[i] > t]
fig.add_trace(
go.Scatter(
x=[t] + false_negative_x + [1],
y=[1] + false_negative_y + [1],
fill="toself",
fillcolor="rgba(0, 255, 0, 0.2)",
line_color="rgba(0, 255, 0, 0)",
showlegend=False,
)
)
st.plotly_chart(fig)
false_positive = integrate.quad(lambda x: 1 - (1 - x**r) ** b, 0, t)[0]
false_negative = integrate.quad(lambda x: (1 - x**r) ** b, t, 1)[0]
cols = st.columns(2)
cols[0].metric(label="False positive area", value=f"{false_positive:.2f}")
cols[1].metric(label="False negative area", value=f"{false_negative:.2f}") |