Sequential minimal optimization
সিকোয়েন্সিয়াল মিনিমাল অপ্টিমাইজেশন (এস. এম. ও) হল সাপোর্ট-ভেক্টর মেশিনের (এস. ভি. এম) প্রশিক্ষণের সময় উদ্ভূত চতুর্ভুজ প্রোগ্রামিং (কিউ. পি) সমস্যা সমাধানের জন্য একটি অ্যালগরিদম। এটি 1998 সালে মাইক্রোসফ্ট রিসার্চের জন প্লাট দ্বারা উদ্ভাবিত হয়েছিল। এস. এম. ও ব্যাপকভাবে সাপোর্ট ভেক্টর মেশিনের প্রশিক্ষণের জন্য ব্যবহৃত হয় এবং জনপ্রিয় এল. আই. বি. এস. ভি. এম টুল দ্বারা প্রয়োগ করা হয়। 1998 সালে এস. এম. ও অ্যালগরিদমের প্রকাশনা এস. ভি. এম সম্প্রদায়ের মধ্যে প্রচুর উত্তেজনা সৃষ্টি করেছে, কারণ এস. ভি. এম প্রশিক্ষণের জন্য পূর্বে উপলব্ধ পদ্ধতিগুলি অনেক বেশি জটিল ছিল এবং ব্যয়বহুল তৃতীয় পক্ষের কিউ. পি সমাধানকারীগুলির প্রয়োজন ছিল। অপ্টিমাইজেশান সমস্যা একটি ডেটাসেট (x1, y1),., (xn, yn) সহ একটি বাইনারি শ্রেণীবিভাগ সমস্যা বিবেচনা করুন, যেখানে xi একটি ইনপুট ভেক্টর এবং এটির সাথে সম্পর্কিত একটি বাইনারি লেবেল। একটি সফ্ট-মার্জিন সাপোর্ট ভেক্টর মেশিনকে একটি চতুর্ভুজ প্রোগ্রামিং সমস্যা সমাধান করে প্রশিক্ষণ দেওয়া হয়, যা নিম্নরূপ দ্বৈত আকারে প্রকাশ করা হয়ঃ বিষয়ঃ যেখানে সি একটি এসভিএম হাইপারপ্যারামিটার এবং কে (xi, xj) কার্নেল ফাংশন, উভয়ই ব্যবহারকারীর দ্বারা সরবরাহ করা হয়; এবং ভেরিয়েবলগুলি ল্যাগ্রেঞ্জ মাল্টিপ্লায়ার। অ্যালগরিদম এস. এম. ও হল উপরে বর্ণিত অপ্টিমাইজেশান সমস্যা সমাধানের জন্য একটি পুনরাবৃত্তিমূলক অ্যালগরিদম। এস. এম. ও এই সমস্যাটিকে ক্ষুদ্রতম সম্ভাব্য উপ-সমস্যাগুলির একটি সিরিজে বিভক্ত করে, যা পরে বিশ্লেষণাত্মকভাবে সমাধান করা হয়। ল্যাগ্রাঞ্জ মাল্টিপ্লায়ার জড়িত রৈখিক সমতা সীমাবদ্ধতার কারণে, সম্ভাব্য ক্ষুদ্রতম সমস্যাটি এই ধরনের দুটি মাল্টিপ্লায়ার জড়িত। তারপরে, যে কোনও দুটি গুণকের জন্য এবং, সীমাবদ্ধতাগুলি হ্রাস করা হয়ঃ এবং এই হ্রাসকৃত সমস্যাটি বিশ্লেষণাত্মকভাবে সমাধান করা যেতে পারেঃ একজনকে ন্যূনতম এক-মাত্রিক দ্বিঘাত ফাংশন খুঁজে বের করতে হবে। সমতা সীমাবদ্ধতার বাকি পদগুলির উপর যোগফলের ঋণাত্মক, যা প্রতিটি পুনরাবৃত্তিতে স্থির করা হয়। অ্যালগরিদমটি নিম্নরূপঃ একটি ল্যাগ্রাঞ্জ গুণক খুঁজে বের করুন যা অপ্টিমাইজেশান সমস্যার জন্য কারুশ-কুন-টাকার (কেকেটি) শর্ত লঙ্ঘন করে। একটি দ্বিতীয় গুণক বেছে নিন এবং জোড়াটিকে অনুকূল করুন। একত্রীকরণ না হওয়া পর্যন্ত 1 এবং 2 ধাপ পুনরাবৃত্তি করুন। যখন সমস্ত ল্যাগ্রাঞ্জ মাল্টিপ্লায়ার কেকেটি শর্ত পূরণ করে (ব্যবহারকারী-সংজ্ঞায়িত সহনশীলতার মধ্যে), তখন সমস্যাটি সমাধান করা হয়েছে। যদিও এই অ্যালগরিদমটি একত্রিত হওয়ার নিশ্চয়তা দেয়, তবে সংশ্লেষের হারকে ত্বরান্বিত করার জন্য গুণকের জোড়া বেছে নেওয়ার জন্য হিউরিস্টিক্স ব্যবহার করা হয়। এটি বড় ডেটা সেটের জন্য গুরুত্বপূর্ণ কারণ এবং এর জন্য সম্ভাব্য পছন্দ রয়েছে। সম্পর্কিত কাজ বড় এসভিএম শেখার সমস্যাগুলিকে ছোট অপ্টিমাইজেশান কাজের একটি সিরিজে বিভক্ত করার প্রথম পদ্ধতিটি বার্নহার্ড বোসার, ইসাবেল গায়োন, ভ্লাদিমির ভাপনিক দ্বারা প্রস্তাবিত হয়েছিল। এটি "চাঙ্কিং অ্যালগরিদম" নামে পরিচিত। অ্যালগরিদমটি তথ্যের একটি এলোমেলো উপসেট দিয়ে শুরু হয়, এই সমস্যার সমাধান করে এবং পুনরাবৃত্তিমূলকভাবে এমন উদাহরণ যোগ করে যা অনুকূলতার শর্ত লঙ্ঘন করে। এই অ্যালগরিদমের একটি অসুবিধা হ 'ল এসভি-র সংখ্যা সহ কিউপি-সমস্যা স্কেলিং সমাধান করা প্রয়োজন। বাস্তব বিশ্বের বিরল ডেটা সেটগুলিতে, এস. এম. ও চাঙ্কিং অ্যালগরিদমের চেয়ে 1000 গুণ বেশি দ্রুত হতে পারে। 1997 সালে, ই. ওসুনা, আর. ফ্রুন্ড এবং এফ. গিরসি একটি উপপাদ্য প্রমাণ করেন যা এসভিএম-এর জন্য কিউপি অ্যালগরিদমের একটি সম্পূর্ণ নতুন সেটের পরামর্শ দেয়। এই উপপাদ্য অনুসারে একটি বড় কিউপি সমস্যাকে ছোট ছোট কিউপি উপ-সমস্যাগুলির একটি সিরিজে বিভক্ত করা যেতে পারে। কিউপি উপ-সমস্যাগুলির একটি ক্রম যা সর্বদা কারুশ-কুন-টাকার (কেকেটি) শর্তগুলির কমপক্ষে একজন লঙ্ঘনকারীকে একত্রিত করার নিশ্চয়তা দেয়। চাংকিং অ্যালগরিদম উপপাদ্যের শর্তগুলি মেনে চলে এবং তাই একত্রিত হবে। এস. এম. ও অ্যালগরিদমকে ওসুনা অ্যালগরিদমের একটি বিশেষ কেস হিসাবে বিবেচনা করা যেতে পারে, যেখানে অপ্টিমাইজেশনের আকার দুটি এবং উভয় ল্যাগ্রাঞ্জ মাল্টিপ্লায়ার প্রতিটি ধাপে নতুন মাল্টিপ্লায়ার দিয়ে প্রতিস্থাপিত হয় যা ভাল হিউরিস্টিক্সের মাধ্যমে বেছে নেওয়া হয়। এস. এম. ও অ্যালগরিদমটি ব্রেগম্যান পদ্ধতি বা রো-অ্যাকশন পদ্ধতি নামে পরিচিত অপ্টিমাইজেশন অ্যালগরিদমের একটি পরিবারের সাথে ঘনিষ্ঠভাবে সম্পর্কিত। এই পদ্ধতিগুলি রৈখিক সীমাবদ্ধতার সাথে উত্তল প্রোগ্রামিং সমস্যাগুলি সমাধান করে। এগুলি পুনরাবৃত্তিমূলক পদ্ধতি যেখানে প্রতিটি ধাপ প্রতিটি সীমাবদ্ধতার উপর বর্তমান প্রাথমিক বিন্দুটিকে প্রজেক্ট করে। আরও দেখুন কার্নেল পারসেপ্ট্রন রেফারেন্স অপ্টিমাইজেশন অ্যালগরিদম এবং পদ্ধতি সাপোর্ট ভেক্টর মেশিন