قضیه جوجه‌اردک زشت

قضیه جوجه‌اردک زشت یک استدلال است که نشان می دهد طبقه بندی بدون جهت گیری غیرممکن است. به طور دقیق‌تر این قضیه تعداد محدودی از ویژگی‌ها را در نظر می‌گیرد که با اتصالات منطفی با هم ترکیب می‌شوند و ادعا می‌کند که هر دو شی متفاوت تعداد برابری از ویژگی‌‌های مشابه دارند.

این قضیه با الهام از داستان «جوجه‌اردک زشت» از هانس کریستیان آندرسن از سال۱۸۴۳ میلادی نام گذاری شده است زیرا ادعا می‌کند که یک جوجه‌اردک به همان اندازه‌ای شبیه یک قو است که دو قو شبیه به یک دیگر هستند.این قضیه توسط ساتوشی واتانابه در سال 1969 میلادی به‌دست‌آمد.

در این مثال S بیانگر لبخند زدن و G بیانگر داشتن عینک است.مشخص می شود که بین این سه نفر در واقع جوجه اردک زشتی وجود ندارد زیرا در همه ویژگی ها به یک اندازه متمایز و به یک اندازه شبیه به هم هستند.

فرمول بندی ریاضی

فرض کنیم که n شی در جهان وجود داشته باشد.حال اگر یک شخص می‌خواهد این اشیا را دسته بندی کند بدون اینکه هیچ گونه سوگیری یا حسی در مورد اینکه چه دسته بندی طبیعی است داشته باشد.برای این کار شخص تمام دسته بندی های ممکن این اشیا را بررسی می‌کند.تمام حالات زیرمجموعه گیری از این n شی برابر است با اندازه زیرمجموعه توانی این n شی که برابر است با $2^{n}$.حال شخص می‌تواند بررسی‌کند که دو شی چند زیرمجموعه مشترک دارند تا میزان شباهت آن‌ها را مشخص‌کند.اما شخص به نتیجه ای نمی‌رسد زیرا هر دو شی دقیقا به یک اندازه در زیرمجوعه ها ظاهر شده‌اند.به طور دقیق تر این اشیا در $2^{n-1}$ دسته (نصف تعداد کل دسته ها )دقیقا مشاهده شده‌اند.

برای اینکه شخص این موضوع را متوجه شود می تواند هر دسته را به شکل یک رشته در نظر بگیرد که برای هر شی که در این دسته نیست 0 و برای هر شی که در این دسته وجود دارد 1 در جایگاه آن درج شده است.مشخص است که $2^{n}$ رشته در کل وجود دارد.

هر دو بیت دقیقا در نیمی از کل حالات با هم مطابقت دارند.شخص ممکن است که دو شی را انتخاب کند و بیت های رشته را دوباره مرتب کند تا این دو بیت در ابتدا قرار بگیرند.همچنین فرض می کند که اعداد به ترتیب الفبایی مرتب شده اند.

$2^{n}/2$ عدد اول بیت اولشان 0 و $2^{n}/2$ عدد دوم بیت اولشان 1 است.بین آن ها نیز $2^{n}/4$ عدد اول بیت اولشان 0 و $2^{n}/4$ عدد دوم بیت اولشان 1 است.پس صرف نظر ازین که شخص کدام دو شی را انتخاب کند همیشه در نصف دسته ها باهم مطابقت دارند.

در نتیجه اگر ما سوگیری نداشته باشیم که کدام دسته‌ها بهتر اند، همه اشیا به یک اندازه بهم شبیه خواهند بود(یا به یک اندازه متفاوت خواهند بود).به بیان دیگر تعداد ویژگی هایی که به شکل همزمان دو شی غیر یکسان را در بر دارد برای همه زوج شی ها یکسان است.

در نتیجه یک سوگیری القایی نیاز است تا بعضی دسته ها را به دیگر دسته ها ترجیح داده شوند.

توابع بولی

فرض کنید که $x_{1},x_{2},..,x_{n}$ یک مجموعه از بردار هایی باشند که هر یک k عنصر بولی دارند. جوجه‌اردک زشت در این مثال برداری است که کم‌ترین شباهت را با بقیه دارد.برای یافتن این بردار می توان از محاسبه فاصله همینگ استفاده کر.

هرچند انتخاب اینکه چه ویژگی های بولی در نظر گرفته شود می تواند دلخواه باشد اما ممکن است که ویژگی هایی مشتق شده از ویژگی‌های اصلی وجود داشته باشند که برای یافتن جوجه‌اردک زشت مهم باشند.

مجموعه بولی های بردار می توانند با ویژگی های جدیدی که از طریق توابع بولی بر حسب k ویژگی اصلی تولید می شوند، گسترش پیدا کنند.تنها راه متعارفی که وجود دارد این است که گسترش بر اساس تمام توابع بولی ممکن انجام شود.بردار های حاصل شده $2^{k}$ ویژگی خواهند داشت. قضیه جوجه‌اردک زشت بیان می کند که هیچ جوجه‌اردک زشتی بین این بردار ها یافت نمی‌شود زیرا هر دو بردار کامل شده ای دقیقا در نصف ویژگی ها یکسان یا متفاوت خواهد بود.

بحث

یک راه حل برای قضیه جوجه‌اردک زشت این است که یک قید تعیین کنیم که نشان دهد چگونه شباهت اندازه‌گیری شود.برای این کار مجموعه مشخصاتی که در دسته بندی دخالت داده می شوند را محدود می‌کنیم.هرچند نشان داده شده است که این راه حل مشکل سوگیری را حل نمی‌کند زیرا اینکه دو شی از چه جنبه ای مشابه اند برحسب زمینه و وظیفه متفاوت است به طوری که هیچ پاسخ منحصر به فردی برای این سوال وجود ندارد.برای مثال اگر اهمیت را روی ویژگی «راه راه بودن» بگذاریم یک آرایشگر(با لباس ها معمولا راه راه) و یک گورخر به هم شبیه تر از یک اسب و یک گورخر خواهند بود.هرچند اگر وزن دهی ویژگی ها را ثابت کنیم این یک مقایسه مقید خواهد بود اما این ادعا که طبقه بندی بر اساس تطابق ویژگی است تقریبا بی معناست.