2025-11-18T15:28:13.400087

Local Causal Discovery for Statistically Efficient Causal Inference

Schubert, Claassen, Magliacane

Causal discovery methods can identify valid adjustment sets for causal effect estimation for a pair of target variables, even when the underlying causal graph is unknown. Global causal discovery methods focus on learning the whole causal graph and therefore enable the recovery of optimal adjustment sets, i.e., sets with the lowest asymptotic variance, but they quickly become computationally prohibitive as the number of variables grows. Local causal discovery methods offer a more scalable alternative by focusing on the local neighborhood of the target variables, but are restricted to statistically suboptimal adjustment sets. In this work, we propose Local Optimal Adjustments Discovery (LOAD), a sound and complete causal discovery approach that combines the computational efficiency of local methods with the statistical optimality of global methods. First, LOAD identifies the causal relation between the targets and tests if the causal effect is identifiable by using only local information. If it is identifiable, it then finds the optimal adjustment set by leveraging local causal discovery to infer the mediators and their parents. Otherwise, it returns the locally valid parent adjustment sets based on the learned local structure. In our experiments on synthetic and realistic data LOAD outperforms global methods in scalability, while providing more accurate effect estimation than local methods.

academic

স্থানীয় কার্যকারণ আবিষ্কার পরিসংখ্যানগতভাবে দক্ষ কার্যকারণ অনুমানের জন্য

মৌলিক তথ্য

পেপার আইডি: 2510.14582
শিরোনাম: Local Causal Discovery for Statistically Efficient Causal Inference
লেখক: Mátyás Schubert (অ্যামস্টারডাম বিশ্ববিদ্যালয়), Tom Claassen (রেডবাউড বিশ্ববিদ্যালয় নিজমেজেন), Sara Magliacane (অ্যামস্টারডাম বিশ্ববিদ্যালয়)
শ্রেণীবিভাগ: stat.ML cs.AI cs.LG
প্রকাশনার সময়: ২০২৫ সালের অক্টোবর ১৬ (arXiv প্রাক-প্রিন্ট)
পেপার লিংক: https://arxiv.org/abs/2510.14582v1

সারসংক্ষেপ

কার্যকারণ আবিষ্কার পদ্ধতিগুলি লক্ষ্য ভেরিয়েবলের একটি জোড়ার জন্য কার্যকারণ প্রভাব অনুমানের জন্য কার্যকর সমন্বয় সেট সনাক্ত করতে পারে, এমনকি যখন অন্তর্নিহিত কার্যকারণ গ্রাফ অজানা থাকে। বৈশ্বিক কার্যকারণ আবিষ্কার পদ্ধতিগুলি সম্পূর্ণ কার্যকারণ গ্রাফ শেখার উপর দৃষ্টি নিবদ্ধ করে, তাই সর্বোত্তম সমন্বয় সেট (অর্থাৎ সর্বনিম্ন অ্যাসিম্পটোটিক ভেরিয়েন্স সহ সেট) পুনরুদ্ধার করতে পারে, কিন্তু ভেরিয়েবলের সংখ্যা বৃদ্ধির সাথে সাথে তারা দ্রুত গণনাগতভাবে অসাধ্য হয়ে ওঠে। স্থানীয় কার্যকারণ আবিষ্কার পদ্ধতিগুলি লক্ষ্য ভেরিয়েবলের স্থানীয় প্রতিবেশীর উপর দৃষ্টি নিবদ্ধ করে আরও মাপযোগ্য বিকল্প প্রদান করে, কিন্তু পরিসংখ্যানগতভাবে উপ-সর্বোত্তম সমন্বয় সেটের মধ্যে সীমাবদ্ধ। এই কাজে, লেখকরা স্থানীয় সর্বোত্তম সমন্বয় আবিষ্কার (LOAD) প্রস্তাব করেছেন, যা স্থানীয় পদ্ধতির গণনাগত দক্ষতা এবং বৈশ্বিক পদ্ধতির পরিসংখ্যানগত সর্বোত্তমতা একত্রিত করে এমন একটি নির্ভরযোগ্য এবং সম্পূর্ণ কার্যকারণ আবিষ্কার পদ্ধতি।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যা সংজ্ঞা

কার্যকারণ অনুমানে, দুটি ভেরিয়েবলের মধ্যে কার্যকারণ প্রভাব অনুমান করা একটি মূল কাজ। যখন অন্তর্নিহিত কার্যকারণ গ্রাফ অজানা থাকে, কার্যকারণ প্রভাব অনুমানের জন্য কার্যকর সমন্বয় সেট সনাক্ত করতে কার্যকারণ আবিষ্কার পদ্ধতির মাধ্যমে প্রয়োজন। বিদ্যমান পদ্ধতিগুলি একটি মৌলিক ট্রেড-অফের সম্মুখীন:

বৈশ্বিক পদ্ধতির দ্বিধা: বৈশ্বিক কার্যকারণ আবিষ্কার পদ্ধতিগুলি (যেমন PC অ্যালগরিদম) সম্পূর্ণ কার্যকারণ গ্রাফ শিখতে এবং সর্বোত্তম সমন্বয় সেট পুনরুদ্ধার করতে পারে, কিন্তু গণনাগত জটিলতা ভেরিয়েবলের সংখ্যার সাথে সূচকীয়ভাবে বৃদ্ধি পায়, বড় আকারের সমস্যায় অসম্ভব।
স্থানীয় পদ্ধতির সীমাবদ্ধতা: স্থানীয় কার্যকারণ আবিষ্কার পদ্ধতিগুলি (যেমন MB-by-MB, LDECC) গণনাগতভাবে দক্ষ, কিন্তু শুধুমাত্র উপ-সর্বোত্তম সমন্বয় সেট পুনরুদ্ধার করতে পারে, যা কার্যকারণ প্রভাব অনুমানের অ্যাসিম্পটোটিক ভেরিয়েন্স বৃদ্ধি করে।

গবেষণা প্রেরণা

লেখকরা বিদ্যমান স্থানীয় পদ্ধতিতে নিম্নলিখিত সমস্যাগুলি খুঁজে পেয়েছেন:

LocalPC অ্যালগরিদম সংলগ্ন ভেরিয়েবল সনাক্ত করার সময় যথেষ্ট নির্ভরযোগ্য নয়, সম্ভবত অ-সংলগ্ন স্পাউসকে সংলগ্ন হিসাবে ভুলভাবে সনাক্ত করতে পারে
LDECC অ্যালগরিদম অসম্পূর্ণ, কিছু ক্ষেত্রে সমস্ত নির্দেশনাযোগ্য প্রান্ত নির্দেশনা দিতে পারে না
LDP অ্যালগরিদম কিছু সনাক্তকরণযোগ্য প্রভাব শূন্য হলে ভুলভাবে প্রভাব অসনাক্তকরণযোগ্য রিপোর্ট করতে পারে

অতএব, একটি নতুন পদ্ধতির প্রয়োজন যা স্থানীয় পদ্ধতির গণনাগত দক্ষতা বজায় রেখে বৈশ্বিক পদ্ধতির পরিসংখ্যানগত সর্বোত্তমতা অর্জন করে।

মূল অবদান

স্থানীয় তথ্যের উপর ভিত্তি করে কার্যকারণ প্রভাব সনাক্তকরণযোগ্যতা নির্ধারণের পদ্ধতি বিকাশ: স্থানীয় তথ্য ব্যবহার করে কার্যকারণ প্রভাব সনাক্তকরণযোগ্য কিনা তা নির্ধারণের জন্য প্রয়োজনীয় এবং যথেষ্ট শর্ত প্রস্তাব করা হয়েছে।
LOAD অ্যালগরিদম প্রস্তাব: একটি নির্ভরযোগ্য এবং সম্পূর্ণ পদ্ধতি যা ভেরিয়েবলের চারপাশের স্থানীয় তথ্য ব্যবহার করে সর্বোত্তম সমন্বয় সেট সনাক্ত করতে পারে।
ব্যাপক পরীক্ষামূলক মূল্যায়ন: সিন্থেটিক এবং বাস্তব ডেটায় LOAD মূল্যায়ন করা হয়েছে, এটি কম গণনাগত খরচে উচ্চ মানের সমন্বয় সেট পুনরুদ্ধার করতে পারে তা প্রমাণ করে।
তাত্ত্বিক গ্যারান্টি: LOAD এর কার্যকারণ প্রভাব সনাক্তকরণযোগ্যতা এবং সর্বোত্তম সমন্বয় সেট খুঁজে পাওয়ার ক্ষেত্রে নির্ভরযোগ্যতা এবং সম্পূর্ণতা প্রমাণ করা হয়েছে।

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

লক্ষ্য ভেরিয়েবল X এবং Y এর একটি জোড়া দেওয়া হলে, লক্ষ্য হল:

X এবং Y এর মধ্যে কার্যকারণ সম্পর্ক নির্ধারণ করা (স্পষ্ট পূর্বপুরুষ, সম্ভাব্য পূর্বপুরুষ বা নিশ্চিত অ-পূর্বপুরুষ)
কার্যকারণ প্রভাব সনাক্তকরণযোগ্য কিনা তা নির্ধারণ করা
যদি সনাক্তকরণযোগ্য হয়, সর্বোত্তম সমন্বয় সেট খুঁজে পাওয়া; অন্যথায় স্থানীয়ভাবে কার্যকর পিতামাতা সমন্বয় সেট ফেরত দেওয়া

LOAD অ্যালগরিদম আর্কিটেকচার

LOAD অ্যালগরিদম ৫টি প্রধান পদক্ষেপে বিভক্ত:

পদক্ষেপ ১: লক্ষ্য ভেরিয়েবলের মধ্যে কার্যকারণ সম্পর্ক নির্ধারণ

LocalRelate অ্যালগরিদম (অ্যালগরিদম ১) ব্যবহার করে নিম্নলিখিত উপপাদ্যের মাধ্যমে সম্পর্ক নির্ধারণ করা হয়:

স্পষ্ট পূর্বপুরুষ সম্পর্ক (উপপাদ্য ৪.১): CPDAG G তে যেকোনো দুটি ভিন্ন নোড X এবং Y এর জন্য, X ∈ ExplAn_G(Y) যদি এবং শুধুমাত্র যদি X ⊥̸⊥ Y | Pa_G(X) ∪ Sib_G(X)
নিশ্চিত অ-পূর্বপুরুষ সম্পর্ক (উপপাদ্য ৪.२): X হল Y এর নিশ্চিত অ-পূর্বপুরুষ যদি এবং শুধুমাত্র যদি X ⊥⊥ Y | Pa_G(X)

পদক্ষেপ ২: কার্যকারণ প্রভাব সনাক্তকরণযোগ্যতা পরীক্ষা করা

স্থানীয় তথ্যের উপর ভিত্তি করে অভিযোজিত পরীক্ষা প্রস্তাব করা হয়েছে:

লেম্মা ৪.३: CPDAG G তে X ∈ PossAn_G(Y) এর জন্য, G (X,Y) এর সাপেক্ষে সমন্বয় অভিযোজিত যদি এবং শুধুমাত্র যদি:

∀V ∈ Sib_G(X) : V ⊥⊥ Y | Pa_G(V) ∪ {X}

এই শর্তটি LocalAmenTest অ্যালগরিদম (অ্যালগরিদম २) দ্বারা দক্ষতার সাথে সনাক্ত করা যায়।

পদক্ষেপ ३-५: সর্বোত্তম সমন্বয় সেট নির্মাণ

যদি কার্যকারণ প্রভাব সনাক্তকরণযোগ্য হয়, LOAD নিম্নলিখিত পদক্ষেপের মাধ্যমে সর্বোত্তম সমন্বয় সেট নির্মাণ করে:

স্পষ্ট বংশধর খুঁজে পাওয়া: T এর সমস্ত স্পষ্ট বংশধর সনাক্ত করা
মধ্যস্থতাকারী নোড চিহ্নিত করা: T এর স্পষ্ট বংশধর এবং O এর স্পষ্ট পূর্বপুরুষ উভয়ই এমন নোড খুঁজে পাওয়া
সর্বোত্তম সমন্বয় সেট নির্মাণ:
```
Oset_G(T,O) = Pa_G(Cn_G(T,O)) \ (Cn_G(T,O) ∪ {T})
```

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

স্থানীয় সমন্বয় পরীক্ষা: প্রথমবারের মতো স্থানীয় তথ্য ব্যবহার করে সমন্বয় পরীক্ষা করার জন্য প্রয়োজনীয় এবং যথেষ্ট শর্ত প্রস্তাব করা হয়েছে, সমস্ত সম্ভাব্য নির্দেশিত পথ পরীক্ষা করার প্রয়োজনীয়তা এড়ায়।
ক্যাশিং মেকানিজম: উন্নত MB-by-MB অ্যালগরিদম পূর্ববর্তী চালনায় সনাক্ত করা Markov কম্বল এবং স্থানীয় কাঠামো পুনরায় ব্যবহার করতে ক্যাশ ব্যবহার করে, গণনাগত দক্ষতা উল্লেখযোগ্যভাবে উন্নত করে।
তাত্ত্বিক সম্পূর্ণতা: LOAD কার্যকারণ সম্পর্ক, সনাক্তকরণযোগ্যতা এবং সর্বোত্তম সমন্বয় সেট নির্ধারণে নির্ভরযোগ্য এবং সম্পূর্ণ তা প্রমাণ করা হয়েছে।

পরীক্ষামূলক সেটআপ

ডেটাসেট

সিন্থেটিক ডেটা:
- র্যান্ডমলি উৎপন্ন Erdős–Rényi গ্রাফ ব্যবহার করা হয়েছে
- ভেরিয়েবলের সংখ্যা: ১০০-১০০০
- প্রত্যাশিত ডিগ্রি: d=२, সর্বোচ্চ ডিগ্রি: dmax=१०
- নমুনা সংখ্যা: nD=१००००
বাস্তব নেটওয়ার্ক:
- MAGIC-NIAB নেটওয়ার্ক: ४४টি নোড, গড় ডিগ্রি ३
- ANDES নেটওয়ার্ক: २२३টি নোড, গড় ডিগ্রি ३.०३

মূল্যায়ন মেট্রিক্স

গণনাগত দক্ষতা: শর্তাধীন স্বাধীনতা পরীক্ষার সংখ্যা
সমন্বয় সেটের গুণমান: সর্বোত্তম সমন্বয় সেটের F१ স্কোর
কার্যকারণ প্রভাব অনুমানের গুণমান: হস্তক্ষেপ দূরত্ব (intervention distance)

তুলনামূলক পদ্ধতি

বৈশ্বিক পদ্ধতি: PC, MARVEL, SNAP(∞)
স্থানীয় পদ্ধতি: MB-by-MB+, LDECC+, LDP+ (সম্প্রসারিত সংস্করণ)

বাস্তবায়ন বিবরণ

তাৎপর্য স্তর: α = ०.०१
তিনটি শর্তাধীন স্বাধীনতা পরীক্ষা: oracle d-separation, Fisher-Z পরীক্ষা, G२ পরীক্ষা
প্রতিটি সেটিংয়ে १००বার চালানো হয়েছে, সেরা এবং সবচেয়ে খারাপ ५টি ফলাফল সরানো হয়েছে

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

গণনাগত দক্ষতা

LOAD সমস্ত সেটিংয়ে শর্তাধীন স্বাধীনতা পরীক্ষার সংখ্যা সর্বদা বৈশ্বিক পদ্ধতির চেয়ে কম, স্থানীয় পদ্ধতির চেয়ে সামান্য বেশি:

१०००টি নোডে, LOAD ९.४३×१०३ পরীক্ষার প্রয়োজন, যখন PC ५४२.५२×१०३ প্রয়োজন
MB-by-MB+ এর ५.६४×१०३ পরীক্ষার তুলনায়, LOAD এর অতিরিক্ত ওভারহেড যুক্তিসঙ্গত

সমন্বয় সেটের গুণমান (F१ স্কোর)

Oracle সেটিং: LOAD নিখুঁত F१=१.० অর্জন করে, বৈশ্বিক পদ্ধতির সমান
Fisher-Z পরীক্ষা: LOAD সমস্ত নোড সংখ্যায় ভিত্তি পদ্ধতির চেয়ে উন্নত, F१ স্কোর প্রায় ०.९१-०.९५
G२ পরীক্ষা: LOAD দ্বিতীয় সেরা পারফরম্যান্স, কিন্তু এখনও দ্বিতীয় সেরা পদ্ধতি

হস্তক্ষেপ দূরত্ব

LOAD বেশিরভাগ সেটিংয়ে সর্বনিম্ন হস্তক্ষেপ দূরত্ব অর্জন করে:

Oracle সেটিং: ०.००३ (PC, SNAP এর সমান)
Fisher-Z পরীক্ষা: ०.०१४-०.०२६ (সেরা)
G२ পরীক্ষা: ०.०२२-०.०३६ (দ্বিতীয় সেরা, শুধুমাত্র PC এর পরে)

বাস্তব ডেটা ফলাফল

MAGIC-NIAB নেটওয়ার্কে:

LOAD সর্বোত্তম F१ স্কোর অর্জন করে (०.६२)
সর্বনিম্ন হস্তক্ষেপ দূরত্ব বাস্তবায়ন করে (०.००७)
শর্তাধীন স্বাধীনতা পরীক্ষার সংখ্যা (४.३५×१०३) স্থানীয় এবং বৈশ্বিক পদ্ধতির মধ্যে

অপসারণ পরীক্ষা

१. পরিচিত চিকিৎসা-ফলাফল সম্পর্ক: যখন পটভূমি জ্ঞান প্রদান করা হয়, LOAD* বাইনারি ডেটায় PC অতিক্রম করে २. সনাক্তকরণযোগ্য লক্ষ্য জোড়া: কার্যকারণ প্রভাব সনাক্তকরণযোগ্য নিশ্চিত করার সেটিংয়ে, ফলাফল প্যাটার্ন সামঞ্জস্যপূর্ণ থাকে ३. প্যারামিটার সংবেদনশীলতা: LOAD বিভিন্ন নমুনা সংখ্যা এবং প্রত্যাশিত ডিগ্রির জন্য শক্তিশালী পারফরম্যান্স প্রদর্শন করে

উপসংহার এবং আলোচনা

প্রধান উপসংহার

१. LOAD স্থানীয় পদ্ধতির গণনাগত দক্ষতা এবং বৈশ্বিক পদ্ধতির পরিসংখ্যানগত সর্বোত্তমতা সফলভাবে একত্রিত করে २. প্রস্তাবিত স্থানীয় সমন্বয় পরীক্ষা কার্যকারণ প্রভাব সনাক্তকরণযোগ্যতার জন্য দক্ষ নির্ধারণ পদ্ধতি প্রদান করে ३. বিভিন্ন ডেটা প্রকার এবং নেটওয়ার্ক কাঠামোতে, LOAD উচ্চতর কর্মক্ষমতা প্রদর্শন করে

সীমাবদ্ধতা

१. কার্যকারণ যথেষ্টতা অনুমান: বর্তমান সংস্করণ কোনো সুপ্ত মিশ্রণকারী বা নির্বাচন পক্ষপাত নেই অনুমান করে २. বড় আকারের নেটওয়ার্কের গণনাগত বাধা: অত্যন্ত বড় গ্রাফে, Markov কম্বল অনুসন্ধান এখনও গণনাগত বাধা হতে পারে ३. বাইনারি ডেটা কর্মক্ষমতা: G२ পরীক্ষা ব্যবহার করে বাইনারি ডেটায় কর্মক্ষমতা সীমিত

ভবিষ্যত দিকনির্দেশনা

१. কার্যকারণ অপর্যাপ্ত সেটিংয়ে সম্প্রসারণ: সুপ্ত মিশ্রণকারী কারণের ক্ষেত্রে পরিচালনা করা २. Markov কম্বল আবিষ্কার অপ্টিমাইজ করা: বড় আকারের নেটওয়ার্কের গণনাগত দক্ষতা আরও উন্নত করা ३. সীমিত নমুনা কর্মক্ষমতা উন্নত করা: বিশেষত বাইনারি ডেটায় কর্মক্ষমতা

গভীর মূল্যায়ন

শক্তি

१. উল্লেখযোগ্য তাত্ত্বিক অবদান: প্রথমবারের মতো স্থানীয় তথ্যের উপর ভিত্তি করে সমন্বয় পরীক্ষা প্রস্তাব করা হয়েছে, গুরুত্বপূর্ণ তাত্ত্বিক মূল্য রয়েছে २. শক্তিশালী ব্যবহারিকতা: গণনাগত দক্ষতা বজায় রেখে পরিসংখ্যানগত সর্বোত্তমতা অর্জন করে, বাস্তব প্রয়োগে মূল সমস্যা সমাধান করে ३. ব্যাপক পরীক্ষা: একাধিক ডেটা প্রকার, নেটওয়ার্ক স্কেল এবং মূল্যায়ন মেট্রিক্স কভার করে, ফলাফল প্রভাবশালী ४. অ্যালগরিদম সম্পূর্ণতা: নির্ভরযোগ্যতা এবং সম্পূর্ণতার তাত্ত্বিক গ্যারান্টি প্রদান করে, অ্যালগরিদম ডিজাইন কঠোর

অপূর্ণতা

१. অনুমান সীমাবদ্ধতা: কার্যকারণ যথেষ্টতা অনুমান বাস্তব প্রয়োগে সন্তুষ্ট নাও হতে পারে २. স্কেলেবিলিটি সমস্যা: যদিও বৈশ্বিক পদ্ধতির চেয়ে ভাল, অতি বড় আকারের নেটওয়ার্কে এখনও গণনাগত চ্যালেঞ্জ রয়েছে ३. সীমিত নমুনা কর্মক্ষমতা: কিছু সীমিত নমুনা সেটিংয়ে কর্মক্ষমতা যথেষ্ট স্থিতিশীল নয়

প্রভাব

१. একাডেমিক মূল্য: কার্যকারণ আবিষ্কার ক্ষেত্রে নতুন তাত্ত্বিক কাঠামো এবং অ্যালগরিদম ডিজাইন চিন্তাভাবনা প্রদান করে २. ব্যবহারিক মূল্য: কার্যকারণ প্রভাব অনুমান প্রয়োজন এমন বাস্তব প্রয়োগে গুরুত্বপূর্ণ মূল্য রয়েছে ३. পুনরুৎপাদনযোগ্যতা: বিস্তারিত অ্যালগরিদম বর্ণনা এবং পরীক্ষামূলক সেটআপ প্রদান করে, পুনরুৎপাদন এবং সম্প্রসারণ সহজ করে

প্রযোজ্য পরিস্থিতি

१. মধ্যম আকারের কার্যকারণ অনুমান: ভেরিয়েবলের সংখ্যা শত থেকে হাজার পর্যন্ত কার্যকারণ প্রভাব অনুমান কাজ २. গণনাগত সম্পদ সীমিত: গণনাগত দক্ষতা এবং পরিসংখ্যানগত কর্মক্ষমতা ভারসাম্য প্রয়োজন এমন প্রয়োগ পরিস্থিতি ३. কার্যকারণ যথেষ্ট পরিবেশ: কোনো গুরুত্বপূর্ণ সুপ্ত মিশ্রণকারী কারণ নেই এমন পর্যবেক্ষণমূলক অধ্যয়ন

রেফারেন্স

পেপারটি কার্যকারণ অনুমান ক্ষেত্রের গুরুত্বপূর্ণ সাহিত্য উদ্ধৃত করে, যার মধ্যে রয়েছে:

Pearl (२००९): Causality - কার্যকারণ অনুমানের ক্লাসিক পাঠ্যপুস্তক
Spirtes et al. (२०००): সীমাবদ্ধতা-ভিত্তিক কার্যকারণ আবিষ্কারের ভিত্তি কাজ
Henckel et al. (२०२२): সর্বোত্তম সমন্বয় সেটের গ্রাফিক মানদণ্ড
Perković et al. (२०१५): সমন্বয়ের সংজ্ঞা এবং বৈশিষ্ট্য

সামগ্রিক মূল্যায়ন: এটি কার্যকারণ অনুমানের একটি উচ্চ মানের পেপার, তাত্ত্বিক এবং ব্যবহারিক স্তরে গুরুত্বপূর্ণ অবদান রয়েছে। LOAD অ্যালগরিদম কার্যকারণ আবিষ্কারে গণনাগত দক্ষতা এবং পরিসংখ্যানগত সর্বোত্তমতার ভারসাম্য সমস্যা চতুরভাবে সমাধান করে, উল্লেখযোগ্য একাডেমিক মূল্য এবং প্রয়োগ সম্ভাবনা রয়েছে।