Spaces:
Runtime error
Runtime error
| 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}") |