গবেষকরা অনলাইন অ্যালগরিদম সম্পর্কে একটি বিস্তৃত বিশ্বাসকে খণ্ডন করেন | কোয়ান্টা ম্যাগাজিন

জীবনে, কখনও কখনও আমাদের ইচ্ছাকৃত সমস্ত তথ্য ছাড়াই সিদ্ধান্ত নিতে হয়; কম্পিউটার বিজ্ঞানেও এটা সত্য। এটি অনলাইন অ্যালগরিদমগুলির ক্ষেত্র — যেগুলি, তাদের নাম থাকা সত্ত্বেও, অগত্যা ইন্টারনেট জড়িত নয়৷ পরিবর্তে, এগুলি সমস্যা সমাধানের কৌশল যা ডেটা আসার সাথে সাথে প্রতিক্রিয়া জানায়, পরবর্তীতে কী হতে পারে সে সম্পর্কে কোনও জ্ঞান ছাড়াই। অনিশ্চয়তার সাথে মোকাবিলা করার ক্ষমতা এই অ্যালগরিদমগুলিকে বাস্তব-বিশ্বের সমস্যাগুলির জন্য উপযোগী করে তোলে, যেমন ল্যাপটপে মেমরি পরিচালনা করা বা যারা ওয়েব ব্রাউজ করেন তাদের কাছে কোন বিজ্ঞাপনগুলি প্রদর্শন করতে হবে তা বেছে নেওয়া।

গবেষকরা তাদের মোকাবেলা করার জন্য নতুন পদ্ধতিগুলি তদন্ত করতে এই সমস্যাগুলির সাধারণ সংস্করণগুলি অধ্যয়ন করেন। এর মধ্যে সবচেয়ে বিখ্যাত হল "k-সার্ভার সমস্যা," যা একের পর এক আগত অনুরোধগুলি পূরণ করার জন্য এজেন্টদের বহর প্রেরণের কাঁটাযুক্ত কাজকে বর্ণনা করে। তারা মেরামত প্রযুক্তিবিদ বা অগ্নিনির্বাপক বা এমনকি ঘোরাঘুরি আইসক্রিম বিক্রয়কর্মী হতে পারে।

"এই সমস্যাটি সংজ্ঞায়িত করা সত্যিই সহজ," বলেন মার্সিন বিয়াঙ্কোস্কি, পোল্যান্ডের ইউনিভার্সিটি অফ রকলো-এর একজন অ্যালগরিদম গবেষক। কিন্তু এটি "অদ্ভুতভাবে কঠিন হতে দেখা যাচ্ছে।" যেহেতু গবেষকরা আক্রমণ শুরু করেছেন k-সার্ভার সমস্যা 1980 এর দশকের শেষের দিকে, তারা বিস্মিত হয়েছে ঠিক কতটা ভাল অনলাইন অ্যালগরিদম কাজটি পরিচালনা করতে পারে।

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

"আমি এটা বলতে পেরে খুশি যে এটি আমার কাছে একটি বড় বিস্ময় ছিল," বলেছেন অনুপম গুপ্ত, যিনি কার্নেগি মেলন ইউনিভার্সিটিতে অ্যালগরিদম অধ্যয়ন করেন এবং কাগজে জড়িত ছিলেন না। কাজটি "এই এলাকার কেন্দ্রীয় সমস্যা সম্পর্কে গভীর অন্তর্দৃষ্টি" প্রদান করে।

প্রথমে কম্পিউটার বিজ্ঞানী ড এই সমস্যার রূপরেখা দিয়েছেন 1988 সালে। এটা বোঝার জন্য, আসুন এমন একটি কোম্পানির কল্পনা করি যেটি plumbers নিয়োগ দেয়। কল আসার সাথে সাথে কোম্পানিকে সিদ্ধান্ত নিতে হবে কোন প্লাম্বার কোন স্থানে যাবে। কোম্পানির লক্ষ্য — এবং একটি অ্যালগরিদমের লক্ষ্য k-সার্ভার সমস্যা - সমস্ত প্লাম্বারদের দ্বারা ভ্রমণ করা মোট দূরত্ব হ্রাস করা।

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

তবে গবেষকরা যতটা সম্ভব কাছাকাছি যেতে চান। তারা প্রতিটি কৌশলে ভ্রমণের দূরত্বের তুলনা করে, প্রতিযোগিতামূলক অনুপাত হিসাবে যা পরিচিত তা গণনা করে একটি অনলাইন অ্যালগরিদমের কর্মক্ষমতা পরিমাপ করে। অ্যালগরিদম ডিজাইনাররা অনলাইন কৌশলগুলি তৈরি করার চেষ্টা করে যা অফলাইন আদর্শের কাছে যায়, এই অনুপাতটি 1-এর দিকে নামিয়ে দেয়।

আসুন কল্পনা করুন আমাদের প্লাম্বিং কোম্পানির মাত্র দুটি প্লাম্বর রয়েছে এবং এটি শুধুমাত্র একটি একক, দীর্ঘ রাস্তায় পরিবেশন করে। কল আসে একে একে। একটি যুক্তিসঙ্গত প্রথম পন্থা, যা লোভী অ্যালগরিদম নামে পরিচিত, প্রতিটি ইনকামিং কলের অবস্থানের কাছাকাছি যেটি প্লাম্বারকে প্রেরণ করা হবে। কিন্তু এখানে একটি দৃশ্যকল্প যেখানে এই অ্যালগরিদম লড়াই করছে: কল্পনা করুন যে একটি প্লাম্বার রাস্তার পশ্চিম প্রান্তে শুরু হয় এবং অন্যটি পূর্ব প্রান্তে, এবং সমস্ত কল পশ্চিম প্রান্তে দুটি প্রতিবেশী বাড়ি থেকে আসে৷ সেক্ষেত্রে, একজন প্লাম্বার কখনই নড়াচড়া করে না যখন অন্যজন সেই দুটি বাড়িতে মাইল পর্যন্ত র‌্যাক করে। পশ্চাদপসরণে, সর্বোত্তম কৌশলটি হ'ল উভয় প্লাম্বারকে সমস্যা-প্রবণ এলাকায় স্থানান্তরিত করা - কিন্তু, হায়, এটি কোথায় হতে চলেছে তা আপনি জানতে পারতেন না।

তবুও, Bieńkowski বলেছেন, লোভী অ্যালগরিদমের চেয়ে ভালো করা সম্ভব। দ্য "ডবল কভারেজ” অ্যালগরিদম উভয় প্লাম্বারকে একই হারে তাদের মধ্যে আসা যেকোনো কলের দিকে নিয়ে যায়, যতক্ষণ না তাদের মধ্যে একজন সেখানে পৌঁছায়। এই পদ্ধতিটি লোভী অ্যালগরিদমের তুলনায় কম প্রতিযোগিতামূলক অনুপাত অর্জন করে।

যদিও এই বিমূর্ত সমস্যা বাস্তব নদীর গভীরতানির্ণয় কোম্পানির জন্য প্রাসঙ্গিক নয়, “The k-সার্ভার সমস্যা নিজেই সত্যিই সংজ্ঞায়িত প্রশ্ন "অনলাইন কম্পিউটিং, বলেন যুবল রবানী, জেরুজালেমের হিব্রু বিশ্ববিদ্যালয়ের একজন কম্পিউটার বিজ্ঞানী যিনি সাম্প্রতিক গবেষণাপত্রটির সহ-লেখক। আংশিকভাবে, এর কারণ হল কাজের সময় বিকশিত সরঞ্জাম এবং কৌশল k-সার্ভার সমস্যা প্রায়ই অনলাইন অ্যালগরিদম অধ্যয়ন অন্য কোথাও অ্যাপ্লিকেশন খুঁজে পেতে, এমনকি এটি বাইরেও.

"এটি অ্যালগরিদমগুলিতে কাজ করার জাদুটির অংশ," তিনি বলেছিলেন।

যখন তারা এই সমস্যাগুলি অধ্যয়ন করে, বিজ্ঞানীরা তাদের প্রতিপক্ষের বিরুদ্ধে গেম হিসাবে কল্পনা করতে পছন্দ করেন। প্রতিপক্ষ তার অফলাইন প্রতিপক্ষের তুলনায় অনলাইন অ্যালগরিদম যতটা সম্ভব খারাপভাবে পারফর্ম করার জন্য অনুরোধের একটি শয়তান ক্রম বেছে নেয়। এর কিছু ক্ষমতা প্রতিপক্ষকে ছিনতাই করতে, গবেষকরা অ্যালগরিদম ব্যবহার করে যা অন্তর্ভুক্ত করে এলোমেলো সিদ্ধান্ত.

এই কৌশলটি বেশ কার্যকর, এবং গবেষকরা 1990-এর দশকের গোড়ার দিকে থেকে সন্দেহ করেছেন যে আপনি সর্বদা একটি এলোমেলো অ্যালগরিদম খুঁজে পেতে পারেন যা একটি নির্দিষ্ট কর্মক্ষমতা লক্ষ্যে পৌঁছায়: লগের সমানুপাতিক একটি প্রতিযোগিতামূলক অনুপাত। k, কোথায় k এজেন্ট সংখ্যা. একে এলোমেলো বলা হয় k-সার্ভার অনুমান, এবং গবেষকরা দেখিয়েছেন যে এটি কিছু স্থানের জন্য সত্য, বা পয়েন্টের নির্দিষ্ট সংগ্রহের জন্য (বাড়ির সমতুল্য যা প্লাম্বার কল করতে পারে)। কিন্তু সব ক্ষেত্রেই তা প্রমাণিত হয়নি।

বেশিরভাগ গবেষকের মতো, রাবানী এবং তার সহ-লেখক- সেবাস্তিয়ান বুবেক মাইক্রোসফট গবেষণা এবং ক্রিশ্চিয়ান কোস্টার অক্সফোর্ড বিশ্ববিদ্যালয়ের - অনুমান সত্য ছিল. "আমার সন্দেহ করার কোন কারণ ছিল না," কোস্টার বলেছিলেন।

কিন্তু তারা অন্য অনলাইন সমস্যায় কাজ করার সাথে সাথে এটি পরিবর্তন হতে শুরু করে। এর সাথে এর সংযোগ ছিল k-সার্ভার সমস্যা, এবং প্রতিযোগিতামূলক অনুপাতের পরিচিত নিম্ন সীমা অপ্রত্যাশিতভাবে বেশি ছিল। এটা তাদের মনে হতে পারে লগ হিসাবে কম হিসাবে একটি লক্ষ্য k জন্য k-সার্ভার সমস্যা অত্যধিক আশাবাদী ছিল.

রাবানি বলেন, কোয়েস্টারই প্রথম প্রস্তাব দিয়েছিলেন যে র্যান্ডমাইজড k-সার্ভার অনুমান মিথ্যা হতে পারে। "তিনি এটি বলার সাথে সাথেই সবকিছু বোঝা গেল।"

অনুমানকে অস্বীকার করার জন্য, লেখকরা প্রতিপক্ষের ভূমিকা পালন করেছেন, একটি নিখুঁত ঝড় তৈরি করেছেন যা কোনো অনলাইন অ্যালগরিদমকে লগের প্রতিযোগিতামূলক অনুপাতে পৌঁছাতে বাধা দেবে। k. তাদের কৌশলটির দুটি অংশ ছিল: তারা জটিল, ফ্র্যাক্টাল-সদৃশ স্পেসগুলির একটি পরিবার তৈরি করেছিল এবং অনুরোধের ক্রমগুলির একটি বন্টন ডিজাইন করেছিল যা কোনও সম্ভাব্য অ্যালগরিদমের জন্য কঠিন হবে। অ্যালগরিদমের প্রথম পদক্ষেপে, স্থানের কাঠামোর অর্থ হল এটিকে দুটি অভিন্ন পথের মধ্যে বেছে নিতে হবে, যার মধ্যে একটির জন্য অনুরোধের ভিত্তিতে অতিরিক্ত ভ্রমণের প্রয়োজন হবে। তারপরে লেখকরা স্পেস তৈরি করার জন্য রিকারসন নামক একটি পদ্ধতি ব্যবহার করেছিলেন যা এই সিদ্ধান্তের পয়েন্টগুলিকে বহুগুণ করে, অ্যালগরিদমকে খারাপ বিকল্পের মোরাসে বাধ্য করে এবং খরচ বাড়িয়ে দেয়।

পছন্দগুলি রাবানিকে রবার্ট ফ্রস্টের কবিতার কথা মনে করিয়ে দেয় "রাস্তা নেওয়া হয়নি,” যেখানে একজন ভ্রমণকারী হলুদ কাঠের মধ্য দিয়ে দুটি সম্ভাব্য পথের কথা চিন্তা করে। তিনি রসিকতা করে বলেন, "আমরা কবিতাটি পুনরাবৃত্তিমূলকভাবে প্রয়োগ করি।" "এবং তারপর জিনিসগুলি সত্যিই খারাপ হয়ে যায়।"

লেখকরা দেখিয়েছেন যে, তারা যে স্থানগুলি তৈরি করেছিলেন সেখানে, একটি র্যান্ডমাইজড অ্যালগরিদম কখনই প্রতিযোগিতামূলক অনুপাত (লগ k)², লগ একটি সার্বজনীন লক্ষ্য ঠেলাঠেলি k চিরতরে নাগালের বাইরে। তারা অনুমান খন্ডন করেছেন।

এই কাজ, যা একটি জিতেছে শ্রেষ্ঠ কাগজ পুরস্কার এ 2023 কম্পিউটিং তত্ত্বের উপর সিম্পোজিয়াম, একটি "দৃঢ়ভাবে তাত্ত্বিক" মাইলফলক চিহ্নিত করে, গুপ্তা বলেন। এই ধরনের ফলাফল আমাদের অ্যালগরিদম থেকে আমরা কি ধরনের কর্মক্ষমতা আশা করতে পারি তা নির্দেশ করতে সাহায্য করে। বাস্তবে, যাইহোক, অ্যালগরিদম ডিজাইনাররা প্রায়শই একটি সর্বশক্তিমান প্রতিপক্ষ এবং ভবিষ্যতের সম্পূর্ণ অজ্ঞতার সাথে সবচেয়ে খারাপ পরিস্থিতির জন্য পরিকল্পনা করে না। যখন অ্যালগরিদমগুলি বাস্তব-বিশ্বের সমস্যাগুলির উপর প্রকাশ করা হয়, তখন তারা প্রায়শই তাত্ত্বিক প্রত্যাশা অতিক্রম করে।

কাগজ, যা অন্যান্য সমস্যার জন্য ব্যবহৃত র্যান্ডমাইজড অ্যালগরিদমের জন্য কাটঅফ প্রমাণ করেছে, এছাড়াও ক্ষেত্রের ভবিষ্যতের কাজের জন্যও প্রভাব থাকতে পারে। ফলাফল স্পষ্টভাবে লেখকদের ব্যবহৃত কৌশলটির "শক্তি হাইলাইট করে", গুপ্ত বলেন।

সম্ভবত এই ভবিষ্যতের ফলাফলগুলি গবেষকদের প্রত্যাশাকে অস্বীকার করবে যেমনটি এটি করেছিল, রাবানি বলেছিলেন। "এটি এমন একটি ক্ষেত্রে যেখানে ভুল হওয়া সত্যিই ভাল মনে হয়।"

কোয়ান্টা আমাদের শ্রোতাদের আরও ভালভাবে পরিবেশন করার জন্য সমীক্ষার একটি সিরিজ পরিচালনা করছে। আমাদের নিন কম্পিউটার বিজ্ঞান পাঠক জরিপ এবং আপনি বিনামূল্যে জিততে প্রবেশ করা হবে কোয়ান্টা পণ্যদ্রব্য.