Deduplicación a gran escala detrás de BigCode

'Deduplicación masiva en BigCode'

Audiencia objetivo

Personas interesadas en la deduplicación a nivel de documento a gran escala, y que tienen cierto entendimiento de hash, grafos y procesamiento de texto.

Motivaciones

Es importante cuidar nuestros datos antes de alimentarlos al modelo, al menos al Gran Modelo de Lenguaje en nuestro caso, como dice el viejo refrán, basura entra, basura sale. Aunque cada vez es más difícil hacerlo con modelos que llaman la atención (o deberíamos decir APIs) creando la ilusión de que la calidad de los datos importa menos.

Uno de los problemas que enfrentamos tanto en BigScience como en BigCode en cuanto a calidad de datos es la duplicación, incluyendo posible contaminación de referencia. Se ha demostrado que los modelos tienden a devolver datos de entrenamiento textualmente cuando hay muchos duplicados [1] (aunque en algunos otros dominios no está tan claro [2]), y también hace que el modelo sea vulnerable a ataques de privacidad [1]. Además, algunos de los beneficios típicos de la deduplicación incluyen:

  1. Entrenamiento eficiente: Puedes lograr el mismo, e incluso mejor, rendimiento con menos pasos de entrenamiento [3] [4].
  2. Prevenir posibles fugas de datos y contaminación de referencia: Los duplicados no nulos desacreditan tus evaluaciones y potencialmente hacen que una supuesta mejora sea una afirmación falsa.
  3. Accesibilidad. La mayoría de nosotros no podemos permitirnos descargar o transferir miles de gigabytes de texto repetidamente, sin mencionar entrenar un modelo con ello. La deduplicación, para un conjunto de datos de tamaño fijo, facilita su estudio, transferencia y colaboración.

De BigScience a BigCode

Permíteme compartir una historia primero sobre cómo me embarqué en esta búsqueda de la deduplicación, cómo han progresado los resultados y qué lecciones he aprendido en el camino.

Todo comenzó con una conversación en LinkedIn cuando BigScience ya llevaba un par de meses en marcha. Huu Nguyen se acercó a mí cuando se dio cuenta de mi proyecto personal en GitHub, preguntándome si estaba interesado en trabajar en la deduplicación para BigScience. Por supuesto, mi respuesta fue sí, completamente ignorante de cuánto esfuerzo requeriría debido a la gran cantidad de datos.

Fue divertido y desafiante al mismo tiempo. Es desafiante en el sentido de que realmente no tenía mucha experiencia de investigación con esa escala masiva de datos, y todos aún te daban la bienvenida y confiaban en ti con miles de dólares de presupuesto de cómputo en la nube. Sí, tuve que despertarme de mi sueño para verificar varias veces que había apagado esas máquinas. Como resultado, tuve que aprender sobre la marcha a través de todos los intentos y errores, lo que al final me abrió a una nueva perspectiva que no creo que hubiera tenido si no fuera por BigScience.

Mirando hacia adelante, un año después, estoy aplicando lo que he aprendido en BigCode, trabajando con conjuntos de datos aún más grandes. Además de los LLM entrenados para inglés [3], hemos confirmado que la deduplicación también mejora los modelos de código [4], utilizando un conjunto de datos mucho más pequeño. Y ahora, estoy compartiendo lo que he aprendido contigo, querido lector, y con suerte, tú también puedes tener una idea de lo que está sucediendo detrás de escena en BigCode a través del enfoque de la deduplicación.

En caso de que estés interesado, aquí tienes una versión actualizada de la comparación de deduplicación que comenzamos en BigScience:

Esto es también para conjuntos de datos de código que creamos para BigCode. Se utilizan nombres de modelos cuando no está disponible el nombre del conjunto de datos.

Parámetros MinHash + LSH ( P , T , K , B , R ) (P, T, K, B, R) ( P , T , K , B , R ) :

  1. P P P número de permutaciones/hashes
  2. T T T umbral de similitud de Jaccard
  3. K K K tamaño de n-grama/shingle
  4. B B B número de bandas
  5. R R R número de filas

Para tener una idea de cómo estos parámetros pueden afectar tus resultados, aquí tienes una demostración simple para ilustrar el cálculo matemáticamente: Demostración Matemática de MinHash.

Recorrido de MinHash

En esta sección, cubriremos cada paso de MinHash, el utilizado en BigCode, y los posibles problemas y soluciones de escalabilidad. Demostraremos el flujo de trabajo mediante un ejemplo de tres documentos en inglés:

El flujo de trabajo típico de MinHash es el siguiente:

  1. Shingling (tokenización) y fingerprinting (MinHashing), donde mapeamos cada documento en un conjunto de hashes.
  2. Localidad-sensible hashing (LSH). Este paso reduce el número de comparaciones agrupando los documentos con bandas similares.
  3. Eliminación de duplicados. En este paso decidimos qué documentos duplicados mantener o eliminar.

Shingles

Al igual que en la mayoría de las aplicaciones que involucran texto, debemos comenzar con la tokenización. Los N-gramos, también conocidos como shingles, se utilizan a menudo. En nuestro ejemplo, utilizaremos trigramas a nivel de palabras, sin puntuación. Volveremos sobre cómo el tamaño de los ngramos afecta el rendimiento en una sección posterior.

Esta operación tiene una complejidad temporal de O ( N M ) \mathcal{O}(NM) O ( N M ) donde N N N es el número de documentos y M M M es la longitud del documento. En otras palabras, depende linealmente del tamaño del conjunto de datos. Este paso se puede escalar fácilmente mediante la paralelización mediante la multiprocesamiento o la computación distribuida.

Cálculo de las huellas dactilares

En MinHash, cada shingle generalmente se 1) ha sido hasheado múltiples veces con diferentes funciones hash, o 2) ha sido permutado múltiples veces utilizando una función hash. Aquí, elegimos permutar cada hash 5 veces. Se pueden encontrar más variantes de MinHash en MinHash – Wikipedia.

Tomando el valor mínimo de cada columna dentro de cada documento, es decir, la parte “Min” de “MinHash”, llegamos a la MinHash final para este documento:

Técnicamente, no es necesario utilizar el valor mínimo de cada columna, pero el valor mínimo es la opción más común. También se pueden utilizar otras estadísticas de orden, como el máximo, el k-ésimo valor más pequeño o el k-ésimo valor más grande [21].

En la implementación, puedes vectorizar fácilmente estos pasos con numpy y esperar tener una complejidad temporal de O ( N M K ) \mathcal{O}(NMK) O ( N M K ) donde K K K es el número de permutaciones. Código modificado basado en Datasketch.

def embed_func(
    content: str,
    idx: int,
    *,
    num_perm: int,
    ngram_size: int,
    hashranges: List[Tuple[int, int]],
    permutations: np.ndarray,
) -> Dict[str, Any]:
    a, b = permutations
    masks: np.ndarray = np.full(shape=num_perm, dtype=np.uint64, fill_value=MAX_HASH)
    tokens: Set[str] = {" ".join(t) for t in ngrams(NON_ALPHA.split(content), ngram_size)}
    hashvalues: np.ndarray = np.array([sha1_hash(token.encode("utf-8")) for token in tokens], dtype=np.uint64)
    permuted_hashvalues = np.bitwise_and(
        ((hashvalues * np.tile(a, (len(hashvalues), 1)).T).T + b) % MERSENNE_PRIME, MAX_HASH
    )
    hashvalues = np.vstack([permuted_hashvalues, masks]).min(axis=0)
    Hs = [bytes(hashvalues[start:end].byteswap().data) for start, end in hashranges]
    return {"__signatures__": Hs, "__id__": idx}

Si estás familiarizado con Datasketch, podrías preguntarte por qué nos molestamos en eliminar todas las funciones de alto nivel que proporciona la biblioteca. No es porque queramos evitar agregar dependencias, sino porque pretendemos exprimir la mayor cantidad de cálculos de la CPU posible durante la paralelización. Fusionar algunos pasos en una sola llamada de función nos permite utilizar mejor nuestros recursos informáticos.

Dado que el cálculo de un documento no depende de nada más. Una buena opción de paralelización sería utilizar la función map de la biblioteca datasets:

embedded = ds.map(
    function=embed_func,
    fn_kwargs={
        "num_perm": args.num_perm,
        "hashranges": HASH_RANGES,
        "ngram_size": args.ngram,
        "permutations": PERMUTATIONS,
    },
    input_columns=[args.column],
    remove_columns=ds.column_names,
    num_proc=os.cpu_count(),
    with_indices=True,
    desc="Fingerprinting...",
)

Después del cálculo de las huellas dactilares, un documento en particular se asigna a una matriz de valores enteros. Para determinar qué documentos son similares entre sí, debemos agruparlos en función de estas huellas dactilares. Entramos en la etapa de Localidad Sensible al Hashing (LSH).

Localidad Sensible al Hashing

LSH divide la matriz de huellas dactilares en bandas, cada banda contiene el mismo número de filas. Si quedan valores hash, se ignorarán. Usemos b = 2 bandas y r = 2 filas para agrupar esos documentos:

Si dos documentos comparten los mismos hashes en una banda en una ubicación particular (índice de banda), se agruparán en el mismo cubo y se considerarán como candidatos.

Para cada fila en la columna doc_ids, podemos generar pares de candidatos combinando todos ellos de a dos. A partir de la tabla anterior, podemos generar un par de candidatos: (0, 1).

Más allá de los pares duplicados

Este es el punto en el que muchas descripciones de deduplicación en artículos o tutoriales se detienen. Aún nos queda la pregunta de qué hacer con ellos. En general, podemos seguir dos opciones:

  1. Verificar sus similitudes de Jaccard reales calculando su superposición de shingles, debido a la naturaleza de estimación de MinHash. La similitud de Jaccard de dos conjuntos se define como el tamaño de la intersección dividido por el tamaño de la unión. Y ahora se vuelve mucho más factible que calcular todas las similitudes entre pares, porque podemos enfocarnos solo en los documentos dentro de un clúster. Esto es también lo que hicimos inicialmente para BigCode, lo cual funcionó bastante bien.
  2. Considerarlos como verdaderos positivos. Probablemente ya hayas notado el problema aquí: la similitud de Jaccard no es transitiva, lo que significa que A A A es similar a B B B y B B B es similar a C C C, pero A A A y C C C no necesariamente comparten la similitud. Sin embargo, nuestros experimentos en The Stack muestran que tratar a todos ellos como duplicados mejora el rendimiento del modelo subsecuente. Y ahora nos estamos moviendo gradualmente hacia este método, que también ahorra tiempo. Pero para aplicar esto a tu conjunto de datos, aún recomendamos revisar tu conjunto de datos y analizar tus duplicados, y luego tomar una decisión basada en los datos.

A partir de tales pares, ya sean validados o no, ahora podemos construir un grafo con esos pares como aristas, y los duplicados se agruparán en comunidades o componentes conectados. En términos de implementación, desafortunadamente, aquí es donde datasets no puede ayudar mucho porque ahora necesitamos algo como un groupby donde podamos agrupar documentos en función de su desplazamiento de banda y valores de banda. Aquí hay algunas opciones que hemos probado:

Opción 1: Iterar los conjuntos de datos de la manera tradicional y recopilar aristas. Luego usar una biblioteca de grafos para detectar comunidades o componentes conectados.

Esto no escaló bien en nuestras pruebas y las razones son diversas. Primero, iterar todo el conjunto de datos es lento y consume mucha memoria a gran escala. Segundo, bibliotecas populares de grafos como graphtool o networkx tienen mucho sobrecarga para la creación de grafos.

Opción 2: Usar frameworks populares de Python como dask para permitir operaciones de groupby más eficientes.

Pero luego aún tienes problemas de iteración lenta y creación de gráficos lenta.

Opción 3: Iterar el conjunto de datos, pero usar una estructura de datos de unión y búsqueda para agrupar documentos.

Esto agrega una sobrecarga insignificante a la iteración y funciona relativamente bien para conjuntos de datos de VoAGI.

for table in tqdm(HASH_TABLES, dynamic_ncols=True, desc="Clustering..."):
    for cluster in table.values():
        if len(cluster) <= 1:
            continue
        idx = min(cluster)
        for x in cluster:
            uf.union(x, idx)

Opción 4: Para conjuntos de datos grandes, usa Spark.

Ya sabemos que los pasos hasta la parte de LSH se pueden paralelizar, lo cual también es posible en Spark. Además de eso, Spark admite groupBy distribuido de manera nativa, y también es sencillo implementar algoritmos como [18] para la detección de componentes conectados. Si te preguntas por qué no usamos la implementación de MinHash de Spark, la respuesta es que todos nuestros experimentos hasta ahora se basaron en Datasketch, que usa una implementación completamente diferente a la de Spark, y queremos asegurarnos de continuar con las lecciones y conocimientos adquiridos de eso sin entrar en otro experimento de ablación.

edges = (
    records.flatMap(
        lambda x: generate_hash_values(
            content=x[1],
            idx=x[0],
            num_perm=args.num_perm,
            ngram_size=args.ngram_size,
            hashranges=HASH_RANGES,
            permutations=PERMUTATIONS,
        )
    )
    .groupBy(lambda x: (x[0], x[1]))
    .flatMap(lambda x: generate_edges([i[2] for i in x[1]]))
    .distinct()
    .cache()
)

Un algoritmo simple de componentes conectados basado en [18] implementado en Spark.

a = edges
while True:
    b = a.flatMap(large_star_map).groupByKey().flatMap(large_star_reduce).distinct().cache()
    a = b.map(small_star_map).groupByKey().flatMap(small_star_reduce).distinct().cache()
    changes = a.subtract(b).union(b.subtract(a)).collect()
    if len(changes) == 0:
        break

results = a.collect()

Además, gracias a los proveedores de servicios en la nube, podemos configurar clústeres de Spark fácilmente con servicios como GCP DataProc. Al final, podemos ejecutar el programa para eliminar duplicados en 1,4 TB de datos en menos de 4 horas con un presupuesto de $15 por hora.

La calidad importa

Subir una escalera no nos lleva a la luna. Por eso debemos asegurarnos de que esta sea la dirección correcta y de que la estemos utilizando de la manera correcta.

Desde el principio, nuestros parámetros se heredaron en gran medida de los experimentos de CodeParrot, y nuestro experimento de ablación indicó que esos ajustes mejoraron el rendimiento del modelo [16]. Luego nos propusimos explorar aún más este camino y podemos confirmar que [4]:

  1. La deduplicación cercana mejora el rendimiento del modelo con un conjunto de datos mucho más pequeño (6 TB frente a 3 TB)
  2. Aún no hemos encontrado el límite, pero una deduplicación más agresiva (6 TB frente a 2,4 TB) puede mejorar aún más el rendimiento:
    1. Reducir el umbral de similitud
    2. Aumentar el tamaño de los shingles (unigramas → 5-gramas)
    3. Eliminar la verificación de falsos positivos porque podemos permitirnos perder un pequeño porcentaje de falsos positivos

Imagen: Dos gráficos que muestran el impacto del umbral de similitud y el tamaño de los shingles, el primero usa unigramas y el segundo 5-gramas. La línea de guiones rojos muestra el límite de similitud: cualquier documento por debajo se consideraría un falso positivo, sus similitudes con otros documentos dentro de un clúster son inferiores al umbral.

Estos gráficos nos ayudan a comprender por qué fue necesario verificar los falsos positivos para CodeParrot y la versión anterior de Stack: el uso de unigramas crea muchos falsos positivos. También demuestran que al aumentar el tamaño de los shingles a 5-gramas, el porcentaje de falsos positivos disminuye significativamente. Se desea un umbral más pequeño si queremos mantener la agresividad en la deduplicación.

Experimentos adicionales también mostraron que reducir el umbral elimina más documentos que tienen pares de alta similitud, lo que significa un aumento en la recuperación en el segmento que realmente nos gustaría eliminar en mayor medida.

Escalabilidad

Imagen: Tiempo de deduplicación versus tamaño del conjunto de datos sin procesar. Esto se logra con 15 máquinas worker c2d-standard-16 en GCP, y cada una tiene un costo de aproximadamente $0.7 por hora.

Imagen: Captura de pantalla del uso de la CPU para el clúster durante el procesamiento del conjunto de datos JSON.

Esto no es la prueba de escalabilidad más rigurosa que se puede encontrar, pero el tiempo de deduplicación, dado un presupuesto de cálculo fijo, parece ser prácticamente lineal al tamaño físico del conjunto de datos. Cuando observamos de cerca el uso de recursos del clúster durante el procesamiento del conjunto de datos JSON, el subconjunto más grande en Stack, podemos ver que MinHash + LSH (etapa 2) domina el tiempo total de cálculo real (etapa 2 + 3), que según nuestro análisis anterior es O ( N M ) \mathcal{O}(NM) O ( N M ) — lineal al volumen físico del conjunto de datos.

Proceder con precaución

La deduplicación no nos exime de una exploración y análisis exhaustivos de los datos. Además, estos descubrimientos de deduplicación son válidos para Stack, pero no significa que se puedan aplicar fácilmente a otros conjuntos de datos o lenguajes. Es un primer paso importante para construir un mejor conjunto de datos, y aún se necesitan investigaciones adicionales, como el filtrado de calidad de datos (por ejemplo, vulnerabilidad, toxicidad, sesgo, plantillas generadas, información de identificación personal).

Todavía te animamos a realizar análisis similares en tus conjuntos de datos antes de entrenar. Por ejemplo, puede que no sea muy útil realizar la deduplicación si tienes restricciones de tiempo y recursos informáticos: @geiping_2022 menciona que la deduplicación de subcadenas no mejoró el rendimiento de su modelo. Los conjuntos de datos existentes también pueden requerir un examen exhaustivo antes de su uso, por ejemplo, @gao_2020 afirma que solo se aseguraron de que Pile en sí mismo, junto con sus divisiones, estén deduplicados, y no realizarán proactivamente la deduplicación para ningún punto de referencia posterior y dejarán esa decisión en manos de los lectores.

En cuanto a la filtración de datos y la contaminación de los puntos de referencia, aún hay mucho por explorar. Tuvimos que volver a entrenar nuestros modelos de código porque HumanEval se publicó en uno de los repositorios de GitHub en Python. Los resultados tempranos de la deduplicación cercana también sugieren que MBPP [19], uno de los puntos de referencia más populares para la codificación, comparte muchas similitudes con muchos problemas de Leetcode (por ejemplo, la tarea 601 en MBPP es básicamente Leetcode 646, la tarea 604 ≃ Leetcode 151.). Y todos sabemos que GitHub no escasea de esos desafíos y soluciones de codificación. Será aún más difícil si alguien con malas intenciones carga todos los puntos de referencia en forma de scripts de Python, u otras formas menos obvias, y contamina todos tus datos de entrenamiento.

Direcciones futuras

  1. Deduplicación de subcadenas. Aunque mostró algunos beneficios para el inglés [3], aún no está claro si esto debería aplicarse también a los datos de código;
  2. Repetición: párrafos que se repiten varias veces en un documento. @rae_2021 compartió algunas heurísticas interesantes sobre cómo detectarlos y eliminarlos.
  3. Uso de incrustaciones de modelos para la deduplicación semántica. Es otra pregunta de investigación completa con experimentos de escala, costo, ablación y compensación con la deduplicación cercana. Hay algunas ideas intrigantes al respecto [20], pero aún necesitamos más evidencia situada para llegar a una conclusión (por ejemplo, la única referencia de deduplicación de texto de @abbas_2023 es @lee_2022a, cuya afirmación principal es que la deduplicación ayuda en lugar de tratar de ser SOTA).
  4. Optimización. Siempre hay espacio para la optimización: mejor evaluación de calidad, escalado, análisis del impacto en el rendimiento posterior, etc.
  5. Luego hay otra dirección para mirar las cosas: ¿Hasta qué punto la deduplicación cercana comienza a afectar el rendimiento? ¿Hasta qué punto se necesita similitud para la diversidad en lugar de considerarse redundancia?

Créditos

La imagen del encabezado contiene emojis (cara abrazando, Papá Noel, documento, mago y varita) de Noto Emoji (Apache 2.0). Esta publicación del blog está escrita con orgullo sin utilizar APIs generativas.

Un agradecimiento enorme a Huu Nguyen @Huu y Hugo Laurençon @HugoLaurencon por la colaboración en BigScience y a todos en BigCode por la ayuda en el camino. Si encuentras algún error, no dudes en contactarme: mouchenghao en gmail punto com.

Recursos de apoyo

  • Datasketch (MIT)
  • simhash-py y simhash-cpp (MIT)
  • Deduplicating Training Data Makes Language Models Better (Apache 2.0)
  • Gaoya (MIT)
  • BigScience (Apache 2.0)
  • BigCode (Apache 2.0)

Referencias

  • [1]: Nikhil Kandpal, Eric Wallace, Colin Raffel, Deduplicating Training Data Mitigates Privacy Risks in Language Models, 2022
  • [2]: Gowthami Somepalli, et al., Diffusion Art or Digital Forgery? Investigating Data Replication in Diffusion Models, 2022
  • [3]: Katherine Lee, Daphne Ippolito, et al., Deduplicating Training Data Makes Language Models Better, 2022
  • [4]: Loubna Ben Allal, Raymond Li, et al., SantaCoder: Don’t reach for the stars!, 2023
  • [5]: Leo Gao, Stella Biderman, et al., The Pile: An 800GB Dataset of Diverse Text for Language Modeling, 2020
  • [6]: Asier Gutiérrez-Fandiño, Jordi Armengol-Estapé, et al., MarIA: Spanish Language Models, 2022
  • [7]: Jack W. Rae, Sebastian Borgeaud, et al., Scaling Language Models: Methods, Analysis & Insights from Training Gopher, 2021
  • [8]: Xi Victoria Lin, Todor Mihaylov, et al., Few-shot Learning with Multilingual Language Models, 2021
  • [9]: Hugo Laurençon, Lucile Saulnier, et al., The BigScience ROOTS Corpus: A 1.6TB Composite Multilingual Dataset, 2022
  • [10]: Daniel Fried, Armen Aghajanyan, et al., InCoder: A Generative Model for Code Infilling and Synthesis, 2022
  • [11]: Erik Nijkamp, Bo Pang, et al., CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis, 2023
  • [12]: Yujia Li, David Choi, et al., Competition-Level Code Generation with AlphaCode, 2022
  • [13]: Frank F. Xu, Uri Alon, et al., A Systematic Evaluation of Large Language Models of Code, 2022
  • [14]: Aakanksha Chowdhery, Sharan Narang, et al., PaLM: Scaling Language Modeling with Pathways, 2022
  • [15]: Lewis Tunstall, Leandro von Werra, Thomas Wolf, Natural Language Processing with Transformers, Revised Edition, 2022
  • [16]: Denis Kocetkov, Raymond Li, et al., The Stack: 3 TB of permissively licensed source code, 2022
  • [17]: Rocky | Project Hail Mary Wiki | Fandom
  • [18]: Raimondas Kiveris, Silvio Lattanzi, et al., Connected Components in MapReduce and Beyond, 2014
  • [19]: Jacob Austin, Augustus Odena, et al., Program Synthesis with Large Language Models, 2021
  • [20]: Amro Abbas, Kushal Tirumala, et al., SemDeDup: Data-efficient learning at web-scale through semantic deduplication, 2023
  • [21]: Edith Cohen, MinHash Sketches: A Brief Survey, 2016

We will continue to update Zepes; if you have any questions or suggestions, please contact us!

Share:

Was this article helpful?

93 out of 132 found this helpful

Discover more

Inteligencia Artificial

Este boletín de inteligencia artificial es todo lo que necesitas #71

Esta semana, el presidente Joe Biden volvió a poner la regulación de la inteligencia artificial en el punto de mira a...

Inteligencia Artificial

Rastreador web de OpenAI y errores de la FTC

OpenAI lanza un rastreador predeterminado de opt-in para raspar Internet, mientras que la FTC lleva a cabo una invest...

Inteligencia Artificial

Expertos en ciberseguridad se disponen a asegurar las elecciones de Estados Unidos en 2024

Un equipo de expertos en ciberseguridad establecido a través del Centro de Intercambio y Análisis de Información Tecn...

Inteligencia Artificial

La estructura más resistente conocida descubierta por el Laboratorio de Robots Autónomos

El laboratorio de robótica experimental autónoma basada en la teoría de Bayes de la Universidad de Toronto en Canadá ...

Inteligencia Artificial

Cómo este investigador ganador de la Turing Award se convirtió en un legendario asesor académico

El científico teórico de la computación, Manuel Blum, ha guiado a generaciones de estudiantes de posgrado hacia carre...