{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"name":"2022-01-24-ope-slate.ipynb","provenance":[{"file_id":"https://github.com/recohut/nbs/blob/main/raw/T262036%20%7C%20Off-Policy%20Evaluation%20for%20Slate%20Recommendation.ipynb","timestamp":1644669113057}],"collapsed_sections":[],"authorship_tag":"ABX9TyM7nOLjbGG0WaTWTvPbHSdH"},"kernelspec":{"name":"python3","display_name":"Python 3"},"language_info":{"name":"python"}},"cells":[{"cell_type":"markdown","source":["# Off-Policy Evaluation for Slate Recommendation"],"metadata":{"id":"cuB0025o7Y3p"}},{"cell_type":"markdown","metadata":{"id":"1FiasDgkd1TI"},"source":["## Imports"]},{"cell_type":"code","metadata":{"id":"MEaMMSa4ekZ7"},"source":["import numpy\n","import decimal\n","import scipy.sparse\n","import os\n","import sys\n","import os.path\n","import sklearn.model_selection\n","import sklearn.tree\n","import sklearn.linear_model\n","import sklearn.tree\n","import sklearn.ensemble\n","from sklearn.externals import joblib\n","import scipy.linalg\n","import itertools"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"5VWgwAETe9uG"},"source":["## Settings"]},{"cell_type":"code","metadata":{"id":"7yXbiVETfD2E"},"source":["DATA_DIR=\"/content\""],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"8eaiJL-ke_pb"},"source":["def get_feature_sets(datasetName):\n","    anchorURL = [0]\n","    bodyDoc = [0]\n","    \n","    if datasetName.startswith('MSLR'):\n","        for i in range(25):\n","            anchorURL.extend([5*i+2, 5*i+4])\n","            bodyDoc.extend([5*i+1, 5*i+3, 5*i+5])\n","        anchorURL.extend([126, 127, 128, 129, 130, 131])\n","        bodyDoc.extend([132,133])\n","        \n","    elif datasetName.startswith('MQ200'):\n","        for i in range(8):\n","            anchorURL.extend([5*i+2, 5*i+4])\n","            bodyDoc.extend([5*i+1, 5*i+3, 5*i+5])\n","        anchorURL.extend([41, 42, 43, 44, 45, 46])\n","\n","    else:\n","        print(\"Settings:get_feature_sets [ERR] Unknown dataset. Use MSLR/MQ200*\", flush=True)\n","        sys.exit(0)\n","        \n","    return anchorURL, bodyDoc"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"g3iPvTWlehc_"},"source":["## Datasets"]},{"cell_type":"markdown","metadata":{"id":"iz2zRXdTeihi"},"source":["Classes that pre-process datasets for semi-synthetic experiments"]},{"cell_type":"code","metadata":{"id":"CqXEXVlOeneC"},"source":["class Datasets:\n","    def __init__(self):\n","        #Must call either loadTxt(...)/loadNpz(...) to set all these members\n","        #before using Datasets objects elsewhere\n","        self.relevances=None\n","        self.features=None\n","        self.docsPerQuery=None\n","        self.queryMappings=None\n","        self.name=None\n","    \n","        #For filtered datasets, some docsPerQuery may be masked\n","        self.mask=None\n","        \n","    ###As a side-effect, loadTxt(...) stores a npz file for\n","    ###faster subsequent loading via loadNpz(...)\n","    #file_name: (str) Path to dataset file (.txt format)\n","    #name:      (str) String to identify this Datasets object henceforth\n","    def loadTxt(self, file_name, name):\n","        #Internal: Counters to keep track of docID and qID\n","        previousQueryID=None\n","        docID=None\n","        qID=0\n","        relevanceArray=None\n","        \n","        #QueryMappings: list[int],length=numQueries\n","        self.queryMappings=[]\n","        \n","        self.name=name\n","        \n","        #DocsPerQuery:  list[int],length=numQueries\n","        self.docsPerQuery=[]\n","        \n","        #Relevances:    list[Alpha],length=numQueries; Alpha:= numpy.array[int],length=docsForQuery\n","        self.relevances=[]\n","        \n","        #Features:      list[Alpha],length=numQueries; \n","        #Alpha:= scipy.sparse.coo_matrix[double],shape=(docsForQuery, numFeatures)\n","        featureRows=None\n","        featureCols=None\n","        featureVals=None\n","        \n","        self.features=[]\n","        numFeatures=None\n","        \n","        #Now read in data\n","        with open(file_name, 'r') as f:\n","            outputFilename=file_name[:-4]\n","            outputFileDir=outputFilename+'_processed'\n","            if not os.path.exists(outputFileDir):\n","                os.makedirs(outputFileDir)\n","            \n","            for line in f:\n","                tokens=line.split(' ', 2)\n","                relevance=int(tokens[0])\n","                queryID=int(tokens[1].split(':', 1)[1])\n","                \n","                #Remove any trailing comments before extracting features\n","                remainder=tokens[2].split('#', 1)\n","                featureTokens=remainder[0].strip().split(' ')\n","                \n","                if numFeatures is None:\n","                    numFeatures=len(featureTokens)+1\n","                    \n","                if (previousQueryID is None) or (queryID!=previousQueryID):\n","                    #Begin processing a new query's documents\n","                    docID=0\n","                    \n","                    if relevanceArray is not None:\n","                        #Previous query's data should be persisted to file/self.members\n","                        currentRelevances=numpy.array(relevanceArray, \n","                                                dtype=numpy.int, copy=False)\n","                        self.relevances.append(currentRelevances)\n","                        numpy.savez_compressed(os.path.join(outputFileDir, str(qID)+'_rel'), \n","                                                relevances=currentRelevances)\n","                        \n","                        maxDocs=len(relevanceArray)\n","                        self.docsPerQuery.append(maxDocs)\n","                        \n","                        currentFeatures=scipy.sparse.coo_matrix((featureVals, (featureRows, featureCols)),\n","                                                shape=(maxDocs, numFeatures), dtype=numpy.float64)\n","                        currentFeatures=currentFeatures.tocsr()\n","                        self.features.append(currentFeatures)\n","                        scipy.sparse.save_npz(os.path.join(outputFileDir, str(qID)+'_feat'), \n","                                                currentFeatures)\n","        \n","                        qID+=1\n","                        self.queryMappings.append(previousQueryID)\n","                        \n","                        if len(self.docsPerQuery)%100==0:\n","                            print(\".\", end=\"\", flush=True)\n","                            \n","                    relevanceArray=[]\n","                    featureRows=[]\n","                    featureCols=[]\n","                    featureVals=[]\n","                    \n","                    previousQueryID=queryID\n","                else:\n","                    docID+=1\n","                    \n","                relevanceArray.append(relevance)\n","                \n","                #Add a feature for the the intercept\n","                featureRows.append(docID)\n","                featureCols.append(0)\n","                featureVals.append(0.01)\n","                \n","                for featureToken in featureTokens:\n","                    featureTokenSplit=featureToken.split(':', 1)\n","                    featureIndex=int(featureTokenSplit[0])\n","                    featureValue=float(featureTokenSplit[1])\n","                    \n","                    featureRows.append(docID)\n","                    featureCols.append(featureIndex)\n","                    featureVals.append(featureValue)\n","            \n","            #Finish processing the final query's data\n","            currentRelevances=numpy.array(relevanceArray, dtype=numpy.int, copy=False)\n","            self.relevances.append(currentRelevances)\n","            numpy.savez_compressed(os.path.join(outputFileDir, str(qID)+'_rel'), \n","                                        relevances=currentRelevances)\n","            \n","            maxDocs=len(relevanceArray)\n","            self.docsPerQuery.append(maxDocs)\n","            \n","            currentFeatures=scipy.sparse.coo_matrix((featureVals, (featureRows, featureCols)),\n","                                        shape=(maxDocs, numFeatures), dtype=numpy.float64)\n","            currentFeatures=currentFeatures.tocsr()\n","            self.features.append(currentFeatures)\n","            scipy.sparse.save_npz(os.path.join(outputFileDir, str(qID)+'_feat'),\n","                                        currentFeatures)\n","            \n","            self.queryMappings.append(previousQueryID)\n","        \n","        #Persist meta-data for the dataset for faster loading through loadNpz\n","        numpy.savez_compressed(outputFilename, docsPerQuery=self.docsPerQuery, \n","                                        name=self.name, queryMappings=self.queryMappings)\n","        \n","        print(\"\", flush=True)\n","        print(\"Datasets:loadTxt [INFO] Loaded\", file_name, \n","                    \"\\t NumQueries\", len(self.docsPerQuery), \n","                    \"\\t [Min/Max]DocsPerQuery\", min(self.docsPerQuery), \n","                    max(self.docsPerQuery), flush=True)\n","    \n","    #file_name: (str) Path to dataset file/directory\n","    def loadNpz(self, file_name):\n","        with numpy.load(file_name+'.npz') as npFile:\n","            self.docsPerQuery=npFile['docsPerQuery']\n","            self.name=str(npFile['name'])\n","            self.queryMappings=npFile['queryMappings']\n","        \n","        fileDir = file_name+'_processed'\n","        if os.path.exists(fileDir):\n","            self.relevances=[]\n","            self.features=[]\n","            \n","            qID=0\n","            while os.path.exists(os.path.join(fileDir, str(qID)+'_rel.npz')):\n","                with numpy.load(os.path.join(fileDir, str(qID)+'_rel.npz')) as currRelFile:\n","                    self.relevances.append(currRelFile['relevances'])\n","                \n","                self.features.append(scipy.sparse.load_npz(os.path.join(fileDir, str(qID)+'_feat.npz')))\n","                    \n","                qID+=1\n","                \n","                if qID%100==0:\n","                    print(\".\", end=\"\", flush=True)\n","                \n","        print(\"\", flush=True)\n","        print(\"Datasets:loadNpz [INFO] Loaded\", file_name, \"\\t NumQueries\", len(self.docsPerQuery), \n","                    \"\\t [Min/Max]DocsPerQuery\", min(self.docsPerQuery), \n","                    max(self.docsPerQuery), \"\\t [Sum] docsPerQuery\", sum(self.docsPerQuery), flush=True)"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"6hXZf6YhexDv"},"source":["\"\"\"\n","mq2008Data=Datasets()\n","mq2008Data.loadTxt(Settings.DATA_DIR+'MQ2008.txt', 'MQ2008')\n","mq2008Data.loadNpz(Settings.DATA_DIR+'MQ2008')\n","del mq2008Data\n","\n","mq2007Data=Datasets()\n","mq2007Data.loadTxt(Settings.DATA_DIR+'MQ2007.txt', 'MQ2007')\n","mq2007Data.loadNpz(Settings.DATA_DIR+'MQ2007')\n","del mq2007Data\n","\"\"\"\n","mslrData=Datasets()\n","mslrData.loadTxt(Settings.DATA_DIR+'MSLR-WEB10K/mslr.txt', 'MSLR10k')\n","del mslrData\n","\n","for foldID in range(1,6):\n","    for fraction in ['train','vali','test']:\n","        mslrData=Datasets()\n","        mslrData.loadTxt(Settings.DATA_DIR+'MSLR-WEB10K\\\\Fold'+str(foldID)+'\\\\'+fraction+'.txt', 'MSLR10k-'+str(foldID)+'-'+fraction)\n","        del mslrData\n","\n","mslrData=Datasets()\n","mslrData.loadTxt(Settings.DATA_DIR+'MSLR/mslr.txt', 'MSLR')\n","del mslrData\n","\n","for foldID in range(1,6):\n","    for fraction in ['train','vali','test']:\n","        mslrData=Datasets()\n","        mslrData.loadTxt(Settings.DATA_DIR+'MSLR\\\\Fold'+str(foldID)+'\\\\'+fraction+'.txt', 'MSLR-'+str(foldID)+'-'+fraction)\n","        del mslrData"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"pgow506kfOuB"},"source":["## Estimators"]},{"cell_type":"code","metadata":{"id":"ELjwikRQfPdt"},"source":["class Estimator:\n","    #ranking_size: (int) Size of slate, l\n","    #logging_policy: (UniformPolicy) Logging policy, \\mu\n","    #target_policy: (Policy) Target policy, \\pi\n","    def __init__(self, ranking_size, logging_policy, target_policy):\n","        self.rankingSize=ranking_size\n","        self.name=None\n","        self.loggingPolicy=logging_policy\n","        self.targetPolicy=target_policy\n","        \n","        if target_policy.name is None or logging_policy.name is None:\n","            print(\"Estimator:init [ERR] Either target or logging policy is not initialized\", flush=True)\n","            sys.exit(0)\n","            \n","        if target_policy.dataset.name != logging_policy.dataset.name:\n","            print(\"Estimator:init [ERR] Target and logging policy operate on different datasets\", flush=True)\n","            sys.exit(0)\n","            \n","        ###All sub-classes of Estimator should supply a estimate method\n","        ###Requires: query, logged_ranking, logged_value,\n","        ###Returns: float indicating estimated value\n","        \n","        self.runningSum=0\n","        self.runningMean=0.0\n","\n","    def updateRunningAverage(self, value):\n","        self.runningSum+=1\n","        delta=value-self.runningMean\n","        self.runningMean+=delta/self.runningSum\n","\n","    def reset(self):\n","        self.runningSum=0\n","        self.runningMean=0.0 "],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"bhcE-LH5gE4n"},"source":[" class OnPolicy(Estimator):\n","    def __init__(self, ranking_size, logging_policy, target_policy, metric):\n","        Estimator.__init__(self, ranking_size, logging_policy, target_policy)\n","        self.name='OnPolicy'\n","        self.metric=metric\n","        \n","        #This member is set on-demand by estimateAll(...)\n","        self.savedValues=None\n","        \n","    def estimateAll(self):\n","        if self.savedValues is not None:\n","            return\n","            \n","        self.savedValues=[]\n","        numQueries=len(self.loggingPolicy.dataset.docsPerQuery)\n","        for i in range(numQueries):\n","            newRanking=self.targetPolicy.predict(i, self.rankingSize)\n","            self.savedValues.append(self.metric.computeMetric(i, newRanking))\n","            if i%100==0:\n","                print(\".\", end=\"\", flush=True)\n","                \n","        print(\"\")\n","        print(\"OnPolicy:estimateAll [LOG] Precomputed estimates.\", flush=True)\n","            \n","    def estimate(self, query, logged_ranking, new_ranking, logged_value):\n","        currentValue=None\n","        if self.savedValues is not None:\n","            currentValue=self.savedValues[query]\n","        else:\n","            currentValue=self.metric.computeMetric(query, new_ranking)\n","            \n","        self.updateRunningAverage(currentValue)\n","        return self.runningMean\n","        \n","    def reset(self):\n","        Estimator.reset(self)\n","        self.savedValues=None"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"3PVjYN3Sf_d4"},"source":["### Uniform IPS"]},{"cell_type":"code","metadata":{"id":"JhQTQ6DDf--k"},"source":["class UniformIPS(Estimator):\n","    def __init__(self, ranking_size, logging_policy, target_policy):\n","        Estimator.__init__(self, ranking_size, logging_policy, target_policy)\n","        self.name='Unif-IPS'\n","        \n","    def estimate(self, query, logged_ranking, new_ranking, logged_value):\n","        exactMatch=numpy.absolute(new_ranking-logged_ranking).sum() == 0\n","        currentValue=0.0\n","        if exactMatch:\n","            numAllowedDocs=self.loggingPolicy.dataset.docsPerQuery[query]\n","            validDocs=logged_ranking.size\n","            invPropensity=None\n","            if self.loggingPolicy.allowRepetitions:\n","                invPropensity=numpy.float_power(numAllowedDocs, validDocs)\n","            else:\n","                invPropensity=numpy.prod(range(numAllowedDocs+1-validDocs, numAllowedDocs+1), dtype=numpy.float64)\n","                \n","            currentValue=logged_value*invPropensity\n","\n","        self.updateRunningAverage(currentValue)\n","        return self.runningMean"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"hq7Mn459f7e1"},"source":["### Non-uniform IPS"]},{"cell_type":"code","metadata":{"id":"H-3GhjpEf62b"},"source":["class NonUniformIPS(Estimator):\n","    def __init__(self, ranking_size, logging_policy, target_policy):\n","        Estimator.__init__(self, ranking_size, logging_policy, target_policy)\n","        self.name='NonUnif-IPS'\n","        \n","    def estimate(self, query, logged_ranking, new_ranking, logged_value):\n","        exactMatch=numpy.absolute(new_ranking-logged_ranking).sum() == 0\n","        currentValue=0.0\n","        if exactMatch:\n","            numAllowedDocs=self.loggingPolicy.dataset.docsPerQuery[query]\n","            underlyingRanking=self.loggingPolicy.policy.predict(query, -1)\n","            currentDistribution=self.loggingPolicy.multinomials[numAllowedDocs]\n","            \n","            numRankedDocs=logged_ranking.size\n","            invPropensity=1.0\n","            denominator=1.0\n","            for j in range(numRankedDocs):\n","                underlyingIndex=numpy.flatnonzero(underlyingRanking == logged_ranking[j])[0]\n","                invPropensity*=(denominator*1.0/currentDistribution[underlyingIndex])\n","                if not self.loggingPolicy.allowRepetitions:\n","                    denominator-=currentDistribution[underlyingIndex]\n","                \n","            currentValue=logged_value*invPropensity\n","\n","        self.updateRunningAverage(currentValue)\n","        return self.runningMean"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"WP3SANInf3LK"},"source":["### Uniform SNIPS"]},{"cell_type":"code","metadata":{"id":"__7sXcHAf2jU"},"source":["class UniformSNIPS(Estimator):\n","    def __init__(self, ranking_size, logging_policy, target_policy):\n","        Estimator.__init__(self, ranking_size, logging_policy, target_policy)\n","        self.name='Unif-IPS_SN'\n","        self.runningDenominatorMean=0.0\n","        \n","    def estimate(self, query, logged_ranking, new_ranking, logged_value):\n","        exactMatch=numpy.absolute(new_ranking-logged_ranking).sum() == 0\n","        currentValue=0.0\n","        if exactMatch:\n","            numAllowedDocs=self.loggingPolicy.dataset.docsPerQuery[query]\n","            validDocs=logged_ranking.size\n","            invPropensity=None\n","            if self.loggingPolicy.allowRepetitions:\n","                invPropensity=numpy.float_power(numAllowedDocs, validDocs)\n","            else:\n","                invPropensity=numpy.prod(range(numAllowedDocs+1-validDocs, numAllowedDocs+1), dtype=numpy.float64)\n","                \n","            currentValue=logged_value*invPropensity\n","\n","            self.updateRunningAverage(currentValue)\n","            denominatorDelta=invPropensity-self.runningDenominatorMean\n","            self.runningDenominatorMean+=denominatorDelta/self.runningSum\n","        if self.runningDenominatorMean!=0.0:\n","            return 1.0*self.runningMean/self.runningDenominatorMean\n","        else:\n","            return 0.0\n","\n","    def reset(self):\n","        Estimator.reset(self)\n","        self.runningDenominatorMean=0.0"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"J5_uSseWfyGL"},"source":["### Non-uniform SNIPS"]},{"cell_type":"code","metadata":{"id":"Qb3AsxMqfxcG"},"source":["class NonUniformSNIPS(Estimator):\n","    def __init__(self, ranking_size, logging_policy, target_policy):\n","        Estimator.__init__(self, ranking_size, logging_policy, target_policy)\n","        self.name='NonUnif-IPS_SN'\n","        self.runningDenominatorMean=0.0\n","        \n","    def estimate(self, query, logged_ranking, new_ranking, logged_value):\n","        exactMatch=numpy.absolute(new_ranking-logged_ranking).sum() == 0\n","        currentValue=0.0\n","        if exactMatch:\n","            numAllowedDocs=self.loggingPolicy.dataset.docsPerQuery[query]\n","            underlyingRanking=self.loggingPolicy.policy.predict(query, -1)\n","            currentDistribution=self.loggingPolicy.multinomials[numAllowedDocs]\n","            \n","            numRankedDocs=logged_ranking.size\n","            invPropensity=1.0\n","            denominator=1.0\n","            for j in range(numRankedDocs):\n","                underlyingIndex=numpy.flatnonzero(underlyingRanking == logged_ranking[j])[0]\n","                invPropensity*=(denominator*1.0/currentDistribution[underlyingIndex])\n","                if not self.loggingPolicy.allowRepetitions:\n","                    denominator-=currentDistribution[underlyingIndex]\n","                \n","            currentValue=logged_value*invPropensity\n","\n","            self.updateRunningAverage(currentValue)\n","            denominatorDelta=invPropensity-self.runningDenominatorMean\n","            self.runningDenominatorMean+=denominatorDelta/self.runningSum\n","        if self.runningDenominatorMean!=0.0:\n","            return 1.0*self.runningMean/self.runningDenominatorMean\n","        else:\n","            return 0.0\n","\n","    def reset(self):\n","        Estimator.reset(self)\n","        self.runningDenominatorMean=0.0"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"okkeE_aGftlY"},"source":["### Uniform PI"]},{"cell_type":"code","metadata":{"id":"dWwKVEPdftBv"},"source":["class UniformPI(Estimator):\n","    def __init__(self, ranking_size, logging_policy, target_policy):\n","        Estimator.__init__(self, ranking_size, logging_policy, target_policy)\n","        self.name='Unif-PI'\n","        \n","    def estimate(self, query, logged_ranking, new_ranking, logged_value):\n","        numAllowedDocs=self.loggingPolicy.dataset.docsPerQuery[query]\n","        validDocs=logged_ranking.size\n","        vectorDimension=validDocs*numAllowedDocs\n","        \n","        exploredMatrix=numpy.zeros((validDocs, numAllowedDocs), dtype=numpy.float64)\n","        newMatrix=numpy.zeros((validDocs, numAllowedDocs), dtype=numpy.float64)\n","        for j in range(validDocs):\n","            if self.loggingPolicy.dataset.mask is None:\n","                exploredMatrix[j, logged_ranking[j]]=1\n","                newMatrix[j, new_ranking[j]]=1\n","            else:\n","                logIndex=numpy.flatnonzero(self.loggingPolicy.dataset.mask[query] == logged_ranking[j])[0]\n","                newIndex=numpy.flatnonzero(self.loggingPolicy.dataset.mask[query] == new_ranking[j])[0]\n","                exploredMatrix[j, logIndex]=1\n","                newMatrix[j, newIndex]=1\n","        \n","        posRelVector=exploredMatrix.reshape(vectorDimension)\n","        newSlateVector=newMatrix.reshape(vectorDimension)\n","        \n","        estimatedPhi=numpy.dot(self.loggingPolicy.gammas[numAllowedDocs], posRelVector)\n","        invPropensity=numpy.dot(estimatedPhi, newSlateVector)\n","        \n","        currentValue=logged_value*invPropensity\n","        \n","        self.updateRunningAverage(currentValue)\n","        return self.runningMean"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"G_bvQ13mfoY5"},"source":["### Non-uniform PI"]},{"cell_type":"code","metadata":{"id":"Sb6AzI-Vfn2d"},"source":["class NonUniformPI(Estimator):\n","    def __init__(self, ranking_size, logging_policy, target_policy):\n","        Estimator.__init__(self, ranking_size, logging_policy, target_policy)\n","        self.name='NonUnif-PI'\n","        \n","    def estimate(self, query, logged_ranking, new_ranking, logged_value):\n","        numAllowedDocs=self.loggingPolicy.dataset.docsPerQuery[query]\n","        underlyingRanking=self.loggingPolicy.policy.predict(query, -1)\n","        validDocs=logged_ranking.size\n","        vectorDimension=validDocs*numAllowedDocs\n","        \n","        exploredMatrix=numpy.zeros((validDocs, numAllowedDocs), dtype=numpy.float64)\n","        newMatrix=numpy.zeros((validDocs, numAllowedDocs), dtype=numpy.float64)\n","        for j in range(validDocs):\n","            logIndex=numpy.flatnonzero(underlyingRanking == logged_ranking[j])[0]\n","            newIndex=numpy.flatnonzero(underlyingRanking == new_ranking[j])[0]\n","            exploredMatrix[j, logIndex]=1\n","            newMatrix[j, newIndex]=1\n","        \n","        posRelVector=exploredMatrix.reshape(vectorDimension)\n","        newSlateVector=newMatrix.reshape(vectorDimension)\n","        \n","        estimatedPhi=numpy.dot(self.loggingPolicy.gammas[numAllowedDocs], posRelVector)\n","        invPropensity=numpy.dot(estimatedPhi, newSlateVector)\n"," \n","        currentValue=logged_value*invPropensity\n","        \n","        self.updateRunningAverage(currentValue)\n","        return self.runningMean"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"rNfsM1yjfkdd"},"source":["### Uniform SNPI"]},{"cell_type":"code","metadata":{"id":"lv2FX7dhfg5L"},"source":["class UniformSNPI(Estimator):\n","    def __init__(self, ranking_size, logging_policy, target_policy):\n","        Estimator.__init__(self, ranking_size, logging_policy, target_policy)\n","        self.name='Unif-PI_SN'\n","        self.runningDenominatorMean=0.0\n","\n","    def estimate(self, query, logged_ranking, new_ranking, logged_value):\n","        numAllowedDocs=self.loggingPolicy.dataset.docsPerQuery[query]\n","        validDocs=logged_ranking.size\n","        vectorDimension=validDocs*numAllowedDocs\n","        \n","        exploredMatrix=numpy.zeros((validDocs, numAllowedDocs), dtype=numpy.float64)\n","        newMatrix=numpy.zeros((validDocs, numAllowedDocs), dtype=numpy.float64)\n","        for j in range(validDocs):\n","            if self.loggingPolicy.dataset.mask is None:\n","                exploredMatrix[j, logged_ranking[j]]=1\n","                newMatrix[j, new_ranking[j]]=1\n","            else:\n","                logIndex=numpy.flatnonzero(self.loggingPolicy.dataset.mask[query] == logged_ranking[j])[0]\n","                newIndex=numpy.flatnonzero(self.loggingPolicy.dataset.mask[query] == new_ranking[j])[0]\n","                exploredMatrix[j, logIndex]=1\n","                newMatrix[j, newIndex]=1\n","        \n","        posRelVector=exploredMatrix.reshape(vectorDimension)\n","        newSlateVector=newMatrix.reshape(vectorDimension)\n","        \n","        estimatedPhi=numpy.dot(self.loggingPolicy.gammas[numAllowedDocs], posRelVector)\n","        invPropensity=numpy.dot(estimatedPhi, newSlateVector)\n","        currentValue=logged_value*invPropensity\n","        \n","        self.updateRunningAverage(currentValue)\n","        \n","        denominatorDelta=invPropensity-self.runningDenominatorMean\n","        self.runningDenominatorMean+=denominatorDelta/self.runningSum\n","        if self.runningDenominatorMean!=0.0:\n","            return 1.0*self.runningMean/self.runningDenominatorMean\n","        else:\n","            return 0.0\n","\n","    def reset(self):\n","        Estimator.reset(self)\n","        self.runningDenominatorMean=0.0"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"qpheFMdMfcXN"},"source":["### Non-uniform SNPI"]},{"cell_type":"code","metadata":{"id":"gIr66upPfbYq"},"source":["class NonUniformSNPI(Estimator):\n","    def __init__(self, ranking_size, logging_policy, target_policy):\n","        Estimator.__init__(self, ranking_size, logging_policy, target_policy)\n","        self.name='NonUnif-PI_SN'\n","        self.runningDenominatorMean=0.0\n","\n","    def estimate(self, query, logged_ranking, new_ranking, logged_value):\n","        numAllowedDocs=self.loggingPolicy.dataset.docsPerQuery[query]\n","        underlyingRanking=self.loggingPolicy.policy.predict(query, -1)\n","        \n","        validDocs=logged_ranking.size\n","        vectorDimension=validDocs*numAllowedDocs\n","        \n","        exploredMatrix=numpy.zeros((validDocs, numAllowedDocs), dtype=numpy.float64)\n","        newMatrix=numpy.zeros((validDocs, numAllowedDocs), dtype=numpy.float64)\n","        for j in range(validDocs):\n","            logIndex=numpy.flatnonzero(underlyingRanking == logged_ranking[j])[0]\n","            newIndex=numpy.flatnonzero(underlyingRanking == new_ranking[j])[0]\n","            exploredMatrix[j, logIndex]=1\n","            newMatrix[j, newIndex]=1\n","        \n","        posRelVector=exploredMatrix.reshape(vectorDimension)\n","        newSlateVector=newMatrix.reshape(vectorDimension)\n","        \n","        estimatedPhi=numpy.dot(self.loggingPolicy.gammas[numAllowedDocs], posRelVector)\n","        invPropensity=numpy.dot(estimatedPhi, newSlateVector)\n","        currentValue=logged_value*invPropensity\n","        \n","        self.updateRunningAverage(currentValue)\n","        \n","        denominatorDelta=invPropensity-self.runningDenominatorMean\n","        self.runningDenominatorMean+=denominatorDelta/self.runningSum\n","        if self.runningDenominatorMean!=0.0:\n","            return 1.0*self.runningMean/self.runningDenominatorMean\n","        else:\n","            return 0.0\n","    \n","    def reset(self):\n","        Estimator.reset(self)\n","        self.runningDenominatorMean=0.0"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"xEQSGR1jfXvQ"},"source":["### DM"]},{"cell_type":"code","metadata":{"id":"YHrGViwrfWdM"},"source":["class Direct(Estimator):\n","    def __init__(self, ranking_size, logging_policy, target_policy, estimator_type):\n","        Estimator.__init__(self, ranking_size, logging_policy, target_policy)\n","        self.name = 'Direct_'+estimator_type\n","        self.estimatorType = estimator_type\n","        self.numFeatures=self.loggingPolicy.dataset.features[0].shape[1]\n","        self.hyperParams={'alpha': (numpy.logspace(-2,1,num=4,base=10)).tolist()}\n","        self.treeDepths={'max_depth': list(range(3,15,3))}\n","        \n","        if self.estimatorType=='tree':\n","            self.tree=None\n","        else:\n","            self.policyParams=None\n","            \n","        #This member is set on-demand by estimateAll(...)\n","        self.savedValues=None\n","        \n","    def estimateAll(self, metric=None):\n","        if self.savedValues is not None:\n","            return\n","            \n","        self.savedValues=[]\n","        numQueries=len(self.loggingPolicy.dataset.docsPerQuery)\n","        for query in range(numQueries):\n","            newRanking=self.targetPolicy.predict(query, self.rankingSize)\n","            allFeatures=self.loggingPolicy.dataset.features[query][newRanking,:]\n","        \n","            if newRanking.size < self.rankingSize:\n","                emptyPad=scipy.sparse.csr_matrix((self.rankingSize-newRanking.size, self.numFeatures), dtype=numpy.float64)\n","                allFeatures=scipy.sparse.vstack((allFeatures, emptyPad), format=\"csr\", dtype=numpy.float64)\n","            \n","            allFeatures=allFeatures.toarray()\n","            nRows, nCols = allFeatures.shape\n","            size=nRows*nCols\n","            currentFeatures=numpy.reshape(allFeatures, (1,size))\n","        \n","            currentValue=None\n","            if self.estimatorType=='tree':\n","                currentValue=self.tree.predict(currentFeatures)[0]\n","            else:\n","                currentValue=numpy.dot(currentFeatures, self.policyParams)[0]\n","            \n","            low=None\n","            high=None\n","            if metric is not None:\n","                low=metric.getMin(newRanking.size)\n","                high=metric.getMax(newRanking.size)\n","                \n","            if low is not None:\n","                currentValue = max(currentValue, low)\n","            if high is not None:\n","                currentValue = min(currentValue, high)\n","\n","            if currentValue > 1.0 or currentValue < 0.0:\n","                print(\"Direct:estimateAll [LOG] estimate %0.3f \" % (currentValue), flush=True)\n","\n","            del allFeatures\n","            del currentFeatures\n","            \n","            self.savedValues.append(currentValue)\n","            \n","            if query%100==0:\n","                print(\".\", end=\"\", flush=True)\n","                \n","        print(\"\")\n","        print(\"Direct:estimateAll [LOG] Precomputed estimates.\", flush=True)\n","        \n","    def train(self, logged_data):\n","        numInstances=len(logged_data)\n","        targets=numpy.zeros(numInstances, order='C', dtype=numpy.float64)\n","        covariates=scipy.sparse.lil_matrix((numInstances, self.numFeatures*self.rankingSize), dtype=numpy.float64)\n","        print(\"Starting to create covariates\", flush=True)\n","        for j in range(numInstances):\n","            currentDatapoint=logged_data.pop()\n","            targets[j]=currentDatapoint[2]\n","            \n","            currentQuery=currentDatapoint[0]\n","            currentRanking=currentDatapoint[1]\n","            allFeatures=self.loggingPolicy.dataset.features[currentQuery][currentRanking,:]\n","            allFeatures.eliminate_zeros()\n","            \n","            covariates.data[j]=allFeatures.data\n","            newIndices=allFeatures.indices\n","            for k in range(allFeatures.shape[0]):\n","                newIndices[allFeatures.indptr[k]:allFeatures.indptr[k+1]]+=k*self.numFeatures\n","                \n","            covariates.rows[j]=newIndices\n","                \n","            if j%1000 == 0:\n","                print(\".\", end='', flush=True)\n","            del currentDatapoint\n","            del allFeatures\n","\n","            \n","        print(\"Converting covariates\", flush=True)\n","        covariates=covariates.tocsr()\n","        print(\"Finished conversion\", flush=True)\n","        \n","        if self.estimatorType=='tree':\n","            treeCV=sklearn.model_selection.GridSearchCV(sklearn.tree.DecisionTreeRegressor(criterion=\"mse\",\n","                                                        splitter=\"random\", min_samples_split=4, \n","                                                        min_samples_leaf=4, presort=False),\n","                                param_grid=self.treeDepths,\n","                                scoring=None, fit_params=None, n_jobs=1,\n","                                iid=True, cv=3, refit=True, verbose=0, pre_dispatch=1,\n","                                error_score='raise', return_train_score=False)\n","            treeCV.fit(covariates, targets)\n","            self.tree=treeCV.best_estimator_\n","            print(\"DirectEstimator:train [INFO] Done. Best depth\", \n","                            treeCV.best_params_['max_depth'], flush=True)\n","        elif self.estimatorType=='lasso':\n","            lassoCV=sklearn.model_selection.GridSearchCV(sklearn.linear_model.Lasso(fit_intercept=False, \n","                                                        normalize=False, precompute=False, copy_X=False, \n","                                                        max_iter=30000, tol=1e-4, warm_start=False, positive=False,\n","                                                        random_state=None, selection='random'),\n","                                param_grid=self.hyperParams,\n","                                scoring=None, fit_params=None, n_jobs=1,\n","                                iid=True, cv=3, refit=True, verbose=0, pre_dispatch=1,\n","                                error_score='raise', return_train_score=False)\n","            lassoCV.fit(covariates, targets)\n","            self.policyParams=lassoCV.best_estimator_.coef_\n","            print(\"DirectEstimator:train [INFO] Done. CVAlpha\", lassoCV.best_params_['alpha'], flush=True)\n","        elif self.estimatorType=='ridge':\n","            ridgeCV=sklearn.model_selection.GridSearchCV(sklearn.linear_model.Ridge(fit_intercept=False,\n","                                                        normalize=False, copy_X=False, max_iter=30000, tol=1e-4, solver='sag',\n","                                                        random_state=None),\n","                                param_grid=self.hyperParams,\n","                                scoring=None, fit_params=None, n_jobs=1,\n","                                iid=True, cv=3, refit=True, verbose=0, pre_dispatch=1,\n","                                error_score='raise', return_train_score=False)\n","            ridgeCV.fit(covariates, targets)\n","            self.policyParams=ridgeCV.best_estimator_.coef_\n","            print(\"DirectEstimator:train [INFO] Done. CVAlpha\", ridgeCV.best_params_['alpha'], flush=True)\n","        else:\n","            print(\"DirectEstimator:train [ERR] %s not supported.\" % self.modelType, flush=True)\n","            sys.exit(0)\n","        \n","    def estimate(self, query, logged_ranking, new_ranking, logged_value):\n","        currentValue=None\n","        if self.savedValues is not None:\n","            currentValue=self.savedValues[query]\n","        else:\n","            allFeatures=self.loggingPolicy.dataset.features[query][new_ranking,:]\n","        \n","            if new_ranking.size < self.rankingSize:\n","                emptyPad=scipy.sparse.csr_matrix((self.rankingSize-new_ranking.size, self.numFeatures), dtype=numpy.float64)\n","                allFeatures=scipy.sparse.vstack((allFeatures, emptyPad), format=\"csr\", dtype=numpy.float64)\n","            \n","            allFeatures=allFeatures.toarray()\n","            nRows, nCols = allFeatures.shape\n","            size=nRows*nCols\n","            currentFeatures=numpy.reshape(allFeatures, (1,size))\n","\n","            if self.estimatorType=='tree':\n","                currentValue=self.tree.predict(currentFeatures)[0]\n","            else:\n","                currentValue=numpy.dot(currentFeatures, self.policyParams)[0]\n","        \n","            del allFeatures\n","            del currentFeatures\n","            \n","        self.updateRunningAverage(currentValue)\n","        return self.runningMean\n","        \n","    def reset(self):\n","        Estimator.reset(self)\n","        self.savedValues=None\n","        if self.estimatorType=='tree':\n","            self.tree=None\n","        else:\n","            self.policyParams=None"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"zSm9QoicgUax"},"source":["## Utils"]},{"cell_type":"code","metadata":{"id":"HSSuW74bgWA9"},"source":["class GammaCalculator:\n","    \n","    def __init__(self, weights, nSlots):\n","        assert nSlots>0, \"NSLOTS MUST BE POSITIVE\"\n","        self.nDocs = len(weights)\n","        self.nSlots = nSlots\n","\n","        self.nTypes = 0\n","        self.weightToType = {}\n","        self.typeToWeight = []\n","        self.typeToDocs = []\n","        self.nDocsOfType = []\n","        self.docToType = []\n","\n","        self.weights = weights\n","\n","        for i in range(len(weights)):\n","            weight = weights[i]\n","            if not weight in self.weightToType:\n","                self.typeToWeight.append(decimal.Decimal(weight))\n","                self.typeToDocs.append([])\n","                self.nDocsOfType.append(0)\n","                self.weightToType[weight] = self.nTypes\n","                self.nTypes += 1\n","\n","            t = self.weightToType[weight]\n","            self.docToType.append(t)\n","            self.nDocsOfType[t] += 1\n","            self.typeToDocs[t].append(i)\n","\n","        self.table = {}\n","        empty_prefix = (0,)*self.nTypes\n","        self.table[ empty_prefix, () ] = decimal.Decimal(1)\n","        self.visited = set()\n","        self.fill_table(empty_prefix, ())\n","\n","        self.gamma_types = {}\n","        for (prefix,anchor) in self.table.keys():\n","            length = sum(prefix)\n","            for t in range(self.nTypes):\n","                if prefix[t]<self.nDocsOfType[t]:\n","                    prob = self.get_prob(prefix, anchor, t)\n","                    if anchor==():\n","                        key = \"types1\", (length,t)\n","                    else:\n","                        key = \"types2\", anchor, (length,t)\n","                    if not key in self.gamma_types:\n","                        self.gamma_types[key] = decimal.Decimal(0)\n","                    self.gamma_types[key] += prob\n","\n","        self.unitMarginals = numpy.zeros((self.nSlots, self.nDocs), dtype = numpy.longdouble)\n","        self.pairwiseMarginals = {}\n","        for (key, prob) in self.gamma_types.items():\n","            if key[0]==\"types1\":\n","                pos, t = key[1]\n","                normalize = decimal.Decimal(self.nDocsOfType[t])\n","                for d in self.typeToDocs[t]:\n","                    self.unitMarginals[pos, d] = numpy.longdouble(prob/normalize)\n","\n","            if key[0]==\"types2\":\n","                pos1, t1 = key[1]\n","                pos2, t2 = key[2]\n","                normalize = None\n","                if t1==t2:\n","                    normalize = decimal.Decimal(self.nDocsOfType[t1]*(self.nDocsOfType[t2]-1))\n","                else:\n","                    normalize = decimal.Decimal(self.nDocsOfType[t1]*self.nDocsOfType[t2])\n","\n","                newKey = (pos1, pos2)\n","                if newKey not in self.pairwiseMarginals:\n","                    self.pairwiseMarginals[newKey] = numpy.zeros((self.nDocs, self.nDocs), dtype = numpy.longdouble)\n","         \n","                for d1 in self.typeToDocs[t1]:\n","                    for d2 in self.typeToDocs[t2]:\n","                        if d1 != d2:\n","                            self.pairwiseMarginals[newKey][d1, d2] = numpy.longdouble(prob/normalize)\n","            \n","    def decr(self, prefix, t):\n","        prefix_mut = list(prefix)\n","        assert prefix_mut[t]>0, \"DECR PREFIX OUT OF BOUNDS\"\n","        prefix_mut[t] -= 1\n","        return tuple(prefix_mut)\n","\n","    def incr(self, prefix, t):\n","        prefix_mut = list(prefix)\n","        assert prefix_mut[t]<self.nDocsOfType[t], \"INCR PREFIX OUT OF BOUNDS\"\n","        prefix_mut[t] += 1\n","        return tuple(prefix_mut)\n","\n","    def get_prob(self, prefix, anchor, t):\n","        posterior = [ self.typeToWeight[tt]*(self.nDocsOfType[tt]-prefix[tt]) for tt in range(self.nTypes) ]\n","        normalize = sum(posterior)\n","        return self.eval_table(prefix, anchor) * posterior[t] / normalize\n","\n","    def eval_table(self, prefix, anchor):\n","        \"\"\"evaluate an entry in the DP table. here:\n","              prefix: tuple of type counts\n","              anchor: specifies (pos, type) where pos<len(prefix)\"\"\"\n","\n","        if (prefix,anchor) in self.table:\n","            return self.table[prefix,anchor]\n","\n","        prob = decimal.Decimal(0)\n","        length = sum(prefix)\n","        if anchor==() or anchor[0]<length-1:\n","            for t in range(self.nTypes):\n","                if prefix[t]>0:\n","                    prefix0 = self.decr(prefix, t)\n","                    if anchor==() or prefix0[anchor[1]]>0:\n","                        prob += self.get_prob(prefix0, anchor, t)\n","        else:\n","            t=anchor[1]\n","            prefix0 = self.decr(prefix, t)\n","            prob += self.get_prob(prefix0, (), t)\n","        self.table[prefix,anchor] = prob\n","        return prob\n","        \n","    def fill_table(self, prefix, anchor):\n","        \"\"\"add more entries to the DP table extending the current prefix. here:\n","              prefix: tuple of type counts\n","              anchor: specifies (pos, type) where pos<len(prefix)\"\"\"\n","\n","        length = sum(prefix)\n","        if (prefix, anchor) in self.visited:\n","            return\n","        self.visited.add( (prefix, anchor) )\n","        self.eval_table(prefix, anchor)\n","        if length==self.nSlots-1:\n","            return\n","\n","        for t in range(self.nTypes):\n","            if prefix[t]<self.nDocsOfType[t]:\n","                prefix1 = self.incr(prefix, t)\n","                anchor1 = (length, t)\n","                self.fill_table(prefix1, anchor)\n","                if anchor==():\n","                    self.fill_table(prefix1, anchor1)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"vgBuPEK0gfmh"},"source":["## Metrics"]},{"cell_type":"code","metadata":{"id":"ZbLiCBPsgfkh"},"source":["class Metric:\n","    #dataset: (Datasets) Must be initialized using Datasets.loadTxt(...)/loadNpz(...)\n","    #ranking_size: (int) Maximum size of slate across contexts, l\n","    def __init__(self, dataset, ranking_size):\n","        self.rankingSize=ranking_size\n","        self.dataset=dataset\n","        self.name=None\n","        ###All sub-classes of Metric should supply a computeMetric method\n","        ###Requires: (int) query_id; list[int],length=ranking_size ranking\n","        ###Returns: (double) value\n","\n","\n","class ConstantMetric(Metric):\n","    #constant: (double) Value returned by this metric\n","    def __init__(self, dataset, ranking_size, constant):\n","        Metric.__init__(self, dataset, ranking_size)\n","        self.constant=constant\n","        self.name='Constant'\n","        print(\"ConstantMetric:init [INFO] RankingSize\", ranking_size, \"\\t Constant\", constant, flush=True)\n","    \n","    #query_id: (int) Index of the query                                                                 (unused)\n","    #ranking: list[int],length=min(ranking_size,docsForQuery); Valid DocID in each slot of the slate    (unused)\n","    def computeMetric(self, query_id, ranking):\n","        return self.constant\n","\n","        \n","class DCG(Metric):\n","    def __init__(self, dataset, ranking_size):\n","        Metric.__init__(self, dataset, ranking_size)\n","        self.discountParams=1.0+numpy.array(range(self.rankingSize), dtype=numpy.float64)\n","        self.discountParams[0]=2.0\n","        self.discountParams[1]=2.0\n","        self.discountParams=numpy.reciprocal(numpy.log2(self.discountParams))\n","        self.name='DCG'\n","        print(\"DCG:init [INFO] RankingSize\", ranking_size, flush=True)\n","    \n","    def computeMetric(self, query_id, ranking):\n","        relevanceList=self.dataset.relevances[query_id][ranking]\n","        gain=numpy.exp2(relevanceList)-1.0\n","        dcg=numpy.dot(self.discountParams[0:numpy.shape(gain)[0]], gain)\n","        return dcg\n","\n","        \n","class NDCG(Metric):\n","    #allow_repetitions: (bool) If True, max gain is computed as if repetitions are allowed in the ranking\n","    def __init__(self, dataset, ranking_size, allow_repetitions):\n","        Metric.__init__(self, dataset, ranking_size)\n","        self.discountParams=1.0+numpy.array(range(self.rankingSize), dtype=numpy.float64)\n","        self.discountParams[0]=2.0\n","        self.discountParams[1]=2.0\n","        self.discountParams=numpy.reciprocal(numpy.log2(self.discountParams))\n","        self.name='NDCG'\n","        \n","        self.normalizers=[]\n","        numQueries=len(self.dataset.docsPerQuery)\n","        for currentQuery in range(numQueries):\n","            validDocs=min(self.dataset.docsPerQuery[currentQuery], ranking_size)\n","            currentRelevances=self.dataset.relevances[currentQuery]\n","            \n","            #Handle filtered datasets properly\n","            if self.dataset.mask is not None:\n","                currentRelevances=currentRelevances[self.dataset.mask[currentQuery]]\n","            \n","            maxRelevances=None\n","            if allow_repetitions:\n","                maxRelevances=numpy.repeat(currentRelevances.max(), validDocs)\n","            else:\n","                maxRelevances=-numpy.sort(-currentRelevances)[0:validDocs]\n","        \n","            maxGain=numpy.exp2(maxRelevances)-1.0\n","            maxDCG=numpy.dot(self.discountParams[0:validDocs], maxGain)\n","            \n","            self.normalizers.append(maxDCG)\n","            \n","            if currentQuery % 1000==0:\n","                print(\".\", end=\"\", flush=True)\n","                \n","        print(\"\", flush=True)        \n","        print(\"NDCG:init [INFO] RankingSize\", ranking_size, \"\\t AllowRepetitions?\", allow_repetitions, flush=True)\n","    \n","    def computeMetric(self, query_id, ranking):\n","        normalizer=self.normalizers[query_id]\n","        if normalizer<=0.0:\n","            return 0.0\n","        else:\n","            relevanceList=self.dataset.relevances[query_id][ranking]\n","            gain=numpy.exp2(relevanceList)-1.0\n","            dcg=numpy.dot(self.discountParams[0:numpy.shape(gain)[0]], gain)\n","            return dcg*1.0/normalizer\n","\n","    def getMax(self,ranking_size):\n","        return 1.0\n","            \n","    def getMin(self,ranking_size):\n","        return 0.0\n","   \n","class ERR(Metric):\n","    def __init__(self, dataset, ranking_size):\n","        Metric.__init__(self, dataset, ranking_size)\n","        self.name='ERR'\n","        \n","        #ERR needs the maximum relevance grade for the dataset\n","        #For MQ200*, this is 2;  For MSLR, this is 4\n","        self.maxrel=None\n","        if self.dataset.name.startswith('MSLR'):\n","            self.maxrel=numpy.exp2(4)\n","        elif self.dataset.name.startswith('MQ200'):\n","            self.maxrel=numpy.exp2(2)\n","        else:\n","            print(\"ERR:init [ERR] Unknown dataset. Use MSLR/MQ200*\", flush=True)\n","            sys.exit(0)\n","        \n","        print(\"ERR:init [INFO] RankingSize\", ranking_size, flush=True)\n","\n","    def computeMetric(self, query_id, ranking):\n","        relevanceList=self.dataset.relevances[query_id][ranking]\n","        gain=numpy.exp2(relevanceList)-1.0\n","        probs=gain*1.0/self.maxrel\n","        validDocs=numpy.shape(probs)[0]\n","        err=0.0\n","        p=1.0\n","        for i in range(validDocs):\n","            err+=p*probs[i]/(i+1)\n","            p=p*(1-probs[i])\n","        return err\n","\n","    def getMax(self, ranking_size):\n","        probs=[(self.maxrel-1.0)/self.maxrel for i in range(ranking_size)]\n","        validDocs=numpy.shape(probs)[0]\n","        err=0.0\n","        p=1.0\n","        for i in range(validDocs):\n","            err+=p*probs[i]/(i+1)\n","            p=p*(1-probs[i])\n","        return err\n","\n","    def getMin(self, ranking_size):\n","        return 0.0\n","        \n","class MaxRelevance(Metric):\n","    def __init__(self, dataset, ranking_size):\n","        Metric.__init__(self, dataset, ranking_size)\n","        self.name='MaxRelevance'\n","        print(\"MaxRelevance:init [INFO] RankingSize\", ranking_size, flush=True)\n","        \n","    def computeMetric(self, query_id, ranking):\n","        relevanceList=self.dataset.relevances[query_id][ranking]\n","        maxRelevance=1.0*relevanceList.max()\n","        return maxRelevance\n","\n","        \n","class SumRelevance(Metric):\n","    def __init__(self, dataset, ranking_size):\n","        Metric.__init__(self, dataset, ranking_size)\n","        self.name='SumRelevance'\n","        print(\"SumRelevance:init [INFO] RankingSize\", ranking_size, flush=True)\n","        \n","    def computeMetric(self, query_id, ranking):\n","        relevanceList=self.dataset.relevances[query_id][ranking]\n","        sumRelevance=relevanceList.sum(dtype=numpy.float64)\n","        return sumRelevance\n","\n","        \n","        \n","if __name__==\"__main__\":\n","    import Settings\n","    import Datasets\n","    \n","    mslrData = Datasets.Datasets()\n","    mslrData.loadNpz(Settings.DATA_DIR+\"mslr/mslr\")\n","    \n","    const=ConstantMetric(mslrData, 4, 5.0)\n","    print(\"Constant\", const.computeMetric(0, [0, 1, 2, 3]), flush=True)\n","    del const\n","    \n","    dcg=DCG(mslrData, 4)\n","    print(\"DCG\", dcg.computeMetric(0, [0, 1, 2, 3]), flush=True)\n","    del dcg\n","    \n","    ndcg=NDCG(mslrData, 4, False)\n","    print(\"NDCG NoRep\", ndcg.computeMetric(0, [0, 1, 2, 3]), flush=True)\n","    del ndcg\n","    \n","    ndcg=NDCG(mslrData, 4, True)\n","    print(\"NDCG YesRep\", ndcg.computeMetric(0, [0, 1, 2, 3]), flush=True)\n","    del ndcg\n","    \n","    err=ERR(mslrData, 4)\n","    print(\"ERR\", err.computeMetric(0, [0, 1, 2, 3]), flush=True)\n","    del err\n","    \n","    maxrel=MaxRelevance(mslrData, 4)\n","    print(\"MaxRelevance\", maxrel.computeMetric(0, [0, 1, 2, 3]), flush=True)\n","    del maxrel\n","    \n","    sumrel=SumRelevance(mslrData, 4)\n","    print(\"SumRelevance\", sumrel.computeMetric(0, [0, 1, 2, 3]), flush=True)  \n","    del sumrel"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"GZVo3XE9gfia"},"source":["## Policy"]},{"cell_type":"markdown","metadata":{"id":"aeOnCXqogffX"},"source":["Class that models a policy for exploration or evaluation"]},{"cell_type":"code","metadata":{"id":"xEXrtKIJgpF6"},"source":["#UniformGamma(...) computes a Gamma_pinv matrix for uniform exploration\n","#num_candidates: (int) Number of candidates, m\n","#ranking_size: (int) Size of slate, l\n","#allow_repetitions: (bool) If True, repetitions were allowed in the ranking\n","def UniformGamma(num_candidates, ranking_size, allow_repetitions):\n","    validDocs=ranking_size\n","    if not allow_repetitions:\n","        validDocs=min(ranking_size, num_candidates)\n","                \n","    gamma=numpy.empty((num_candidates*validDocs, num_candidates*validDocs), dtype=numpy.float64)\n","    if num_candidates==1:\n","        gamma.fill(1.0)\n","    else:\n","        #First set all the off-diagonal blocks\n","        if allow_repetitions:\n","            gamma.fill(1.0/(num_candidates*num_candidates))\n","        else:\n","            gamma.fill(1.0/(num_candidates*(num_candidates-1)))\n","            #Correct the diagonal of each off-diagonal block: Pairwise=0\n","            for p in range(1,validDocs):\n","                diag=numpy.diagonal(gamma, offset=p*num_candidates)\n","                diag.setflags(write=True)\n","                diag.fill(0)\n","                        \n","                diag=numpy.diagonal(gamma, offset=-p*num_candidates)\n","                diag.setflags(write=True)\n","                diag.fill(0)\n","                        \n","        #Now correct the diagonal blocks: Diagonal matrix with marginals = 1/m\n","        for j in range(validDocs):\n","            currentStart=j*num_candidates\n","            currentEnd=(j+1)*num_candidates\n","            gamma[currentStart:currentEnd, currentStart:currentEnd]=0\n","            numpy.fill_diagonal(gamma, 1.0/num_candidates)\n","\n","    gammaInv=scipy.linalg.pinv(gamma)\n","    return (num_candidates, gammaInv)\n","    \n","    \n","#NonUniformGamma(...) computes a Gamma_pinv matrix for non-uniform exploration\n","#num_candidates: (int) Number of candidates, m\n","#decay: (double) Decay factor. Doc Selection Prob \\propto exp2(-decay * floor[ log2(rank) ])\n","#ranking_size: (int) Size of slate, l\n","#allow_repetitions: (bool) If True, repetitions were allowed in the ranking\n","def NonUniformGamma(num_candidates, decay, ranking_size, allow_repetitions):\n","    validDocs=ranking_size\n","    if not allow_repetitions:\n","        validDocs=min(ranking_size, num_candidates)\n","\n","    multinomial=numpy.arange(1, num_candidates+1, dtype=numpy.float64)\n","    multinomial=numpy.exp2((-decay)*numpy.floor(numpy.log2(multinomial)))\n","    \n","    for i in range(1,num_candidates):\n","        prevVal=multinomial[i-1]\n","        currVal=multinomial[i]\n","        if numpy.isclose(currVal, prevVal):\n","            multinomial[i]=prevVal\n","    \n","    gamma=None\n","    if num_candidates==1:\n","        gamma=numpy.ones((num_candidates*validDocs, num_candidates*validDocs), dtype=numpy.longdouble)\n","    else:\n","        if allow_repetitions:\n","            offDiagonal=numpy.outer(multinomial, multinomial)\n","            gamma=numpy.tile(offDiagonal, (validDocs, validDocs))\n","            for j in range(validDocs):\n","                currentStart=j*num_candidates\n","                currentEnd=(j+1)*num_candidates\n","                gamma[currentStart:currentEnd, currentStart:currentEnd]=numpy.diag(multinomial)\n","        else:\n","            gammaVals=GammaDP.GammaCalculator(multinomial.tolist(), validDocs)\n","            gamma=numpy.diag(numpy.ravel(gammaVals.unitMarginals))\n","            \n","            for p in range(validDocs):\n","                for q in range(p+1, validDocs):\n","                    pairMarginals=gammaVals.pairwiseMarginals[(p,q)]\n","                    currentRowStart=p*num_candidates\n","                    currentRowEnd=(p+1)*num_candidates\n","                    currentColumnStart=q*num_candidates\n","                    currentColumnEnd=(q+1)*num_candidates\n","                    gamma[currentRowStart:currentRowEnd, currentColumnStart:currentColumnEnd]=pairMarginals\n","                    gamma[currentColumnStart:currentColumnEnd, currentRowStart:currentRowEnd]=pairMarginals.T\n","    \n","    normalizer=numpy.sum(multinomial, dtype=numpy.longdouble)\n","    multinomial=multinomial/normalizer\n","\n","    gammaInv=scipy.linalg.pinv(gamma)\n","    return (num_candidates, multinomial, gammaInv)\n","    \n","\n","class RecursiveSlateEval:\n","    def __init__(self, scores):\n","        self.m=scores.shape[0]\n","        self.l=scores.shape[1]\n","        self.scores=scores\n","        self.sortedIndices=numpy.argsort(scores, axis=0)\n","        self.bestSoFar=None\n","        self.bestSlate=None\n","        self.counter=0\n","        self.upperPos=numpy.amax(scores, axis=0)\n","        self.eval_slate([], 0.0)\n","        print(self.m, self.counter, flush=True)\n","        \n","    def eval_slate(self, slate_prefix, prefix_value):\n","        currentPos=len(slate_prefix)\n","        if currentPos==self.l:\n","            self.counter+=1\n","            if self.bestSoFar is None or prefix_value > self.bestSoFar:\n","                self.bestSoFar=prefix_value\n","                self.bestSlate=slate_prefix\n","            return\n","        \n","        docSet=set(slate_prefix)\n","        bestFutureVal=0.0\n","        if currentPos < self.l:\n","            bestFutureVal=self.upperPos[currentPos:].sum()\n","        delta=prefix_value+bestFutureVal\n","        for i in range(self.m):\n","            currentDoc=self.sortedIndices[-1-i, currentPos]\n","            if currentDoc in docSet:\n","                continue\n","            currentVal=self.scores[currentDoc, currentPos]\n","            if self.bestSoFar is None or ((currentVal+delta) > self.bestSoFar):\n","                self.eval_slate(slate_prefix + [currentDoc], prefix_value+currentVal)\n","            else:\n","                break\n","            \n","class Policy:\n","    #dataset: (Datasets) Must be initialized using Datasets.loadTxt(...)/loadNpz(...)\n","    #allow_repetitions: (bool) If true, the policy predicts rankings with repeated documents\n","    def __init__(self, dataset, allow_repetitions):\n","        self.dataset=dataset\n","        self.allowRepetitions=allow_repetitions\n","        self.name=None\n","        ###All sub-classes of Policy should supply a predict method\n","        ###Requires: (int) query_id; (int) ranking_size.\n","        ###Returns: list[int],length=min(ranking_size,docsPerQuery[query_id]) ranking\n","\n","\n","class L2RPolicy(Policy):\n","    def __init__(self, dataset, ranking_size, model_type, greedy_select, cross_features):\n","        Policy.__init__(self, dataset, False)\n","        self.rankingSize=ranking_size\n","        self.numDocFeatures=dataset.features[0].shape[1]\n","        self.modelType=model_type\n","        self.crossFeatures=cross_features\n","        self.hyperParams=numpy.logspace(0,2,num=5,base=10).tolist()\n","        if self.modelType=='tree' or self.modelType=='gbrt':\n","            self.tree=None\n","        else:\n","            self.policyParams=None\n","\n","        self.greedy=greedy_select\n","        \n","        self.numFeatures=self.numDocFeatures+self.rankingSize \n","        if self.crossFeatures:\n","            self.numFeatures+=self.numDocFeatures*self.rankingSize\n","        print(\"L2RPolicy:init [INFO] Dataset:\", dataset.name, flush=True)\n","\n","    def createFeature(self, docFeatures, position):\n","        currFeature=numpy.zeros(self.numFeatures, dtype=numpy.float64)\n","        currFeature[0:self.numDocFeatures]=docFeatures\n","        currFeature[self.numDocFeatures+position]=1\n","        if self.crossFeatures:\n","            currFeature[self.numDocFeatures+self.rankingSize+position*self.numDocFeatures: \\\n","                        self.numDocFeatures+self.rankingSize+(position+1)*self.numDocFeatures]=docFeatures\n","\n","        return currFeature.reshape(1,-1)\n","\n","    def predict(self, query_id, ranking_size):\n","        allowedDocs=self.dataset.docsPerQuery[query_id]\n","        validDocs=min(allowedDocs, self.rankingSize)\n","\n","        allScores=numpy.zeros((allowedDocs, validDocs), dtype=numpy.float64)\n","        allFeatures=self.dataset.features[query_id].toarray()\n","        \n","        for doc in range(allowedDocs):\n","            docID=doc\n","            if self.dataset.mask is not None:\n","                docID=self.dataset.mask[query_id][doc]\n","            for pos in range(validDocs):\n","                currFeature=self.createFeature(allFeatures[docID,:], pos)\n","\n","                if self.modelType=='tree' or self.modelType=='gbrt':\n","                    allScores[doc, pos]=self.tree.predict(currFeature)\n","                else:\n","                    allScores[doc, pos]=currFeature.dot(self.policyParams)\n","\n","        tieBreaker=1e-14*numpy.random.random((allowedDocs, validDocs))\n","        allScores+=tieBreaker\n","        upperBound=numpy.amax(allScores, axis=0)\n","        \n","        producedRanking=None\n","        if self.greedy:\n","            \n","            producedRanking=numpy.empty(validDocs, dtype=numpy.int32)\n","            currentVal=0.0\n","            for i in range(validDocs):\n","                maxIndex=numpy.argmax(allScores)\n","                chosenDoc,chosenPos = numpy.unravel_index(maxIndex, allScores.shape)\n","                currentVal+=allScores[chosenDoc, chosenPos]\n","                if self.dataset.mask is None:\n","                    producedRanking[chosenPos]=chosenDoc\n","                else:\n","                    producedRanking[chosenPos]=self.dataset.mask[query_id][chosenDoc]\n","                \n","                allScores[chosenDoc,:] = float('-inf')\n","                allScores[:,chosenPos] = float('-inf')\n","            \n","            self.debug=upperBound.sum()-currentVal\n","        else:\n","            slateScorer=RecursiveSlateEval(allScores)\n","            if self.dataset.mask is None:\n","                producedRanking=numpy.array(slateScorer.bestSlate)\n","            else:\n","                producedRanking=self.dataset.mask[slateScorer.bestSlate]\n","                \n","            self.debug=upperBound.sum()-slateScorer.bestSoFar\n","            del slateScorer\n","            \n","        del allFeatures\n","        del allScores\n","        \n","        return producedRanking\n","\n","    def train(self, dataset, targets, hyper_params):\n","        numQueries=len(dataset.docsPerQuery)\n","        validDocs=numpy.minimum(dataset.docsPerQuery, self.rankingSize)\n","        queryDocPosTriplets=numpy.dot(dataset.docsPerQuery, validDocs)\n","        designMatrix=numpy.zeros((queryDocPosTriplets, self.numFeatures), dtype=numpy.float32, order='F')\n","        regressionTargets=numpy.zeros(queryDocPosTriplets, dtype=numpy.float64, order='C')\n","        sampleWeights=numpy.zeros(queryDocPosTriplets, dtype=numpy.float32)\n","        currID=-1\n","        for i in range(numQueries):\n","            numAllowedDocs=dataset.docsPerQuery[i]\n","            currValidDocs=validDocs[i]\n","            allFeatures=dataset.features[i].toarray()\n","            \n","            for doc in range(numAllowedDocs):\n","                docID=doc\n","                if dataset.mask is not None:\n","                    docID=dataset.mask[i][doc]\n","                    \n","                for j in range(currValidDocs):\n","                    currID+=1\n","\n","                    designMatrix[currID,:]=self.createFeature(allFeatures[docID,:], j)\n","                    regressionTargets[currID]=targets[i][j,doc] \n","                    sampleWeights[currID]=1.0/(numAllowedDocs * currValidDocs)\n","        \n","        for i in targets:\n","            del i\n","        del targets\n","        \n","        print(\"L2RPolicy:train [LOG] Finished creating features and targets \", \n","                numpy.amin(regressionTargets), numpy.amax(regressionTargets), numpy.median(regressionTargets), flush=True)\n","        print(\"L2RPolicy:train [LOG] Histogram of targets \", numpy.histogram(regressionTargets), flush=True)\n","        \n","        if self.modelType == 'gbrt':\n","            tree=sklearn.ensemble.GradientBoostingRegressor(learning_rate=hyper_params['lr'],\n","                            n_estimators=hyper_params['ensemble'], subsample=hyper_params['subsample'], max_leaf_nodes=hyper_params['leaves'], \n","                            max_features=1.0, presort=False)\n","            tree.fit(designMatrix, regressionTargets, sample_weight=sampleWeights)\n","            self.tree=tree\n","            print(\"L2RPolicy:train [INFO] %s\" % self.modelType, flush=True)\n","                \n","        elif self.modelType == 'ridge':\n","            ridgeCV=sklearn.linear_model.RidgeCV(alphas=self.hyperParams, fit_intercept=False,\n","                                                            normalize=False, cv=3)\n","            ridgeCV.fit(designMatrix, regressionTargets, sample_weight=sampleWeights)\n","            self.policyParams=ridgeCV.coef_\n","            print(\"L2RPolicy:train [INFO] Done. \", flush=True)\n","            \n","        else:\n","            print(\"L2RPolicy:train [ERR] %s not supported.\" % self.modelType, flush = True)\n","            sys.exit(0)\n","            \n","        print(\"L2R:train [INFO] Created %s predictor using dataset %s.\" %\n","                (self.modelType, dataset.name), flush = True)\n","                \n","                \n","class DeterministicPolicy(Policy):\n","    #model_type: (str) Model class to use for scoring documents\n","    def __init__(self, dataset, model_type, regress_gains=False, weighted_ls=False, hyper_params=None):\n","        Policy.__init__(self, dataset, False)\n","        self.modelType=model_type\n","        self.hyperParams={'alpha': (numpy.logspace(-3,2,num=6,base=10)).tolist()}\n","        if hyper_params is not None:\n","            self.hyperParams=hyper_params\n","        \n","        self.regressGains=regress_gains\n","        self.weighted=weighted_ls\n","        \n","        self.treeDepths={'max_depth': list(range(3,21,3))}\n","        \n","        #Must call train(...) to set all these members\n","        #before using DeterministicPolicy objects elsewhere\n","        self.featureList=None\n","        if self.modelType=='tree':\n","            self.tree=None\n","        else:\n","            self.policyParams=None\n","            \n","        #These members are set by predictAll(...) method\n","        self.savedRankingsSize=None\n","        self.savedRankings=None\n","        \n","        print(\"DeterministicPolicy:init [INFO] Dataset\", dataset.name, flush=True)\n","    \n","    #feature_list: list[int],length=unmaskedFeatures; List of features that should be used for training\n","    #name: (str) String to help identify this DeterministicPolicy object henceforth\n","    def train(self, feature_list, name):\n","        self.featureList=feature_list\n","        self.name=name+'-'+self.modelType\n","        modelFile=Settings.DATA_DIR+self.dataset.name+'_'+self.name\n","        if 'alpha' not in self.hyperParams:\n","            #Expecting hyper-params for GBRT; Add those hyper-params to the model file name\n","            modelFile=modelFile+'ensemble-'+str(self.hyperParams['ensemble'])+'_lr-'+str(self.hyperParams['lr'])+'_subsample-'+str(self.hyperParams['subsample'])+'_leaves-'+str(self.hyperParams['leaves'])\n","            \n","        if self.modelType=='tree' or self.modelType=='gbrt':\n","            modelFile+='.z'\n","        else:\n","            modelFile+='.npz'\n","            \n","        self.savedRankingsSize=None\n","        self.savedRankings=None\n","        \n","        if os.path.exists(modelFile):\n","            if self.modelType=='tree' or self.modelType=='gbrt':\n","                self.tree=joblib.load(modelFile)\n","                print(\"DeterministicPolicy:train [INFO] Using precomputed policy\", modelFile, flush=True)\n","            else:\n","                with numpy.load(modelFile) as npFile:\n","                    self.policyParams=npFile['policyParams']\n","                print(\"DeterministicPolicy:train [INFO] Using precomputed policy\", modelFile, flush=True)\n","                print(\"DeterministicPolicy:train [INFO] PolicyParams\", self.policyParams,flush=True)\n","        else:\n","            numQueries=len(self.dataset.features)\n","        \n","            allFeatures=None\n","            allTargets=None\n","            print(\"DeterministicPolicy:train [INFO] Constructing features and targets\", flush=True)\n","                \n","            if self.dataset.mask is None:\n","                allFeatures=scipy.sparse.vstack(self.dataset.features, format='csc')\n","                allTargets=numpy.hstack(self.dataset.relevances)\n","            else:\n","                temporaryFeatures=[]\n","                temporaryTargets=[]\n","                for currentQuery in range(numQueries):\n","                    temporaryFeatures.append(self.dataset.features[currentQuery][self.dataset.mask[currentQuery], :])\n","                    temporaryTargets.append(self.dataset.relevances[currentQuery][self.dataset.mask[currentQuery]])\n","                \n","                allFeatures=scipy.sparse.vstack(temporaryFeatures, format='csc')\n","                allTargets=numpy.hstack(temporaryTargets)\n","        \n","            if self.regressGains:\n","                allTargets=numpy.exp2(allTargets)-1.0\n","            \n","            allSampleWeights=None\n","            fitParams=None\n","            if self.weighted:\n","                allSampleWeights=numpy.array(self.dataset.docsPerQuery, dtype=numpy.float64)\n","                allSampleWeights=numpy.reciprocal(allSampleWeights)\n","                allSampleWeights=numpy.repeat(allSampleWeights, self.dataset.docsPerQuery)    \n","                fitParams={'sample_weight': allSampleWeights}\n","            \n","            #Restrict features to only the unmasked features\n","            if self.featureList is not None:\n","                print(\"DeterministicPolicy:train [INFO] Masking unused features. Remaining feature size\", \n","                    len(feature_list), flush=True)\n","                allFeatures = allFeatures[:, self.featureList]\n","        \n","            print(\"DeterministicPolicy:train [INFO] Beginning training\", self.modelType, flush=True)\n","            if self.modelType=='tree':\n","                treeCV=sklearn.model_selection.GridSearchCV(sklearn.tree.DecisionTreeRegressor(criterion=\"mse\",\n","                                                        splitter=\"random\", min_samples_split=4, \n","                                                        min_samples_leaf=4, presort=False),\n","                                param_grid=self.treeDepths,\n","                                scoring=None, fit_params=fitParams, n_jobs=-2,\n","                                iid=True, cv=5, refit=True, verbose=0, pre_dispatch=\"1*n_jobs\",\n","                                error_score='raise', return_train_score=False)\n","                            \n","                treeCV.fit(allFeatures, allTargets)\n","                self.tree=treeCV.best_estimator_\n","                print(\"DeterministicPolicy:train [INFO] Done. Best depth\", \n","                            treeCV.best_params_['max_depth'], flush=True)\n","                joblib.dump(self.tree, modelFile, compress=9, protocol=-1)\n","            \n","            elif self.modelType=='lasso':\n","                lassoCV=sklearn.model_selection.GridSearchCV(sklearn.linear_model.Lasso(fit_intercept=False,\n","                                                        normalize=False, precompute=False, copy_X=False, \n","                                                        max_iter=3000, tol=1e-4, warm_start=False, positive=False,\n","                                                        random_state=None, selection='random'),\n","                                param_grid=self.hyperParams,\n","                                scoring=None, fit_params=fitParams, n_jobs=-2,\n","                                iid=True, cv=5, refit=True, verbose=0, pre_dispatch=\"1*n_jobs\",\n","                                error_score='raise', return_train_score=False)\n","                                \n","                lassoCV.fit(allFeatures, allTargets)\n","                self.policyParams=lassoCV.best_estimator_.coef_\n","                print(\"DeterministicPolicy:train [INFO] Done. CVAlpha\", lassoCV.best_params_['alpha'], flush=True)\n","                print(\"DeterministicPolicy:train [INFO] PolicyParams\", self.policyParams,flush=True)\n","                numpy.savez_compressed(modelFile, policyParams=self.policyParams)\n","        \n","            elif self.modelType == 'ridge':\n","                ridgeCV=sklearn.model_selection.GridSearchCV(sklearn.linear_model.Ridge(fit_intercept=False,\n","                                                                                    normalize=False, copy_X=False,\n","                                                                                    max_iter=3000, tol=1e-4, random_state=None),\n","                                                         param_grid=self.hyperParams,\n","                                                         n_jobs=-2, fit_params=fitParams,\n","                                                         iid=True, cv=3, refit=True, verbose=0, pre_dispatch='1*n_jobs')\n","                ridgeCV.fit(allFeatures, allTargets)\n","                self.policyParams=ridgeCV.best_estimator_.coef_\n","                print(\"DeterministicPolicy:train [INFO] Done. CVAlpha\", ridgeCV.best_params_['alpha'], flush=True)\n","            elif self.modelType=='gbrt':\n","                tree=sklearn.ensemble.GradientBoostingRegressor(learning_rate=self.hyperParams['lr'],\n","                            n_estimators=self.hyperParams['ensemble'], subsample=self.hyperParams['subsample'], max_leaf_nodes=self.hyperParams['leaves'], \n","                            max_features=1.0, presort=False)\n","                tree.fit(allFeatures, allTargets, sample_weight=allSampleWeights)\n","                self.tree=tree\n","                print(\"DeterministicPolicy:train [INFO] Done.\", flush=True)\n","                joblib.dump(self.tree, modelFile, compress=9, protocol=-1)\n","            \n","            else:\n","                print(\"DeterministicPolicy:train [ERR] %s not supported.\" % self.modelType, flush=True)\n","                sys.exit(0)\n","    \n","    #query_id: (int) Query ID in self.dataset\n","    #ranking_size: (int) Size of ranking. Returned ranking length is min(ranking_size,docsPerQuery[query_id])\n","    #                       Use ranking_size=-1 to rank all available documents for query_id\n","    def predict(self, query_id, ranking_size):\n","        if self.savedRankingsSize is not None and self.savedRankingsSize==ranking_size:\n","            return self.savedRankings[query_id]\n","        \n","        allowedDocs=self.dataset.docsPerQuery[query_id]\n","        validDocs=ranking_size\n","        if ranking_size <= 0 or validDocs > allowedDocs:\n","            validDocs=allowedDocs\n","        \n","        currentFeatures=None\n","        if self.dataset.mask is None:\n","            if self.featureList is not None:\n","                currentFeatures=self.dataset.features[query_id][:, self.featureList]\n","            else:\n","                currentFeatures=self.dataset.features[query_id]\n","            \n","        else:\n","            currentFeatures=self.dataset.features[query_id][self.dataset.mask[query_id], :]\n","            if self.featureList is not None:\n","                currentFeatures=currentFeatures[:, self.featureList]\n","        \n","        allDocScores=None\n","        if self.modelType=='tree':\n","            allDocScores=self.tree.predict(currentFeatures)\n","        elif self.modelType=='gbrt':\n","            allDocScores=self.tree.predict(currentFeatures.toarray())\n","        else:\n","            allDocScores=currentFeatures.dot(self.policyParams)\n","            \n","        tieBreaker=numpy.random.random(allDocScores.size)\n","        sortedDocScores=numpy.lexsort((tieBreaker,-allDocScores))[0:validDocs]\n","        if self.dataset.mask is None:\n","            return sortedDocScores\n","        else:\n","            return self.dataset.mask[query_id][sortedDocScores]\n","    \n","    #ranking_size: (int) Size of ranking. Returned ranking length is min(ranking_size,docsPerQuery[query_id])\n","    #                       Use ranking_size=-1 to rank all available documents for query_id\n","    def predictAll(self, ranking_size):\n","        if self.savedRankingsSize is not None and self.savedRankingsSize==ranking_size:\n","            return\n","            \n","        numQueries=len(self.dataset.features)\n","        predictedRankings=[]\n","        for i in range(numQueries):\n","            predictedRankings.append(self.predict(i, ranking_size))\n","                \n","            if i%100==0:\n","                print(\".\", end=\"\", flush=True)\n","                \n","        self.savedRankingsSize=ranking_size\n","        self.savedRankings=predictedRankings\n","        print(\"\", flush=True)\n","        print(\"DeterministicPolicy:predictAll [INFO] Generated all predictions for %s using policy: \" %\n","                self.dataset.name, self.name, flush=True)\n","        \n","    #num_allowed_docs: (int) Filters the dataset where the max docs per query is num_allowed_docs.\n","    #                        Uses policyParams to rank and filter the original document set.\n","    def filterDataset(self, num_allowed_docs):\n","        self.savedRankingsSize=None\n","        self.savedRankings=None\n","        \n","        numQueries=len(self.dataset.docsPerQuery)\n","        \n","        self.dataset.name=self.dataset.name+'-filt('+self.name+'-'+str(num_allowed_docs)+')'\n","        \n","        newMask = []\n","        for i in range(numQueries):\n","            producedRanking=self.predict(i, num_allowed_docs)\n","            self.dataset.docsPerQuery[i]=numpy.shape(producedRanking)[0]\n","            newMask.append(producedRanking)\n","            if i%100==0:\n","                print(\".\", end=\"\", flush=True)\n","                \n","        self.dataset.mask=newMask\n","        print(\"\", flush=True)\n","        print(\"DeterministicPolicy:filteredDataset [INFO] New Name\", self.dataset.name, \"\\t MaxNumDocs\", num_allowed_docs, flush=True)\n","\n","        \n","class UniformPolicy(Policy):\n","    def __init__(self, dataset, allow_repetitions):\n","        Policy.__init__(self, dataset, allow_repetitions)\n","        self.name='Unif-'\n","        if allow_repetitions:\n","            self.name+='Rep'\n","        else:\n","            self.name+='NoRep'\n","    \n","        #These members are set on-demand by setupGamma(...)\n","        self.gammas=None\n","        self.gammaRankingSize=None\n","        \n","        print(\"UniformPolicy:init [INFO] Dataset: %s AllowRepetitions:\" % dataset.name,\n","                        allow_repetitions, flush=True)\n","    \n","    #ranking_size: (int) Size of ranking.\n","    def setupGamma(self, ranking_size):\n","        if self.gammaRankingSize is not None and self.gammaRankingSize==ranking_size:\n","            print(\"UniformPolicy:setupGamma [INFO] Gamma has been pre-computed for this ranking_size. Size of Gamma cache:\", len(self.gammas), flush=True)\n","            return\n","        \n","        gammaFile=Settings.DATA_DIR+self.dataset.name+'_'+self.name+'_'+str(ranking_size)+'.z'\n","        if os.path.exists(gammaFile):\n","            self.gammas=joblib.load(gammaFile)\n","            self.gammaRankingSize=ranking_size\n","            print(\"UniformPolicy:setupGamma [INFO] Using precomputed gamma\", gammaFile, flush=True)\n","            \n","        else:\n","            self.gammas={}\n","            self.gammaRankingSize=ranking_size\n","            \n","            candidateSet=set(self.dataset.docsPerQuery)\n","            \n","            responses=joblib.Parallel(n_jobs=-2, verbose=50)(joblib.delayed(UniformGamma)(i, ranking_size, self.allowRepetitions) for i in candidateSet)\n","            \n","            for tup in responses:\n","                self.gammas[tup[0]]=tup[1]\n","            \n","            joblib.dump(self.gammas, gammaFile, compress=9, protocol=-1)\n","            print(\"\", flush=True)\n","            print(\"UniformPolicy:setupGamma [INFO] Finished creating Gamma_pinv cache. Size\", len(self.gammas), flush=True)\n","\n","    def predict(self, query_id, ranking_size):\n","        allowedDocs=self.dataset.docsPerQuery[query_id]    \n","        \n","        validDocs=ranking_size\n","        if ranking_size < 0 or ((not self.allowRepetitions) and (validDocs > allowedDocs)):\n","            validDocs=allowedDocs\n","            \n","        producedRanking=None\n","        if self.allowRepetitions:\n","            producedRanking=numpy.random.choice(allowedDocs, size=validDocs,\n","                                replace=True)\n","        else:\n","            producedRanking=numpy.random.choice(allowedDocs, size=validDocs,\n","                                replace=False)\n","                                \n","        if self.dataset.mask is None:\n","            return producedRanking\n","        else:\n","            return self.dataset.mask[query_id][producedRanking]\n","        \n","\n","class NonUniformPolicy(Policy):\n","    def __init__(self, deterministic_policy, dataset, allow_repetitions, decay):\n","        Policy.__init__(self, dataset, allow_repetitions)\n","        self.decay = decay\n","        self.policy = deterministic_policy\n","        self.name='NonUnif-'\n","        if allow_repetitions:\n","            self.name+='Rep'\n","        else:\n","            self.name+='NoRep'\n","        self.name += '(' + deterministic_policy.name + ';' + str(decay) + ')'\n","        \n","        #These members are set on-demand by setupGamma\n","        self.gammas=None\n","        self.multinomials=None\n","        self.gammaRankingSize=None\n","        \n","        print(\"NonUniformPolicy:init [INFO] Dataset: %s AllowRepetitions:\" % dataset.name,\n","                        allow_repetitions, \"\\t Decay:\", decay, flush=True)\n","    \n","    \n","    def setupGamma(self, ranking_size):\n","        if self.gammaRankingSize is not None and self.gammaRankingSize==ranking_size:\n","            print(\"NonUniformPolicy:setupGamma [INFO] Gamma has been pre-computed for this ranking_size. Size of Gamma cache:\", len(self.gammas), flush=True)\n","            return\n","        \n","        gammaFile=Settings.DATA_DIR+self.dataset.name+'_'+self.name+'_'+str(ranking_size)+'.z'\n","        if os.path.exists(gammaFile):\n","            self.gammas, self.multinomials=joblib.load(gammaFile)\n","            self.gammaRankingSize=ranking_size\n","            print(\"NonUniformPolicy:setupGamma [INFO] Using precomputed gamma\", gammaFile, flush=True)\n","            \n","        else:\n","            self.gammas={}\n","            self.multinomials={}\n","            self.gammaRankingSize=ranking_size\n","            \n","            candidateSet=set(self.dataset.docsPerQuery)\n","            responses=joblib.Parallel(n_jobs=-2, verbose=50)(joblib.delayed(NonUniformGamma)(i, self.decay, ranking_size, self.allowRepetitions) for i in candidateSet)\n","            \n","            for tup in responses:\n","                self.gammas[tup[0]]=tup[2]\n","                self.multinomials[tup[0]]=tup[1]\n","            \n","            joblib.dump((self.gammas, self.multinomials), gammaFile, compress=9, protocol=-1)\n","            print(\"\", flush=True)\n","            print(\"NonUniformPolicy:setupGamma [INFO] Finished creating Gamma_pinv cache. Size\", len(self.gammas), flush=True)\n","\n","        self.policy.predictAll(-1)\n","\n","    def predict(self, query_id, ranking_size):\n","        allowedDocs=self.dataset.docsPerQuery[query_id]    \n","        underlyingRanking=self.policy.predict(query_id, -1)\n","            \n","        validDocs=ranking_size\n","        if ranking_size < 0 or ((not self.allowRepetitions) and (validDocs > allowedDocs)):\n","            validDocs=allowedDocs\n","            \n","        currentDistribution=self.multinomials[allowedDocs]\n","        producedRanking=None\n","        if self.allowRepetitions:\n","            producedRanking=numpy.random.choice(allowedDocs, size=validDocs,\n","                                replace=True, p=currentDistribution)\n","        else:\n","            producedRanking=numpy.random.choice(allowedDocs, size=validDocs,\n","                                replace=False, p=currentDistribution)\n","                                \n","        return underlyingRanking[producedRanking]"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"Ts3P5f8Hg-ov"},"source":["M=100\n","L=10\n","resetSeed=387\n","\n","mslrData=Datasets.Datasets()\n","mslrData.loadNpz(Settings.DATA_DIR+'MSLR/mslr')\n","\n","anchorURLFeatures, bodyTitleDocFeatures=Settings.get_feature_sets(\"MSLR\")\n","\n","numpy.random.seed(resetSeed)\n","detLogger=DeterministicPolicy(mslrData, 'tree')\n","detLogger.train(anchorURLFeatures, 'url')\n","\n","detLogger.filterDataset(M)\n","\n","filteredDataset=detLogger.dataset\n","del mslrData\n","del detLogger\n","\n","uniform=UniformPolicy(filteredDataset, False)\n","uniform.setupGamma(L)\n","del uniform\n","\n","numpy.random.seed(resetSeed)\n","loggingPolicyTree=DeterministicPolicy(filteredDataset, 'tree')\n","loggingPolicyTree.train(anchorURLFeatures, 'url')\n","        \n","numpy.random.seed(resetSeed)\n","targetPolicyTree=DeterministicPolicy(filteredDataset, 'tree')\n","targetPolicyTree.train(bodyTitleDocFeatures, 'body')\n","\n","numpy.random.seed(resetSeed)\n","loggingPolicyLinear=DeterministicPolicy(filteredDataset, 'lasso')\n","loggingPolicyLinear.train(anchorURLFeatures, 'url')\n","\n","numpy.random.seed(resetSeed)\n","targetPolicyLinear=DeterministicPolicy(filteredDataset, 'lasso')\n","targetPolicyLinear.train(bodyTitleDocFeatures, 'body')\n","\n","numQueries=len(filteredDataset.docsPerQuery)\n","\n","TTtau=[]\n","TToverlap=[]\n","TLtau=[]\n","TLoverlap=[]\n","LTtau=[]\n","LToverlap=[]\n","LLtau=[]\n","LLoverlap=[]\n","LogLogtau=[]\n","LogLogoverlap=[]\n","TargetTargettau=[]\n","TargetTargetoverlap=[]\n","\n","def computeTau(ranking1, ranking2):\n","    rank1set=set(ranking1)\n","    rank2set=set(ranking2)\n","    documents=rank1set | rank2set\n","    rankingSize=len(rank1set)\n","    \n","    newRanking1=numpy.zeros(len(documents), dtype=numpy.int)\n","    newRanking2=numpy.zeros(len(documents), dtype=numpy.int)\n","    \n","    for docID, doc in enumerate(documents):\n","        if doc not in rank1set:\n","            newRanking1[docID]=rankingSize + 1\n","            newRanking2[docID]=ranking2.index(doc)\n","        elif doc not in rank2set:\n","            newRanking2[docID]=rankingSize + 1\n","            newRanking1[docID]=ranking1.index(doc)\n","        else:\n","            newRanking1[docID]=ranking1.index(doc)\n","            newRanking2[docID]=ranking2.index(doc)\n","        \n","    return scipy.stats.kendalltau(newRanking1, newRanking2)[0], 1.0*len(rank1set&rank2set)/rankingSize\n","\n","numpy.random.seed(resetSeed)    \n","for currentQuery in range(numQueries):\n","    if filteredDataset.docsPerQuery[currentQuery]<4:\n","        continue\n","        \n","    logTreeRanking=loggingPolicyTree.predict(currentQuery, L).tolist()\n","    logLinearRanking=loggingPolicyLinear.predict(currentQuery, L).tolist()\n","    \n","    targetTreeRanking=targetPolicyTree.predict(currentQuery, L).tolist()\n","    targetLinearRanking=targetPolicyLinear.predict(currentQuery, L).tolist()\n","    \n","    tau, overlap=computeTau(logTreeRanking, targetTreeRanking)\n","    TTtau.append(tau)\n","    TToverlap.append(overlap)\n","    \n","    tau, overlap=computeTau(logTreeRanking, targetLinearRanking)\n","    TLtau.append(tau)\n","    TLoverlap.append(overlap)\n","    \n","    tau, overlap=computeTau(logLinearRanking, targetTreeRanking)\n","    LTtau.append(tau)\n","    LToverlap.append(overlap)\n","    \n","    tau, overlap=computeTau(logLinearRanking, targetLinearRanking)\n","    LLtau.append(tau)\n","    LLoverlap.append(overlap)\n","    \n","    tau, overlap=computeTau(logLinearRanking, logTreeRanking)\n","    LogLogtau.append(tau)\n","    LogLogoverlap.append(overlap)\n","    \n","    tau, overlap=computeTau(targetLinearRanking, targetTreeRanking)\n","    TargetTargettau.append(tau)\n","    TargetTargetoverlap.append(overlap)\n","    \n","    if len(TTtau) % 100 == 0:\n","        print(\".\", end=\"\", flush=True)\n","\n","TTtau=numpy.array(TTtau)\n","TLtau=numpy.array(TLtau)\n","LTtau=numpy.array(LTtau)\n","LLtau=numpy.array(LLtau)\n","LogLogtau=numpy.array(LogLogtau)\n","TargetTargettau=numpy.array(TargetTargettau)\n","\n","TToverlap=numpy.array(TToverlap)\n","TLoverlap=numpy.array(TLoverlap)\n","LToverlap=numpy.array(LToverlap)\n","LLoverlap=numpy.array(LLoverlap)\n","LogLogoverlap=numpy.array(LogLogoverlap)\n","TargetTargetoverlap=numpy.array(TargetTargetoverlap)\n","\n","print(\"\", flush=True)    \n","print(\"TTtau\", numpy.amax(TTtau), numpy.amin(TTtau), numpy.mean(TTtau), numpy.std(TTtau), numpy.median(TTtau), len(numpy.where(TTtau > 0.99)[0]))\n","print(\"TToverlap\", numpy.amax(TToverlap), numpy.amin(TToverlap), numpy.mean(TToverlap), numpy.std(TToverlap), numpy.median(TToverlap), len(numpy.where(TToverlap > 0.99)[0]))\n","print(\"TLtau\", numpy.amax(TLtau), numpy.amin(TLtau), numpy.mean(TLtau), numpy.std(TLtau), numpy.median(TLtau), len(numpy.where(TLtau > 0.99)[0]))\n","print(\"TLoverlap\", numpy.amax(TLoverlap), numpy.amin(TLoverlap), numpy.mean(TLoverlap), numpy.std(TLoverlap), numpy.median(TLoverlap), len(numpy.where(TLoverlap > 0.99)[0]))\n","print(\"LTtau\", numpy.amax(LTtau), numpy.amin(LTtau), numpy.mean(LTtau), numpy.std(LTtau), numpy.median(LTtau), len(numpy.where(LTtau > 0.99)[0]))\n","print(\"LToverlap\", numpy.amax(LToverlap), numpy.amin(LToverlap), numpy.mean(LToverlap), numpy.std(LToverlap), numpy.median(LToverlap), len(numpy.where(LToverlap > 0.99)[0]))\n","print(\"LLtau\", numpy.amax(LLtau), numpy.amin(LLtau), numpy.mean(LLtau), numpy.std(LLtau), numpy.median(LLtau), len(numpy.where(LLtau > 0.99)[0]))\n","print(\"LLoverlap\", numpy.amax(LLoverlap), numpy.amin(LLoverlap), numpy.mean(LLoverlap), numpy.std(LLoverlap), numpy.median(LLoverlap), len(numpy.where(LLoverlap > 0.99)[0]))\n","print(\"LogLogtau\", numpy.amax(LogLogtau), numpy.amin(LogLogtau), numpy.mean(LogLogtau), numpy.std(LogLogtau), numpy.median(LogLogtau), len(numpy.where(LogLogtau > 0.99)[0]))\n","print(\"LogLogoverlap\", numpy.amax(LogLogoverlap), numpy.amin(LogLogoverlap), numpy.mean(LogLogoverlap), numpy.std(LogLogoverlap), numpy.median(LogLogoverlap), len(numpy.where(LogLogoverlap > 0.99)[0]))\n","print(\"TargetTargettau\", numpy.amax(TargetTargettau), numpy.amin(TargetTargettau), numpy.mean(TargetTargettau), numpy.std(TargetTargettau), numpy.median(TargetTargettau), len(numpy.where(TargetTargettau > 0.99)[0]))\n","print(\"TargetTargetoverlap\", numpy.amax(TargetTargetoverlap), numpy.amin(TargetTargetoverlap), numpy.mean(TargetTargetoverlap), numpy.std(TargetTargetoverlap), numpy.median(TargetTargetoverlap), len(numpy.where(TargetTargetoverlap > 0.99)[0]))"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"OarlWfFjhQBo"},"source":["## Optimization"]},{"cell_type":"markdown","metadata":{"id":"c-VnRUUzhQkx"},"source":["Script for semi-synthetic optimization runs"]},{"cell_type":"code","metadata":{"id":"QROXnqZJhZ6v"},"source":["# import Datasets\n","# import argparse\n","# import Settings\n","# import sys\n","# import os\n","# import numpy\n","# import Policy\n","# import Metrics"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"dd-RLGN8hcmM"},"source":[""],"execution_count":null,"outputs":[]}]}