স্পার্স গ্রাফে রাউটিং: ডেটা সায়েন্সের দিকে একটি বিতরণ করা Q-লার্নিং পদ্ধতি

1960-এর দশকে স্ট্যানলি মিলগ্রাম দ্বারা পরিচালিত ছোট-বিশ্বের পরীক্ষা সম্পর্কে। তারা একটি পরীক্ষা ডিজাইন করেছে যেখানে মার্কিন যুক্তরাষ্ট্রে একজন স্বেচ্ছাসেবককে একটি চিঠি দেওয়া হয়েছিল, যাতে চিঠিটি তাদের ব্যক্তিগত যোগাযোগের কাছে ফরোয়ার্ড করার নির্দেশনা ছিল, সম্ভবত একই দেশের অন্য একজনের কাছে পরিচিত – লক্ষ্য। বিনিময়ে, চিঠিটি প্রাপ্ত ব্যক্তিকে চিঠিটি পুনরায় ফরওয়ার্ড করতে বলা হবে যতক্ষণ না এটি লক্ষ্যযুক্ত ব্যক্তির কাছে পৌঁছায়। যদিও বেশির ভাগ চিঠি কখনোই লক্ষ্যযুক্ত ব্যক্তির কাছে পৌঁছায়নি, যাদের মধ্যে (এখানে খেলায় বেঁচে থাকার পক্ষপাতিত্ব!), হপসের গড় সংখ্যা ছিল প্রায় 6। “ছয় ডিগ্রি বিচ্ছেদ” সমাজের শক্ত আন্তঃসংযোগের একটি সাংস্কৃতিক রেফারেন্স হয়ে উঠেছে।

আমি এখনও এই ধারণা দ্বারা বিস্মিত যে ~10 সহ লোকেরা² পরিচিতিগুলি ~10 এর একটি নেটওয়ার্কে একটি এলোমেলো ব্যক্তির সাথে সংযোগ করতে পরিচালনা করে৷⁸ মানুষ, কয়েক hops মাধ্যমে.

এটা কিভাবে সম্ভব? অনুমান।

ধরুন আমাকে ফিনল্যান্ডের একজন টার্গেট ব্যক্তির কাছে একটি চিঠি পাঠাতে বলা হয়েছে¹.

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

যদি আমরা নেটওয়ার্কের নোডগুলির দৃষ্টিভঙ্গি গ্রহণ করি (পরীক্ষায় জড়িত মানুষ), তাদের উপলব্ধ ক্রিয়াগুলি হ’ল তাদের বহির্গামী প্রান্তগুলির একটিতে বার্তা (চিঠি) ফরোয়ার্ড করা (ব্যক্তিগত পরিচিতি)। বার্তা পাওয়ার এই সমস্যাটি মেশিন লার্নিংয়ের সাথে মজা করার সুযোগ দেয়!

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

যারা কোড চালাতে আগ্রহী তাদের জন্য, আপনি এখানে রেপো অ্যাক্সেস করতে পারেন।

সমস্যা

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

আমরা যে সমস্যাটি বিবেচনা করব তা হল একটি রিইনফোর্সমেন্ট লার্নিং অ্যালগরিদম ডিজাইন করা যা একটি নির্বিচারে স্টার্ট নোড থেকে একটি স্পার্স নির্দেশিত গ্রাফে একটি নির্বিচারে লক্ষ্য নোডের পথ খুঁজে পায়, যদি এই ধরনের একটি পথ বিদ্যমান থাকে তবে যতটা সম্ভব কম খরচে। এই সমস্যার জন্য নির্ধারক সমাধান বিদ্যমান। উদাহরণস্বরূপ, Dijkstra এর অ্যালগরিদম একটি নির্দেশিত গ্রাফে স্টার্ট নোড থেকে অন্য সমস্ত নোডের সংক্ষিপ্ততম পথ খুঁজে পায়। এটি আমাদের শক্তিবৃদ্ধি শেখার অ্যালগরিদমগুলির ফলাফলগুলি মূল্যায়ন করতে কার্যকর হবে, যা সর্বোত্তম সমাধান খুঁজে পাওয়ার গ্যারান্টিযুক্ত নয়৷

প্রশ্ন-শিক্ষা

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

হালনাগাদ নিয়ম, একটি পরীক্ষা কর্ম দেওয়া a_জেরাজ্য থেকে সংক্রমণের ফলে s_আমি বলুন s_এরপুরস্কার rএবং পরবর্তী রাজ্যের গুণমানের সর্বোত্তম অনুমান s_এরহল:

\[ Q(i, j) \leftarrow (1 – \alpha) Q(i, j) + \alpha \left( r + \gamma \max_{l} Q(k, l) \right) \]

_{সমীকরণ 1: কিউ-লার্নিংয়ের জন্য আপডেট করা নিয়ম।}

সমীকরণ 1 এ:

• α শেখার হার নিয়ন্ত্রণ করে কত দ্রুত নতুন ফলাফল পুরানো মানের অনুমান মুছে ফেলবে।
• γ হল ডিসকাউন্ট ফ্যাক্টর, যা তাৎক্ষণিক পুরষ্কারের সাথে ভবিষ্যতের পুরস্কারের তুলনা কতটা নিয়ন্ত্রণ করে।
• Q গুণমান হল ম্যাট্রিক্স। সারি সূচক i মূল অবস্থানের সূচী এবং কলাম সূচী j নির্বাচিত কর্মের সূচক।

সংক্ষেপে, সমীকরণ 1 বলে যে (রাষ্ট্র, ক্রিয়া) গুণমানকে আংশিকভাবে একটি নতুন গুণমানের সাথে আপডেট করা উচিত যা তাত্ক্ষণিক পুরষ্কার এবং সম্ভাব্য কর্মের যোগফলের উপর পরবর্তী রাজ্যের সর্বোচ্চ মানের একটি ছাড় অনুমান দ্বারা গঠিত।

আমাদের সমস্যা বিবৃতির জন্য, রাষ্ট্রের জন্য একটি সম্ভাব্য প্রণয়ন হবে জোড়া (বর্তমান নোড, লক্ষ্য নোড), এবং কর্মের সেটটি নোডের সেট হবে। তারপর রাজ্য সেট অন্তর্ভুক্ত হবে N² মান, এবং কর্ম সেট অন্তর্ভুক্ত করা হবে N মান, কোথায় N নোডের সংখ্যা। যাইহোক, যেহেতু গ্রাফটি বিক্ষিপ্ত, একটি প্রদত্ত রুট নোডে বহির্গামী প্রান্ত হিসাবে নোডগুলির একটি ছোট উপসেট রয়েছে। এই ফর্মুলেশনের ফলে একটি Q-ম্যাট্রিক্স যেখানে বড় সংখ্যাগরিষ্ঠ N³ এন্ট্রি কখনও দেখা যায় না, অকারণে স্মৃতি গ্রাস করে।

বিতরণ এজেন্ট

সম্পদের একটি ভাল ব্যবহার হল এজেন্টদের কাছে বিতরণ করা। প্রতিটি নোড একটি এজেন্ট হিসাবে চিন্তা করা যেতে পারে. এজেন্ট রাষ্ট্র টার্গেট নোড, তাই এটি Q-ম্যাট্রিক্স হল N লাইন এবং N_{বাইরে} কলাম (এই নির্দিষ্ট নোডের জন্য বহির্গামী প্রান্তের সংখ্যা)। সঙ্গে N এজেন্ট, ম্যাট্রিক্স এন্ট্রির মোট সংখ্যা N²N_{বাইরে}যা কম N³.

সংক্ষেপে:

• আমরা প্রশিক্ষণ দেব N এজেন্ট, গ্রাফে প্রতিটি নোডের জন্য একটি।
• প্রতিটি এজেন্ট শিখবে Q– মাত্রার ম্যাট্রিক্স [N x N_out]. বহির্গামী প্রান্তের সংখ্যা (N_{বাইরে}) এক নোড থেকে অন্য নোডে পরিবর্তিত হতে পারে। বিরলভাবে সংযুক্ত গ্রাফের জন্য, N_{বাইরে} << N.
• এর সারি সূচক Q-ম্যাট্রিক্স এজেন্টের অবস্থানের সাথে সামঞ্জস্যপূর্ণ, যেমন, লক্ষ্য নোড।
• এর কলাম সূচক Q-ম্যাট্রিক্স লক্ষ্য নোডের দিকে একটি বার্তা পাঠাতে এজেন্ট দ্বারা নির্বাচিত বহির্গামী প্রান্তের সাথে মিলে যায়।
• Q[i, j] বার্তা ফরোয়ার্ডিংয়ের গুণমানের একটি নোডের অনুমান উপস্থাপন করে। j^ম আউটগোয়িং এজ, টার্গেট নোড দেওয়া আছে i.
• যখন একটি নোড একটি বার্তা পায়, এটি লক্ষ্য নোড অন্তর্ভুক্ত করবে। যেহেতু পূর্ববর্তী বার্তার প্রেরককে পরবর্তী বার্তার রুট নির্ধারণ করার প্রয়োজন নেই, তাই এটি পরবর্তীতে অন্তর্ভুক্ত করা হবে না।

কোড

প্রধান ক্লাস, নোড, নাম দেওয়া হবে QNode.

class QNode:
    def __init__(self, number_of_nodes=0, connectivity_average=0, connectivity_std_dev=0, Q_arr=None, neighbor_nodes=None,
                 state_dict=None):
        if state_dict is not None:
            self.Q = state_dict['Q']
            self.number_of_nodes = state_dict['number_of_nodes']
            self.neighbor_nodes = state_dict['neighbor_nodes']
        else:  # state_dict is None
            if Q_arr is None:
                self.number_of_nodes = number_of_nodes
                number_of_neighbors = connectivity_average + connectivity_std_dev * np.random.randn()
                number_of_neighbors = round(number_of_neighbors)
                number_of_neighbors = max(number_of_neighbors, 2)  # At least two out-connections
                number_of_neighbors = min(number_of_neighbors, self.number_of_nodes)  # Not more than N connections
                self.neighbor_nodes = random.sample(range(self.number_of_nodes), number_of_neighbors)  # [1, 4, 5, ...]
                self.Q = np.zeros((self.number_of_nodes, number_of_neighbors))  # Optimistic initialization: all rewards will be negative
                # q = self.Q[state, action]: state = target node; action = chosen neighbor node (converted to column index) to route the message to

            else:  # state_dict is None and Q_arr is not None
                self.Q = Q_arr
                self.number_of_nodes = self.Q.shape[0]
                self.neighbor_nodes = neighbor_nodes

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

যখন একটি বার্তা আসে QNode বস্তু, এটি তার বহির্গামী প্রান্তগুলির একটি নির্বাচন করে epsilon- লোভী অ্যালগরিদম। যদি ε ছোট হয়, তবে এপিসিলন-লোভী অ্যালগরিদম বেশিরভাগ সময় সর্বোচ্চ দিয়ে বহির্গামী প্রান্ত নির্বাচন করে Q-মূল্য। কখনও কখনও, এটি এলোমেলোভাবে একটি বহির্গামী প্রান্ত নির্বাচন করবে:

def epsilon_greedy(self, target_node, epsilon):
        rdm_nbr = random.random()
        if rdm_nbr < epsilon:  # Random choice
            random_choice = random.choice(self.neighbor_nodes)
            return random_choice
        else:  # Greedy choice
            neighbor_columns = np.where(self.Q[target_node, :] == self.Q[target_node, :].max())[0]  # [1, 4, 5]
            neighbor_column = random.choice(neighbor_columns)
            neighbor_node = self.neighbor_node(neighbor_column)
            return neighbor_node

দ্বিতীয় শ্রেণী হল গ্রাফ, যাকে বলা হয় QGraph.

class QGraph:
    def __init__(self, number_of_nodes=10, connectivity_average=3, connectivity_std_dev=0, cost_range=[0.0, 1.0],
                 maximum_hops=100, maximum_hops_penalty=1.0):
        self.number_of_nodes = number_of_nodes
        self.connectivity_average = connectivity_average
        self.connectivity_std_dev = connectivity_std_dev
        self.cost_range = cost_range
        self.maximum_hops = maximum_hops
        self.maximum_hops_penalty = maximum_hops_penalty
        self.QNodes = []
        for node in range(self.number_of_nodes):
            self.QNodes.append(QNode(self.number_of_nodes, self.connectivity_average, self.connectivity_std_dev))

        self.cost_arr = cost_range[0] + (cost_range[1] - cost_range[0]) * np.random.random((self.number_of_nodes, self.number_of_nodes))

এর প্রধান ক্ষেত্র হল নোডের তালিকা এবং প্রান্ত খরচের অ্যারে। মনে রাখবেন যে আসল প্রান্তগুলি এর অংশ QNode ক্লাস, বহির্গামী নোডের একটি তালিকা হিসাবে।

যখন আমরা স্টার্ট নোড থেকে টার্গেট নোড পর্যন্ত একটি পথ তৈরি করতে চাই, তখন আমরা কল করি QGraph.trajectory() পদ্ধতি যে কল QNode.epsilon_greedy() পদ্ধতি:

    def trajectory(self, start_node, target_node, epsilon):
        visited_nodes = [start_node]
        costs = []
        if start_node == target_node:
            return visited_nodes, costs
        current_node = start_node
        while len(visited_nodes) < self.maximum_hops + 1:
            next_node = self.QNodes[current_node].epsilon_greedy(target_node, epsilon)
            cost = float(self.cost_arr[current_node, next_node])
            visited_nodes.append(next_node)
            costs.append(cost)
            current_node = next_node
            if current_node == target_node:
                return visited_nodes, costs
        # We reached the maximum number of hops
        return visited_nodes, costs

trajectory() পদ্ধতিটি পথ বরাবর পরিদর্শন করা নোডের তালিকা এবং ব্যবহৃত প্রান্তগুলির সাথে সম্পর্কিত খরচ প্রদান করে।

শেষ অনুপস্থিত অংশ সমীকরণ 1 এর আপডেট নিয়ম, দ্বারা বাস্তবায়িত QGraph.update_Q() পদ্ধতি:

def update_Q(self, start_node, neighbor_node, alpha, gamma, target_node):
   cost = self.cost_arr[start_node, neighbor_node]
   reward = -cost
   # Q_orig(target, dest) <- (1 - alpha) Q_orig(target, dest) + alpha * ( r + gamma * max_neigh' Q_dest(target, neigh') )
   Q_orig_target_dest = self.QNodes[start_node].Q[target_node, self.QNodes[start_node].neighbor_column(neighbor_node)]
   max_neigh_Q_dest_target_neigh = np.max(self.QNodes[neighbor_node].Q[target_node, :])
   updated_Q = (1 - alpha) * Q_orig_target_dest + alpha * (reward + gamma * max_neigh_Q_dest_target_neigh)
   self.QNodes[start_node].Q[target_node, self.QNodes[start_node].neighbor_column(neighbor_node)] = updated_Q

আমাদের এজেন্টদের প্রশিক্ষিত করার জন্য, আমরা পুনরাবৃত্তভাবে জোড়া দিয়ে লুপ করি (start_node, target_node) এর প্রতিবেশী নোডের উপর একটি অভ্যন্তরীণ লুপ সহ start_nodeএবং আমরা কল করি update_Q().

পরীক্ষা এবং ফলাফল

নির্দেশিত ওজনযুক্ত প্রান্ত সহ 12টি নোডের একটি সাধারণ গ্রাফ দিয়ে শুরু করা যাক।

আমরা চিত্র 1 থেকে দেখতে পাচ্ছি যে নোড-1 তে আসা একমাত্র নোডটি হল নোড-7, এবং একমাত্র নোডটি নোড-7 এ আসে তা হল নোড-1। অতএব, এই দুটি ব্যতীত অন্য কোন নোড নোড-1 এবং নোড-7-এ পৌঁছাতে পারে না। যখন অন্য নোডকে নোড-1 বা নোড-7-এ একটি বার্তা পাঠানোর দায়িত্ব দেওয়া হয়, তখন বার্তাটি গ্রাফের চারপাশে বাউন্স হবে যতক্ষণ না সর্বাধিক সংখ্যায় পৌঁছে যায়। আমরা বড় নেতিবাচকতা দেখতে আশা করি Q-এসব ক্ষেত্রে মান.

যখন আমরা আমাদের গ্রাফকে প্রশিক্ষণ দিই, তখন আমরা চিত্র 2-এর মতো যুগের একটি ফাংশন হিসাবে খরচ এবং হপগুলির সংখ্যা সম্পর্কে পরিসংখ্যান পাই:

এটি প্রশিক্ষণের পরে Q-নোড-4 এর জন্য ম্যাট্রিক্স:

নোড-4 থেকে নোড-11 পর্যন্ত ট্র্যাজেক্টোরি কল করে পাওয়া যাবে trajectory() পদ্ধতি, সেটিং epsilon=0 লোভী নির্ধারক সমাধানের জন্য: [4, 3, 5, 11] 0.9 + 0.9 + 0.3 = 2.1 এর মোট ছাড়বিহীন খরচের জন্য। Dijkstra অ্যালগরিদম একই পথে ফিরে আসে।

কিছু বিরল ক্ষেত্রে, সর্বোত্তম পথ খুঁজে পাওয়া যায়নি। উদাহরণস্বরূপ, নোড-6 থেকে নোড-9-এ যেতে, প্রশিক্ষিত Q-গ্রাফের একটি নির্দিষ্ট উদাহরণ দেওয়া হয়। [6, 11, 0, 4, 10, 2, 9] ডিজকস্ট্রা অ্যালগরিদম ফিরে আসার সময় মোট 3.5 মূল্যের ছাড়হীন খরচের জন্য [6, 0, 4, 10, 2, 9] মোট 3.4 এর মূল্যছাড়হীন খরচের জন্য। আমরা আগেই বলেছি, এটি একটি পুনরাবৃত্তিমূলক অ্যালগরিদম থেকে প্রত্যাশিত

উপসংহার

আমরা ছোট-বিশ্বের পরীক্ষাটিকে ওজনযুক্ত প্রান্ত সহ একটি বিক্ষিপ্ত নির্দেশিত গ্রাফে যেকোন জোড়া নোডের মধ্যে ন্যূনতম খরচ সহ একটি পথ খুঁজে পাওয়ার সমস্যা হিসাবে তৈরি করেছি। আমরা নোডগুলিকে কিউ-লার্নিং এজেন্ট হিসাবে প্রয়োগ করেছি, যা একটি টার্গেট নোডের জন্য সর্বনিম্ন ব্যয়বহুল পদক্ষেপ নিতে আপডেট নিয়মের মাধ্যমে শেখে।

একটি সাধারণ গ্রাফের সাহায্যে, আমরা দেখিয়েছি যে প্রশিক্ষণটি অনুকূলের কাছাকাছি একটি সমাধানের উপর ভিত্তি করে।

আপনার সময় জন্য ধন্যবাদ, এবং কোড সঙ্গে পরীক্ষা নির্দ্বিধায়. কিউ-লার্নিং-এর জন্য মজাদার অ্যাপের জন্য আপনার কাছে ধারনা থাকলে, দয়া করে আমাকে জানান!

¹ ঠিক আছে, আমি আসল ছোট-বিশ্বের পরীক্ষাকে ছাড়িয়ে যাচ্ছি, যাকে ছোট-দেশের পরীক্ষা বলা উচিত।

রেফারেন্স

রিইনফোর্সমেন্ট লার্নিং, রিচার্ড এস সাটন, অ্যান্ড্রু জি বার্তো, এমআইটি প্রেস, 1998