ডিরিচলেট প্রক্রিয়া মিশ্রণ মডেল

• জুন 23, 2014
• ভ্যাসিলিস ভ্রাইনিওটিস
• . 2 মন্তব্য

এই ব্লগ পোস্টটি সিরিজের চতুর্থ অংশ Dirichlet প্রক্রিয়া মিশ্রণ মডেল সঙ্গে ক্লাস্টারিং. পূর্ববর্তী নিবন্ধগুলিতে আমরা সীমাবদ্ধ ডিরিচলেট মিশ্রণের মডেলগুলি নিয়ে আলোচনা করেছি এবং আমরা অসীম কে ক্লাস্টারগুলির জন্য তাদের মডেলের সীমা নিয়েছি যা আমাদের ডিরিচলেট প্রক্রিয়াগুলির প্রবর্তনের দিকে নিয়ে গিয়েছিল। আমরা যেমন দেখেছি, আমাদের লক্ষ্য হল একটি মিশ্রণ মডেল তৈরি করা যার জন্য আমাদের শুরু থেকে k ক্লাস্টার/কম্পোনেন্টের সংখ্যা নির্দিষ্ট করার প্রয়োজন নেই। পরে ডিরিচলেট প্রক্রিয়াগুলির বিভিন্ন উপস্থাপনা উপস্থাপন করা, এখন সময় এসেছে প্রকৃতপক্ষে একটি অসীম মিশ্রণ মডেল তৈরি করতে ডিপি ব্যবহার করার যা আমাদের ক্লাস্টারিং সম্পাদন করতে সক্ষম করে। এই নিবন্ধটির লক্ষ্য হল ডিরিচলেট প্রক্রিয়া মিশ্রণের মডেলগুলিকে সংজ্ঞায়িত করা এবং চাইনিজ রেস্তোরাঁ প্রক্রিয়া এবং গিবস স্যাম্পলিং এর ব্যবহার নিয়ে আলোচনা করা। আপনি যদি আগের পোস্টগুলি না পড়ে থাকেন তবে এটি করার জন্য এটি অত্যন্ত সুপারিশ করা হচ্ছে কারণ বিষয়টি কিছুটা তাত্ত্বিক এবং মডেলটির নির্মাণ সম্পর্কে ভাল বোঝার প্রয়োজন।

আপডেট: Datumbox মেশিন লার্নিং ফ্রেমওয়ার্ক এখন ওপেন সোর্স এবং বিনামূল্যে ডাউনলোড. জাভাতে ডিরিচলেট প্রসেস মিক্সচার মডেলের বাস্তবায়ন দেখতে com.datumbox.framework.machinelearning.clustering প্যাকেজটি দেখুন।

1. ডিরিচলেট প্রক্রিয়া মিশ্রণ মডেলের সংজ্ঞা

ডিরিচলেট প্রসেস ব্যবহার করে আমাদেরকে অসীম উপাদান সহ একটি মিশ্রণের মডেল থাকতে দেয় যা k থেকে অসীম পর্যন্ত সসীম মডেলের সীমা গ্রহণ বলে মনে করা যেতে পারে। আসুন আমরা অনুমান করি যে আমাদের নিম্নলিখিত মডেল রয়েছে:

সমীকরণ 1: ডিরিচলেট প্রক্রিয়া মিশ্রণ মডেল

যেখানে G হিসাবে সংজ্ঞায়িত করা হয়েছে এবং জন্য একটি সংক্ষিপ্ত স্বরলিপি হিসাবে ব্যবহৃত যা একটি ডেল্টা ফাংশন যা 1 যদি নেয় এবং অন্য কোথাও 0। θ_i হল ক্লাস্টার প্যারামিটার যা G থেকে নমুনা করা হয়েছে। জেনারেটিভ ডিস্ট্রিবিউশন F ক্লাস্টার প্যারামিটার θ দ্বারা কনফিগার করা হয়েছে_i এবং x তৈরি করতে ব্যবহৃত হয়_i পর্যবেক্ষণ অবশেষে আমরা একটি ঘনত্ব বন্টন সংজ্ঞায়িত করতে পারি যা আমাদের মিশ্রণ বন্টন (গণনাযোগ্য অসীম মিশ্রণ) মিশ্রণ অনুপাতের সাথে এবং মিশ্রণ উপাদান .

চিত্র 1: ডিরিচলেট প্রক্রিয়া মিশ্রণ মডেলের গ্রাফিক্যাল মডেল

উপরে আমরা DPMM এর সমতুল্য গ্রাফিক্যাল মডেল দেখতে পাচ্ছি। জি₀ DP এর বেস ডিস্ট্রিবিউশন এবং এটিকে সাধারণত আমাদের জেনারেটিভ ডিস্ট্রিবিউশন F এর আগে সংযোজিত হওয়ার জন্য নির্বাচন করা হয় যাতে কম্পিউটেশন সহজ করা যায় এবং আকর্ষণীয় গাণিতিক বৈশিষ্ট্য ব্যবহার করা যায়। α হল ডিরিচলেট প্রক্রিয়ার স্কেলার হাইপারপ্যারামিটার এবং আমরা যে ক্লাস্টারগুলি পাব তা প্রভাবিত করে। α এর মান যত বড়, ক্লাস্টার তত বেশি; যত ছোট α তত কম ক্লাস্টার। আমাদের লক্ষ্য করা উচিত যে α এর মান প্রকাশ করে বিশ্বাসের শক্তি জি তে₀. একটি বড় মান নির্দেশ করে যে বেশিরভাগ নমুনা স্বতন্ত্র হবে এবং মানগুলি G-তে কেন্দ্রীভূত হবে₀. G হল Θ প্যারামিটার স্পেসের উপর একটি র্যান্ডম ডিস্ট্রিবিউশন যা DP থেকে নমুনা করা হয় যা প্যারামিটারগুলিতে সম্ভাব্যতা নির্ধারণ করে। θ_i একটি প্যারামিটার ভেক্টর যা G বিতরণ থেকে আঁকা হয় এবং ক্লাস্টারের পরামিতি ধারণ করে, F বন্টন θ দ্বারা প্যারামিটারাইজ করা হয়_i এবং এক্স_i জেনারেটিভ ডিস্ট্রিবিউশন F দ্বারা উত্পন্ন ডেটা পয়েন্ট।

এটি লক্ষ্য করা গুরুত্বপূর্ণ যে θ_i Θ প্যারামিটার স্পেসের উপাদান এবং তারা আমাদের ক্লাস্টারকে "কনফিগার" করে। এগুলিকে x-এর সুপ্ত ভেরিয়েবল হিসাবেও দেখা যেতে পারে_i যা আমাদের বলে যে কোন উপাদান/গুচ্ছ x থেকে_i থেকে আসে এবং এই উপাদানের পরামিতি কি. এইভাবে প্রতিটি x জন্য_i যে আমরা পর্যবেক্ষণ করি, আমরা একটি θ আঁকি_i জি বিতরণ থেকে। প্রতি ড্রয়ের সাথে পূর্ববর্তী নির্বাচনের উপর নির্ভর করে বিতরণ পরিবর্তন হয়। যেমনটি আমরা ব্ল্যাকওয়েল-ম্যাককুইন urn স্কিমে দেখেছি G বিতরণকে একীভূত করা যেতে পারে এবং আমাদের ভবিষ্যতের নির্বাচনগুলি θ_i শুধুমাত্র জি এর উপর নির্ভর করে₀: . পূর্ববর্তী সূত্র থেকে পরামিতি θi অনুমান করা সবসময় সম্ভব নয় কারণ অনেক বাস্তবায়ন (যেমন চাইনিজ রেস্তোরাঁ প্রক্রিয়া) এর মাধ্যমে গণনা করা জড়িত। দ্রুতগতিতে k উপাদান বৃদ্ধি. এইভাবে আনুমানিক গণনা পদ্ধতি ব্যবহার করা হয় যেমন গিবস স্যাম্পলিং। অবশেষে আমাদের লক্ষ্য করা উচিত যে k ক্লাস্টার অসীম হলেও সক্রিয় ক্লাস্টারের সংখ্যা হল . এইভাবে θ_i পুনরাবৃত্তি করবে এবং একটি ক্লাস্টারিং প্রভাব প্রদর্শন করবে।

2. একটি অসীম মিশ্রণ মডেল সংজ্ঞায়িত করতে চাইনিজ রেস্টুরেন্ট প্রক্রিয়া ব্যবহার করা

পূর্ববর্তী বিভাগে সংজ্ঞায়িত মডেলটি গাণিতিকভাবে কঠিন, তবুও এটির একটি বড় ত্রুটি রয়েছে: প্রতিটি নতুন x এর জন্য_i যে আমরা পর্যবেক্ষণ করি, আমাদের অবশ্যই একটি নতুন θ নমুনা করতে হবে_i θ এর পূর্ববর্তী মানগুলিকে বিবেচনায় নিয়ে। সমস্যা হল যে অনেক ক্ষেত্রে, এই পরামিতিগুলির নমুনা করা একটি কঠিন এবং গণনাগতভাবে ব্যয়বহুল কাজ হতে পারে।

একটি বিকল্প পদ্ধতি হল সুপ্ত ভেরিয়েবল z মডেল করতে চাইনিজ রেস্টুরেন্ট প্রক্রিয়া ব্যবহার করা_i ক্লাস্টার অ্যাসাইনমেন্টের। এইভাবে θ ব্যবহার করার পরিবর্তে_i ক্লাস্টার প্যারামিটার এবং ক্লাস্টার অ্যাসাইনমেন্ট উভয়ই বোঝাতে, আমরা সুপ্ত পরিবর্তনশীল z ব্যবহার করি_i ক্লাস্টার আইডি নির্দেশ করতে এবং তারপর ক্লাস্টার পরামিতি নির্ধারণ করতে এই মানটি ব্যবহার করুন। ফলস্বরূপ, প্রতিবার যখন আমরা একটি নতুন পর্যবেক্ষণ পাই তখন আমাদের আর একটি θ নমুনা দেওয়ার দরকার নেই, বরং আমরা z নমুনা করে ক্লাস্টার অ্যাসাইনমেন্ট পাই।_i সিআরপি থেকে। এই স্কিমের সাথে একটি নতুন θ নমুনা করা হয় শুধুমাত্র যখন আমাদের একটি নতুন ক্লাস্টার তৈরি করতে হবে। নীচে আমরা এই পদ্ধতির মডেল উপস্থাপন করছি:

সমীকরণ 2: CRP-এর সাথে মিশ্রণের মডেল

উপরেরটি একটি জেনারেটিভ মডেল যা বর্ণনা করে কিভাবে ডেটা এক্স_i এবং ক্লাস্টার তৈরি হয়। ক্লাস্টার বিশ্লেষণ সঞ্চালনের জন্য আমাদের অবশ্যই x পর্যবেক্ষণগুলি ব্যবহার করতে হবে_i এবং ক্লাস্টার অ্যাসাইনমেন্ট z অনুমান করুন_i.

3. মিশ্রণ মডেল ইনফারেন্স এবং গিবস স্যাম্পলিং

দুর্ভাগ্যবশত যেহেতু ডিরিচলেট প্রসেসগুলি অ-প্যারামেট্রিক, আমরা EM অ্যালগরিদম ব্যবহার করতে পারবেন না ক্লাস্টার অ্যাসাইনমেন্টগুলি সংরক্ষণ করে এমন সুপ্ত ভেরিয়েবলগুলি অনুমান করতে। অ্যাসাইনমেন্ট অনুমান করার জন্য আমরা ব্যবহার করব সংকুচিত গিবস স্যাম্পলিং.

কোল্যাপসড গিবস স্যাম্পলিং হল একটি সাধারণ মার্কভ চেইন মন্টে কার্লো (MCMC) অ্যালগরিদম। এটি দ্রুত এবং অন্য ভেরিয়েবলের নমুনা নেওয়ার সময় আমাদের কিছু ভেরিয়েবলকে একীভূত করতে সক্ষম করে। তবুও এই অ্যালগরিদমের জন্য আমাদের একটি জি নির্বাচন করতে হবে₀ যা বিশ্লেষণাত্মক সমীকরণগুলি সমাধান করতে সক্ষম হওয়ার জন্য এবং সরাসরি থেকে নমুনা নিতে সক্ষম হওয়ার জন্য F জেনারেটিভ ডিস্ট্রিবিউশনের পূর্ববর্তী একটি সংযোজন .

ক্লাস্টার অ্যাসাইনমেন্টের অনুমান করার জন্য আমরা যেগুলি ব্যবহার করব তা সংকুচিত গিবস স্যাম্পলিং-এর ধাপগুলি হল:

• z আরম্ভ করুন_i এলোমেলোভাবে ক্লাস্টার অ্যাসাইনমেন্ট
• একত্রিত হওয়া পর্যন্ত পুনরাবৃত্তি করুন
• এলোমেলোভাবে কুঠার নির্বাচন করুন_i
  
• অন্য z রাখুন_j প্রতিটি j≠i এর জন্য স্থির:
• z-এ একটি নতুন মান বরাদ্দ করুন_i "CRP সম্ভাব্যতা" গণনা করে যা z এর উপর নির্ভর করে_j এবং এক্স_j সমস্ত j≠i:

পরবর্তী প্রবন্ধে আমরা ডিরিচলেট প্রসেস মিক্সচার মডেল ব্যবহার করে ক্লাস্টার বিশ্লেষণ কীভাবে করতে হয় তার উপর ফোকাস করব। ক্রমাগত ডেটাসেট এবং নথিতে ক্লাস্টারিং সঞ্চালনের জন্য আমরা দুটি ভিন্ন ডিরিচলেট প্রসেস মিশ্রণ মডেলকে সংজ্ঞায়িত করব যা চাইনিজ রেস্তোরাঁ প্রক্রিয়া এবং সংকুচিত গিবস স্যাম্পলিং ব্যবহার করে।