2025-11-14T20:13:11.521057

Minimax Optimal Kernel Two-Sample Tests with Random Features

Mukherjee, Sriperumbudur
Reproducing Kernel Hilbert Space (RKHS) embedding of probability distributions has proved to be an effective approach, via MMD (maximum mean discrepancy), for nonparametric hypothesis testing problems involving distributions defined over general (non-Euclidean) domains. While a substantial amount of work has been done on this topic, only recently have minimax optimal two-sample tests been constructed that incorporate, unlike MMD, both the mean element and a regularized version of the covariance operator. However, as with most kernel algorithms, the optimal test scales cubically in the sample size, limiting its applicability. In this paper, we propose a spectral-regularized two-sample test based on random Fourier feature (RFF) approximation and investigate the trade-offs between statistical optimality and computational efficiency. We show the proposed test to be minimax optimal if the approximation order of RFF (which depends on the smoothness of the likelihood ratio and the decay rate of the eigenvalues of the integral operator) is sufficiently large. We develop a practically implementable permutation-based version of the proposed test with a data-adaptive strategy for selecting the regularization parameter. Finally, through numerical experiments on simulated and benchmark datasets, we demonstrate that the proposed RFF-based test is computationally efficient and performs almost similarly (with a small drop in power) to the exact test.
academic

اختبارات النواة ثنائية العينة المثلى بالحد الأدنى مع الميزات العشوائية

المعلومات الأساسية

  • معرّف الورقة: 2502.20755
  • العنوان: اختبارات النواة ثنائية العينة المثلى بالحد الأدنى مع الميزات العشوائية
  • المؤلفون: Soumya Mukherjee, Bharath K. Sriperumbudur (جامعة ولاية بنسلفانيا)
  • التصنيف: math.ST cs.LG stat.ML stat.TH
  • تاريخ النشر: 17 أكتوبر 2025 (نسخة arXiv المسبقة)
  • رابط الورقة: https://arxiv.org/abs/2502.20755

الملخص

تقترح هذه الورقة طريقة اختبار ثنائية العينة منتظمة طيفياً قائمة على تقريب ميزات فورييه العشوائية (RFF) لمشكلة الاختبار ثنائي العينة بناءً على تضمينات فضاء هيلبرت النواة القابلة للإعادة (RKHS). تحافظ الطريقة على الأمثلية الإحصائية مع تقليل التعقيد الحسابي بشكل كبير من المستوى المكعب إلى ما يقرب من الخطي، وتوفر نسخة عملية قابلة للتحقيق بالكامل من البيانات.

خلفية البحث والدافع

المشكلة الأساسية

الاختبار ثنائي العينة هو مشكلة أساسية في الإحصاء، تهدف إلى تحديد ما إذا كانت توزيعات الاحتمالات لعينتين عشوائيتين متساوية من خلال تحليل العينات. تواجه طرق الاختبار البارامترية وغير البارامترية التقليدية قيوداً كبيرة عند التعامل مع البيانات عالية الأبعاد أو التوزيعات على المجالات غير الإقليدية.

قيود الطرق الموجودة

  1. دون الأمثلية في اختبار MMD: على الرغم من التطبيق الواسع لاختبار الفرق المتوسط الأقصى (MMD)، فإنه يفتقر إلى الأمثلية بالحد الأدنى، ويأخذ في الاعتبار فقط تضمين المتوسط ويتجاهل معلومات مشغل التباين
  2. الاختناق الحسابي للطرق المنتظمة طيفياً: على الرغم من أن اختبار MMD المنتظم طيفياً الذي تم اقتراحه مؤخراً يحقق الأمثلية بالحد الأدنى، فإن التعقيد الحسابي هو O(n³)، مما يحد من تطبيقه على البيانات الضخمة
  3. صعوبة اختيار المعاملات: يعتمد اختيار معامل التنظيم على خصائص التوزيع غير المعروفة، وتفتقر إلى استراتيجيات التكيف المدفوعة بالبيانات

دافع البحث

تهدف هذه الورقة إلى تحسين الكفاءة الحسابية لاختبار ثنائي العينة منتظم طيفياً بشكل كبير من خلال تقنية تقريب ميزات فورييه العشوائية، مع الحفاظ على الأمثلية الإحصائية، وتطوير نسخة تكيفية قابلة للاستخدام العملي.

المساهمات الأساسية

  1. اختبار فعال حسابياً وأمثل إحصائياً: يقترح اختبار ثنائي العينة منتظم طيفياً قائم على RFF، مما يقلل التعقيد الحسابي من O(n³) إلى O(nl² + nld)، مع الحفاظ على الأمثلية بالحد الأدنى في ظل شروط كافية
  2. الضمانات النظرية: يؤسس الارتباط النظري بين ترتيب تقريب RFF والأمثلية الإحصائية، ويثبت أمثلية الاختبار بالحد الأدنى عندما يفي عدد الميزات l بشروط محددة
  3. نسخة تكيفية عملية: يطور نسخة مدفوعة بالبيانات بالكامل بناءً على اختبار التبديل، تتضمن استراتيجيات اختيار تكيفية لمعامل التنظيم والدالة النواة
  4. التحقق التجريبي الشامل: يتحقق من فعالية الطريقة من خلال البيانات الاصطناعية ومجموعات البيانات المرجعية، ويعرض التوازن الجيد بين الكفاءة الحسابية والأداء الإحصائي

شرح الطريقة

تعريف المهمة

بالنظر إلى العينات المستقلة X₁:N و Y₁:M من التوزيعات P و Q، اختبر الفرضية H₀: P = Q مقابل H₁: P ≠ Q.

معمارية الطريقة الأساسية

1. الإطار المنتظم طيفياً

بالنسبة للدالة النواة K، حدد الفرق المنتظم طيفياً:

ηλ(P,Q) = 4⟨Tgλ(T)u, u⟩_{L²(R)}

حيث T هو المشغل المتكامل، u = dP/dR - 1 هو انحراف نسبة الاحتمالية، gλ هي دالة التنظيم.

2. تقريب ميزات فورييه العشوائية

بالنسبة للنوى بالشكل K(x,y) = ∫φ(x,θ)φ(y,θ)dΞ(θ)، قم بإنشاء نواة تقريبية:

Kₗ(x,y) = (1/l)∑ᵢ₌₁ˡ φ(x,θᵢ)φ(y,θᵢ)

3. إحصائية الاختبار التقريبية

بناءً على النواة التقريبية Kₗ، قم بإنشاء إحصائية الاختبار:

η̂λ,l = (1/[n(n-1)m(m-1)]) ∑ᵢ≠ⱼ ∑ᵢ'≠ⱼ' t(Xᵢ,Xⱼ,Yᵢ',Yⱼ')

حيث تتضمن دالة t الجذر التربيعي لمشغل التباين المنتظم.

نقاط الابتكار التقني

1. الابتكار النظري

  • شروط الأمثلية بالحد الأدنى: إنشاء العلاقة الدقيقة بين عدد ميزات RFF l والأمثلية الإحصائية
  • حالات الاضمحلال متعدد الحدود والأسي: تحليل أنماط الاضمحلال المختلفة لقيم المشغل المتكامل
  • التحليل غير المقارب: توفير ضمانات الأداء في العينات المحدودة

2. الابتكار الخوارزمي

  • التنظيم التكيفي: تحقيق اختيار مدفوع بالبيانات لمعامل التنظيم من خلال الاختبار المشترك
  • التكيف مع دالة النواة: التوسع إلى اختيار تكيفي لدوال النواة المتعددة
  • تنفيذ اختبار التبديل: توفير حساب القيمة الحرجة المدفوع بالبيانات بالكامل

3. الابتكار الحسابي

  • خوارزمية فعالة: تحليل تفصيلي للتعقيد الحسابي والتنفيذ المحسّن
  • المعالجة المتوازية: الطبيعة المتوازية الطبيعية لاختبار التبديل

إعداد التجربة

مجموعات البيانات

  1. البيانات الاصطناعية:
    • إزاحة المتوسط الغاوسي: P = N(0,I), Q = N(μ,I)
    • إزاحة مقياس غاوسي: P = N(0,I), Q = N(0,σ²I)
    • إزاحة وسيط كوشي: توزيعات كوشي بوسطاء مختلفة
  2. البيانات الحقيقية:
    • مجموعة بيانات MNIST: صور الأرقام المكتوبة بخط اليد 7×7 بكسل، البعد d=49
    • كشف الفروقات في التوزيع بين مجموعات الأرقام المختلفة

مؤشرات التقييم

  • القوة الإحصائية (Power): احتمالية رفض الفرضية الصفرية بشكل صحيح تحت الفرضية البديلة
  • وقت الحساب: مقارنة وقت تشغيل الخوارزمية
  • خطأ من النوع الأول: التحكم عند مستوى α=0.05

طرق المقارنة

  • الاختبار التكيفي الدقيق: اختبار منتظم طيفياً قائم على مصفوفة النواة الكاملة
  • أعداد ميزات RFF المختلفة: مقارنة الأداء لـ l ∈ {1,3,5,7,9,15,20}

تفاصيل التنفيذ

  • دالة التنظيم: منظم Showalter gλ(x) = (1-e^(-x/λ))/x
  • دوال النواة: نوى غاوسية ولابلاسية، مع اختيار عرض النطاق التكيفي
  • عدد التبديلات: نسخة RFF B=550-800، نسخة دقيقة B'=250-450

نتائج التجربة

النتائج الرئيسية

1. الأداء الإحصائي

  • إزاحة المتوسط الغاوسي: عندما l≥7، تكون القوة قريبة من الطريقة الدقيقة
  • إزاحة مقياس غاوسي: تحقيق أداء جيدة عند l≥5
  • توزيع كوشي: يتطلب ميزات أكثر (l≥10-15) للتعامل مع التوزيعات ذات الذيل الثقيل
  • بيانات MNIST: أداء جيدة على البيانات الحقيقية المعقدة عند l≥15

2. الكفاءة الحسابية

توفير وقت حسابي كبير:

  • تجارب غاوسية: تتطلب طريقة RFF فقط 33-44% من وقت الحساب
  • إزاحة المقياس: استهلاك 30-40% من الوقت
  • تجارب كوشي: فقط 5-6% من وقت الحساب
  • MNIST: استهلاك 5-15% من الوقت

3. التحقق النظري

تتحقق نتائج التجربة من التنبؤات النظرية:

  • احتياجات عدد الميزات مرتبطة بأبعاد البيانات وتعقيد التوزيع
  • المقايضة بين الحساب والإحصاء تتوافق مع التحليل النظري

تجارب الاستئصال

من خلال مقارنة أعداد ميزات RFF المختلفة، تم التحقق من:

  1. وجود عتبة عدد الميزات
  2. عدد الميزات القليل جداً يؤدي إلى فقدان القوة
  3. عدد الميزات المناسب يحقق أفضل توازن

النتائج التجريبية

  1. تأثير البعد: البيانات عالية الأبعاد تتطلب ميزات RFF أكثر
  2. تأثير نوع التوزيع: التوزيعات ذات الذيل الثقيل تتطلب ميزات أكثر لضمان الأداء
  3. العتبات العملية: يمكن تقليل عدد الميزات المطلوب نظرياً بشكل معقول في الممارسة

الأعمال ذات الصلة

اختبارات النواة ثنائية العينة

  • اختبار MMD: العمل الرائد لـ Gretton et al. (2006, 2012)
  • الأمثلية بالحد الأدنى: التطورات الأخيرة لـ Li & Yuan (2024), Schrab et al. (2023)
  • التنظيم الطيفي: الاختراق النظري لـ Hagrass et al. (2024)

تقريب الميزات العشوائية

  • نظرية RFF: الإطار الأساسي لـ Rahimi & Recht (2007)
  • تسريع MMD: التطبيقات لـ Zhao & Meng (2015), Choi & Kim (2024)
  • المقايضة بين الحساب والإحصاء: التحليل النظري لـ Sriperumbudur & Sterge (2022)

مزايا هذه الورقة

المزايا الرئيسية مقارنة بالأعمال الموجودة:

  1. دوال نواة أكثر عمومية: غير مقتصرة على النوى المتغيرة الثابتة
  2. قابلية تطبيق أوسع: دعم المجالات غير الإقليدية
  3. ضمانات نظرية أقوى: أمثلية بالحد الأدنى غير مقاربة
  4. خوارزمية أكثر عملية: تنفيذ مدفوع بالبيانات بالكامل

الخلاصة والمناقشة

الاستنتاجات الرئيسية

  1. المساهمة النظرية: إنشاء نظرية الأمثلية بالحد الأدنى لاختبار ثنائي العينة منتظم طيفياً تحت تقريب RFF للمرة الأولى
  2. المساهمة الخوارزمية: توفير خوارزمية عملية فعالة حسابياً وأمثل إحصائياً
  3. التحقق التجريبي: التحقق من فعالية الطريقة على أنواع بيانات متعددة

القيود

  1. اختيار عدد الميزات: على الرغم من توفير التوجيه النظري، فإن الاختيار العملي لا يزال يتطلب تعديلاً تجريبياً
  2. الاعتماد على دالة النواة: الأداء لا تزال تعتمد على اختيار دالة النواة
  3. التوزيعات ذات الذيل الثقيل: قد تتطلب عدداً كبيراً من الميزات للتوزيعات ذات الذيل الثقيل الشديد

الاتجاهات المستقبلية

  1. طرق تقريب أخرى: استكشاف تقنيات تقريب بديلة مثل Nyström
  2. اختبار التبديل الرخيص: دمج اختبار التبديل الرخيص لتقليل التكلفة الحسابية بشكل أكبر
  3. الضبط التلقائي للمعاملات: تطوير استراتيجيات اختيار معاملات فائقة أكثر ذكاءً

التقييم المتعمق

المزايا

  1. الصرامة النظرية: توفير تحليل نظري غير مقارب كامل، بما في ذلك الشروط الكافية وإثبات الأمثلية بالحد الأدنى
  2. قوة عملية: الخوارزمية مدفوعة بالبيانات بالكامل، بدون الحاجة إلى معرفة مسبقة
  3. تجارب شاملة: تغطي البيانات الاصطناعية والحقيقية، أنواع توزيع متعددة
  4. كتابة واضحة: تفاصيل تقنية شاملة، إثباتات كاملة

أوجه القصور

  1. تحليل التعقيد: على الرغم من تقليل التعقيد المقارب، قد تكون عوامل الثابت كبيرة
  2. حساسية المعاملات: اختيار معامل التنظيم وعدد الميزات لا يزال حساساً نسبياً
  3. معالجة الذيل الثقيل: تأثير معالجة التوزيعات ذات الذيل الثقيل يحتاج إلى تحسين

التأثير

  1. القيمة النظرية: توفير إطار نظري جديد للمقايضة بين الحساب والإحصاء في طرق النواة
  2. القيمة العملية: آفاق تطبيق مهمة في اختبار ثنائي العينة للبيانات الضخمة
  3. المساهمة المنهجية: توفير أفكار جديدة لتطبيق تقريب RFF في الاختبارات الإحصائية

السيناريوهات المناسبة

  1. البيانات الضخمة: المزايا الحسابية واضحة عندما تكون حجم العينة كبيراً
  2. البيانات عالية الأبعاد: مزايا كبيرة مقارنة بالطرق التقليدية في الإعدادات عالية الأبعاد
  3. التطبيقات في الوقت الفعلي: تحسين الكفاءة الحسابية يجعل الاختبار في الوقت الفعلي ممكناً
  4. الإعدادات غير البارامترية: مناسبة للحالات العامة حيث يكون شكل التوزيع غير معروف

المراجع

  1. Gretton, A., et al. (2012). اختبار نواة ثنائي العينة. JMLR.
  2. Hagrass, O., et al. (2024). اختبارات نواة منتظمة طيفياً ثنائية العينة. Annals of Statistics.
  3. Rahimi, A., & Recht, B. (2007). ميزات عشوائية للآلات النواة واسعة النطاق. NIPS.
  4. Choi, I., & Kim, I. (2024). المقايضة بين الحساب والإحصاء في اختبار نواة ثنائي العينة مع ميزات فورييه العشوائية.
  5. Sriperumbudur, B. K., & Sterge, N. (2022). تقريب PCA النواة التقريبي: المقايضة بين الحساب والإحصاء. Annals of Statistics.

التقييم العام: هذه ورقة عالية الجودة في الإحصاء النظري، تطبق بنجاح تقنية تقريب الميزات العشوائية على اختبار ثنائي العينة منتظم طيفياً، مما يحسن الكفاءة الحسابية بشكل كبير مع الحفاظ على الأمثلية الإحصائية. يتمتع التحليل النظري للورقة بعمق وتفصيل، والتحقق التجريبي شامل، وله قيمة مهمة لكل من نظرية التعلم الإحصائي والتطبيقات العملية.