"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"![](\"images/VW_chart_motivation.png\")
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"
"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "notes"
}
},
"source": [
"OTHER WAYS TO DO IT \n",
"pretty important \n",
"means you can apply this approach to any problem which involves events happening in time (sensor, serer requests, biochimical..)\n",
"\n",
"Define features which make the measured variable unexpected \n",
"Consider a different quantity (or quality) and define what anomalous means with respect to this new target (inter-arrival times, another quantity, another approach bayesian)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Model the tweets rate\n",
"\n",
"- Static volume\n",
"- Dinamic amount to account for seasonality \n",
"- Include short time memory to only detect spikes\n",
"\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Natural way to model counts of events happening in time is to use a Poisson process $N(t)$ with parameter $\\lambda$, the rate at which the events happen\n",
"\n",
"$$ \\mathbb{E}[N(t)] = \\textbf{expected number of events occurred until time } t = \\lambda t$$\n",
"\n",
"A Poisson regression models the logarithm of the expected number of events as a **linear combination** of predictor variables\n",
"\n",
"$$ \\log(\\mathbb{E}[N]) = log(\\lambda) = \\beta_1 x_1 + \\beta_2 x_2 + \\dots + \\beta_k x_k $$\n",
"\n",
"with $\\beta_i$ coefficients of the model estimated based on volume history and $x_i$ observable quantities of the datapoint."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Predictor variables for $\\lambda$\n",
"Consider seasonality at different scales \n",
"- day of the week $x_w$ \n",
"- hour of the day $x_h$ \n",
"- month (?)\n",
"- ...\n",
"\n",
"Consider recent behaviour\n",
"- count in the previous time window $x_{t-1}$\n",
"- count 2 time windows before $x_{t-2}$\n",
"- ...\n",
"- count for the day so far or yesterday (?)\n",
"\n",
"Other variables?\n",
"- ..."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Detect the anomaly\n",
"\n",
"With the expected rate $\\lambda_{pred}$, how (un)likely is that we see a number of tweets $N$ higher than the one we have so far? \n",
"\n",
"If this event has probability lower than $\\alpha$, it is anomalous!\n",
"\n",
"$$\\mathbb{P}(N \\geq n_{obs} | \\lambda_{pred}) < \\alpha$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Pros \n",
"\n",
"- timely (predict in advance)\n",
"- unsupervised (no need for annotations)\n",
"- easily adapt to different time scales \n",
"- easy to extend and include more predictors\n",
"- applicable to discrete data of different nature\n",
"- Generalised Linear Model applicable to different distribution families\n",
"\n",
"## ...and Cons\n",
"\n",
"- needs other algorithms to determine if the anomaly is geneuine (spam driven, somehow expected, ...)\n",
"- higly sensitive (try Zero inflated Poisson)\n",
"- variance and expected value are the same (try Negative Binomial)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Novelty Detection"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "-"
}
},
"source": [
"Given an **anomaly period**, identify which tweets are **novel**\n",
"\n",
"Observation: tweets tend to cluster in **stories**"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Given an **anomaly period**, identify the tweets which are ~~novel~~ **not part of old stories**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# VW Example"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Challenges"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"- **streaming** setting - each tweet needs to be processed in **bounded space** and **time**\n",
" - bounded space - constant amount of stories in memory \n",
" - bounded time - Locality Sensitive Hashing (Indyk and Motwani, 1998)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"- how much history is required to decide if a tweet is novel"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"- stories can be reoccurring"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# First Story Detection"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "-"
}
},
"source": [
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Locality Sensitive Hashing\n",
"\n",
"- approximate nearest neighbor task\n",
"- hashing each tweet into buckets to maximize the probability of collision for tweets which are close\n",
"- requires a measure of distance for tweets"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Advantage:\n",
"- LSH works well if tweet is close to its nearest neighbor"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Disadvantage:\n",
"- LSH fails to return the nearest neighbor for distant tweets\n",
"- Solution: if the LSH doesn't return a neighbor, check novelty against most recent tweets"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Novelty Flow"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"![](\"images/LSH_flow.png\")
"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": false
},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Conclusions\n",
"\n",
"- general anomaly detection algorithm which is:\n",
" - applicable to different problems\n",
" - easily understandable\n",
" - fast training and detection\n",
" - works well in a streaming pipeline\n",
" \n",
"- two-step novelty detection\n",
" - fast lookup using LSH\n",
" - additional lookup in inverted index for the most recent tweets"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Thank You!\n",
"\n",
"\n", "\n", "Presentation & Notebooks:\n", "\n", "https://github.com/knowsis/novel-twitter-anomalies-pydatalondon2016/\n", "\n", "\n", "
\n", "\n", "delia@knowsis.com\n", "\n", "mattia@knowsis.com\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
"
]
}
],
"metadata": {
"celltoolbar": "Slideshow",
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.11"
}
},
"nbformat": 4,
"nbformat_minor": 0
}