Marouane.B

تخيل معايا عطيتي لـ ChatGPT شي ملف PDF فيه 1000 صفحة، وسولتيه على شي تفصيلة صغيرة. في أجزاء من الثانية، كيجيب ليك الجواب من وسط داك البحر ديال الكلمات. كيفاش دار ليها؟ واش قرا الكتاب كامل في ديك اللحظة؟ مستحيل.

السر هو أن داك الكتاب تقسم وتحول لـ Vectors (مصفوفات أرقام) باستعمال شي embedding model. فاش كتسول، سؤالك حتى هو كيتحول لـ Vector، والسيستم كيمشي يقلب على أقرب 3 أو 4 نصوص كيشبهو ليه في المعنى.

التحدي هنا هو: كيفاش هاد السيستم كيقدر يلقى هاد النصوص وسط الملايين ديال الـ Vectors في رمشة عين بلا ما يفحصهم كاملين؟

الحل الذكي هو تبني Graph - شبكة ديال الاتصالات بين هاد الـ vectors - و تنقل فيه بطريقة greedy حتى توصل للأقرب. هاد الحل كيتسمى Navigable Small World (NSW).

الجزء الأول: KNN - البحث الشامل

KNN في سياق الـ vector search هو "الجهد العضلي" أو brute force: عندك query vector” q”، كتحسب المسافة بينو وبين كاع الـ vectors اللي عندك في الـ dataset، وكتعزل أقرب k.

def brute_force_search(query, all_vectors, k):
    distances = []
    for v in all_vectors:
        d = euclidean_distance(query, v)
        distances.append((v, d))
    distances.sort(key=lambda x: x[1])
    return distances[:k]

التكلفة: O(n × d) لكل query. (n هو عدد الـ vectors، و d هو عدد الأبعاد).

كل dimension هو رقم واحد فـ vector، وكيعبّر على جانب معيّن من المعنى ديال النص.

يلا عندك مليون vector بـ 768 بُعد؟ غادي إلزمك 768 مليون عملية حسابية غير باش تجاوب على سؤال واحد. النتيجة غتكون دقيقة 100%، ولكن السيستم غيكون ثقيل لدرجة ما يمكنش تخدم بيه في تطبيق عملي.

السؤال اللي NSW كيجاوب عليه: واش نقدرو ننظمو هاد الـ vectors فشي بنية (data structure) تخلينا نلقاو أقرب k vectors في O(log n) بلا ما نفحصو الداتا (data) كاملة؟

الجزء الثاني: علاش Graph؟

قبل ما يفكرو في الـ graphs، الناس جربو بزاف ديال الحلول بحال شجر البحث (KD-trees) ولا الـ hashing (LSH). ولكن هاد الحلول كاملة كتفشل فاش كيكترو الأبعاد (dimensions) ديال الـ vectors، وهي المشكلة اللي معروفة بـ curse of dimensionality.

الـ graph كياخد طريق أخرى تماماً.

الفكرة الأساسية

الفكرة هي أنك يلا ربطتي كل Vector بجيرانو اللي قراب ليه، هاد 'القرب' كيولي مسار (Path) تقدر تمشي فيه. عوض ما تقلب في الداتا كاملة، كتدخل لـ Graph من أي نقطة (randomly)، وكتسول الجيران: 'شكون فيكم اللي كيشبه لهاد الـ Query أكتر؟'.

كتحول للنقطة الأقرب، وكتعاود نفس العملية (Greedy Search) حتى كتوصل لـ 'أقرب الجيران' (Nearest Neighbors) ممكنين.

شنو هي الـ Small World Topology؟

هاد المفهوم كيعني بلي الـ graph ديالنا خاص يكون فيه جوج أنواع ديال الروابط:

روابط قصيرة المدى (Short-range): هادي كتعطيك الدقة فاش كتقرب من الهدف.
روابط طويلة المدى (Long-range): هادو هما اللي كيخليوك تقطع مسافات كبيرة في رمشة عين.

تشبيه: فكّر فيها بحال شبكة الطرقان في المغرب. لوطوروت (Highway) هو الـ Long-range link اللي كيوصلك من كازا لأكادير في وقت قياسي. أما الشوارع وسط المدينة فهي الـ Short-range links اللي كتوصلك للعنوان بالضبط … بلا لوطوروت، كنتي غادي تضطر تدخل لوسط كاع المدن اللي في الطريق (برشيد ,بنت جرير، قلعة السراغنة...)

الجزء الثالث: NSW - كيفاش كنبنيو الـ Graph

الورقة البحثية الأصلية (Malkov et al., 2014) كتقترح طريقة بناء ذكية وبسيطة في نفس الوقت، وهي الإدراج المتسلسل (Sequential Insertion). الـ vectors كيدخلو واحد بواحد لـ graph اللي كيبدا خاوي:

البحث في الـ Graph الحالي: بالنسبة لكل vector جديد، كانديرو بحث سريع باش نلقاو أحسن M جيران (أقرب النقط اللي ديجا كاينين في الشبكة).
إنشاء الروابط (Edges): كانديرو روابط ثنائية الاتجاه (Bidirectional) بين الـ vector الجديد وهاد الجيران.

هاد العملية كتحوّل الـ dataset من مجرد نقط مفرقة لـ شبكة متصلة (Connected Network).

الكود:

def insert(self, new_node: Node):
    if len(self.nodes) == 0:
        self.entry_point = new_node
        self.nodes.append(new_node)
        return

    if len(self.nodes) < self.m:
        for node in self.nodes:
            new_node.neighbors.append(node)
            node.neighbors.append(new_node)
        self.nodes.append(new_node)
        return

    # البحث العادي على الجيران
    neighbors = self.search(new_node.vector, [self.entry_point], self.m)
    for neighbor in neighbors:
        new_node.neighbors.append(neighbor)
        neighbor.neighbors.append(new_node)
    self.nodes.append(new_node)

فاش كنعيطو على insert لشي Vector جديد، الكود كيدوز من 3 ديال المراحل على حسب حالة الـ Graph:

1. البداية (The First Node): يلا كان الـ Graph خاوي (len == 0)، هاد النقطة هي اللي كتولي نقطة الدخول (entry_point). هي الساس اللي غيبدا منه كاع البحث في المستقبل.

2. مرحلة الـ Bootstrap: فاش كيكون عدد النقط اللي دخلنا قل من M (عدد الجيران اللي بغينا)، كنربطو النقطة الجديدة مع كاع النقط اللي كاينين.

علاش؟ حيت في الأول ما كيكونش عندنا داتا كافية باش نديرو "بحث" حقيقي. هاد المرحلة هي اللي كتعطينا دوك الروابط الطويلة (Long-range links) اللي هضرنا عليهم.

3. (The Greedy Search): فاش كيدخل Vector جديد، كنخدمو self.search (اللي غنشرحوها لتحت) باش تقلب لينا في الـ Graph اللي كاين دابا على أقرب M جيران لهاد النقطة.

غير كنلقاوهم، كانديرو روابط ثنائية (Bidirectional).
يعني النقطة الجديدة كتعرف جيرانها، والجيران حتى هما كيتزاد عندهم هاد "الوافد الجديد" في ليستة الجيران ديالهم. (common technique)

منين كيجيو الروابط الطويلة؟

ما كاين حتى شي سطر في الكود كيقول "صاوب رابط طويل".

هاد الروابط كيتصاوبو بوحدهم بفضل الترتيب: الـ vectors اللولين اللي دخلوا للـ graph كيكونوا مضطرين يرتبطوا ببعضياتهم وخا يكونوا بعاد (حيت ما كاينش غيرهم). هادوك هما اللي كيوليو "لوطوروت" ديال السيستم من بعد.

لاحظ واحد الحاجة مهمة: باش النقطة الجديدة تلقى بلاصتها في هاد الـ Graph اللي كتشوف قدامك، خاصها تدير "بحث" وسط النقط اللي ديجا كاينين.

يلا جربتي تبرك على Play في الـ Animation، غتلاحظ كيفاش الروابط كيتصاوبو واحد بواحد. هادشي كيدينا مباشرة لأهم سؤال: كيفاش السيستم كيقدر "يتمشى" وسط هاد الزحام ديال النقط بلا ما يتلف؟

الجزء الرابع: NSW Search - كيفاش كنتنقلو

دابا تخيل معايا الـ Graph واجد، وجا يوزر (user) عطانا سؤال (Query). الهدف هو نلقاو أقرب النقط لهاد السؤال بلا ما نشوفو المليون نقطة كاملة. هنا كنبداو من الـ entry_point وكنتحركو بطريقة Greedy : ديما كنمشيو عند الجار اللي كيبان لينا أقرب للهدف.

باش ننظمو هاد الحركة ونضمنوا الدقة، كنستعملو جوج ديال الـ Heaps:

candidates (Min-Heap): هادي هي "ليستة الانتظار". فيها كاع النقط اللي يلاه اكتشفناهم وخصنا نفحصو جيرانهم. ديما كنعطيو الأسبقية للنقطة الأقرب للـ Query.
results (Max-Heap): هادي هي "المنصة الشرفية". فيها أحسن k نتائج لقينا تال دابا.

شرط التوقف الذكي

البحث ما كيبقاش خدام لمالانهاية. كاين واحد السطر في الكود هو اللي كيعطي لـ NSW السرعة ديالو:

# ... code   

closest_node, closest_dist = candidates.pop_min()
furthest_node, furthest_dist = results.peek_max()

if closest_dist > furthest_dist:
   break

# ... code

المنطق بسيط: يلا كان أقرب مرشح عندي في candidates (يعني أحسن واحد ممكن نكتشفو دابا) أبعد من أسوأ نتيجة عندي في results... فهذا يعني أنني وصلت لـ "طريق مسدود". أي جار جديد غنكتشفو غيكون غير كيزيد يبعد على الهدف. هنا كنحبسو البحث وكنرجعو النتائج اللي عندنا.

دابا أجي نشوفو هاد الـ "Greedy Search" كيفاش كيطبق هاد القاعدة في الواقع

(ملاحظة: الـ EF (Search Capacity) اللي كتشوف هو اللي كيحدد شحال من "مرشح" كنقدرو نخليو في الـ Heaps في نفس الوقت باش نضمنو الدقة).

الجزء الخامس: النتائج — Brute Force مقابل NSW

جربت هادشي على داتا (Dataset) ديال مقالات شطرنج، وهادو هما الملاحظات اللي لقيت:

marouaneboufarouj@marouanes-MacBook-Air ~/..../jiwar  main  python3 nsw.py

BertModel LOAD REPORT from: sentence-transformers/all-MiniLM-L6-V2
Key                     | Status     |  |
------------------------+------------+--+-
embeddings.position_ids | UNEXPECTED |  |

Query: 'how do pawns affect the position':
0 - [pawn_structure.md] 'Pawn structure determines the character of a posit...'
1 - [endgame_principles.md] 'behind passed pawns, whether your own or your oppo...'
2 - [endgame_principles.md] 'In the endgame, the king becomes an active piece a...'

Distance computation (build): 267
Distance computation (search): 114

marouaneboufarouj@marouanes-MacBook-Air ~/..../jiwar  main  python3 brute.py

BertModel LOAD REPORT from: sentence-transformers/all-MiniLM-L6-V2
Key                     | Status     |  |
------------------------+------------+--+-
embeddings.position_ids | UNEXPECTED |  |

Query: 'how do pawns affect the position':
0 - 0.8990233550498961 [pawn_structure.md] 'Pawn structure determines the character of a posit...'
1 - 0.9252497085480987 [endgame_principles.md] 'behind passed pawns, whether your own or your oppo...'
2 - 0.9331996353277733 [endgame_principles.md] 'In the endgame, the king becomes an active piece a...'


Distance computation: 125

الدقة (Recall): في الداتا الصغيرة، NSW كيعطي نفس نتائج البحث الشامل بالضبط (100% Recall).
الكفاءة: فاش كيكون عندك غير 25 مقال، الـ Brute Force كيربح حيت ما كيحتاجش وقت للبناء. ولكن غير كتوصل لمليون وثيقة، الـ Brute Force كيولي مستحيل، بينما NSW كيبقى "خفيف" حيت كيدير غير ~200 عملية حسابية بلاصة مليون.

عدد الـ Vectors	Brute Force (وقت البحث)	NSW (وقت البحث)
1,000	خطي (linear, كيثقال)	سريع
1,000,000	بطيء جداً	سريع (لوغاريتمي)

شنو بعد هادشي؟

الـ NSW اللي هضرنا عليه واعر، ولكن فيه واحد العيب صغير: فاش كتكبر الداتا بزاف، "نقطة الدخول" تقدر تكون بعيدة بزاف على الجواب. الخوارزمية كتضيع الوقت وهي "كتسارا" في الزناقي باش يلاه تقرب للمنطقة اللي فيها الجواب.

هنا كايجي الـ HNSW (Hierarchical Navigable Small World) باش يحل هاد المشكل بفكرة واعرة مستوحاة من Google Maps.

تخيل معايا السيناريو التالي: أنت دابا فاتح الخريطة ومزومّي (Zoom in) لدرجة كتشوف فيها غير الزناقي وسط مدينة مكسيكو سيتي، وفجأة بغيتي تمشي لـ تغازوت في المغرب.

في NSW العادي، غتضطر "تزلق" فوق الخريطة وأنت شاد نفس الـ Zoom. غتدوز فوق المحيط الأطلسي مليمتر بمليمتر، وغتضيع وقت خيالي وأنت كتشوف غير الما، غير باش توصل للمغرب. هادي هي تمارة ديال البحث في "طبقة وحدة".

أما في HNSW، الملاحة كتولي ذكية بفضل نظام الطبقات:

المرحلة 1 (The Big Jump): أول حاجة كيديرها السيستم هي Zoom Out. مابقيتيش كتشوف الزناقي، وليتي كتشوف غير القارات. بـ "نقزة" وحدة، كتحول من أمريكا لـ أفريقيا في رمشة عين.

المرحلة 2 (Regional Search): دابا كيهبط السيستم درجة وحدة (Zoom In 50%). كتبدا تبان ليك خريطة المغرب والمدن الكبار. كتحرك لجهة أكادير حيت هي الأقرب للهدف ديالك.

المرحلة 3 (The Final Destination): هنا كيدير السيستم Zoom In 100% (الطبقة السفلية). كيرجعك للزناقي والدروب، وكيحطك في تغازوت بالضبط.

الورقة ديال HNSW (2018)
Efficient and Robust Approximate Nearest Neighbor Search using HNSW Graphs هادي هي الـ Paper "الأسطورية" اللي حطات المعايير الجديدة للـ Vector Databases اللي كنخدمو بيهم اليوم (بحال Milvus, Weaviate, و Pinecone).

الكود الكامل ديال هاد التجربة متاح على GitHub — المشروع سميتو jiwar (جوار).