File size: 17,775 Bytes
e137e27
 
c31df73
 
 
 
 
5637ee4
 
 
 
7e67bfe
b46a153
e137e27
21e2e7a
 
ccd1474
 
 
 
 
 
 
 
46e355f
ccd1474
 
 
 
 
 
69caf20
ccd1474
dc5ac06
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
459f6d5
dc5ac06
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
d95e4d8
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
ccd1474
d95e4d8
 
 
 
 
 
 
 
 
 
 
 
ccd1474
c31df73
 
 
 
 
 
 
 
 
 
 
 
 
 
 
e137e27
c31df73
 
 
 
0f14580
 
 
 
 
 
 
11009b9
 
 
 
 
 
752d87b
 
 
44f2e3d
5236603
 
 
 
44f2e3d
 
9cf15e6
44f2e3d
 
 
 
 
 
 
 
 
9cf15e6
44f2e3d
 
 
 
 
 
 
c31df73
 
 
 
 
 
 
 
 
 
ccd1474
c31df73
 
 
 
 
 
466af30
e01353c
c31df73
 
 
 
 
c9d881b
e01353c
c31df73
 
 
 
 
dc5ac06
e01353c
 
c31df73
 
 
 
 
 
 
d95e4d8
c31df73
 
 
 
 
 
 
 
 
 
 
 
 
 
44f2e3d
c31df73
 
 
 
 
c9d881b
c31df73
 
 
 
 
 
 
 
5236603
c9d881b
c31df73
 
 
 
 
 
e137e27
c31df73
 
 
 
 
 
 
 
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
from fasthtml.common import *
from fasthtml.components import *
from fasthtml.components import D_title, D_article, D_front_matter, D_contents, D_byline
from plotly import graph_objects as go
from fh_plotly import plotly2fasthtml
import pandas as pd
import json
import random
import string
from rich import print
import jsonlines
import plotly.express as px
from fasthtml.components import D_code

with open("data/cluster_sizes_100.json", "r") as f:
    data = json.load(f)

dump_counts = pd.DataFrame(sorted(data.items()), columns=["cluster_size_range", "counts"])

fig = px.bar(
    dump_counts,
    x="cluster_size_range",
    y="counts",
    log_y=True,
    color="counts",
    labels={
        "cluster_size_range": "Size of Near-Duplicate Clusters (Document Count)",
        "counts": "Number of Clusters",
    },
)

dup_cluster_graph = fig.update_layout(showlegend=False) 


bloom_filter_table_info = pd.DataFrame(
        {
            "Bloom Filter": [
                "BF 0",
                "BF 8 ",
            ],
            "Band 0": [
                """
                (A,B)
                (C,D)
                (E,K)
                 """,
                "(B,K)",
            ],
            "Band 1": [
                """
                (A,B)
                (C,D)
                (F,K)
                 """,
                "(B,K)",
            ],
            "....": [
                "...",
                "...",
            ],
            "Band 8": [
                """
                (A,B)
                (C,D)
                (D,E)
                 """,
                """
                (E,K)
                (B,K)
                 """,
            ],
          
        }
    )

table_html_bloom_filter = bloom_filter_table_info.to_html(index=False, border=0)
table_div_bloom_examples = Div(NotStr(table_html_bloom_filter), style="margin: 40px;")



dup_docs_count = {
    "80": 382164413,
    "90": 660766607,
    "94": 2004544307,
    "49": 1249363963,
    "96": 6378899946,
    "91": 796400555,
    "13": 170737436,
    "34": 390565222,
    "37": 243097281,
    "78": 333786871,
    "40": 331019592,
    "47": 633983288,
    "74": 443143441,
    "12": 115630971,
    "82": 491144800,
    "63": 335567006,
    "60": 361001039,
    "42": 369986102,
    "43": 344094214,
    "95": 3297371929,
    "56": 450449769,
    "58": 394889638,
    "48": 821491815,
    "18": 192658724,
    "86": 621122463,
    "50": 917219351,
    "83": 468165632,
    "38": 281883697,
    "51": 244891366,
    "93": 1236979939,
    "65": 396080116,
    "71": 403250107,
    "11": 101639319,
    "81": 367154215,
    "72": 458795954,
    "32": 218765954,
    "92": 943046601,
    "85": 507967375,
    "66": 279985567,
    "54": 291611429,
    "87": 657754973,
    "39": 296672084,
    "89": 747973994,
    "26": 179628225,
    "45": 441047510,
    "64": 319547728,
    "76": 337730046,
    "57": 415519600,
    "53": 346555733,
    "75": 319730996,
    "21": 239475626,
    "67": 277544884,
    "10": 102493868,
    "68": 348155455,
    "59": 344897755,
    "62": 326551051,
    "22": 223000489,
    "88": 722070344,
    "52": 295881819,
    "84": 613535675,
    "55": 487356947,
    "17": 226423150,
    "69": 349626770,
    "20": 163869592,
    "16": 452282480,
    "70": 390584359,
    "73": 394778904,
    "28": 197047765,
    "36": 230817595,
    "44": 618669127,
    "29": 180518021,
    "77": 429496570,
    "25": 140344588,
    "14": 212064682,
    "41": 428759750,
    "15": 147268059,
    "00": 136048949,
    "31": 325178167,
    "35": 213448884,
    "79": 394056890,
    "24": 359444850,
    "30": 178934263,
    "61": 336060420,
    "23": 378045294,
    "46": 417319179,
    "33": 239167872,
    "27": 111503187,
    "19": 125085842,
}

dup_docs_count_for_graph = pd.DataFrame(
    sorted(dup_docs_count.items()), columns=["CC_dump", "num_duplicates"]
)

fig = px.bar(
    dup_docs_count_for_graph,
    x="CC_dump",
    y="num_duplicates",
    labels={"CC_dump": "CommonCrawl Dump", "num_duplicates": "Number of duplicates"},
)

dup_docs_count_graph = fig

nfc_examples = pd.DataFrame(
        {
            "Original Text": [
                "für",
                "the problem \ ud83d \ ude42",
                "peptidoglycan`s",
            ],
            "NFC Text": [
                "für",
                "the problem 🙂",
                "peptidoglycan's",
            ],
          
        }
    )

table_html_nfc = nfc_examples.to_html(index=False, border=0)
table_div_nfc_examples = Div(NotStr(table_html_nfc), style="margin: 40px;")


dask_algo = """
dask.bag.from_sequence(doc_file_paths)
.map_partitions(stream_docs)
.groupby(lambda doc: doc["hash"])
.map_partitions(make_doc_pairs)
.compute()
"""
email_code = """
r"[A-Za-z0-9!#$%&'*+/=?^_`{|}~-]+(?:\.[A-Za-z0-9!#$%&'*+/=?^_`{|}~-]+)*@(?:(?:[A-Za-z0-9]
(?:["r"A-Za-z0-9-]*[A-Za-z0-9])?\.)+[A-Za-z0-9](?:[A-Za-z0-9-]*[A-Za-z0-9])?|\[(?:(?:25
[0-5]|2[0-4][0-9]|[&quot r&quot01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?
|[A-Za-z0-9-]*[A-Za-z0-9]:)])
"""
ip_address_code = """
r"(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)"
"""

nfc_code = """
ftfy.fix_text(text, normalization="NFC")
"""

pii_table = pd.DataFrame(
        {
            "PII Type": [
                "Email",
                "IP Address",
            ],
            "Examples": [
                "[email protected]",
                "172.217.164.110",
            ],
            "Target": [
                "[email protected]",
                "[22.214.171.124 , ...]",
            ],
        }
    )

table_html_pii = pii_table.to_html(index=False, border=0)
table_div_pii = Div(NotStr(table_html_pii), style="margin: 40px;")

global_div = Div(
        Section(
            H2("Global Steps"),
            P("Deduplication is one of the most important steps when creating large web datasets for LLM pretraining. Methods to deduplicate datasets attempt to identify and remove redundant/repeated data from the dataset."),
        ),
        Section(
            H2("Deduplication"),
            H3("Why do we need deduplication?"),
            P("Deduplication is beneficial for LM pretraining in several ways, the most obvious being the reduction of training data. With less training data, the model requires shorter training times to achieve the same or even better accuracy. Deduplication also helps avoid train-test overlap, thereby improving evaluation metrics. Additionally, it reduces the risk of memorization [1]. Duplicate data can lead to a strong double descent phenomenon, where repeated data causes test loss to increase midway through training [2]. By implementing deduplication and selective upsampling, we gain control over the pretraining data distribution, rather than relying on the inherent distribution of the source, which is often the internet."),
            P("To illustrate this, below is the distribution of near-duplicate clusters, organized into buckets of 100. The first bucket contains clusters with sizes ranging from 2 to 100, as found in the Common Crawl dataset. Some clusters even reach up to a million documents."),
            plotly2fasthtml(dup_cluster_graph),
            Img(src="images/100k.png", height = "300", width = "600" ),
            P("We started deduplication with 61.8 TB of high-quality, filtered, and compressed documents. The initial dataset had roughly 48.83 billion documents. First, we performed exact deduplication using a Bloom filter with a capacity of 1 billion and a false positive rate of 0.001. This reduced the documents from 48.83 billion to 40.21 billion, removing about 17% as exact duplicates. This step used constant memory for the Bloom filter and lessened the workload for subsequent near-deduplication."),
            P("For the global near-deduplication, we employed a methodology used by prior works like SlimPajama [3] but scaled it to the entire dataset which includes 87 Common Crawl dumps (also called “crawls”) and the curated data. This near-deduplication process involved generating signatures for every document, matching these signatures to identify near-duplicates, and then clustering the near-duplicate documents to select all but one for deletion. We choose a curated document over a Common Crawl document and later in time dump than an earlier dump when we choose the one document we keep between the matching cluster. Additionally, we maintained statistics about these matching clusters as they were formed during the final stage of deduplication. Below are the details of all four stages of our deduplication pipeline. We use Dask extensively throughout all stages of the deduplication. We have included the size of results of each stage on disk to give an idea about the scale:"),
        ),
    Section(
            H3("MinHash Generation"),
            P("We use the datasketch library to generate MinHash signatures with the number of permutations to 128. To calculate a signature, represented as a MinHash object for each document, we first clean the text by stripping whitespace, converting to lowercase, and removing punctuation, consecutive spaces, newlines, and tabs. Next, we generate a list of 13-grams to use as features for creating a document signature. These signatures along with globally-unique document ids are then saved to disk. We designed a document id encoding scheme to convert file names and line numbers (there is one document per line) to unique document ids. This also helped a lot in saving disk and memory for this stage."),
            P(B("This step produced 20 TB of hashes.")),
        ),
    Section(
            H3("Matching Pairs Generation"),
            P("We are using a Jaccard similarity threshold of 0.8 to identify near-duplicate documents. To do this, we divide the MinHashes into 9 bands, each with 13 hashes (also known as the range). To save memory during matching, we first store each band of MinHashes separately on disk. We then process each band individually. Within each band, documents are matched based on their hashes, and the matches are saved as document pairs. A document is considered a match if it matches another document in any of the 9 bands. Since we are looking for near-duplicates, a document may match multiple documents across different bands."),
            P("For partitioning and matching the hashes, we utilize Dask's bag data structure to load the document ids and MinHashes. The matching process is simply a group by operation on this bag data structure. This approach allows us to group matches efficiently and distribute the operation to multiple machines. Also doing a group by produces full components (documents that share the same signature) within a band which simplifies the later stages. The algorithm can be expressed using the Dask expression below:"),
            D_code(dask_algo, block="block", language="python"),
            P(B("This step produced 9.2 TB of matching pairs from all bands.")),
        ),
    Section(
            H3("Finding Duplicate Pairs"),
            P("Multiple bands can create the same document pairs, leading to duplicates. The simplest way to eliminate these duplicate pairs is to call distinct() before the compute(). However, we found that Dask is not very efficient when it comes to distributed distinct execution. Additionally, since we process each band separately, this approach wouldn’t remove duplicates across different bands."),
            P("To address this, we use a Bloom filter with a capacity of 64 billion and a false positive rate of 0.001 to remove duplicates. One way we parallelize the Bloom filter execution is by partitioning pairs horizontally and running one filter per partition, as shown in the table below. There is a high chance that duplicates from different bands will have the same pairs in the same horizontal partition. This step reduces the number of pairs by nearly ninefold."),
            table_div_bloom_examples,
            P("The resulting unique pairs are then used to identify clusters of near-duplicates by finding connected components in a graph, where the vertices represent documents and the edges represent matches."),
            P(B("This step produced 1.9 TB of unique pairs.")),
        ),
    Section(
            H3("Finding Connected Components using MapReduce"),
            Img(src="images/cc.png", height = "300", width = "600" ),
            P("The purpose of this step is to create a set of clusters of matching pairs. For example, a list of pairs (A, B), (B, C), (D, E) is merged into a list of components (A, B, C) and (D, E). Using a third-party library like NetworkX to find connected components would require all pairs to fit into the memory of a single machine, which is not feasible. Instead, we implemented a distributed connected component finder [4] using the Dask framework, which can scale across multiple machines. The algorithm works by mapping edges by both the source and destination of pairs and reducing only edges where the source is greater than the destination. It performs successive iterations of this MapReduce computation until convergence, meaning the number of new edges produced becomes zero. In the end, every document in a cluster points to the smallest document within the cluster. Later, we compile a list of duplicate documents that need deletion and gather statistics about each component."),
            P("We needed to partition the duplicate pairs generated in the third stage into three groups to reduce memory pressure on the final stage. We observed that the second stage itself generates partial components which have some overlap. These overlapping clusters cause some documents to appear in the delete set multiple times. However, our deletion code handled this overlap."),
            P("Below is the distribution of duplicate documents found across different dumps of CommonCrawl. The distribution is skewed to the right because the documents are bucketed by the dump ID of the document we retain, and we prefer documents from higher dump IDs."),
            plotly2fasthtml(dup_docs_count_graph),
        ),
    Section(
            H3("Analysis of Near-Duplicate Clusters"),
            P("Smaller components tend to have more overlap in their MinHash bands. Smallest components which are basically pairs have exact duplicate documents. The ones that the local exact deduplication missed."),
            Img(src="images/image3.png", height = "300", width = "600" ),
            P("From 3 or more documents per cluster you see changes in the text that are incremental. For example below there is a growing list of personnel over the years."),
            Img(src="images/image7.png", height = "300", width = "600" ),
            P("In sizable clusters comprising 1000 or more documents, we observe a trend towards templatization. This involves the recurrent use of standardized language to convey general topics such as terms and conditions, warnings, and disclaimers. Such language is prevalent on commercial websites, offering a consistent and efficient way to communicate commonly encountered information."),
            Img(src="images/image9.png", height = "300", width = "600" ),
        ),
    Section(
            H2("PII Removal"),
            H3("Motivation Behind PII Removal"),
            P("PII refers to any information that can be used to identify an individual, such as names, addresses, phone numbers, email addresses, and social security numbers. PII removal is essential for data privacy and security, as well as for compliance with global regulations. By removing PII from the training data, we can reduce the risk of data breaches and unauthorized access to sensitive information. Additionally, models can also generate PII during inference time."),
            table_div_pii,
        ),
    Section(
            H3("Removing PII"),
            P("We have removed two types of PII from the dataset: email address and IP address. Regular expressions are used to identify and replace these PII with a generic placeholder. Below is an example of how we removed email addresses from the dataset:"),
            P("We have used the following regular expressions to identify and replace PII:"),
            Ul(Li("Email:"), Li(D_code(email_code, block="block", language="python"), style="list-style-type: none"), Li("IP Address:"), Li(D_code(ip_address_code, block="block", language="python"), style="list-style-type: none")),
        ),
    Section(
            H2("Normalization Form C (NFC)"),
            H3("NFC Defined"),
            P("NFC (Normalization Form C) is a Unicode normalization form that combines characters with diacritics into a single code point. This is important for text processing tasks as it ensures that the text is consistently represented across different languages and scripts. By normalizing the text to NFC, we can avoid issues related to character encoding, such as duplicate tokens and incorrect tokenization."),
        ),
    Section(
            H3("NFC Implementation"),
            P("We have used the ftfy library to normalize the text to NFC. The library provides a simple API for normalizing text to NFC, which can be applied to the entire dataset one row at a time. Below is the code snippet about how we normalized text to NFC:"),
            Ul(Li(D_code(nfc_code, block="block", language="python"), style="list-style-type: none")), #"background-color= gray" "color= blue" maybe add this later
        ),
    Section(
            H3("NFC Examples"),
            table_div_nfc_examples,
        ),
)


def common_steps():
    return Div(
                Section(
                    global_div,
                    id="inner-text"
                )
    )