In this paper we will give a characterization of the learnability of forgiving 0-1 loss functions in the finite label multiclass setting. To do this, we create a new combinatorial dimension that is based off of the Natarajan Dimension and we show that a hypothesis class is learnable in our setting if and only if this Generalized Natarajan Dimension is finite. We also show a connection to learning with set-valued feedback. Through our results we show that the learnability of a set learning problem is characterized by the Natarajan Dimension.
- পত্র আইডি: 2510.08382
- শিরোনাম: ক্ষমাশীল 0-1 ক্ষতি ফাংশনের বহুশ্রেণী শিক্ষণযোগ্যতার বৈশিষ্ট্যায়ন
- লেখক: জ্যাকব ট্রাউগার (মিশিগান বিশ্ববিদ্যালয়), টাইসন ট্রাউগার (ওহাইও স্টেট বিশ্ববিদ্যালয়), অম্বুজ তেওয়ারী (মিশিগান বিশ্ববিদ্যালয়)
- শ্রেণীবিভাগ: cs.LG (যন্ত্র শিক্ষা), stat.ML (পরিসংখ্যান - যন্ত্র শিক্ষা)
- প্রকাশনার সময়: ২০২৫ সালের অক্টোবর (arXiv প্রাক-মুদ্রণ)
- পত্র লিঙ্ক: https://arxiv.org/abs/2510.08382
এই পত্রটি সীমিত লেবেল বহুশ্রেণী শ্রেণীবিভাগ সেটিংয়ে ক্ষমাশীল 0-1 ক্ষতি ফাংশনের শিক্ষণযোগ্যতার একটি বৈশিষ্ট্যায়ন প্রদান করে। এই উদ্দেশ্যে, লেখকরা নাতারাজন মাত্রার উপর ভিত্তি করে একটি নতুন সমন্বয়মূলক মাত্রা তৈরি করেছেন এবং প্রমাণ করেছেন যে অনুমান শ্রেণী এই সেটিংয়ে শিক্ষণযোগ্য যদি এবং শুধুমাত্র যদি এই সাধারণীকৃত নাতারাজন মাত্রা সীমিত হয়। নিবন্ধটি সেট-মূল্যবান প্রতিক্রিয়া শিক্ষার সাথে সংযোগও প্রদর্শন করে, ফলাফলের মাধ্যমে দেখায় যে সেট শিক্ষা সমস্যার শিক্ষণযোগ্যতা নাতারাজন মাত্রা দ্বারা বৈশিষ্ট্যপূর্ণ।
যন্ত্র শিক্ষা তত্ত্বে, শ্রেণীবিভাগ কাজের শিক্ষণযোগ্যতার বৈশিষ্ট্যায়ন একটি মূল সমস্যা। দ্বিশ্রেণী শ্রেণীবিভাগের জন্য, VC মাত্রা PAC শিক্ষণযোগ্যতা সম্পূর্ণভাবে বৈশিষ্ট্যপূর্ণ করে; বহুশ্রেণী শ্রেণীবিভাগের জন্য, সীমিত লেবেল পরিস্থিতিতে নাতারাজন মাত্রা অনুরূপ ভূমিকা পালন করে। তবে, এই তত্ত্বগুলি সমস্ত মান 0-1 ক্ষতি ফাংশনের উপর ভিত্তি করে, যা "পরিচয়ের অবিচ্ছেদ্যতা" (Identity of Indiscernibles) বৈশিষ্ট্য রাখে, অর্থাৎ যখন এবং শুধুমাত্র যখন দুটি লেবেল সমান হয় তখনই ক্ষতি শূন্য হয়।
বাস্তব প্রয়োগে, প্রায়শই আরও "ক্ষমাশীল" ক্ষতি ফাংশনের প্রয়োজন হয়, যেমন:
- বাক্য পুনর্লিখন কাজ: একাধিক ভিন্ন বাক্য সঠিক পুনর্লিখন হতে পারে
- থ্রেশহোল্ড-ভিত্তিক মেট্রিক্স: একটি নির্দিষ্ট থ্রেশহোল্ড পরিসরের মধ্যে আউটপুট সবই গ্রহণযোগ্য
- সেট-মূল্যবান প্রতিক্রিয়া শিক্ষা: পূর্বাভাস ফলাফল শুধুমাত্র একটি প্রদত্ত সেটে থাকা প্রয়োজন
এই পরিস্থিতিতে, একাধিক ভিন্ন আউটপুট একই প্রকৃত লেবেলের জন্য শূন্য ক্ষতি তৈরি করতে পারে, যা ঐতিহ্যবাহী তত্ত্বের মৌলিক অনুমানকে ভেঙে দেয়।
বিদ্যমান শিক্ষণযোগ্যতা তত্ত্ব (VC মাত্রা, নাতারাজন মাত্রা ইত্যাদি) সবই লেবেল সমতা এবং ক্ষতি মূল্যকে অন্তর্নিহিতভাবে সংযুক্ত করে। যখন ক্ষতি ফাংশন পরিচয়ের অবিচ্ছেদ্যতা সন্তুষ্ট করে না, এই তত্ত্বগুলি আর প্রযোজ্য নয়, শিক্ষণযোগ্যতা বৈশিষ্ট্যপূর্ণ করার জন্য নতুন তাত্ত্বিক কাঠামোর প্রয়োজন।
- সাধারণীকৃত নাতারাজন মাত্রা প্রস্তাব: নাতারাজন মাত্রার উপর ভিত্তি করে একটি নতুন সমন্বয়মূলক মাত্রা তৈরি করা, যা ক্ষমাশীল 0-1 ক্ষতি ফাংশনের জন্য প্রযোজ্য
- সম্পূর্ণ শিক্ষণযোগ্যতা বৈশিষ্ট্যায়ন: প্রমাণ করা যে অনুমান শ্রেণী ক্ষমাশীল 0-1 ক্ষতির অধীনে PAC শিক্ষণযোগ্য যদি এবং শুধুমাত্র যদি সাধারণীকৃত নাতারাজন মাত্রা সীমিত হয়
- সেট শিক্ষা সমস্যার সমাধান: ব্যাচ সেটিংয়ে সেট-মূল্যবান প্রতিক্রিয়া শিক্ষার শিক্ষণযোগ্যতা প্রথমবারের মতো বৈশিষ্ট্যপূর্ণ করা
- তাত্ত্বিক কাঠামোর প্রতিষ্ঠা: পরিচয়ের অবিচ্ছেদ্যতা সন্তুষ্ট না করে এমন ক্ষতি ফাংশনের জন্য একটি সিস্টেমেটিক শিক্ষা তত্ত্ব প্রতিষ্ঠা করা
ইনপুট স্পেস: X (যেকোনো ইনপুট স্পেস)
আউটপুট স্পেস: Y=[k] (সীমিত লেবেল সেট, ∣Y∣=k)
অনুমান শ্রেণী: H⊂YXক্ষতি ফাংশন: ℓ:Y×Y→{0,1}, নিম্নলিখিত সীমাবদ্ধতা সন্তুষ্ট করে:
- দ্বিমূল্যবান: ∀y1,y2∈Y,ℓ(y1,y2)∈{0,1}
- প্রতিসাম্য: ∀y1,y2∈Y,ℓ(y1,y2)=ℓ(y2,y1)
- অ-অন্তর্ভুক্তি: ∀y1,y2∈Y,σ(y1)⊂σ(y2)
- স্বতঃসিদ্ধি: ∀y∈Y,ℓ(y,y)=0
যেখানে σ(y)={y′∣ℓ(y,y′)=0} y এর সাথে শূন্য ক্ষতি তৈরি করে এমন সমস্ত লেবেলের সেট প্রতিনিধিত্ব করে।
সংজ্ঞা 4 (সাধারণীকৃত নাতারাজন মাত্রা):
অনুমান শ্রেণী H এবং ক্ষতি ফাংশন ℓ সাধারণীকৃত নাতারাজন পাউডার সেট S={s1,...,sn}, যদি h1,h2∈H বিদ্যমান থাকে যেমন:
- বিভাজন শর্ত: ∀si∈S,σ(h1(si))=σ(h2(si))
- বাস্তবায়ন শর্ত: ∀S′⊆S, একটি h∈H বিদ্যমান যেমন:
- ∀s∈S′:σ(h(s))=σ(h1(s))
- ∀s∈S∖S′:σ(h(s))=σ(h2(s))
সাধারণীকৃত নাতারাজন মাত্রা GNdim(H,ℓ) হল H দ্বারা সাধারণীকৃত নাতারাজন পাউডার করা যায় এমন সর্ববৃহৎ সেটের মূলত্ব।
মূল অন্তর্দৃষ্টি: সমতুল্য সম্পর্ক y∼y′⇔σ(y)=σ(y′) এর মাধ্যমে সংজ্ঞায়িত করে, মূল সমস্যাটিকে ভাগফল স্পেস YC=Y/∼ এ একটি মান বহুশ্রেণী শিক্ষা সমস্যায় রূপান্তরিত করা।
লেম্মা 1: ক্ষতি ফাংশন সমতুল্য সম্পর্ককে সম্মান করে, অর্থাৎ যদি y1∼y1′ এবং y2∼y2′, তাহলে ℓ(y1,y2)=ℓ(y1′,y2′)।
অনুসিদ্ধান্ত 1: মূল শিক্ষা সমস্যা (X,Y,H,ℓ) ভাগফল স্পেস শিক্ষা সমস্যা (X,YC,HC,ℓC) এর সমতুল্য।
অনুসিদ্ধান্ত 2: GNdim(H,ℓ)=Ndim(HC)
উপপাদ্য 1 (প্রধান ফলাফল): শিক্ষা সমস্যা (X,Y,H,ℓ) PAC শিক্ষণযোগ্য যদি এবং শুধুমাত্র যদি GNdim(H,ℓ)<∞।
প্রয়োজনীয়তা (লেম্মা 2):
- প্রতিপ্রমাণ ব্যবহার করে, ধরে নিন GNdim(H,ℓ)=∞
- প্রতিকূল বিতরণ পরিবার নির্মাণ করুন যাতে কোনো শিক্ষা অ্যালগরিদম কোনো বিতরণে খারাপ পারফর্ম করে
- পাউডার সম্পত্তি ব্যবহার করে 2m পয়েন্টে জটিল ফাংশন পরিবার নির্মাণ করুন
- সম্ভাব্যতা যুক্তির মাধ্যমে প্রমাণ করুন যে একটি বাস্তবায়ন বিতরণ বিদ্যমান যেখানে যেকোনো অ্যালগরিদমের ক্ষতি কমপক্ষে 2k1
পর্যাপ্ততা (লেম্মা 3):
- সমতুল্য শিক্ষা সমস্যার নির্মাণ ব্যবহার করুন
- মূল ক্ষতিকে k টি মান 0-1 ক্ষতির রৈখিক সমন্বয়ে বিয়োজন করুন: 1−LD(h)=∑i=1k(1−LDi(h))
- যেহেতু HC সীমিত নাতারাজন মাত্রা রাখে, এটি একীভূত সংগ্রহ সম্পত্তি রাখে
- যৌথ সীমা ব্যবহার করে ERM অ্যালগরিদমের কার্যকারিতা প্রমাণ করুন
এই পত্রটি একটি বিশুদ্ধ তাত্ত্বিক কাজ, প্রধানত গাণিতিক প্রমাণের মাধ্যমে তাত্ত্বিক ফলাফল যাচাই করে, ঐতিহ্যবাহী অর্থে কোনো পরীক্ষামূলক সেটআপ নেই। তাত্ত্বিক যাচাইকরণ নিম্নলিখিত উপায়ে সম্পাদিত হয়:
- গঠনমূলক প্রমাণ: প্রয়োজনীয়তা প্রমাণ করার জন্য নির্দিষ্ট প্রতিকূল বিতরণ নির্মাণের মাধ্যমে
- হ্রাস প্রমাণ: জটিল সমস্যাকে পরিচিত মান বহুশ্রেণী শিক্ষা সমস্যায় হ্রাস করা
- মাত্রা বিশ্লেষণ: সমন্বয়মূলক মাত্রার সীমিততার মাধ্যমে শিক্ষণযোগ্যতা বৈশিষ্ট্যপূর্ণ করা
নিবন্ধটি সেট শিক্ষা সমস্যার মাধ্যমে তত্ত্বের কার্যকারিতা যাচাই করে, তাত্ত্বিক প্রযোজ্যতা প্রদর্শনের জন্য নির্দিষ্ট ক্ষতি ম্যাট্রিক্স নির্মাণ করে।
উপপাদ্য 1 এর প্রমাণ সম্পূর্ণ: সাধারণীকৃত নাতারাজন মাত্রা সম্পূর্ণভাবে ক্ষমাশীল 0-1 ক্ষতি ফাংশনের PAC শিক্ষণযোগ্যতা বৈশিষ্ট্যপূর্ণ করে তা সফলভাবে প্রমাণ করা।
সেট শিক্ষার বৈশিষ্ট্যায়ন (অনুসিদ্ধান্ত 3):
সেট শিক্ষা সমস্যার জন্য, যেখানে ক্ষতি ফাংশন সংজ্ঞায়িত:
ℓ(y,v)={01y∈vঅন্যথায়
প্রমাণ করা হয়েছে যে এই সমস্যার শিক্ষণযোগ্যতা মান নাতারাজন মাত্রা দ্বারা বৈশিষ্ট্যপূর্ণ, অর্থাৎ GNdim(H,ℓ)=Ndim(H)।
- মাত্রা সংরক্ষণ সম্পত্তি: অনেক ক্ষেত্রে, এমনকি যখন ক্ষতি ফাংশন আরও ক্ষমাশীল হয়ে ওঠে, শিক্ষা জটিলতা (মাত্রা দ্বারা পরিমাপ করা) অপরিবর্তিত থাকতে পারে
- প্রতিকূল বিতরণের অস্তিত্ব: PAC শিক্ষার কঠোরতা মানে এমনকি যখন ক্ষতি ফাংশন বেশিরভাগ শূন্য হয়, তখনও শিক্ষা কঠিন করে এমন বিতরণ বিদ্যমান থাকতে পারে
- ভাগফল স্পেসের গুরুত্ব: উপযুক্ত সমতুল্য সম্পর্কের মাধ্যমে, জটিল শিক্ষা সমস্যা মান সমস্যায় হ্রাস করা যায়
- VC তত্ত্ব: ভ্যাপনিক এবং চার্ভোনেনকিস (১৯৭৪) দ্বিশ্রেণী শ্রেণীবিভাগের শিক্ষণযোগ্যতা তত্ত্ব প্রতিষ্ঠা করেছেন
- নাতারাজন মাত্রা: নাতারাজন (১৯৮৯) তত্ত্বটি বহুশ্রেণী শ্রেণীবিভাগে প্রসারিত করেছেন
- DS মাত্রা: ড্যানিয়েলি এবং শালেভ-শোয়ার্টজ (২০১৪) অসীম লেবেল পরিস্থিতি পরিচালনা করেছেন
- আংশিক ধারণা শ্রেণী: অ্যালন এবং অন্যরা (২০২২) আংশিকভাবে সংজ্ঞায়িত ধারণা শ্রেণী অধ্যয়ন করেছেন
- বহু-আউটপুট শিক্ষা: রামান এবং অন্যরা (২০২৪) বহু-আউটপুট শিক্ষা সমস্যা বৈশিষ্ট্যপূর্ণ করেছেন
- অনলাইন সেট শিক্ষা: রামান এবং অন্যরা (২০২৪) অনলাইন সেটিংয়ে সেট-মূল্যবান প্রতিক্রিয়া অধ্যয়ন করেছেন
এই পত্রটি ব্যাচ সেটিংয়ে ক্ষমাশীল ক্ষতি ফাংশন তত্ত্বের শূন্যস্থান পূরণ করে, বিশেষত পরিচয়ের অবিচ্ছেদ্যতা সন্তুষ্ট না করে এমন ক্ষতি ফাংশন প্রথমবারের মতো সিস্টেমেটিকভাবে পরিচালনা করে।
- সম্পূর্ণ বৈশিষ্ট্যায়ন: সাধারণীকৃত নাতারাজন মাত্রা সম্পূর্ণভাবে ক্ষমাশীল 0-1 ক্ষতি ফাংশনের PAC শিক্ষণযোগ্যতা বৈশিষ্ট্যপূর্ণ করে
- সেট শিক্ষা সমাধান: ব্যাচ সেটিংয়ে সেট শিক্ষার শিক্ষণযোগ্যতা প্রথমবারের মতো সম্পূর্ণভাবে বৈশিষ্ট্যপূর্ণ করা
- তাত্ত্বিক একীকরণ: পরিচয়ের অবিচ্ছেদ্যতা সন্তুষ্ট না করে এমন ক্ষতি ফাংশনের জন্য একটি একীভূত তাত্ত্বিক কাঠামো প্রতিষ্ঠা করা
- প্রতিসাম্য অনুমান: বর্তমান তত্ত্ব প্রতিসাম্য ক্ষতি ফাংশন প্রয়োজন, এই অনুমান অত্যন্ত কঠোর হতে পারে
- সীমিত লেবেল সীমাবদ্ধতা: তত্ত্ব শুধুমাত্র সীমিত লেবেল পরিস্থিতিতে প্রযোজ্য, অসীম লেবেলের সম্প্রসারণ এখনও গবেষণা অপেক্ষা করছে
- শিক্ষা হার: যদিও শিক্ষণযোগ্যতা বৈশিষ্ট্যপূর্ণ করা হয়েছে, শিক্ষা হার কীভাবে ক্ষতি ফাংশনের ক্ষমাশীলতার ডিগ্রির সাথে পরিবর্তিত হয় তা বিশ্লেষণ করা হয়নি
- প্রতিসাম্য অনুমান অপসারণ: অ-প্রতিসাম্য ক্ষতি ফাংশনের শিক্ষণযোগ্যতা অধ্যয়ন করা
- অসীম লেবেল সম্প্রসারণ: DS মাত্রার নাতারাজন মাত্রায় সম্প্রসারণের অনুরূপ
- শিক্ষা হার বিশ্লেষণ: নমুনা জটিলতা কীভাবে ক্ষতি ফাংশনের ক্ষমাশীলতার উপর নির্ভর করে তা অধ্যয়ন করা
- অ্যালগরিদম ডিজাইন: ক্ষমাশীল ক্ষতি ফাংশনের জন্য বিশেষভাবে ডিজাইন করা দক্ষ শিক্ষা অ্যালগরিদম তৈরি করা
- শক্তিশালী তাত্ত্বিক উদ্ভাবন: পরিচয়ের অবিচ্ছেদ্যতা সন্তুষ্ট না করে এমন ক্ষতি ফাংশন প্রথমবারের মতো সিস্টেমেটিকভাবে পরিচালনা করা, গুরুত্বপূর্ণ তাত্ত্বিক শূন্যস্থান পূরণ করা
- গাণিতিক কঠোরতা: সম্পূর্ণ এবং কঠোর প্রমাণ, বিশেষত ভাগফল স্পেস নির্মাণের মাধ্যমে জটিল সমস্যাকে পরিচিত সমস্যায় হ্রাস করার কৌশল অত্যন্ত চতুর
- উচ্চ ব্যবহারিক মূল্য: সেট শিক্ষা ইত্যাদি বাস্তব সমস্যার তাত্ত্বিক ভিত্তি সমাধান করা, গুরুত্বপূর্ণ প্রয়োগ মূল্য রাখা
- স্পষ্ট লেখা: স্পষ্ট কাঠামো, নির্ভুল গাণিতিক অভিব্যক্তি, বোঝা এবং যাচাই করা সহজ
- অনুমানের সীমাবদ্ধতা: প্রতিসাম্য এবং সীমিত লেবেলের অনুমান তত্ত্বের প্রযোজ্যতার পরিসীমা সীমিত করে
- অ্যালগরিদম বিশ্লেষণের অভাব: যদিও ERM এর কার্যকারিতা প্রমাণ করা হয়েছে, নির্দিষ্ট অ্যালগরিদম ডিজাইন এবং অপ্টিমাইজেশনে গভীর বিশ্লেষণ নেই
- পরীক্ষামূলক যাচাইকরণের অভাব: বিশুদ্ধ তাত্ত্বিক কাজ হিসাবে, প্রকৃত ডেটাসেটে যাচাইকরণ এবং প্রয়োগ কেস অভাব
- অসম্পূর্ণ জটিলতা বিশ্লেষণ: নির্দিষ্ট নমুনা জটিলতা সীমা প্রদান করা হয়নি
- বড় তাত্ত্বিক অবদান: শিক্ষা তত্ত্বের জন্য নতুন গবেষণা দিকনির্দেশনা খোলা, পরবর্তী বিস্তৃত গবেষণা উদ্দীপিত করার প্রত্যাশা
- উল্লেখযোগ্য ব্যবহারিক মূল্য: সেট শিক্ষা, বহু-লেবেল শিক্ষা ইত্যাদি বাস্তব সমস্যার তাত্ত্বিক ভিত্তি প্রদান করা
- ভাল পুনরুৎপাদনযোগ্যতা: তাত্ত্বিক ফলাফল সম্পূর্ণভাবে গাণিতিক প্রমাণের উপর ভিত্তি করে, নিখুঁত পুনরুৎপাদনযোগ্যতা রাখে
- শক্তিশালী অনুপ্রেরণা: প্রস্তাবিত প্রযুক্তিগত পদ্ধতি (ভাগফল স্পেস নির্মাণ, সমতুল্য সম্পর্ক ইত্যাদি) অন্যান্য শিক্ষা তত্ত্ব সমস্যায় প্রযোজ্য হতে পারে
- সেট-মূল্যবান পূর্বাভাস: সুপারিশ সিস্টেম, তথ্য পুনরুদ্ধার ইত্যাদি প্রার্থী সেট প্রত্যাবর্তন প্রয়োজন এমন পরিস্থিতি
- বহু-লেবেল শিক্ষা: পাঠ্য শ্রেণীবিভাগ, চিত্র টীকা ইত্যাদি একাধিক সঠিক উত্তর অনুমতি দেয় এমন কাজ
- শক্তিশালী শিক্ষা: লেবেল শব্দের প্রতি সহনশীলতা প্রয়োজন এমন শিক্ষা পরিস্থিতি
- আনুমানিক শিক্ষা: একটি নির্দিষ্ট ডিগ্রি অনুমান অনুমতি দেয় এমন পূর্বাভাস কাজ
পত্রটি শিক্ষা তত্ত্ব ক্ষেত্রের গুরুত্বপূর্ণ সাহিত্য উদ্ধৃত করে, যার মধ্যে রয়েছে:
- ভ্যাপনিক এবং চার্ভোনেনকিস (১৯৭৪): VC তত্ত্বের প্রতিষ্ঠাতা কাজ
- নাতারাজন (১৯৮৯): বহুশ্রেণী শিক্ষা তত্ত্বের গুরুত্বপূর্ণ অবদান
- শালেভ-শোয়ার্টজ এবং বেন-ডেভিড (২০১৪): আধুনিক শিক্ষা তত্ত্ব পাঠ্যপুস্তক
- সাম্প্রতিক সম্পর্কিত কাজ যেমন ড্যানিয়েলি এবং অন্যরা, ব্রুখিম এবং অন্যরা, রামান এবং অন্যরা
সামগ্রিক মূল্যায়ন: এটি শিক্ষা তত্ত্ব ক্ষেত্রে একটি উচ্চ-মানের তাত্ত্বিক পত্র যা গুরুত্বপূর্ণ অবদান রাখে। যদিও কিছু অনুমান সীমাবদ্ধতা রয়েছে, এটি নতুন গবেষণা দিকনির্দেশনা খোলে এবং গুরুত্বপূর্ণ তাত্ত্বিক মূল্য এবং ব্যবহারিক তাৎপর্য রাখে।