How you can use Minimum Covariance Determinant (MCD) to detect novel news headlines

In today’s information age, we’re inundated with news articles each day. Lots of these articles are merely restatements of the identical facts, but some contain genuinely recent information that may have a significant impact on our decision-making. For instance, someone looking to take a position in Meta will want to deal with articles that contain exclusive information, reasonably than those who simply reiterate previously published data. It’s crucial to give you the chance to tell apart between news that’s novel and news that’s redundant, in order that we are able to make informed decisions without being overwhelmed by the deluge of data.

That is where novelty detection comes it. Novelty detection refers back to the task of identifying recent or unknown data that differs from previously seen data. It’s an unsupervised learning technique used to detect anomalies, outliers, or recent patterns in data. The important thing idea is to construct a model of “normal” data, after which use that model to discover data points that deviate from normal.

Within the context of reports articles, this involves detecting whether an article incorporates recent information that shouldn’t be available elsewhere. To do that, we are able to perhaps develop a baseline of what is thought or available, after which compare recent information to that baseline. If there are significant differences between the brand new information and the baseline, then we are able to say that the data is novel.

Minimum Covariance Determinant (MCD)

Minimum Covariance Determinant (MCD) method is a way for estimating the covariance matrix of a dataset. It may be used to create an elliptical shape that encapsulates the central mode of a Gaussian distribution, and any data points that lie outside of this shape could be regarded as novelties (sometimes referred as anomalies). The MCD method is especially useful for datasets which might be noisy or have outliers, as it might probably help to discover unusual data points that will not fit the general pattern of the info. (see example).

MCD could be used to detect novelty in news headlines. While the tactic could be generalized to full articles, our aim is to offer a concise example of applying MCD for novelty detection on short texts. MCD is a strong estimator of multivariate location and scatter, making it well-suited for identifying outliers in high-dimensional data equivalent to text. On a dataset of reports headlines, MCD will learn a model of “normal” headlines based on covariance. We are able to then use this model to attain recent headlines and flag those who significantly deviate from the norm as potential novel or anomalous stories. The sample code and experiments will illustrate how MCD novelty detection works in practice.

Step-by-Step Approach

Embedding: In machine learning we use embedding as a method to represent data in a more compact and efficient form. Embedding transforms raw data right into a lower-dimensional representation that captures crucial features of the info.

Text embedding is a selected kind of embedding that’s used to rework text data right into a vector representation. It takes into consideration the semantics and relationships between words, phrases, and sentences, and converts them right into a numerical representation that captures the meaning of the text. This enables us to perform operations equivalent to finding similar text, clustering text based on semantic meaning, and more.

Suppose we gather the next headlines about Meta up to now couple of months:

news = [
"Mark Zuckerberg touts potential of remote work in metaverse as Meta threatens employees for violating return-to-office mandate",
"Meta Quest 3 Shows Us the Metaverse Dream isn’t Dead Yet",
"Meta has Apple to thank for giving its annual VR conference added sizzle this year",
"Meta launches AI chatbots for Instagram, Facebook and WhatsApp",
"Meta Launches AI Chatbots for Snoop Dogg, MrBeast, Tom Brady, Kendall Jenner, Charli D’Amelio and More",
"Llama 2: why is Meta releasing open-source AI model and are there any risks?",
"Meta's Mandatory Return to Office Is 'a Mess'",
"Meta shares soar on resilient revenue and $40bn in buybacks",
"Facebook suffers fresh setback after EU ruling on use of personal data",
"Facebook owner Meta hit with record €1.2bn fine over EU-US data transfers"
]

We are able to use OpenAI to generate text embedding for every of the sentences as:

def get_embedding(text, 
model = 'text-embedding-ada-002'):
text = text.replace("n", " ")
return openai.Embedding.create(input = [text], engine = model)['data'][0]['embedding']
df['embedding'] = df.news.apply(lambda x: get_embedding(x))
df['embedding'] = df['embedding'].apply(np.array)
matrix = np.vstack(df['embedding'].values)
matrix.shape
# Output: (10, 1536)

The text-embedding-ada-002 model from OpenAI is a cutting-edge embedding model that takes a sentence as input and outputs an embedding vector of length 1536. The vector represents the semantic meaning of the input sentence, and could be used for tasks equivalent to semantic similarity, text classification, and more. The newest version of the model incorporates state-of-the-art language representation techniques to provide highly accurate and robust embeddings. In the event you shouldn’t have access to OpenAI, you should use other embedding models equivalent to Sentence Transformers.

Once we produce the embedding, we make a matrix variable that stores a matrix representation of the embeddings from the df[‘embedding’] column. This is finished by utilizing the vstack function from the NumPy library, which stacks all the vectors (each representing a single sentence) within the column vertically to create a matrix. This enables us to make use of matrix operations in the following step.

Compute MCD: We use the embeddings as features and compute the MCD to estimate the situation and shape of the central data cloud (central mode of a multivariate Gaussian distribution).

Fit an Elliptic Envelope: We then fit an elliptic envelope to the central mode using the computed MCD. This envelope acts as a boundary to separate normal points from the novel ones.

Predict Novel Sentences: Finally, we use the elliptic envelope to categorise the embeddings. Points lying contained in the envelope are considered normal, and points lying outside are considered novel or anomalous.

To do all this, we use EllipticEnvelope class from scikit-learn in Python to use the MCD:

# Reduce the dimensionality of the embeddings to 2D using PCA
pca = PCA(n_components=2)
reduced_matrix = pca.fit_transform(matrix)
reduced_matrix.shape
# Fit the Elliptic Envelope (MCD-based robust estimator)
envelope = EllipticEnvelope(contamination=0.2)  
envelope.fit(reduced_matrix)
# Predict the labels of the sentences
labels = envelope.predict(reduced_matrix)
# Find the indices of the novel sentences
novel_indices = np.where(labels == -1)[0]
novel_indices
#Output: array([8, 9])

contamination is a parameter which you can tune depending on what number of sentences you expect to be novel. It represents the proportion of outliers within the dataset. The predict method returns an array of labels, where 1 denotes inliers (normal points), and -1 denotes outliers (novel points).

Moreover, to visualise the high-dimensional embeddings in 2D in addition to saving computation time, we use PCA to project the high-dimensional embedding vectors to a lower-dimensional 2D space, we denote this by reduced_matrix.

We are able to see that novel_indices outputs array([8, 9]), that are the sentence indices which might be found to be novel.

Plotting the result: we can visualise the result by plotting the embeddings and the elliptic envelope. The inliers (normal points) could be plotted with one color or marker, and the outliers (novel points) could be plotted with one other. The elliptic envelope could be visualized by plotting the ellipse that corresponds to the Mahalanobis distance.

To realize the visualisation we:

1. Extract the situation and covariance matrix of the fitted elliptic envelope model.
2. Compute the eigenvalues and eigenvectors of the covariance matrix to find out the orientation and axes lengths of the ellipse.
3. Compute the Mahalanobis distance of every sample from the middle of the fitted ellipse model.
4. Determine a threshold distance based on the contamination parameter, which specifies the expected percentage of outliers.
5. Scale the width and height of the ellipse based on the edge Mahalanobis distance.
6. Label points contained in the ellipse as inliers and outdoors as outliers.
7. Plot the inliers and outliers, adding the scaled ellipse patch.
8. Annotate each data point with its index to discover outliers.

# Extract the situation and covariance of the central mode
location = envelope.location_
covariance = envelope.covariance_
# Compute the angle, width, and height of the ellipse
eigenvalues, eigenvectors = np.linalg.eigh(covariance)
order = eigenvalues.argsort()[::-1]
eigenvalues, eigenvectors = eigenvalues[order], eigenvectors[:, order]
vx, vy = eigenvectors[:, 0]
theta = np.arctan2(vy, vx)
# Compute the width and height of the ellipse based on the eigenvalues (variances)
width, height = 2 * np.sqrt(eigenvalues)
# Compute the Mahalanobis distance of the reduced 2D embeddings
mahalanobis_distances = envelope.mahalanobis(reduced_matrix)
# Compute the edge based on the contamination parameter
threshold = np.percentile(mahalanobis_distances, (1 - envelope.contamination) * 100)
# Scale the width and height of the ellipse based on the Mahalanobis distance threshold
width, height = width * np.sqrt(threshold), height * np.sqrt(threshold)
# Plot the inliers and outliers
inliers = reduced_matrix[labels == 1]
outliers = reduced_matrix[labels == -1]
# Re-plot the inliers and outliers together with the elliptic envelope with annotations
plt.scatter(inliers[:, 0], inliers[:, 1], c='b', label='Inliers')
plt.scatter(outliers[:, 0], outliers[:, 1], c='r', label='Outliers', marker='x')
ellipse = Ellipse(location, width, height, angle=np.degrees(theta), edgecolor='k', facecolor='none')
plt.gca().add_patch(ellipse)
# Annotate each point with its index
for i, (x, y) in enumerate(reduced_matrix):
plt.annotate(str(i), (x, y), textcoords="offset points", xytext=(0, 5), ha='center')
plt.title('Novelty Detection using MCD with Annotations')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend()
plt.grid(True)
plt.show()

Finally, we get the visualisation for inliers and outliers as:

Now allow us to visit the headlines, 8 and 9 are:

Facebook suffers fresh setback after EU ruling on use of private data.

Facebook owner Meta hit with record €1.2bn high-quality over EU-US data transfers.

Each headlines are related to the European Union’s efforts to control how Meta use and transfer personal data on their platforms.

While the inlier headlines are mostly about how Meta goes all-in on AI and virtual reality. The AI focus is clear in the discharge of a brand new AI chatbot, and the virtual reality focus is clear in the discharge of the brand new Meta Quest 3 headset. You too can notice that 0th and sixth headlines are about earn a living from home setup and hence they’re closer to one another on the plot.

Summary

On this post we’ve shown how one can distinguish between Normal Points and Novel Points based on distribution. Briefly, Normal Points are the points that lie within the high-density region of the info distribution, i.e., they’re near nearly all of the opposite points within the feature space. Meanwhile, Novel Points These are the points that lie within the low-density region of the info distribution, i.e., they’re removed from nearly all of the opposite points within the feature space.

Within the Context of MCD and Elliptic Envelope, Normal Points are points that lie contained in the elliptic envelope, which is fitted to the central mode of the info distribution. While, Novel Points lie outside the elliptic envelope.

We learned also that there are parameters which might be influencing the consequence of MCD, these are:

• Threshold: The choice boundary or threshold is crucial in determining whether a degree is normal or novel. For example, within the Elliptic Envelope method, points contained in the envelope are considered normal, and people outside are considered novel.
• Contamination Parameter: This parameter, often utilized in novelty detection methods, defines the proportion of the info expected to be novel or contaminated. It affects the tightness of the envelope or threshold, influencing whether a degree is assessed as normal or novel.

We must always also note that within the case of latest articles, since each news article comes from a special week, the novelty detection method should consider the temporal aspect of the news. If the tactic doesn’t inherently account for the temporal order, you might need to include this aspect manually, equivalent to by considering the change in topics or sentiments over time, which can be beyond the scope of this post.